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

Question

[mariofag]

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

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

Что бы вы предложили использовать в таком случае?

Answer 1

[NiGHt_LEshiY]

BerkeleyDB

Comments

[mariofag]

Звучит интересно. Спасибо, возьму на заметку.

[nrgian]

Устарела лет на 100 уже.

Answer 2

[Александр]

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

А если же это дело будет регулярно изменяться, то лучше SQL ничего не придумать. 2 Млн записей — не так уж много, тем более что не нужно по ключам выбирать.

Comments

[mariofag]

С простыми файлами идея хорошая, да.
А насчёт SQL — в нём есть вообще возможность выбрать именно N рандомных записей? Если да, то какую конкретно СУБД посоветуете?

[s0rr0w]

В различных версиях SQL свои способы искать рандомные записи. Можно взять тот же mySQL из-за его распростаненности, только не ошибитесь с выбором типа хранилища, innoDB или myISAM. Первый, по идее, будет быстрее в вашем случае.

Вообще, чем тупее и легковеснее DB, тем лучше — меньше пенальти на рюшечки.

Answer 3

[ComodoHacker]

Хранилище должно потреблять по возможности меньше оперативной памяти и работать быстро.

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

Если память действительно критична, то можно подумать о более компактном представлении доменных имен (словарь TLD, точки и т.п.)

Answer 4

[Kindman]

На самом деле поставленная задача распадается на несколько более мелких подзадач:
1) хранение 2 миллионов доменных имен.
2) генерация неповторяющейся последовательности из 2 миллионов псевдослучайных чисел.
Нужно так же еще одно уточнение:
«доменные имена» в самом хранилище должны быть уникальными, или могут повторяться?
Другими словами, могут ли одному доменному имени соответствовать два и более трех-байтовых числа одновременно?
и, допускаются ли «пустые» значения для доменного имени?
Ответы на эти вопросы очень сильно влияют на размер памяти.

Comments

[mariofag]

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

[Kindman]

А, выборка (поиск) данных будет проводиться по полному совпадению доменного имени, или же по маске (регулярному выражению)?

Answer 5

[smartly]

Баланс скорость/пространство.
К первому совету ещё можно добавить, что в каждом отдельном файле записи хранятся компактно, с переменнымми длинами полей.

Answer 6

[el777]

берите любую SQL-базу и не мучайтесь.
Вам нужно поизобретать велосипед или решить задачу?
2М коротких записей это ерунда, у меня в одной таблице 6М с 30 колонками — работает на ура.

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

Comments

[smartly]

Мы ж не знаем скоростных требований автора вопроса. Может ему такой поиск на каждый пакет по сети делать надо. SQL — самый простой но и самый медленный способ. Но может и его скорости хватит.

[el777]

К сожалению, автор не дал никаких конкретных критериев скорости. Кроме того даны взаимоисключающие требования: минимизация памяти и скорость работы. То есть это абстрактные соображения, ну типо «чтобы не тормозило сильно». Не надо додумывать задачу за Product Owner'a :)

Answer 7

[Dmitry Dedukhin]

Не знаю насчет других БД, но в MySQL мне известен только один способ получения случайной выборки:

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

Это _очень_ медленно работает, т.к. сканируется вся таблица («Using temporary; Using filesort» со всеми вытекающими).

Comments

[el777]

лучше N раз дернуть запись по рандомному ключу
Берете N от 0 до max(id).

SELECT * FROM table WHERE id>N LIMIT 1;
Хотя, оно конечно не очень честное будет — все зависит от «дырок».

[Dmitry Dedukhin]

Ваш способ плох тем, что количество запросов зависит от N: при N=1000 вам придется сделать 1000 запросов.
Поэтому, я всегда стараюсь избегать случайных выборок.

Answer 8

[Kindman]

К сожалению «простой» массив, целиком загружаемый из файла при каждом запуске скрипта — это и есть самое-самое медленное решение из всех возможных, поскольку очень много времени будет тратиться как раз на разбор содержимого файла, и на создание динамической структуры массива.

Comments

[Roder]

Зачем каждый раз? Что-нибуть вроде memcached.org/ и тогда один раз при первом вызове. И источник уже совсем не критичен.

[Kindman]

Массив (в РНР) гораздо больше (в 30 раз) памяти кушает, чем одна упакованная бинарная строка такой же емкости. Не хватит и 128 мегабайт памяти, чтобы создать array() с 2 миллионами целых чисел.

<?php
$n=2000000;
$m0=memory_get_usage();
for ($i=0; $i<$n; $i++)
  $a[]=$i;
echo memory_get_usage()-$m0;

Answer 9

[debugger88]

noSQL? redis.io/ например. Очень быстро и просто.