| наши грабли самые фигурные! |
[Sep. 30th, 2019|05:58 am] |
поскольку я так и не нашёл кейвалуя, который бы сделал меня кончить и закурить, придётся запиливать свой. что-то типа lmdb-без-mmap: тоже на b+tree, с acid, variable-length keys, и — скорее всего — без блокирования читалок пока писалка всё портит.
оно кажется ambitious, но на самом деле весь акцид и прочие продвинутые фичи основаны на очень простой концепции: pages are immutable (except the first one, where db header is stored). ну, точнее, кроме первых двух, потому что они используются в режиме flip-flop, на тот маловероятный случай, когда фс умудрится при записи одну из них убить (впрочем, эта фича сдизайнена, но я не уверен, что я стану её делать; а если делать, то лучше тогда заголовки разнести килобайта на 64 друг от друга хотя бы).
в общем, все изменения дерева делаются в скопированых страницах (поэтому читалки спокойно работают, пока мы обновляем базу), а коммит транзакции заключается в том, что мы пишем новый заголовок, и к этому времени все остальные страницы уже обновлены. если у нас нет активных читалок, то старые страницы сразу коммитятся в список пустых, если есть — идут в список «освободить, когда отвалятся читалки»: это обеспечивает consistent database view для всяких курсоров.
ах, да: иногда в b+ приделывают «горизонтальные указатели», чтобы проще было итераторы пилить. это во-первых, лишнее, а во-вторых, с immutable pages без нужды увеличивает количество страниц для обновления. намного проще просто хранить в итераторе весь путь до текущего листа: дерево n-арное, жёстко балансированое, так что тупой массив на 16 элементов справится без проблем (особенно с учётом лимита в 4 гига на базу).
поскольку я не собираюсь ни с кем состязаться в скорости, то всё кэширование пусть делает ось, там не зря дисковые кэши придумали. lmdb их использует через mmap, я буду через read. жаль, правда, что нет возможности сказать оси: «я буду работать с этим файлом строго блоками по 4 кб, можешь смело оптимизировать доступы для такой схемы» (это как раз примерно то, что делает mmap).
пилю я неспешно, потому что срочной нужды в этом всём нет, а делать структуры данных я не очень люблю. так что релиз может и через пару десятков лет быть. но когда-нибудь — я думаю — будет.
p.s.: код lmdb я не смотрел, так что все мои рассуждения о ней — на основе кое-какой инфы от автора и прочих интернет-слухов.
p.p.s: mmap, возможно, будет для больших валуев, чтобы zero-copy. но отдельным режимом, и в версии 2, потому что он дорогой, если его постоянно ставить и снимать. |
|
|