Как лучше хранить большой массив чисел на диске с очень быстрым поиском?
Представим, что есть массив типа:
{"1": [1,5,11,15,22,34...], "5": [55,44,22,67]}
То есть, много ключей (1, 5, 1005...) внутри одного ключа около 20 миллионов чисел, а в общем количество чисел может доходить до 800 миллионов.
Нужно постоянное хранение этой информации (то есть, вариант исключительно с оперативной памятью отпадает) и при этом организовать быстрый поиск вхождения определенного числа в эти огромные массивы (как я понимаю, должна помогать индексация). То есть, я должен иметь возможность быстро найти, входит ли чисто 505050 в массив с 20 миллионов чисел.
Какое решение посоветуете использовать?
Сейчас используется таблица MySQL, но она довольно медленная и уже показывает невысокую производительность. Redis работает быстрее, но когда число доходит до даже до 40 миллионов, начинает занимать 3.5 ГБ оперативки, а мы ведь даже не добрались до 100 миллионов...
Как я понимаю, наверняка существуют какие-то более быстрые и специфические базы данных, которые подходили бы мне для этой довольно узконаправленной задачи, но сеанс гугления на английском мне особо не помог.
Да, конечно же, это как-то нужно заставить работать с PHP (поэтому если есть какая-то библиотека для работы с подобным хранилищем - это будет огромным плюсом) :-D
Посоветуйте, в какую сторону мне искать решение? Буду благодарен за название хранилищ, которые помогут мне решить эту задачу. В приоритете, на самом деле - скорость поиска, так как если записей будет немного, то будет происходить много операций поиска. На задачу можно выделить около 10 ГБ оперативной памяти (но как я сказал, по моим подсчетам, Redis с этим не справляется).
Еще раз. Представим на примере Redis. Есть ключ big_array1, в нем хранится 20 миллионов цифр в формате SETS.
Самый частый запрос, который мы делаем:
sismember big_array1 1234567
То есть, узнаем, хранится ли в big_array1 число 1234567.
Вот эта функция для Redis работает отлично, но забирает слишком много оперативной памяти.
Приведите текущую информацию по MySQL. Как сейчас хранятся данные в таблицах, какие использованы индексы и типы таблиц. Реляционные БД вполне неплохо должны справляться с такими простыми запросами. Возможно нужно просто поэкспериментировать с памятью, выделенной на кеш индексов, попробовать разные движки и СУБД.
На самом деле, структура простейшая:
Таблица sent_keys, две колонки: id_message id_key
Стоит индекс KEY(id_message, id_key)
Запрос:
SELECT EXISTS(SELECT * FROM sent_keys WHERE id_message=100 AND id_key=765000)
Все работает (хотя и весит немало). Но хочется более быстрой скорости. Специфика алгоритма такова, что нужно делать запрос на каждый ключ.
Я понимаю, что видимо придется как-то делать цикличную проверку, но это чертовски усложняет алгоритм просчетов.
Поэтому решил поискать, существует ли более быстрое решение именно в базе данных. Если ничего более быстрого найти не удастся - придется как-то переосмысливать систему отбора ключей.
Если допустимы ложноположительные ошибки (например, с шансом в 0,1%), то можно юзать фильтр Блума. Так ты 800млн значений впихнешь в 1,34гб. Чем меньше ошибка - тем больше нужно места
Средствами реляционной БД и если не критична скорость вставки, то можно попробовать реорганизовать таблицу со строками
{"1": [1,5,11,15,22,34...], "5": [55,44,22,67]}
к виду {1:["1"], 5:["1"], ...., 22:["1", "5"]}, т.е. теперь первым стоит значение для проверки, потом массив ключей- поменять местами ключи со значениями.
Делаете 1 индекс.
Жрать ресурсов будем меньше+ скорость поиска, усложняется доступ к бывшим ключам вхождения("1", "2",...).
Можно попробовать создать 2 таблицы: первая просто число, которое нужно искать(скорость поиска О(1)+высота дерева в индексе), а вторую с ключами вхождения и внешний ключ к первой.
