Способ хранения для 2 млн. записей

Задача такова: нужно хранить около 2 млн. различных записей вида «доменное имя; 3-х байтовое число», необходима возможность осуществлять операцию «получить N случайных (но различных) записей» при N ≤ 2 млн.

Желательно, чтобы к хранилищу был удобный доступ из PHP и Python. Хранилище должно потреблять по возможности меньше оперативной памяти и работать быстро.

Что бы вы предложили использовать в таком случае?
  • Вопрос задан
  • 3149 просмотров
Решения вопроса 1
Пригласить эксперта
Ответы на вопрос 8
Т.е. я так понимаю, оно пополняться не будет? Если нет — то можно сделать свой велосипед на основе flat файлов с фиксированными длинами полей. Будет быстрая выборка обычными seek. По необходимости [s]присыпать солью[/s] разбить на группы по N записей и хранить в отдельных файлах, именованных согласно (id / N), таким образом файловая система будет частично решать вопросы случайного поиска. Если еще дальше развивать идею, можно попробовать еще разбить по папкам (как например хранит кеш squid).

А если же это дело будет регулярно изменяться, то лучше SQL ничего не придумать. 2 Млн записей — не так уж много, тем более что не нужно по ключам выбирать.
Ответ написан
@ComodoHacker
Хранилище должно потреблять по возможности меньше оперативной памяти и работать быстро.
Если «быстро», значит все данные должны находиться в оперативной памяти. Сколько ее потребуется? Примем, что средняя длина доменного имени 30 символов (уверен, это с большим запасом). Если их хранить просто как текст, нужно 30 байт. Еще 3 байта на число, 1 байт на длину строки, итого 33 байта на запись. Для двух миллионов записей потребуется около 63 Мб. Столько оперативной памяти придется выделить для быстрой работы. Значит мы можем минимизировать только оверхед по памяти, обусловленный выбором того или иного «движка» для нашего хранилища. Отсюда вывод: лучшее хранилище — простой массив, загружаемый из простого текстового файла. Генерируем последовательность псевдослучайных чисел и делаем выборку из массива по индексам.

Если память действительно критична, то можно подумать о более компактном представлении доменных имен (словарь TLD, точки и т.п.)
Ответ написан
Комментировать
Kindman
@Kindman
На самом деле поставленная задача распадается на несколько более мелких подзадач:
1) хранение 2 миллионов доменных имен.
2) генерация неповторяющейся последовательности из 2 миллионов псевдослучайных чисел.
Нужно так же еще одно уточнение:
«доменные имена» в самом хранилище должны быть уникальными, или могут повторяться?
Другими словами, могут ли одному доменному имени соответствовать два и более трех-байтовых числа одновременно?
и, допускаются ли «пустые» значения для доменного имени?
Ответы на эти вопросы очень сильно влияют на размер памяти.
Ответ написан
@smartly
Баланс скорость/пространство.
К первому совету ещё можно добавить, что в каждом отдельном файле записи хранятся компактно, с переменнымми длинами полей.
Ответ написан
Комментировать
el777
@el777
берите любую SQL-базу и не мучайтесь.
Вам нужно поизобретать велосипед или решить задачу?
2М коротких записей это ерунда, у меня в одной таблице 6М с 30 колонками — работает на ура.

Конечно, сейчас вы можете легко реализовать это на файлах. Но подумайте чуть вперед — наверняка нужно будет еще что-то добавить, делать какие-то дополнительные возможности, банально добавить дату регистрации или еще что-то. И что? Все переписывать? Конвертировать все файлы и пр.? Зачем это?
Все это уже сделали за вас разработчики БД.
Ответ написан
@Demetros
Не знаю насчет других БД, но в MySQL мне известен только один способ получения случайной выборки:

SELECT * FROM table ORDER BY rand() LIMIT N;

Это _очень_ медленно работает, т.к. сканируется вся таблица («Using temporary; Using filesort» со всеми вытекающими).
Ответ написан
Kindman
@Kindman
К сожалению «простой» массив, целиком загружаемый из файла при каждом запуске скрипта — это и есть самое-самое медленное решение из всех возможных, поскольку очень много времени будет тратиться как раз на разбор содержимого файла, и на создание динамической структуры массива.
Ответ написан
debugger88
@debugger88
noSQL? redis.io/ например. Очень быстро и просто.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы