Свежие комментарии

Если хэш в памяти - вопросов нет (надо смотреть на оверхеды и все такое, но принципиальных возражений нет)

Как только в память влезать перестаем - с хэшами начинается катастрофа, ибо любое обращение к этой конструкции с вероятностью (размер кэша/размер данных) преврашается в seek(rand()) и вместо сотен тысяч транзакций в секунду мы скатываемся в лучшем случае к первым сотням в секунду (от дисковой подсистемы зависит, на SSD будет быстрее, скажем 10^4 в секунду)

Может у Berkeley DB какой-нибудь lazy write и она репортает запись до фактического завершения? :-)

3 миллиона 22х байтовых записей, 114MB файл.
14s запись и 4s построение индекса.

Ключ, правда, у меня 8байтовый datetime, распределение почти уникальное.

Ну я попробовал одним проходом - залил в таблицу с индексом, пакетами по 100k rows. Он перемены мест слагаемых сумма не изменилась. Раздельность же дает представление, что время теряется на фактической записи, а не сортировке.
Дисковые технологии демонстрируют удивительный прогресс в объеме и удивительное отсутствие прогресса в скорости.

Сервер настоящий, cpu-z:
http://www.dontsov.com/tmp/pc1.png
http://www.dontsov.com/tmp/pc2.png
http://www.dontsov.com/tmp/pc3.png
а вот что происходит на другом конце fiber'а (гигантский SAN) мне неподконтрольно.

lookup - не пользовательский. Эта штука обрабатывает входные данные (неважно откуда взяты, просто поток данных), заявленная в требованиях скорость обработки приводит к указанной частоте лукапов (100k/sec - хороший случай, 500k/sec - плохой), при этом обработчик данных на самом деле может их жевать на одном ядре производя 2-3 миллиона ключей для лукапа в секунду, но этого уже не прожевать (а 500k на заявленных размерах - прожевать без проблем). Я, по всей видимости, не могу рассказывать более подробно (даже из какой конкретно области задача. ну обычная такая задача).

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

Интересно еще машинами померяться. Ты, небось, на настоящем сервере развлекался?

А скорость заливки меня интересует по той причине, что неприлично елозить диском и заливать три часа то, что заливается за минуту. Три часа - это в ситуации когда а) "индекс не влезает в кэш" б) решаем в лоб. Т.е. сам сторадж (Berkeley DB) - он хороший, там можно быстро поудалять-повставлять немножко, но с точки зрения обычной SQL-бд это в одной кучке и индекс и данные, индекс оторвать нельзя.

Именно. Скока не жалко. Гораздо полезнее отвести буфер на это а не на свой кэш базы (в случае Berkeley DB всегда есть выбор).

Собственно, если посмотреть на предыдущий постинг и сделать поправку на то, что кэш вообще не нужен (нужно исчезающе мало), то получится что если выделить 300M на буфер сортировки а не на кэш, мы получаем ускорение в 130 раз (для данного конкретного примера с 18M записей).

Блин, вот казалось бы соседних областях работаем, и то нужно о базовых понятиях договариваться.

lookup - это пользовательский запрос найти запись по ключу?
500 тыс пользователей в секунду где-то нажимают на кнопку и вытаскивают запись из этой базы? Это какая-то фантастическая нагрузка.

Время записи тебя волнует из-за downtime'а ? Записи генерятся и должны быть записаны в течении дня или один раз в конце дня?

Я тут попытался воспроизвести - 18млн 30 байтных записей.
bcp-in в неиндексированную таблицу заняло 88s (сейчас пойду вешать звезлюлей SAN-техникам) и построение индекса 9s.

mmap-ed файл, естественно сортированный, это отличное хранилище, пока оно не очень большое. Там довольно очевидные недостатки
- очень дорогое удаление и вставка (в общем случае, половину файла надо подвинуть)
- 2-гигабайтное ограничение для 32-битных ОС
- вымывается кэш операционки.

Но для read-only storage не очень больших размеров (или в ситуации, когда можно побить на сегменты и одновременного доступа к разным сегментам немного) - отличная вещь, очень любим.

Я чего-то не понял задачу задачи.

"Индекс должен помещаться в кеш" - это достаточно тривиально и известно сто лет.

У меня задача - принять 500 млн записей в день. Самая важная технология - partitioned table. СУБД работает с сегодняшним субсетом данных, в предыдущие дни лежат на диске не мешаются.

В свое время в Top100 этот фокус не удался - что-то там падало и было криво. Разбираться тогда - не было сил.

Заметим, что при использовании qsort() целочисленные сравнения нифига не более быстрые, ибо строковое побайтовое сравнение в очень большой доле случаев срабатывает по первому или второму байту.

Ну, в общем случае сделать ~50-60% сортировки (судя по числу срабатываний сравнений, см тут: http://blog.lexa.ru/2008/11/20/o_sortirovke_uzhasi_programmirovanija___2...) наверное не сильно хуже. Мне не сложно проверить (заменив функцию сравнения в сортировщике).

Но надо учитывать вот что
1) сортировка - штука быстрая, это где-то 2% от рантайма и 10% от user time
2) за счет полной сортировки получается заранее склеить записи с одинаковыми ключами, а это ~10% обращений в базу в моем случае
3) Списки дадут большой оверхед по памяти: 1 или 2 указателя (8 или 16 байт на 64-битной архитектуре), а размер записи с ключом у меня - 28. Можно, наверное, 256 динамически растущих массивов, но на реаллоках умрем (память будет сильно фрагментированной - а речь ведь идет о десятке мегабайт на список, скорее всего реальной памяти мы возьмем вдвое против потребного т.е сравнимо со списком).

Т.е. не все так просто :)

> Не забываем, что BerkeleyDB рассматривает ключи как > байтовую строку, поэтому сортировать надо в
> лексическом порядке.

А это всегда так? Вроде, в BerkeleyDB можно подменить функцию сравнения ключей на свою - тогда в твоем случае можно пользоваться более быстрыми целочисленными сравнениями?

А если вообще отказаться от полной сортировки? У нас ведь задача попасть в кэш СУБД, а кэш СУБД может быть не таким уж и маленьким. Достаточно отсортировать по первому байту и иметь кэш размером в 1/256 от предполагаемого объема СУБД (несколько упрощенно) чтоб в кэш помещались все записи с ключом начинающимся на, скажем, 0x55. Вне зависимости от следующих за ним байтов. Они же все кучно расположены. Что это дает? Да удаление операции сортировки вообще. Достаточно иметь 256 односвязных списков в которые будут добавляться записи при генерации, в какой именно - вибирать согласно первому байту хэша. Операция очень быстрая, выбрать из 256-байтной таблицы адрес головы списка и два указателя поправить. Не чета настоящей сортировке. После заполнения буфера - выгружаем списки последовательно. Внятно у меня получилось изложить?

Я извиняюсь, откуда такие цифры - 10 и 110?
Мне он предложил 22.99 и 252.99.

Ой, ответил у себя в блоге (а нотифай от ЖЖ почему то не пришел).

Повтор:
Нам чужого не надо, у нас свое "Семантическое зеркало".
http://www.ashmanov.com/tech/semantic/