Previous Entry Поделиться Next Entry
Вопрос к программистам про хэш-таблицу
prof
mit_idv
Друзья, а скажите мне, какими инструментами вы бы в наши дни решали такую задачу:
1. Есть хэш-таблица. Ключ - 32-битное слово, значение - ещё 8 байт. Итого 12 байт. Одному ключу может соответствовать несколько элементов.
2. В хэш-таблице 2,5 миллиарда элементов (уникальных ключей примерно 1 миллиард). То есть 30 гигабайт данных.
3. Требуется поискать в этой таблице 600 ключей. Если по ключу находятся элементы - достать их для обработки.

Всё это хочется успеть за 1-2 секунды.

Есть идеи кроме использования сервера с 64 гигабайтами оперативки? :)
Кто знает реальную производительность разных MoSQL баз данных?

  • 1
мне кажется, что нормальный b-tree индекс справится "на ура" и в sql-базе. Постгрес там, например. Ну и базу можно положить на SSD.

Я думаю, что то что ты требуешь, с легкостью сделают:

Postgres,
KoitoCabinet,
memcachedb

Если спросить меня, то я бы попробовал Postgres... Т.к. я его лучше всего знаю :)





А разные значения для одного и того же ключа, я так понимаю, списком хранятся?
Я бы, наверное, в случае использования NoSQL изменил бы структуру данных, чтобы не делать 600 запросов. Ведь что-то эти 600 ключей объединяет?

Могу сказать за redis: очень простой и очень быстрый. Одна особенность - все данные должны быть в ОЗУ. В предыдущих версиях разработчики пытались прикрутить поддержку виртуальной памяти, но сдались и объявили её deprecated.

Но не всё так плохо - для очень большого количества данных применяют горизонтальный шардинг, то есть разнесение базы на несколько физических узлов. В самом простом случае клиент Redis определяет на каком инстансе брать значение, вычислив хэш от ключа. http://redis.io/topics/partitioning

MongoDB более развесистая, умеет использовать виртуальную память, является документоориентированной (а не просто key-value, как редис). Горизонтальное масштабирование тоже есть, разумеется. Очень быстрая, но я её не щупал.

Думаю, если в памяти, уложиться 100 миллисекунд вполне сможешь, а скорее всего - в несколько раз быстрее. Но тут бенчмарки надо делать.



Edited at 2013-08-04 13:34 (UTC)

Redis Cluster + Consistent Hashing.

Про 600 ключей правда не очень понял -- как часто их надо искать и "атомарная" ли это комбинация. Ну и известны ли все 600 ключей заранее.

  • 1
?

Log in