Блокировка структуры данных Less Less Key
Мне нужна структура данных для хранения 500 тыс. Ключей, каждый со своими данными. 150 потоков будут работать одновременно и получать доступ к ключам. Один раз в день мне нужно обновить структуру данных, поскольку могут быть какие-то манипуляции, скажем, удаление ключа, добавление нового ключа или изменение данных. Когда происходит обновление структуры данных, я не могу заблокировать доступ к ней ни одному из 150 потоков. Я не хочу использовать текущие реализации хеша, такие как memcache или redis, так как в будущем число ключей может возрасти, и я хочу доступ в память для более быстрого поиска? Вместо этого предпочтет некоторую реализацию структуры данных в C/C++.
2 ответа
Библиотека Userspace RCU содержит набор параллельных структур данных, реализованных с помощью RCU. Среди них хеш-таблица без изменения размера, основанная на статьях
- Ори Шалев и Нир Шавит. Упорядоченные списки: расширяемые хеш-таблицы без блокировок. J. ACM 53, 3 (May 2006), 379-405.
- Michael, MM Высокопроизводительные динамические хэш-таблицы без блокировок и наборы на основе списков. В материалах четырнадцатого ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам, ACM Press, (2002), 73-82.
Для получения дополнительной информации вы можете увидеть комментарии в реализации на http://git.lttng.org/?p=userspace-rcu.git;a=blob;f=rculfhash.c
LMDB может справиться с этим http://symas.com/mdb/ Поскольку он использует MVCC, авторы не блокируют читателей. Вы можете обновлять все что угодно и когда угодно, и ваши 150 потоков читателей будут работать нормально. Считывания LMDB не выполняют никаких операций блокировки и идеально линейно масштабируются на любом количестве процессоров.
(Отказ от ответственности: я автор LMDB)