Хранение — пожалуй самое тонкое место подобных проектов. В зависимости от решаемых задач оно должно обеспечивать:
— быстрый доступ к данным;
— быстрое обновление данных;
— достаточный функционал с возможностями расширения.
В системах массового обслуживания с большим потоком запросов, малое время обработки отдельного запроса — залог работоспособности системы.
Если важна оперативность появления в доступе новых данных (новостные системы), то на первый план выходит скорость обновления базы.
С ростом объемов данных совмещать совмещать высокую скорость доступа и обновления становится практически невозможно.
Использование в данной ситуации универсальных СУБД практически невозможно (кто не согласен с данным тезисом — предлагаю убедить в этом Яндекс или Гугл). Объемы обрабатываемых мной данных намного скромнее (развернутые на отдельном сервере данные занимают порядка двухсто гиг), но тоже заставили искать другие решения.
Использование известных KeyValue NoSQL хранилищ тоже не всегда помогает. Я пробовал обновлять несколько сотен миллионов записей в Berkelley DB — результат меня не устроил, особенно с учетом необходимости проделывать данную операцию ежедневно.
В итоге для себя я выбрал следующий коктейль (описанные ниже приемы работы используются в реальных задачах и доказали свою эффективность):
— упорядоченный линейный список с хэш-ключами;
— упорядоченный линейный список с индексом в виде двоичного дерева;
— Berkeley DB с надстройкой из MemcacheDB.
Первые два варианта используются для хранения основного индекса, последний — когда количество записей, требующих ежедневного обновления/добавления не превышает нескольких миллионов и необходимо быстро добавить-удалить-зименить несколько записей.
Индексы достаточно большие, поэтому хранение всех данных в оперативной памяти невозможно.
Самый быстрый вариант, конечно — хэш-ключи. По значению сразу получаем результат. Единственный недостаток данных ключей — для хранения требуются избыточные ресурсы. У меня пустоты в индексе не превышают 20% от общего объема. Это достигается благодаря тому, что хэш не вычисляется по искомому значению, а фактически является ID, присвоенным данной записи. ID выбывающих со временем записей используются повторно.
К сожалению такая схема не везде возможна. НАпример иногда необходимо провести обратную операцию — по значению получить ID. В данной ситуации использование хэшей может оказаться слишком ресурсоемким. В таких случаях я использую ключ в виде двоичного дерева. Основной его недостаток перед хэшем — для поиска отдельной записи требуется log2 обращений к диску вместо одного. Когда индекс содержит более 500 миллионов записей — не менее 28 операций чтения. Это довольно накладно. Конечно система пытается помочь мне, кэшируя наиболее часто запрашиваемые блоки. В итоге результат вполне приемлем. Но чтобы не полагаться на милость системы, следующий вариант хранения я решил сделать комбинированным. В памяти в виде хэша будет храниться первая половина ключей. Таким образом при небольшом расходе оперативки получим уменьщение количества обращений к диску. А если принять во внимание, что данные на диске упорядочены, то по хэщу мы единожды читаем блок ключей и дальше работаем с ним в паимяти. Этот вариант пока не реализован, но думаю, он будет более шустрым, чем двоичное дерево.
Таким образом я стараюсь обеспечить высокую скорость доступа к данным. Теперь необходимо решить задачу обновления.
В процессе обновления данных ежедневно участвуют четыре таблицы, в каждой от полумиллиарда до миллиарда записей. Плюс на вход поступает порядка полутораста миллионов новых записей, которые в процессе как через сито проходят через эти таблицы.
Для примера одна из операций. Дано:
— словарь [ключ, ID], порядка 700 миллионов записей;
— исходные данные [ключ, данные], порядка 70 миллионов записей.
Ключи — текстовые строки. Необходимо во второй таблице ключи заменить на ID, а в первую добавить новые ключи из второй таблицы. Клюяи во торой таблице неуникальные. Для реляционно СУБД одним запросом не обойтись, плюс добавьте накладные расходы на импорт и индексирование второй таблицы (данные приходят в текстовом файле). Сколько будет весь этот процесс выполняться — сложно представить. Работа с меньшими объемами давала неудовлетворительный результат.
KeyValue системы тоже не спасают ситуацию. Хотя по MemcacheDB выложены довольно вкусные бенчмарки, судя по испльзуемым в эксперименте объемам данных, такие результаты достигнуты не выходя за пределы оперативки, что в моем случае невозможно (первая таблица — 7 гиг в зипе собственно данные).
Для рещения данной задачи я использую слияние двух потоков с последующим разделением результата (вторая таблица подливается к первой с одновременным сохранением результатов замены). Алгоритм довольно простой, давно описан Д.Кнутом и не только им, и вполне эффективный. В тех или иных вариациях данную схему я использую во многих других обработках.
На выполнение вышеописанной операции у меня уходит порядка 50 минут (сервер 2x2.6GHz Opteron-2218, 16 Гиг ОП, диски — 4x73G scsi).
Таким образом задача ежедневного обновления решается за приемлемое время. Не скажу, что оно меня полностью устраивает, но для повышения эфективности могут потребоваться более сложные разработки, на которые пока нет времени. Есть несколько бумажных набросков, но они требуют предварительной проверке «в металле», поэтому что есть, о том и говорю.
— быстрый доступ к данным;
— быстрое обновление данных;
— достаточный функционал с возможностями расширения.
В системах массового обслуживания с большим потоком запросов, малое время обработки отдельного запроса — залог работоспособности системы.
Если важна оперативность появления в доступе новых данных (новостные системы), то на первый план выходит скорость обновления базы.
С ростом объемов данных совмещать совмещать высокую скорость доступа и обновления становится практически невозможно.
Использование в данной ситуации универсальных СУБД практически невозможно (кто не согласен с данным тезисом — предлагаю убедить в этом Яндекс или Гугл). Объемы обрабатываемых мной данных намного скромнее (развернутые на отдельном сервере данные занимают порядка двухсто гиг), но тоже заставили искать другие решения.
Использование известных KeyValue NoSQL хранилищ тоже не всегда помогает. Я пробовал обновлять несколько сотен миллионов записей в Berkelley DB — результат меня не устроил, особенно с учетом необходимости проделывать данную операцию ежедневно.
В итоге для себя я выбрал следующий коктейль (описанные ниже приемы работы используются в реальных задачах и доказали свою эффективность):
— упорядоченный линейный список с хэш-ключами;
— упорядоченный линейный список с индексом в виде двоичного дерева;
— Berkeley DB с надстройкой из MemcacheDB.
Первые два варианта используются для хранения основного индекса, последний — когда количество записей, требующих ежедневного обновления/добавления не превышает нескольких миллионов и необходимо быстро добавить-удалить-зименить несколько записей.
Индексы достаточно большие, поэтому хранение всех данных в оперативной памяти невозможно.
Самый быстрый вариант, конечно — хэш-ключи. По значению сразу получаем результат. Единственный недостаток данных ключей — для хранения требуются избыточные ресурсы. У меня пустоты в индексе не превышают 20% от общего объема. Это достигается благодаря тому, что хэш не вычисляется по искомому значению, а фактически является ID, присвоенным данной записи. ID выбывающих со временем записей используются повторно.
К сожалению такая схема не везде возможна. НАпример иногда необходимо провести обратную операцию — по значению получить ID. В данной ситуации использование хэшей может оказаться слишком ресурсоемким. В таких случаях я использую ключ в виде двоичного дерева. Основной его недостаток перед хэшем — для поиска отдельной записи требуется log2 обращений к диску вместо одного. Когда индекс содержит более 500 миллионов записей — не менее 28 операций чтения. Это довольно накладно. Конечно система пытается помочь мне, кэшируя наиболее часто запрашиваемые блоки. В итоге результат вполне приемлем. Но чтобы не полагаться на милость системы, следующий вариант хранения я решил сделать комбинированным. В памяти в виде хэша будет храниться первая половина ключей. Таким образом при небольшом расходе оперативки получим уменьщение количества обращений к диску. А если принять во внимание, что данные на диске упорядочены, то по хэщу мы единожды читаем блок ключей и дальше работаем с ним в паимяти. Этот вариант пока не реализован, но думаю, он будет более шустрым, чем двоичное дерево.
Таким образом я стараюсь обеспечить высокую скорость доступа к данным. Теперь необходимо решить задачу обновления.
В процессе обновления данных ежедневно участвуют четыре таблицы, в каждой от полумиллиарда до миллиарда записей. Плюс на вход поступает порядка полутораста миллионов новых записей, которые в процессе как через сито проходят через эти таблицы.
Для примера одна из операций. Дано:
— словарь [ключ, ID], порядка 700 миллионов записей;
— исходные данные [ключ, данные], порядка 70 миллионов записей.
Ключи — текстовые строки. Необходимо во второй таблице ключи заменить на ID, а в первую добавить новые ключи из второй таблицы. Клюяи во торой таблице неуникальные. Для реляционно СУБД одним запросом не обойтись, плюс добавьте накладные расходы на импорт и индексирование второй таблицы (данные приходят в текстовом файле). Сколько будет весь этот процесс выполняться — сложно представить. Работа с меньшими объемами давала неудовлетворительный результат.
KeyValue системы тоже не спасают ситуацию. Хотя по MemcacheDB выложены довольно вкусные бенчмарки, судя по испльзуемым в эксперименте объемам данных, такие результаты достигнуты не выходя за пределы оперативки, что в моем случае невозможно (первая таблица — 7 гиг в зипе собственно данные).
Для рещения данной задачи я использую слияние двух потоков с последующим разделением результата (вторая таблица подливается к первой с одновременным сохранением результатов замены). Алгоритм довольно простой, давно описан Д.Кнутом и не только им, и вполне эффективный. В тех или иных вариациях данную схему я использую во многих других обработках.
На выполнение вышеописанной операции у меня уходит порядка 50 минут (сервер 2x2.6GHz Opteron-2218, 16 Гиг ОП, диски — 4x73G scsi).
Таким образом задача ежедневного обновления решается за приемлемое время. Не скажу, что оно меня полностью устраивает, но для повышения эфективности могут потребоваться более сложные разработки, на которые пока нет времени. Есть несколько бумажных набросков, но они требуют предварительной проверке «в металле», поэтому что есть, о том и говорю.
