Проект Java: Сделать производительность HashMap (включая загрузку) Лучше

Question

Я пытаюсь закодировать для нашего сервера, где я должен найти тип доступа пользователей по URL-адресу.

Теперь, в начале, мы видим, что каждый день доступны 100 миллионов различных URL-адресов. Теперь, к тому времени, он стал почти 600 миллионов разных URL-адресов в день.

За 100 миллионов, что мы сделали это следующее:

1) Построение HashMap, используя параллельный массив, ключ являются URL в одной части (представлены в виде LONG) и значение другой часть URL-адрес (представлен как INT) - ключ может иметь несколько значений.

2) Затем найдите HashMap, чтобы узнать, сколько URL-адресов времени.

Теперь, как HashTable укрупняются, что мы сделали следующий:

1) Построить два/три отдельных HashTable и нагрузки и хранить его (в общей файловой системы), чтобы найти, сколько раз URL доступ.

Теперь вопрос,

1) Хотя HashTable производительность довольно хорошо, код занимает больше времени при загрузке/хранения HashTable (мы используем File Channel, занимает 16-19 секунд, чтобы загрузить/магазин HashTable - 200 миллионов entry-, как коэффициент загрузки 0,5)

Что мы пытаемся спросить:

1) Любой комментарий, как решить эту проблему?

2) Как уменьшить время загрузки/хранения (я спросил раньше, но кажется, что File Channel - лучший способ)?

3) Является ли хранение большого HashTable (более памяти) и его кеширование неоднократно будет хорошим решением? Если да, то как это сделать (по крайней мере, некоторые указатели). Мы попробовали его, используя

RandomAccessFile raf = new RandomAccessFile("array.dat", "rw"); 
IntBuffer map = raf.getChannel().map(FileChannel.MapMode.READ_WRITE, 0, 1 << 30).order(ByteOrder.nativeOrder()).asIntBuffer(); 

Однако, это дает более высокую производительность, чем предыдущая.

Спасибо.

NB:

1) В соответствии с предыдущими предложениями Stack Overflow, мы используем некоторые NoSQL БД как TokyoCabinet но из нашего опыта, обычай HashTable дает лучшую производительность, чем это на 100 миллионов пар ключ-значение.

2) Предварительно прочитанные данные для кэширования дисков невозможны, поскольку при запуске системы наше приложение начнет работать и на следующий день при запуске системы.

Что мы забыли упомянуть:

1) Как наше приложение является частью проекта и будет применяться на небольшом университетском городке, поэтому мы предполагаем URL доступ не более чем 800 миллионов человек. Таким образом, вы можете думать, что значение 600/700 данных фиксировано.

2) Наша основная забота - производительность.

3) Мы должны запускать наше приложение локально.

Edit: code of our hashmap can be found here.

Answer 1

Возможно, было бы лучше получить доступ к таблице как буфер memory-mapped. Таким образом, вы можете просто реализовать произвольный доступ к файлу, не беспокоясь о загрузке и хранении, и оставить кэширование в операционной системе. Я вижу, что your current implementation уже использует доступ к памяти для чтения и записи, но все равно загружает вещи в кучу java между ними. Избегайте дублирования и копирования данных! Обращайтесь к файлу резервной копии как к структуре данных и получайте доступ к тем частям, которые вам действительно нужны, только когда они вам понадобятся.

В этом файле хеш-карты будут работать, если вы действительно действительно уверены, что столкновение хэша не является проблемой. В противном случае я бы пошел за B+ tree там, с узлами размером ваших страниц на жестком диске. Таким образом, каждый доступ к диску даст намного больше пригодных для использования данных, чем просто один ключ, что приведет к более мелкому дереву и меньшим индивидуальным дисковым операциям.

Я предполагаю, что другие будут реализовывать такие вещи, как это, но если вы предпочитаете свою собственную реализацию хеш-карты, вы можете также написать свои собственные деревья с + B +.

Answer 2

Вы можете использовать структуру кэширования как JCS. 1 миллиард пар ключ-значение не должно быть проблемой.

http://commons.apache.org/jcs/

Answer 3

Определенно попробовать redis, думаю, что это бьет что-нибудь еще руки вниз

Answer 4

Вы можете использовать Berkeley DB, который является в основном ключ/значение магазина написано в C для максимальной производительности. Это продукт Oracle (Open Source), поэтому я бы воспринял это серьезно.

Answer 5

Весь подход звучит смешно для меня. Я собираю то, что вы действительно хотите достичь, - это простой счетчик доступа на отдельный URL. По самой своей природе эти данные часто пишутся, но редко читаются.

Для этой цели я бы просто имел таблицу базы данных и добавлял новую запись для каждого доступа (она также может служить журналом). Когда вам нужно выяснить, как часто обращался к любому URL, это можно легко сделать, используя SELECT COUNT из таблицы (в зависимости от того, сколько дополнительных данных вы храните вместе с URL-позициями, вы можете даже ограничить количество просмотров, например, как часто обращались вчера , на прошлой неделе и т. д.).

Это откладывает всю работу до такой степени, что результат действительно необходим.

Кстати, вы также можете получать данные о доступе из файлов журналов веб-серверов, поэтому, возможно, вам не нужно писать какие-либо данные самостоятельно. Посмотрите на это в первую очередь.

Answer 6

