Демка куска пашэ-СУБД движка. Сложно, но мы обсудим. Ссылка. Прототип. Можно тыкать.
|
||
---|---|---|
Очередной какой-то там пашэпроект.
http://fintank.ru:9090/ Что это. По ссылке - тестовая морда в самописный B+-Tree (с дикимичи фичами). Зачем писать своё B+-Tree Незнаю, чё-то все их пишут в мире, наверное это круто. Да ещё вещь не простая, каждый раз что-то своё получается под свои задачи. Как понять. Зайдя по ссылке видим корень дерева. Сверху написано level 5. Значит дерево высотой 6 (самый нижний листовой уровень - level = 0). Почему такое высокое - оно тестовое с размером страницы 512 байт, чтобы блоки почаще делились и проявлялись всякие краевые эффекты. В это дерево напихано 1М элементов. Элемент - это key=value, но их только половина от ляма. Остальная половина элементов - это другие упоротые вещи, о них речь далее. В корне мы видим, что у нас там лежат два разделяющих (всё наше пространство) ключа. По текущей ссылке это: пустая строка и cgLQ. Почему там два - ну так сложилось, обычно больше. Каждый ключ ссылается на блок уровнем ниже (level 4). Если вы хотите найти что-то, что в порядке сортировки строк идёт после cgLQ - жмите на эту ссылку, если до - жмите на предыдущую. Вот скажем я жму на предыдущую (которая "пустая строка). Прихожу в этот блок: http://fintank.ru:9090/?block_id=451 Там навалены разделяющие ключи, которые все до cgLQ. Ну и так далее. Жмём на Bz: http://fintank.ru:9090/?block_id=104958 Жмём на CwvNtFkJk: http://fintank.ru:9090/?block_id=59010 Жмём на CzpDbTlmooFIljFDWNKzGy: http://fintank.ru:9090/?block_id=66489 Жмём на Czz: http://fintank.ru:9090/?block_id=131180 Оппа, пришли на level 0. Это листовой блок, он хранит сами полезные данные, а не информацию роутинга. В данном листовом блоке мы видим несколько ключей: Czz CzzKYs CzzZhYTyER <-- обсудите тот факт, что только у этого ключа тип key=value (KV). D Остальные ключи оказались не просто key=value, а массивами (листами). Например ключ Czz - хранит массив из 2 элементов: @@ocYDrqX @@UOV Это пример "дикой фичи" данного B+-Tree: key=[array]. Есть там ещё key=[set] и ещё key=[map], например. Зачем? - спросит очередной формоклёп с горы. "Разве нельзя было просто сериализовать как-нибудь что угодно, включая список, в строку и сохранить в любое key=value" - спросит он? Можно. Но так любая псина умеет. А чё ты будешь делать, если тебе надо вставить в конец списка? Достанешь ключ, десериализуешь, засериализуешь и пересетишь? Ясно. Сам так живи, мы не хотим. Нам надо так: список длинной 6 млрд элементов и мы вставляем в его середину, да так, чтобы это было за время вставки маленького key=value и чтобы индексы всех 3-млрд-после-середины элементов автоматом сдвинулись на 1 (или N, сколько мы там вставляем). Т.е. список может занимать много блоков данного B+-Tree. И мы не хотим трогать все эти блоки. Я не знаю сколько блоков займёт 6 млрд строчек. И я хочу потрогать максимум 2-3 блока, чтобы выполнить вышеозвученное требование. И хочу вообще на диск не ходить, если уже потрогал эти блоки и снова надо в середину вставить. Короче нужен не какой-то детский уровень, а чтобы сам товарищ Сталин руку пожал. Посмотрим на ключ D в данном листовом блоке. В нём лежит 15 элементов. Но это только кусок, точнее начало. Мы не зря в этот блок пришли. В нём кончается C-пространство и начинается D-пространство, скажем, например. Сколько элементов лежит в списке D я не знаю. Дохрена. Мы видим голову. Выйдем на уровень выше. Кнопки выше нет, юзайте назад в браузере или смотрите выше наш путь в этот листовой блок. А на уровне выше мы видим разделитель D:15. Он показывает на блок, в котором список D продолжается с элемента 15. Можно туда сходить, там всего 3 элемента и в блоке свободно 90% памяти. "Чё так не плотно" - спросит читатель. Ну уплотнялка тут решила не работать или выключена, не помню. Всё потому, что когда в список D в этом B+-Tree инсертились ключи, то они втыкались в рандомные смещения: ну типо 4, 1, 3, 2, 4, 1, 0, 3, 2.... Инсерт в позицию 0 предполагает что старый 0 становится 1. Чё-то я щас смотрю на этот D, у него только голова плотная, остальное надроблено по 1 элементу-на-блок. Короче ладно, это потом пофиксим. Можно посмотреть на этот блок: http://fintank.ru:9090/?block_id=59010 Видно что тут индексы у D шагают на сотни. Если я хочу элемент списка >= 709,то ясно по какому маршруту идти. Вся структура, ясно дело, относительная, на новом уровне надо всё суммировать к 709. Относительная она потому, что... долго объяснять... короче чтобы разные куски маршрутов были максимально независимы. Так мы добиваемся того, что при сдвиге всех элементов в 6-млрд-элементном списке можно пошевелить только какой-то верхний уровень, не думая больше ни о чём. В общем, подумайте и поймёте. Очевидное решение довольно. А вот тут: http://fintank.ru:9090/?block_id=104958 есть D:963. В общем, можно сказать что в D лежит больше 963 элемента точно. Больше чем D:963 + D:590 ну и т.п. - сходите по той ветке, суммируя максимальные индексы разделителей, узнаете. Там оказывается ещё список DA валяется. А тут лежит последний ключ дерева: http://fintank.ru:9090/?block_id=114364 Он называется zzzo и он оказался тоже списком из 1 элемента. Нахрен нужны списки обычному человеку и подобный простой доступ к его рандомным кускам и диапазонам? Например, чатики любых размеров хранить. Большой чатик из 10 млрд сообщений просто жрёт блоки, а доступ к любой месаге по порядковому номеру моментален. Чатик из 1 сообщения занимает как 1 жалкое key=value - удобно, дёшево, молодёжно. Можно дать юзеру создать сто миллиардов топиков в день и никто не умрёт. А в структурах типа key=[set] можно хранить инфу из кнопки лайков. Пихаешь туда id юзеров, оно гарантирует их уникальность и может быстро сказать количество элементов в сете - можно нарисовать циферку лайков. Массивы, сеты (множества), мапы (словари) и прочая дичь, рубить которую на куски умеет B+-Tree - это очень мощно, потому что блоки - вещь децентрализуемая, компактная, сжимаемая и очень сильно крупнологарифмическая, что в целом приводит к существенной бесплатности происходящего. Бенчмарки: в среднем инсерт сюда стоил 7 микросек, селект стоил в среднем 0.7 микросек. Блоки нарублены плохо, во многих 90% пустого пространства. Стоит включить мёржилку, чтобы при инсертах она смотрела на соседей и объединяла их. Это сожрёт сколько-то тактов, но селекты будут ещё быстрее, блоков-то будет меньше раз в 10. Если делать размер блока не наркоманский, а нормальный, где-нибудь в 65 Кб, то уровней будет не 5, а естественно штуки 2-3. Чтокакбе намекает нам на то, что это надо протестить. Вообще у всяких Дональдов-Кнутов описаны B*-Tree (звёздочка) и там есть какие-то соотношения про 2/3 и мёржинг, но в реальности нужно думать. Могу бухнуть с экспертами в этой области. А, да, я ещё статистику считаю конечно же: скажем, если с вероятностью 0.9 втыкали в конец блока (кто-то льёт в конец списка или инсертит возрастающие ключи), то при делении блока левый сын получит 90% старых ключей, а всё свободное место и 10% старых ключей достанется перспективному правому сыну. Левые обычно социалисты. Хорошо примерчик получился про "перспективый", конечно. Мемно! Ну и вот. Я незнаю чё в этот раз так наделилось странно. А вспомнил, мёржилка не работала вообще и был полный рандом во вставке. Да, конечно тестировали на совпадение данных в этом B+-Tree с референсным хранилищем - всё совпадает, обижаешь. Нормальные люди ещё умеют сжимать ключи, скажем сохранять только общие префиксы. Миллиард литературы есть по теме, конечно. Досвидания. |
||
Модератор:
Нравится:
Не нравится:
|
||
30.08.2020, 03:26 |
|
get settings: | 1ms |
get forum list: | 1ms |
searching: | 19ms |
>>> redirection >>>: | 126ms |
get settings: | 1ms |
get forum list: | 1ms |
check forum access: | 0ms |
check topic access: | 0ms |
get topic data: | 2ms |
get forum data: | 0ms |
get found posts: | 7ms |
track hit: | 4ms |
get online users: | 1ms |
check new: | 2ms |
others: | 4ms |
total: | 169ms |