bbtree обгоняет skiplist в LSM-деревьях до 6,8 раза
Bbtree: Fastest Ordered Map
Новая структура данных bbtree заменяет skiplist в memtable четырёх LSM-деревьев — fjall, SlateDB, Tonbo и Lance — и ускоряет операции в 1,37–6,83 раза. В индексах Turso вставки стали быстрее в 2,22 раза, а SELECT — в 1,90. При mmap с диска bbtree не требует перестройки после перезапуска: первый ответ приходит в 160–2500 раз раньше, чем у std BTreeMap. Секрет — минимизация промахов кэша за счёт inline-ключей и префиксов.
В bbtree мы относимся к промаху кэша как к Future и тоже его await-им.
- geraneum
> Готово к продакшену благодаря формальной верификации, проверке моделей, детерминированному симулированию, фаззингу и куче тестирования.
Что здесь означает «проверка моделей»?
- tyilo
> Ни один человек не напишет код лучше LLM.
Смелое заявление...
- jared_hulbert
Очень хорошая работа. Я работаю над вещами... смежными с этим, полагаю. Я всё время твержу, что нам нужно гораздо охотнее прибегать к интринсикам, быть нацеленными на кэш-линии как лазер, относиться к DRAM скорее как к асинхронному блочному устройству, но не могу поверить, что не додумался показать влияние трафика когерентности! Когда у меня будет время, я, может, попробую применить некоторые свои трюки к bbtree. Напишите мне в личку. Буду рад связаться, когда займусь этим.