Если ваше приложение должно запускаться локально без использования какой-либо внешней вычислительной мощности, нет решения, которое может быть более эффективным, чем прямой доступ к памяти: единственная структура данных, которая может обеспечить вам лучшие характеристики, тогда HashMap массив, где доступ в каждом элементе равен O (1). Это требует, однако, заранее зная, сколько у вас элементов имеет уникальный индекс адресации на элемент, а также возможность резервирования значительной смежной памяти.

После массивов, которые, как описано, подходят для ограниченного числа случаев, у вас есть HashTables, однако по мере роста размера данных стоимость с коллизиями и динамическим изменением размеров увеличивается и делает работу плохой.

Вы можете обратиться к java.util.HashMap Javadoc, но и в Википедию http://en.wikipedia.org/wiki/Hash_table понять следующее:

• Как дорого это вычислить его?
• Как хорошо распределены цены?
• Каков фактор нагрузки, который вы используете, то есть какая у вас стоимость для разрешения конфликтов?
• Как часто вам нужно изменить размер вашей HashMap до того, как вы получите полную информацию?

Если производительность при продукты разложения строить свой HashMap, что я на самом деле считаю, что это ConcurrentHashMap (если вы строите его паралельно она должна быть поточно), вы можете выяснить, почему это происходит.

Простым, но легким началом будет замена вашего HashMap на TreeMap, характеристики которого являются детерминированной функцией его размера и сравнивают два исполнения.

---

Если с другой стороны, я неправильно ваш вопрос, и вы имеете возможность масштабировать на несколько машин, расчет, у Вас есть много интересного решения на рынке, как кто-то уже отметил, и к которым я бы добавить Кассандру.

Эти решения обеспечивают повышение производительности путем распределения нагрузки между несколькими узлами, но внутри каждого узла используется хорошо известный алгоритм быстрой и эффективной адресации.

Answer 7

Непонятно для обсуждения вопросов и последующих вопросов, но какова природа ваших запросов? У вас очень разные ситуации между
a), работая через все ~ 700 миллионов URL-адресов в течение каждого рабочего дня, или
b) попадание небольшого количества этих ~ 700 миллионов URL-адресов.

Итак: каково отношение количества запросов к # URL-адресам?

Из ваших описаний, похоже, что вы можете загружать/выгружать разные файлы, представляющие разные части вашего массива ..., который предлагает случайные запросы, которые предлагают (b).

Как я уже понял, вы уже осознали, что «все-в-памяти» не представляется возможным (т. Е. Вы разбили массив на несколько файлов), поэтому оптимальный алгоритм доступа к диску, по-видимому, является следующий порядок ведения бизнеса, нет?

Вы пробовали в запросе простой поиск (n * arrayElementSize) для смещения в файле и просто прочитали несколько страниц в памяти (знаете ли вы/знаете максимальное количество значений для ключа?). Вы уже вычислили базовый индекс в своем массиве, поэтому это прототип должен быть прост.

Answer 8

Я предлагаю вам использовать Oracle Coherence Cache. Вы можете получить все преимущества HashTable, у него есть все методы, которые имеет карта.

Производительность разумно, вы можете хранить данные согласно требованиям. Пожалуйста, посмотрите.

Answer 9

Вы можете попробовать HugeCollections, я думаю, что она была написана для этой цели

HugeCollections
библиотеки для поддержки коллекций с миллионами или миллиардами записей.

специально HugeMap

Answer 10

Использование с открытым исходным кодом SQLite в базе данных памяти.

Answer 11

Если я вас правильно понял, ваша структура данных не такая большая

[(32 + 64) * 600 million] bits i.e. a 53.644 MB structure in memory 

карта структура данных будет потреблять некоторое пространство тоже. Я обнаружил трудный путь, который представляет собой одну из наиболее эффективных в области памяти структур данных. Я бы использовал TLongIntHashMap для хранения длинных ключей и целочисленных значений. Он хранит необработанные примитивы, так что вы обходите объекты памяти Long и Integer.

Answer 12

Кажется, у вас есть набор данных, предназначенный только для чтения, который не вписывается в память, и вам нужны быстрые поисковые запросы. Боюсь, здесь нет решения серебряной пули, кроме нескольких возможных компромиссов.

Если вы получаете доступ к 600-мегабайтным записям, независимо от того, что вы делаете, вы будете ограничены скоростью случайного доступа к диску (а не последовательным доступом). Используйте FileChannel.map для прямого доступа к файлу (нет, не читайте содержимое файла в памяти, просто работайте на MappedByteBuffer. Ваша ОС позаботится о кешировании для вас). Инвестирование в SSD выглядит как хороший способ тратить деньги (или, может быть, просто купить еще больше памяти?).

Это среда университетского городка, не так ли? Возможно, вы можете использовать компьютеры в лаборатории для создания memcached/redis/etc. кластер? Может быть, вы могли бы использовать его в нерабочее время?

Если вы одновременно получаете доступ к некоторым идентифицируемым фрагментам данных (т. Е. Теперь мы анализируем домен a, затем b и т. Д.), То разделение данных на ведра - хорошая идея. Подобно тому, как физически закрывать связанные данные, чтобы помочь кешировать. Или, может быть, предварительно отсортировать URL-адреса и получить доступ к ним в режиме двоичного поиска?

Если допустима вероятность столкновения, возможно, не сохраняются полные URL-адреса, но приемлемы только 64-битные хэши URL-адресов в качестве хеш-ключей? С какой-то гимнастикой вы, вероятно, могли бы уйти, не сохранив ключи вообще?

Это мои идеи на данный момент.