УкроСУБД
Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті
Взять все и поделить
К документоориентированым базам данных я уже давно проявляю немалый интерес. Причем с присущими свойствами скорее механика, а не водителя. Взять в руки Монго, нет нет нет ... разве же это наш путь ? А что если взять и выковырять из поисковика базу данных и приспособить ее к обработке Json документов ? В этом чтото есть. Пока мои роботы, караваны интернета, неспеша натягивают терабайты текстовых данных, приближая момент сингулярности данных (хе-хе), есть время застартапить еще одну нетленку, тем более в свете модного ныне импортозамещения. Ну или пародии на него. В любом случае уверен, что любая красивая и стройная мат модель имеет право на реализацию хотябы до версии 0.0.0.1.
Дальше будет чуток теории, но совсем не скучной, просто и на пальцах. За последние несколько десятков лет эволюции, инженеры наплодили множество хитроумных поисковых алгоритмов, прям как звезд на небе. Но я бы их разделил на три основные категории. Это разные виды бинарных деревьев. Хештаблицы и ... Trie. Если с первыми двумя вроде как все понятно, то о третьих знают не многие. Их просто намного реже включают в меинстримовые языки.
Пока не буду рассказывать что такое Trie, гугль (ну или бубен :) ) в помощь, сейчас мы возьмем лопату и начнем копать фундамент. Первое что нужно понимать, это путь от Key\Value базы данных до документоориентированой Json базы данных ооочень короткий, как не странно. Достаточно нарезать Json на ключи, где ключ это путь к аттрибуту и листьями будут номера документов и вуаля. Отискать все документы по атрибуту будет равно взятие ключа из Key\Value, а это ну ооочень быстро.
И тут есть тонкий момент. Большинство баз данных используют разные подвиды бинарных деревьев и хештаблицы, но в схеме выше они не эффективны. Первое, это размер ключа. Ключи у нас будут длинные, по природе они будут очень похожи друг на друга. Бинарные деревья не подойдут, много дублей, скорость работы неочень. Хештаблицы тоже не подойдут, поскольку опять же дубли, опять память и отсудствие возможности просканировать диапазон ключей. И тут на арену выходит Trie. Эта структура данных прекрасно работает с длинными ключами, обожает похожие ключи, позволяет сканировать диапазоны, поддеревья и позволяет эффективно делать даже экзотические запросы вроде, определить есть ли в хранилище часть ключа. При этом, что очень важно, по скорости работы особенно на больших обьемах данных обгоняют хештаблицы, поскольку последние «плывут» с коллизиями.
Для чего я это все рассказываю. Да просто потому, что если форточки в доме будут не ахти, то прийдут более профессиональные ребята и починят форточки. А если с фундаментом не сложилось, то спасет только выброс в море.
Итак, наш выбор Trie. Да да да. Термоядерно быстрая структура, которая обрабатывает миллионы и миллионы запросов в секунду. Кстате спешу Вас заверить господа, что алгоритмы разных ассоциативных няшек самые мозгодробильные в плане затраченых девелоперочасов на строчку кода. Не верите ? Узнайте сколько недель, месяцев или лет тратят на разработку эффективной хешфункции для хештаблицы, хотя с точки зрения реализации это может быть всего
Гараж
Теперь оторвемся от теории поисковых алгоритмов и попробуем собрать ядро нашей базы данных. Под капотом у нас расположатся два черезвычайно эффективных высокооборотистых двигателя. Каждый из которых обрабатывает до 10 млн запросов в секунду на 128ми битных ключах. Между прочим это почти в двое быстрее чем в попсовых хештаблицах из меинстримовых фреймворков, или в пять раз быстрее чем реализации бинарных деревьев. Эти два Trie движка зеркалируют друг друга, они как Инь и Янь в нашей красивой и стройной мат модели. Первый позволяет эффективно искать разные документы по всевозможным аттрибутам, второй движок делает экстракт документов по заданому шаблону. Все просто и эффективно. И, небольшой бонус. Каждый добавленный джисон документ в базу индексируется по всем полям. В этом кстате нет ничего удивительного, именно так ведут себя полнотекстовые субд.
Есть подружки
База данных была бы скучна и кодинг был бы мало эффективным, если бы не было к ней ОРМки. В коде мы работаем с бизнесс обьектами и желательно все эти обьекты автоматом конвертить в джисоны, джисоны в ключи, ключи в кей\велью. Потому пришлось по ходу дела запилить и ОРМку под .NET. Вообщем сервер на Си, к нему конектится дот нет клиент. В целом у меня есть несколько небольших бенчмарков на разные задачи, пару иллюстративных задач вроде «Как написать веб форум в 50 строк кода за час», но всё это пожалуй даст мало впечетления. Поэтому я решил просто скопировать этот черновик из рабочего проекта, чтобы просто оценить примерно синтаксис.
namespace DniproClient { public class User { public string FirstName { get; set; } public string LastName { get; set; } public string Status { get; set; } } public static void Test14(DniproDB db) { User u1 = new User() { FirstName = "Заяц", LastName = "Зайцев", Status = "Offline" }; //save doc uint docId = db.AddDoc(u1); //load doc User u2 = db.GetDoc<user>(docId); //sometime later .... //status was changed in the db db.UpdPartDoc("{'Status':'Online'}", docId); //sometime later .... //update only status in the document //do not recreate object, do not reload FirstName and LastName ! db.LoadPartDoc<user>(u2, "{'Status':$}", docId); } } }
Иподром
Да инмемори. Да отложеная запись на диск (500мс).
Но сеть в замерах участвовала и ОРМ присудствует.
Короче как Вы поняли речь пойдет дальше о штангельциркуле :) Куда уж без него. Набросал четыре бенча
forum.pikosec.com/viewforum.php?f=7
Истина не в последней инстанции, просто чтобы оценить так сказать запас по мощности. Если бы проиграли уже сейчас, то смысла двигаться не было бы дальше вообще.
Что в планах
Не лениться! Допилить рабоче крестьянский джоин, сделать транзакции.
А главное обзавестись несколькими академическими задачами, чтобы на них как на кошках подчистить оставшиеся косячки.
300 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів