Высокопроизводительная хэш-таблица

Кто-нибудь знает проверенную в бою готовую реализацию высокопроизводительной хэш-таблицы или хотя бы материалы какие?

Требования:

1. multiple readers / multiple writers
2. должна отлично справляться со следующими нагрузками: avg reads/writes, intensive writes
3. хорошее scalability
4. желательно cache-friendly
5. адекватное влияние load factor, адекватный rehashing, адекватное потребление памяти.

0

ct0r, этот не подошел? http://www.boost.org/doc/libs/... tiset.html

0

std::unordered_map + std::mutex или boost::shared_lock по ситуации точно не подходят?

0

NoMasters, а также std::shared_lock: http://en.cppreference.com/w/c... hared_lock

0

Сообщение от DrOffset этот не подошел?

Интрузивные контейнеры из коробки это хорошо, но как можно реализовать надстройку множества одновременных чтений и записей без грубой блокировки?

Сообщение от NoMasters std::unordered_map + std::mutex или boost::shared_lock по ситуации точно не подходят?

Ситуация такая. Пишу демон.

Есть собственно эта самая таблица размером в несколько сотен Гб. При внешних запросах в несколько тысяч RPS мы лезем в эту таблицу (как раз там сейчас read-write мьютекс, но не стандартной, а внутренней реализации, с приоритетом читателям) и отдаем ответ. Одновременно в демон поступают новые данные через сислог, мы в онлайн режиме обновляем таблицу, но с некоторой допустимой ошибкой. Поэтому периодически нам нужно эту таблицу полностью пересчитывать. Поскольку демон должен всегда и максимально быстро отвечать на запросы, то пересчет делается в такую же отдельную таблицу, на которую мы затем мгновенно переключаемся. Но на время пересчета приостанавливается чтение сислога, так как они используют одни и те же данные. Нужно сократить время этого пересчета до минимума. Я распараллелил пересчет на 16 (по кол-ву ядер) потоков-производителей, которые пачками пихают данные в лок-фри очередь, откуда их одновременно забирает поток-потребитель и записывает в таблицу. Но это все равно не так быстро, как хотелось бы. Если бы эти 16 потоков сразу писали в таблицу, то было бы куда лучше. Заодно из-за смены структуры данных автоматом улучшилось бы чтение сислога и выдача ответов.

0

Сообщение от ct0r Интрузивные контейнеры из коробки это хорошо, но как можно реализовать надстройку множества одновременных чтений и записей без грубой блокировки?

В конференции буста пишут, что это нетривиально. Оттуда:

So, my question: is it possible to use bucket_traits to have a lock per bucket? > I don't think so. We can obtain the bucket from the value but there is > no insert function taking a bucket as argument. That would be an easy way > to get some paralelism, at least for insertions. Intrusive could guarantee > that the bucket search can be done in parallel and the insert_in_bucket > function could be called with a locked mutex. > > We would need an erase_from_bucket function that does not return an > iterator to the next remaining object, as that could provoke race > conditions (the next remaining object can be in a different bucket). > > It's an interesting optimization for Intrusive, but I'm afraid it's not > trivial.

Может тогда это подойдет: https://www.threadingbuildingb... ap_cls.htm

Или это: https://msdn.microsoft.com/en-... 50089.aspx

2

Сообщение от DrOffset В конференции буста пишут, что это нетривиально. Оттуда:

Я так и думал, что это не так просто. Когда читал документацию, я видел bucket_traits, но не увидел, куда там можно взять и вставить блокировку по бакетам. Спасибо за подтверждение.

Сообщение от DrOffset Может тогда это подойдет: https://www.threadingbuildingb... ap_cls.htm

Увы. TBB был бы неплохой дешевый стартовый вариант на попробовать, но... из-за одной структуры тащить всю библиотеку в репозиторий - это минус. Хотя это не главное. Там же GPLv2, поэтому нужна коммерческая лицензия, а стоит она недешево.

Сообщение от DrOffset Или это: https://msdn.microsoft.com/en-... 50089.aspx

Увы. ОС FreeBSD.

Пока думаю на эту тему.
https://github.com/efficient/libcuckoo
http://www.cs.princeton.edu/~m... osys14.pdf
http://excess-project.eu/publi... _ICDCS.pdf

1

Сообщение от ct0r Но на время пересчета приостанавливается чтение сислога, так как они используют одни и те же данные.

Не очень понятно, какие данные совместно используются. Выходная таблица? Что мешает писать в ту же локфри очередь, пока идет пересчет?

0

ct0r, кстати, существуют пропозалы подобного контейнера в новый стандарт С++.
Вот еще что нашлось:
https://github.com/tamanyan/lmn-concurrent-hashmap (на С)
https://github.com/noporpoise/jelly-hash (тоже на C) на базе этого https://code.google.com/p/ulib/
https://code.google.com/p/nbds/
https://github.com/facebook/fo... cHashMap.h (на C++)

на всякий случай: https://www.usenix.org/legacy/... iplett.pdf

0

Сообщение от NoMasters Не очень понятно, какие данные совместно используются. Выходная таблица? Что мешает писать в ту же локфри очередь, пока идет пересчет?

Нет, не выходная таблица. Каждая строка в сислоге апдейтит данные, которые используются для расчетов. А мешают писать две причины.
1) Данные тогда все равно в ответ попадут не сразу. Только после всего пересчета. Цель у нас какая - разница во времени между приходом строки в сислоге и соответствующим изменением ответа на внешние запросы должна быть как можно меньше.
2) Не очень понятно, как тогда делать точный пересчет на основе тех данных, которые мы в тот момент и изменяем (читая сислог).

Сообщение от DrOffset ct0r, кстати, существуют пропозалы подобного контейнера в новый стандарт С++.

Да, тоже видел. Внутренняя реализация там вроде на split ordered lists, как например и в TBB, PPL. Со всеми соответствующими достоинствами и недостатками.

Сообщение от DrOffset Вот еще что нашлось:

Спасибо, посмотрю внимательней.

Добавлено через 14 часов 17 минут

Сообщение от ct0r Спасибо, посмотрю внимательней.

К продакшену только фейсбуковская folly подходит. Жаль, что подключается она не одним файлом. Попробую и ее тоже для начала.

0

Ни фига себе, "С++ для начинающих"

0