Berkeley DB

Оптимальная запись в BTree (Живительная сортировка-2)

lexa - 26/Ноя/2008 10:20

Программирование

Интересным следствием из оптимальной записи в BTree является то, что кэш практически перестает быть нужен.

Действительно, нам локально-моментно нужно иметь в кэше по одной странице с каждого уровня дерева плюс место под пару страниц на сплит. Всего получается 4-6 страниц или меньше 50 килобайт для стандартных 8k-страниц.

Эксперименты подтверждают: уменьшение размера кэша с 100 мегабайт до 128k никак не ухудшают производительность. Даже нет смысла приводить результаты замеров, цифры просто такие же (плюс-минус разумный разброс в пару процентов).

Естественно, это относится и к чтению. Если вы собрались читать из BTree (а это не только Berkeley DB, но и большинство индексов в базах данных) много данных и ваше дерево не в памяти - отсортируйте ключи в том же порядке, в котором они в индексе/базе и вам за это воздастся.

Живительная сортировка

lexa - 25/Ноя/2008 22:57

Программирование

Я нижеописанную технику знаю и применяю уже больше восьми лет (с первой "моей" версии Top100), но тут представился прекрасный случай ее побенчмаркать в рафинированном виде.

Задача

Некий код производит записи фиксированной длины:

8-байт ключа
20 байт данных на запись

Эти записи надо сложить в простую базу данных к которой другой код будет доступаться по ключу. Если несколько записей имеют один ключ, то в одну кучку надо сложить все эти записи.

В качестве хранилища используется BerkeleyDB, формат Btree. Исторически сложилось, не обсуждается, впрочем любые базы данных себя поведут примерно одинаково.

Кто виноват

Ключей - много. В моем тестовом примере их 18 миллионов, а вообще может быть несколько сотен миллионов (на бОльшие размеры пока рассчитывать не надо).
Ключ - это хороший хэш от строки, поэтому некий код практически является генератором случайных чисел.
Дублирующих ключей (требующих аппенда записи) относительно мало, около 10%, правда есть ключи-рекордсмены, которые повторяются примерно в 0.3% случаев (60 тыс. повторов на 18M).

В результате, если не делать кэша размером хотя бы с половину базы данных (а делать его разумным, процентов 10-15) и просто писать данные в базу по мере образования, то все происходит довольно медленно: тестовые 18 млн. ключей пишутся в базу на моей тестовой машине около трех часов при размере кэша в 300 мегабайт и базе, дорастающей до 800M. Нет, 1800 транзакций в секунду - это неплохо, но хочется гораздо больше, ибо генерация тестовых данных занимает примерно 3 минуты.

Причина торможения понятна: если ходить в кэш с random-ключом, то вероятность cache hit примерно равна отношению размера кэша к размеру базы. Пока база маленькая - мы попадаем почти всегда, как только перерастаем кэш, так сразу начинаем изучать время HDD seek вместо более полезного занятия.

Решение, впрочем, довольно тривиальное.