Микросервисы и точки отказа.

У меня есть планы по запихиванию нижнего слоя SWMRStore из Мемории прямо в контроллер SSD, чтобы работать напрямую с флешем.

звучит очень перспективно, интересно было бы увидеть результаты

Под фреймворком я понимаю вертикально интегрированную среду, оптимизированную для какого-то класса задач. У нас уже есть вполне годные (на мой субъективный взгляд) фреймворки для «микросервисов» без состояния, но чего-то подобного для «сервисов с состоянием» нет. Причины тут вполне объективные, и участники дискуссии прямо или косвенно их уже отметили. В идеале тут нужно было бы «раздербанить» какую-нибудь СУБД, упаковав её функционал в переиспользуемые библиотеки, интегрироанные в фреймворк, но тут будет просто адов объем работы. На мой субъективный взгляд этот объем работы сопоставим с разработкой СУБД «с нуля», так как надо (1) всё писать на подходящем ЯП (C, С++ и Java «не предлагать»), (2) не ограничиваться реляционной моделью и (3) не ограничиваться SQL. И там по ходу будет еще много технических проблем, от слабости интерфейсов ОС, вранья дисков и до необходимости задействовать широкий класс акселераторов для БД и ИИ.

Сложность работы с состоянием состоит в том, что хороших универсальных решений нет. Ту же CAP можно «нарушать», но только в частных ограниченных случаях, за счет хорошей проработки модели данных, получая одновременно и хорошие гарантии консистентности, и хорошие числа доступности, и вполне приемлемую отказоустойчивость (обсуждаемая выше Causal Consistency — пример такого компромисса). Но это будет очень частное решение (например, социальная сеть), и до уровня фреймворка его доводить нет никакого смысла. Потому что нам не нужно клепать социальные сети одну за другой, как мы делаем это для веб-магазинов.

Поэтому таких фреймворков и нет. Сделай ты его, и у него будет 3 юзера с половиной. Потому что остальные просто не смогут впихнуть в него свои задачи. И это в лучшем случае. В худшем ты будешь просто кормить своих (потенциальных) конкурентов.

Сейчас, кто может в такие вещи, делает сразу облачные СУБД, причем оптимизированные для работы в своем же собственном облаке. Внутри они могут быть сделаны уже по сервисной парадигме, тут нет никаких проблем.

Если тебе интересно этим заняться, то начни с изучения внутренностей опенсорсных СУБД.

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

Да, и если ядро необосновано разделить на микросервисы, то оно окажется больше и ненадежнее. При этом я полностью согласен с тем, что вспомогательные фичи нужно выносить из ядра. Но есть фичи, которые придется реализовать единым куском, независимо от конечной формы реализации, и это нужно будет сделать, сколько митингов не организуй, сколько диаграмм не рисуй, сколько смузи не хлебай. Что-то должно стать самым ответственным, и если ответственность прекидывать, как «горячий пирожок», то может оказаться, что ключевые фичи в итоге напишут самые бездарные программисты и все остальные будут харкать кровью до конца своих дней.

В том-то и дело, что в CoW-based SWMR блокировок на сами данные нет, поэтому нет и таких искусственных, но фундаментальных ограничений на производительность. У меня есть планы по запихиванию нижнего слоя SWMRStore из Мемории прямо в контроллер SSD, чтобы работать напрямую с флешем. Тут можно будет получить сотни тысяч TPS на запись на устройствах консьюмерсокго класса с «ценой вопроса» в $100

Проблема в том, что сложность с числом блокируемых таблиц будет расти как O(N). То есть, при одной таблице это очень приятно, при двух просадка серьезная, но очень даже неплохо, 3-4 — уже накладно, 10-20 — затея уже спорна, учитывая тот факт, что какой-нибудь Berkley DB будет бегать со сравнимой скоростью, поскольку блокирует отдельную запись, а не всю таблицу, в результате чего все транзакции выполняются не конфликтую друг с другом.

Согласованность для CAP и для ACID — разная, но сводимая друг к другу

Я уже отвечал, что не нужно пытаться их сводить друг к другу — они просто разные. C в CAP — это «актуальность», C в ACID — это «логическая корректность». Они имеют ненулевое пересечение, но довольно часто не пересекаются.

N упорядоченных элементов могут быть согласованы N! (N-факториал) разными способами, и когда мы говорим про работу с рассогласованными данными, мы должны как-то разделять такое количество вариантов на согласованные и несогласованные. Это будет, как минимум, очень трудоемко в плане просто кодирования

Как правило, всё намного проще, в системе просто-напросто нет агентов-ораклов, которые видят и слышат всё сразу, потому проблемы с «N! разными способами» нет, каждому агенту важно лишь видеть соблюдение некоторого набора логических взаимосвязей, как то увидеть собственные изменения и видеть изменение системы только в одном направлении — дальше уже не важно, какими перемешанными увидит другой агент эти данные.

То, что нет инструментов для проектирования и реализации таких систем? Ну да. Тебя не не возмущает, что банальная сишная программа, вроде Quicksort, вроде как может иметь N! вариантов выполнения — потому что рациональная сложность этого алгоритма для человека намного, намного меньше.

Я, например, не представляю, как это можно сделать каким-то универсальным способом, когда мы говорим об открытом фреймворке, а не об узком частном закрытом решении

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

Особенно ехидные комментарии от людей вида «Эй, Амазон, как тебе тут помогли экстремальные навыки оборачивания связанных списков, которые ты меня спрашивал на собеседовании?»

А можно ссылку на комментарии? Очень уж мне доставляет злорадствовать над криворукими индусами из «уважаемой» корпорации.

Там компиляция прошивки длится в районе получаса. Еще куда ни шло. FPGA печально известны своим очень долгим development iteration

Хм-м-м, я серьезно FPGA не занимался, потому для меня удивительно твои слова. Я абсолютно уверен, что слабо оптимизированную топологию можно очень быстро собрать на FPGA, просто раскидав узлы «от балды». Но тут я не специалист, как я уже написал.

емнип были какие-то монеты, которые специально создавались для майнинга на cpu и против майнинга на gpgpu (правда это не доказывает что там кэш играет роль)

Ну да, можно много чего запутать так, что на GPGPU оно будет невычисляемо. Только если ставить даже ту же задачу с XML как «сериализация данных в и десериализация из текстового формата», не ставя условие на конкретный кривой формат, то эта задача прекрасно решается GPGPU, FPGA, и просто параллельными вычислителями.

например, для последовательности 3n+1 десктопный вариант это посчитать k-ый элемент последовательности (что ты отказываешься считать задачей, хотя это все же задача), а серверный будет «нагрузив все доступные ядра, проверить что 3n+1 возвращается к 1 для максимального числа начальных чисел за заданное время (или за минимальное время для заданного множества начальных чисел)»

Это всё мартышкин труд, как и парсинг XML. Можно с таким же успехом рассуждать про «а что будет, если абсолютно твердым шаром ударить в абсолютно непробиваемую стену?». Бензин подорожает — вот что будет.

я оцениваю ситуацию в железе сейчас почти так же, как ты пишешь — но виноват тут не рыночек, виноват покупатель, согласный потреблять говно

95% покупателей — идиоты, они вообще не понимают, зачем им это железо, да и не нужно оно им совсем. «Согласен» он через те же механизмы.

У нас уже есть вполне годные (на мой субъективный взгляд) фреймворки для «микросервисов» без состояния, но чего-то подобного для «сервисов с состоянием» нет

«У нас есть вполне годные заводы для производства машин без колёс, четырехзонный кондиционер, управление жестами, но чего-то подобного с колесами пока что нету» — да, в том-то и проблема, что почти все прикладные задачи требуют состояния.

В идеале тут нужно было бы «раздербанить» какую-нибудь СУБД, упаковав её функционал в переиспользуемые библиотеки, интегрироанные в фреймворк, но тут будет просто адов объем работы

На дербанинг какого-нибудь SQLite не нужно адового объема работы. Добрая половина реализации какого-нибудь постгреса — это SQL, в том числе оптимизатор, встроенные функции и типы данных. Если порезать всё лишнее, то получится реализация не сильно больше SQLite.

Сложность работы с состоянием состоит в том, что хороших универсальных решений нет

Сложность работы с состоянием заключается в том, что в индустрии долгое время доминировали старые пердуны с C/C++, изначально построенными вокруг синхронной модели «вызвал функцию — получил ответ». И да, это в том числе касается C++ с его стэковой RAII — если ответ функции откладывается, то непонятно, как учитывать выделенные ресурсы и когда их высвобождать, а GC туда не завезли. Максимум прогресса, который смогли родить за эти годы — это async/await, который позволяет продолжать писать код так же, но при этом код магически становится асинхронным.

Как ты можешь догадаться, это касается не только БД, а вообще растянутых во времени «побочных эффектов» (а побочные эффекты — это единственная цель написания программ). Модель синхронного выполнения плохо работает решительно везде, но старые пердуны продолжают бережно передавать ее новым поколениям.

И дальше уже логично мы приходим к тому, что если у тебя атомарность и согласованность невозможна согласно законам физики, но коммерческий кодер «за деньги» с дипломом престижного ВУЗ-а умеет писать только со строгой атомарностью и согласованностью, то спрос рождает предложение, и тогда индустрия начинает делать вид (чем она обычно и занимается), что имеет решение класса «вечный двигатель», хотя на самом деле нет. Дальше уже производители вечных двигателей соревнуются по числу зон климат-контроля и обивке сидений, пытаясь замять тот факт, что на самом деле ездить машина не умеет.

Невозможно даже банально атомарно выполнить запрос-ответ на удаленном сервере — сервер может выполнить операцию, не послав ответ. Причем, таких операций может быть много, такой «безответный» режим является нормой даже для какого-нибудь ZooKeeper. Но любой уважающий себя маркетолог очередной СУБД будет кричать тебе про безупречные гарантии ACID и прочие бессмысленные слова.

Проблема в том, что сложность с числом блокируемых таблиц будет расти как O(N).

Чего ты опять про блокировки? В SWMR (single writer multiple readers) все писатели огорожены одной большой блокировкой на всё хранилище. Зато, за счет CoW, писатели совсем не мешают читателям, что и позволяет выжать из физики устройства по максимуму (отсутствие координации).

Причина, по которой эту схему не использовали ранее, в том, что CoW очень плохо себя ведет на HDD: фрагментация из-за копирования убивает линейное чтение. На SSD сейчас модны LSM, якобы они продлевают работу диска. LSM хорошо держат пики по записи, что хорошо для веб-сценариев («Black Friday»-proof) и бенчмарков («смотрите, какие у меня миллионы записей в секунду»), но плохо себя ведут, когда сборщик мусора включается (интенсивная запись в устоявшемся режиме).

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

Я тебе подскажу, куда смотреть. С точки зрения теории информации, рассогласованность это – «потеря информации». Соответственно, теоретико-информационными методами, за счет достаточной избыточности кодирования, можно компенсировать эту потерю. А вот уже на сколько получится компенсировать – зависит от задачи. Вообще говоря, идея «интервального счисления» в Spanner, а так же схема с голосованием между репликами в NoSQL K/V, растет именно отсюда.

Лучше всего на такую модель хранилища лягут задачи, которые изначально допускают некоторую неточность. Например, задачи комбинаторной оптимизации. Тот же ML, много их. Т.е. твой оригинальный тезис о том, что нужно сразу затачиваться на рассогласованность вполне здрав и рационален. Просто раскрывается он на классе задач (и с использованием матчасти), с которым редко сталкиваются обычные программисты.

А можно ссылку на комментарии? Очень уж мне доставляет злорадствовать над криворукими индусами из «уважаемой» корпорации.

К сожалению, нет. Я по памяти пересказываю)

Если порезать всё лишнее, то получится реализация не сильно больше SQLite.

Это, кстати, да. Но, в любом случае, если этим кто-то и занимается, то «тихо и незаметно». Мейнстрим же продолжает идти в направлении монолитных СУБД (по моему впечатлению).

Модель синхронного выполнения плохо работает решительно везде, но старые пердуны продолжают бережно передавать ее новым поколениям.

Если ты так угораешь по асинхронной модели (я, кстати, тоже), то я настоятельно рекомендую тебе ознакомиться с алгоритмом RETE, Complex Event Processing и их реализацией в Drools (как площадки, где всё это можно пощупать-попробовать).

Привычное уже нам асинхронное программирование в рамках RETE расширяется т.н. «join-узлами», за счет которых можно делать pattern matching на множествах событий, и много чего еще вкусного. Gaia Platfrom, кстати, делает HAL BERENSON, довольно известный человек в мире БД.

Я в рамках Мемории буду делать полноценную реализацию RETE, с многопотоком и аппаратной акселерацией. И плотной интеграцией со слоем данных.

Трехзвенка — только тогда трехзвенка, когда одну БД можно легко заменить на другую.

Опасное заблуждение. Попробуй замнить Оракл, в котором пустые строки и NULL одно и тоже на MSSQL где это разные вещи. Неговоря уже о прочих различиях.

Я в курсе, поэтому слой изоляции бизнес-логики от особенностей БД был довольно-таки сложным.

Причина, по которой эту схему не использовали ранее, в том, что CoW очень плохо себя ведет на HDD: фрагментация из-за копирования убивает линейное чтение

HSQL смеется тебе в лицо.

В SWMR (single writer multiple readers) все писатели огорожены одной большой блокировкой на всё хранилище

Причина, по которой эту схему не использовали ранее, заключается в том, что под нее почти нет задач. ну не ограничивается даже в самых простых случаях транзакция одной-двумя-тремя сущностями. Я подчеркиваю здесь, что речь идет не просто о «добавить», а и про «изменить и проверить инварианты», что требует сочетания многочисленных операций чтения и записи под блокировкой. Под одной большой блокировкой. Целое семейство долгих операций изменения просто нельзя реализовать в такой модели.

С точки зрения теории информации, рассогласованность это – «потеря информации»

Ты бы мог сохранять в БД с каждой операцией температуру диска и уровень загрузки ЦП, но ты этого не делаешь. Это «потеря информации»? Потерей для меня оно будет только если я действительно хотел эту информацию иметь, но не смог. Если независимые операции не сохраняют информации о своем порядке, то это не «потеря», а «отсутствие избыточности» — примерно как кодеки аудио и видео убирают малозначимую информацию из потока, утрамбовывая его таким образом в десятки раз меньшее число байтов. Вот как определить, что является бессмысленным шумом, а что — полезной информацией, и является наиболее важной и сложной задачей.

Вообще говоря, идея «интервального счисления» в Spanner, а так же схема с голосованием между репликами в NoSQL K/V, растет именно отсюда

Ты про то, что глобальные версии в Spanner формируются шагами? При чем тут голосование между репликами — я вообще не понимаю.

Лучше всего на такую модель хранилища лягут задачи, которые изначально допускают некоторую неточность. Например, задачи комбинаторной оптимизации

Например, почти любая прикладная задача офисного работника. Лишь изредка при конфликтах нужно определить порядок операций — но только порядок, сами транзакции можно выполнять в режиме eventual consistency сколько угодно долго. Даже банальный LOR требует согласованности по большей части лишь на уровне одного сообщения, то есть, определить порядок редактирования-удаления сообщений, чтобы найти конечное состояние сообщения. Дальше уже треды могут собираться по какой угодно модели.

Мейнстрим же продолжает идти в направлении монолитных СУБД (по моему впечатлению)

Я даже могу сказать, почему. Потому что большинство БД чудом отлажено до работоспособного состояния, и совать в нее какую-то сложную логику — большой риск для сохранности данных. Другое дело, что все они поголовно опираются на единственный лидер, который обрабатывает все запросы для некоего шарда — никакой отказоустойчивости плана «на лидере некорректные данные — скорректируемся по вспомогательному серверу» там нету.

Привычное уже нам асинхронное программирование в рамках RETE расширяется т.н. «join-узлами», за счет которых можно делать pattern matching на множествах событий, и много чего еще вкусного. Gaia Platfrom, кстати, делает HAL BERENSON, довольно известный человек в мире БД

Спасибо, посмотрю.

Причина, по которой эту схему не использовали ранее, заключается в том, что под нее почти нет задач.

Тебе в лицо смеются сразу два класса задач. Это NoSQL с их «ручными транзакциями уровня приложения» и гибридная транзакционная аналитика реального времени, в рамках которой я когда-то с SWMR-CoW и познакомился. Схема очень гибкая, ты в ней за бесплатно получаешь wait-free читателей, консистентные снэпшоты неограниченного размера, конфлюентную персистентность прямо из коробки (историю коммитов как в Git), высокий TPS на запись. Цена всего этого удовольствия — высокие задержки писателей. Если в смеси появится долгий писатель, то все следующие за ним будут его долго ждать. Вот и всё. А дальше мы смотрим, какие задержки по записи мы можем обеспечить (средняя, медианная и максимальная длительности транзакций), и какие достаточны для нормальной работы приложения.

И тут можно/нужно задать вопрос, а на каких технологиях делаются современные гибридные OLTP-аналитические БД и NoSQL. Там сейчас превалирует LSM. Видимо, решили, что LSM для них сейчас лучше. Или просто потому, что модно («все так делают»).

Даже банальный LOR требует согласованности по большей части лишь на уровне одного сообщения, то есть, определить порядок редактирования-удаления сообщений, чтобы найти конечное состояние сообщения. Дальше уже треды могут собираться по какой угодно модели.

Это было бы, если бы сообщения были бы иммутабельными. Такие структуры данных образуют 2PSet и являются CRDT, по какой причине отлично живут в EC (при условии наличия сборщика мусора). Так как комменты можно редактировать, то для LOR-а нужна Causal Consistency. Иначе пользователь А может увидеть, что пользователь Б поменял свой комментарий и изменить свой ответ на него. Но пользователь C может увидеть изменение Б без изменений А и быть из-за этого сильно сконфуженным (если тема «чувствительная»).

Спасибо, посмотрю.

Спрашивай, если что.

У меня к тебе еще пара вопросов по поводу того, что ты упоминал выше.

1. Ты упомнянул некоторое «дерево индексов». Можешь раскрыть тему?

2. Ты сказал (не дословно), что «реляционная модель является источником проблем». Опять же, можешь раскрыть тему? Какие проблемы ты видишь и какая может быть альтернатива?

ты похоже не распарсил то, что я хотел сказать (довольно простую вещь, кстати)

Можно с таким же успехом рассуждать про «а что будет, если абсолютно твердым шаром ударить в абсолютно непробиваемую стену?».

шар абсолютно упруго отскочит, совершенно не деформируясь, и что тут не ясно?

(в оригинале было «всепробивающий шар», но, по-моему, понятие «всепробивающий» не выразимо в классической механике, в то время как «непробиваемая» выразимо как «абсолютно упругая», гы-гы)

Это всё мартышкин труд, как и парсинг XML.

а какие текстовые форматы пригодны под параллельный парсинг хотя бы 4 ядрами?

Под фреймворком я понимаю вертикально интегрированную среду, оптимизированную для какого-то класса задач

а такое вообще бывает в природе?

я было хотел написать «вертикально интегрированных сред не бывает» — но это не так, они бывают (пример — кто-то лепит процы с рандомной системой команд и компиляторы к ним, для того, чтобы бинарный софт или даже бинарный апейт софта на проц юзера А не подошел юзеру Б)

я отказываюсь называть это «фреймворком», на лоре это называют «ограждение», а иногда и «анальное ограждение»

но даже если полностью исключить эмоции, мне не ясна принципиальная возможность такого, как ты его называешь, фреймворка в рассматриваемой области (ниже я об этом)

В идеале тут нужно было бы «раздербанить» какую-нибудь СУБД, упаковав её функционал в переиспользуемые библиотеки, интегрироанные в фреймворк, но тут будет просто адов объем работы. ... И там по ходу будет еще много технических проблем, от слабости интерфейсов ОС, вранья дисков и до необходимости задействовать широкий класс акселераторов для БД и ИИ.

а обычные БД вроде как-то справляются с враньем, причем даже вроде как и в проде?

вот эта идея «самому писать ОС, БД, а чтобы не давать софт чужим — гонять софт в своем облаке (и/или продаться амазону)» по-моему не взлетит или даже не осуществима

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

а вот как ты думаешь сделать аналогичное для распределенной БД? ладно, засекретить свое железо (или даже разработать свое, действительно хорошее) ты можешь, но ты ведь должен ЧЕТКО И ПОЛНОСТЬЮ довести до чужих программистов свою модель данных, например, «это Causal Consistency плюс вот это и минус вот то»

и в таком случае они спокойно смогут сделать то же самое на своих БД

чем выше квалификация, тем меньше людям понравится переносить свою в общем-то рабочую БД черти-куда, когда достаточно переписать отдельные части под подходящую модель Consistency

а вот модель «обычное железо, своя секретная фирмарь, патченный постгрес/sqlite/еще-че-то с открытыми патчами» вроде как может и взлететь — хотя тут думать еще много

Если ты так угораешь по асинхронной модели (я, кстати, тоже), то я настоятельно рекомендую тебе ознакомиться с алгоритмом RETE, Complex Event Processing и их реализацией в Drools (как площадки, где всё это можно пощупать-попробовать).

я вот точно не угораю, но мне интересны именно новые модели, а не код реализаций опенсурсных субд, который ты советовал мне читать (код читать нужно только тогда, когда с моделями уже все ясно — как со старыми, так и с новыми)

а обычные БД вроде как-то справляются с враньем, причем даже вроде как и в проде?

Они справляются за счет сертификации работы СУБД «А» на конкретных конфигурациях серверов фирмы «Б».

а вот модель «обычное железо, своя секретная фирмарь, патченный постгрес/sqlite/еще-че-то с открытыми патчами» вроде как может и взлететь — хотя тут думать еще много

Это и имеется в виду. Открытая версия стека должна быть полнофункциональной с точки зрения разработчика. Например, поддерживать все те же функции SQL и API, что и облачная, только в «более медленном» (без акселерации, etc) или «менее надежном» варианте. Чтобы разработчик мог все делать на своем говно-лэптопе за $500. Как особый подарок, открытая версия может работать в небольших кластерах, за счет доступной HA-опции. Фишка (виртуального) облака в том, что ты можешь притирать софт к конкретному железу и за счет этого иметь возможность продавать дополнительные гарантии.

Второй момент в том, что ты видишь телеметрию своих клиентов и на её основе можешь целевым образом улучшать продукт.

Чтение кода даст тебе понятие о реальной инженерной сложности тех моделей, которые сейчас в работе. Без чего всё будет казаться сильно проще, чем на самом деле. И что то, что мы не имеем пока что «фреймоврков для микросервисов с состоянием» — это результат общей некомпетентности и/или происков корпораций (патенты, etc).

СУБД здесь на «особом счету» в том плане, что их разработчики обычно безбожно врут об их реальных возможностях (и хорошо, есои не сами — себе). СУБД требуется интенсивно тестировать в условиях, приближенных к боевым, и только на основе таких бенчмарков выбирать или отбрасывать. Особенно это относится к СУБД на основе LSM-деревьев, которые очень капризны под нагрузкой и требую тонкой под ней настройки (это если надо выжать из них «обещанное»).

Прелесть СУБД с доступными исходниками в том, что ты в них можешь посмотреть и во всем разобраться.

Это всё, конечно, — «в идеальном мире». В реальности же мы просто берем то, что уже хорошо зарекомендовало себя на заданном классе задач и системных требованиях.

а какие текстовые форматы пригодны под параллельный парсинг хотя бы 4 ядрами?

Тот же Json.

Там, где важна скорость сетевого ввода-вывода, текстовые форматы не используются вообще. Там используются (бинарные) форматы с нулевой сериализацией. Если не все участники доверенные, то дополнительно делается расширенная валидация сообщений.

Столкнуться с ситуацией, когда тебе надо «парсить джейсон в 4 потока» ты можешь в ETL. Когда надо затаскивать в БД большие файлы, которые тебе сбрасывает продьюсер. Ну, затаскивай файлы в несколько рабочих потоков, и всё.

И тут можно/нужно задать вопрос, а на каких технологиях делаются современные гибридные OLTP-аналитические БД и NoSQL. Там сейчас превалирует LSM. Видимо, решили, что LSM для них сейчас лучше. Или просто потому, что модно («все так делают»)

Гибридные СУБД хранят недавние изменения в некоем строчном «кэше», который периодически вливается в основную таблицу в КОЛОНОЧНОМ виде для последующей аналитики. Причем, многие из них даже не умеют толком удалять данные из колоночного хранилища (как минимум ClickHouse и ElasticSearch). Аналитические БД — только колоночные, без вариантов, они настолько в хламину укатывают построчные (на два-три порядка), что сравнивать бесполезно. Такая архитектура делает практически нереализуемым классический ACID с мгновенной фиксацией изменений на дисках, потому что мало просто записать строчные таблички из кэшей — нужно как-то зафиксировать на дисках перенос данных из строк в колонки, а это убивает производительность и лишает затею смысла. Потому вместо ACID делают снимки (еще раз к слову о том, что ACID — чисто маркетинговый термин без технического смысла).

LSM тут ни к селу ни к городу, потому что это метод слияния ИНДЕКСОВ, а не просто таблиц. Поскольку колоночные таблицы обычно проиндексированы по главному ключу, то для них тоже может быть применимо LSM, но это не обязательно.

Так как комменты можно редактировать, то для LOR-а нужна Causal Consistency. Иначе пользователь А может увидеть, что пользователь Б поменял свой комментарий и изменить свой ответ на него. Но пользователь C может увидеть изменение Б без изменений А и быть из-за этого сильно сконфуженным (если тема «чувствительная»)

Да, очевидно, ответ привязан к сообщению, на которое отвечают. При рассогласовании есть более одного решения: можно не делать ничего, поскольку eventual consistency отработает за секунду и проблему заметит только один пользователь за 5 лет; можно уходить на второй раунд при обнаружении ссылки на еще не доступный коммент; а еще можно работать по наиболее старой доступной версии, то есть, грубо говоря, пользователи пару секунд не увидят свои комменты после отправки, пока все версии связанных комментов не обновятся — последний сценарий наиболее сочен и я склоняюсь к этой модели, как самой перспективной. Другое дело, что, как я писал, иногда нужно просто определить глобальный приоритет конфликтующих операций, как то одновременное редактирование одного сообщения — опять же, на этом примере хорошо видно, что такая проблема очень редка, большинстве случаев снимка БД и редактирования одной записи более чем достаточно для всех применений.

Иными словами, CRDT оно только когда нет конфликтов, а когда конфликты есть, то оно ZooKeeper — вот коротко моя идея.

1. Ты упомнянул некоторое «дерево индексов». Можешь раскрыть тему?

Ну как бы индексы являются деревьями, тут секрета нет. Можно заметить, что каждая ветка индекса в отдельности тоже является индексом. Таким образом индекс ресурсивно является деревом из индексов. Для вставки уникального ключа в индекс можно лочить не весь индекс, а только ту ветку, в которой может быть этот индекс — это причина, по которой когда-то на иерархические БД возлагались большие надежды.

Те же Amazon S3 и Ceph очень активно используют шардирование по веткам, где перегруженное дерево бьется на две ветки, которые разъезжаются на разные сервера — такая архитектура, в отличие от случайного шардирования по хэшу, дает возможность собирать на одном сервере близкие сущности и выдавать список файлов в папке из одного сервера, а каждый раз опрашивать весь кластер. Это опять же к слову о причинной согласованности: в случае файлового хранилища близкими становятся сущности из одной папки. Другое дело, что далеко не всегда близкость по главному ключу является решающей — именно потому иерархические БД по большому счету сдохли, а возможность строить запросы по любым ключам были убийственной функцией реляционных табличек.

2. Ты сказал (не дословно), что «реляционная модель является источником проблем». Опять же, можешь раскрыть тему? Какие проблемы ты видишь и какая может быть альтернатива?

У нас есть клиент, клиент делает заказ — как клиенты относятся к заказам? 1-к-N? А может быть такое, что один клиент заказал, но для другого клиента? Сделал подарок, или заплатил. Первый постулат прикладного таблицестроения: в типовой прикладной задаче сущности всегда относятся друг к другу как хер-знает-что-к-черт-пойми-чему. Если ты попытаешься четко установить взаимосвязь, то в следующий же момент ты побежишь ее менять. А менять тип связи в реляционных таблицах очень больно — нужно переписывать все запросы после этого. Можно писать всё как N-к-M, но такой тип связи больно обрабатывать средствами SQL. По этой причине 99% интернет-магазинов плохо, очень плохо, еще хуже обрабатывают неожиданные ситуации при недоплате-переплате-отмене-замене-подмене-измене, «давайте отменим заказ и сделаем новый».

Далее, какие у нас столбцы-поля у заказа? Какой бы ты набор полей не выбрал, завтра прибежит менеджер с вопросом «куда мне записывать регион?». И тогда либо в «комментарии», то есть, key-value, который не подлежит обработке SQL и потому недопустим в рамках реляционной модели, либо создавать еще один столбец. Второй постулат прикладного таблицестроения: в типовой прикладной задаче число столбцов, ассоциированных с прикладной сущностью, стремится к бесконечности.

Именно по этим причинам все РСУБД неизбежно скатываются в key-value, которое позволяет хранить информацию неограниченной сложности и произвольными отношениями. Следующий шаг — это заменить бесполезный SQL на язык, который сможет делать запросы по key-value хранилищу — что активно делают в виде тех же JSON полей и расширений для запросов по ним. Другое дело, что это все еще костыли, а не фундаментальное решение проблемы.

а какие текстовые форматы пригодны под параллельный парсинг хотя бы 4 ядрами?

JSON уже упомянули. На самом деле, парсить параллельно можно любой достаточно простой текстовой формат. В случая JSON принцип прост: сначала делаем посимвольный анализ, здесь нам мешают только экранирущие кавычки, которые превращаются в маски, по маскам детектируем управляющие сущности, потом из оставшихся истинных управляющих символов собираем модель — даже последний этап, насколько мне известно, научились параллелизовывать за счет того, что строится не дерево, а плоская модель, которая конкатенируется и дополняется прыжками аля skip-list.

LSM тут ни к селу ни к городу, потому что это метод слияния ИНДЕКСОВ, а не просто таблиц.

Ничего подобного! LSM — это базовая форма представления данных во внешней памяти, от свойств которой в конечном итоге зависит то, с какой скоростью ты можешь туда писать и с какой скоростью ты можешь оттуда читать. Например, чтение на LSM фундаментально медленнее относительно BTREE, плюс нехилый read amplification на линейном чтении на изменяющихся/удаляемых данных. Новые проекты сейчас на LSM делают. И когда ты видишь в опциях storage backend RocksDB — это оно.

SWMR-CoW работает на этом же уровне и определяет то, с какой скоростью ты можешь читать и писать в свою внешнюю память. Он гораздо быстрее на чтение, чем LSM, не страдает так сильно от фрагментации, а read amplification = 0.

Построчник/поколоночник — это уже уровень доменной модели данных, висящей выше storage. В BTREE, который предоставляется самим SWMR-CoW «на халяву», в пакетном режиме (например, добавление в «конец») можно лить миллионами записей в секунду на одно ядро, а колонки создавать в параллель. По коммиту всё сразу фиксируется во внешней памяти, а аналитика видит консистентный снимок пакета изменений уже через микросекунду. Идеальная схема.

Таким образом индекс ресурсивно является деревом из индексов.

Ок, тут понятно. Вы сделали свое, оптимизированное под свою задачу, дерево.

в типовой прикладной задаче сущности всегда относятся друг к другу как хер-знает-что-к-черт-пойми-чему.

в типовой прикладной задаче число столбцов, ассоциированных с прикладной сущностью, стремится к бесконечности.

Следующий шаг — это заменить бесполезный SQL на язык, который сможет делать запросы по key-value хранилищу — что активно делают в виде тех же JSON полей и расширений для запросов по ним.

Ок. Тут тоже понятно. Как ты в этом смысле относишься к графовым моделям (property graphs, RDF)? (вынося пока что за скобки вопрос эффективности реализации графов на том или ином движке)

Я к тому, что параллелить парсинг текстовых форматов — это что-то типа олимпиады по программированию. Эффектно, но бессмысленно. Максимум, можно SIMD использовать. В IO-интенсивных задачах всё равно одно ядро будет на входящий поток данных. Потоков просто значительно больше, чем ядер.

хаха. С учётом того, что смена СУБД событие нечастое, зачем столько усилий, которые, скорее всего, никому не нужны окажутся.

Это уже другой вопрос. Отличительная черта трехзвенки — наличие состояния в сервере приложений. Это состояние было необходимо, чтобы разгрузить БД. Теоретическая же возможность переехать с одной БД на другую шла просто бонусом к используемому стеку персистентности объектов. Но как маркетинговое качество трехзвенки использовалось.

Сейчас такая мода на микросервисы…

Плохие решения в IT всегда приживаются. Посмотрите, для примера, на популярность Go и Python.

Но смищно когда все микросервисы разворачивают на одном сервере, но это ССЗБ.

Да. Особенно в разрезе того, что микросервис - не всегда отдельный полноценный HTTP сервер, для примера. Это может быть и россыпь демонов, к которым обращается API Gateway. И даже просто модуль/пакет, живущий в сопроцессе. Но это уже сложно, поэтому об этом не говорят на каждом углу.

А еще, когда я рос в ИТ, я помню постулат «Всегда снижай точки отказа», а с развитием микросервисов мне кажется что точек отказа просто писец как больше становиться.

Не только больше. Ещё будет нарушаться тот же DRY (ведь микросервисы нужны для быстрой эволюционной модели). А ещё KISS системы в целом становится невозможен (ведь появляется 100500 логических сущностей со своими правилами CI/CD).

Притом админ при каждом обновлении фронта и бэка ставиться бешенной собакой.

Теперь эти люди называются DevOps и они созданы, чтобы страдать). Конечно, современный рынок не будет думать о том, что по идее они нужны для упрощения ландшафта и автоматизации.

Обновления «экосистемы» становяться каким-то нетривиальным делом. Еще и микрофронтэнд тут сбоку подползает.

Микрофронтенды - это вообще боль, которая не понятно кому и зачем нужна. Из web давно пытаются сделать какую-то НЁХ. Вот и микрофронтенды - попытка сделать быстро эволюционирующий frontend. Как правило итог очень печальный, ибо специалистов нормальных нет

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

Скажи мне на милость, так почему же еще 40 лет назад эту «базовую форму представления» не задействовали во всех хранилищах? Раньше ведь ограничения были еще жеще, данные хранились на магнитной ленте, где переход на произвольную позицию занимал минуту времени. Не умели логи писать или деревья сливать? Потому что не все данные представляют из себя индексы! RocksDB, оно же LevelDB, представляет из себя один-единственный key-value индекс и больше ничего — потому логично, что для него применяется LSM. Однако, таблица в РСУБД вполне может представлять собой банальный лог, который не нужно LSM-ить. Некоторые СУБД пишут лог даже индексированных данных без каких-то дополнительных представлений, как это делает HSQL.

SWMR-CoW работает на этом же уровне и определяет то, с какой скоростью ты можешь читать и писать в свою внешнюю память. Он гораздо быстрее на чтение, чем LSM, не страдает так сильно от фрагментации, а read amplification = 0

SWMR-CoW сам по себе не является способом оптимизации доступа к постоянному хранилищу, аналогичным LSM, потому сравнивать их некорректно. На LSM точно так же реализуется CoW, потенциально можно сделать SWMR.

Построчник/поколоночник — это уже уровень доменной модели данных, висящей выше storage

А заодно и 90% сложности реализации СУБД. Ты бы еще файловую систему вспомнил.

По коммиту всё сразу фиксируется во внешней памяти, а аналитика видит консистентный снимок пакета изменений уже через микросекунду

Если система распределенная (привет доменной модели данных), то никакой микросекунды не будет. А «распределенной» может быть система из двух локальных БД. Не все прикладные задачи получается засунуть в тупое key-value.

Как ты в этом смысле относишься к графовым моделям (property graphs, RDF)? (вынося пока что за скобки вопрос эффективности реализации графов на том или ином движке)

Не отношусь, именно потому, что не верю в эффективную реализацию оных. Железо, целиком и полностью оптимизированное под алгоритмы и типы данных Си, решительно никак не дружит с графами и прочими вариантами околопроизвольного доступа. Индексы с большим скрипом оседлали, но с графами трюк провернуть намного сложнее. По-хорошему нужен вычислитель со значительной паралеллизуемостью (хотя бы тысяча ядер-потоков и стоимостью создания-завершения потока сравнимой с вызовом функции) — а таких вычислителей не существует, хотя по современным 20 нм техпроцессам такое устройство потребляло бы 0.1 Вт и стоило бы пару долларов в массовом производстве.

Я к тому, что параллелить парсинг текстовых форматов — это что-то типа олимпиады по программированию. Эффектно, но бессмысленно. Максимум, можно SIMD использовать. В IO-интенсивных задачах всё равно одно ядро будет на входящий поток данных. Потоков просто значительно больше, чем ядер.

Современные устройства ввода-вывода с легкостью затыкают все ядра CPU, поскольку NVMe уже выдают единицы ГБ/с, а вот распарсить гигабайты текста в секунду не так-то просто. А NVMe накопителей тоже может быть несколько. И сеточки 10-50 Гб/с уже активно применяются. Как я уже писал, самые производительные ЦП могут распарсить всего-лишь десятки МБ/с XML в одном потоке — по этой причине XML не имеет никаких перспектив. Так что одно ядро затыкается в легкую. Да, SIMD — это один из способов решить проблему. На GPGPU парсинг того же JSON смысла нет переносить, потому что обычно JSON маленький, он не оправдывает накладных расходов по передаче на видюху и обратно, но если JSON больше мегабайта — можно начинать и об этом думать.

вот эта идея «самому писать ОС, БД, а чтобы не давать софт чужим — гонять софт в своем облаке (и/или продаться амазону)» по-моему не взлетит или даже не осуществима

а вот модель «обычное железо, своя секретная фирмарь, патченный постгрес/sqlite/еще-че-то с открытыми патчами» вроде как может и взлететь — хотя тут думать еще много

Да, да, да, рыночек гарантирует отсутствие инноваций и любого развития, более того, не так важно иметь «свою секретную фирмварь», как рассказывать о том, что она у тебя есть. Например, Apple использует массовое железо с незначительными модификациями, но эти модификации позволяют ему говорить про «своё секретное железо, не имеющее аналогов». Смартфоны с тачскрином у Nokia были технологически лучше, чем айфоны, но именно Apple придумал, как их продать, Стив Джобс в своем фирменном стиле сумел создать самый такой же, как у конкурентов, продукт — и его купили.

чем выше квалификация, тем меньше людям понравится переносить свою в общем-то рабочую БД черти-куда, когда достаточно переписать отдельные части под подходящую модель Consistency

Квалификация? Она в чем изменяется? В нежелании изучать новые технологии и методики?

то, что мы не имеем пока что «фреймоврков для микросервисов с состоянием» — это результат общей некомпетентности и/или происков корпораций (патенты, etc)

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

Как правило итог очень печальный, ибо специалистов нормальных нет

Разве микросервисы в целом не являются проявлением этого самого «специалистов нормальных нет, потому будем делать вразнобой десятком некоординируемых команд»?

Не все прикладные задачи получается засунуть в тупое key-value.

Давай, я объясню. В тупое key-value можно засунуть всё, что можно засунуть в RAM. Это такая же обобщенная модель памяти. Проблему могут представлять модели консистентности. В случае слабой модели прикладная структура данных над K/V просто «рассыпится» точно так же, как неогороженные блокировками контейнеры в RAM рассыпаются при параллельном доступе к ним. Но, предположим, что K/V нам дает гибко настраиваемые уровни консистентности, от EC до сильной.

Что нам теперь надо, так это уровень моделирования данных, который преобразует структуры уровня приложения (массивы, очереди, таблицы, графы, деревья во всех ипостасях и т.д.) в блоки фиксированного размера, пригодные для сохранения в K/V. Это все можно сделать на базе BTree, добавляя в дерево различные метаданные. Например, сохраняя в каждом бранч-узле количество ключей в соответствующем поддереве, можно сделать и динамический массив, и очередь с приоритетами. BTree оказывается на удивление composable базовой структурой данных как для основной, так и для внешней памяти. И что тут нужно, так это программный фреймворк, который позволит строить такие деревья с заданным набором метаданных. Я в начале 10-х ожидал, что такие фреймворки над K/V появятся массово, но народ просто вернулся на SQL и «таблицы сразу из коробки», назвав это «NewSQL».

SWMR-CoW — это способ атомарно и транзакционно сохранять блоки прикладных контейнеров, реализованных в виде BTree, прямо на блочное устройство, минуя всякие промежуточные слои типа RocksDB. Всё, что для этого надо (по минимуму) — это блочный аллокатор, который тоже можно сделать на Btree-bitmap. Схема частично реализована в LMDB, а так же в куче CoW FS. Её близкий аналог — это Append-Only BTree.

LSM тоже допускают некоторый уровень композиционности с точки зрения отображения прикладных структур данных на них, но и близко не стояли с BTree в этом плане. В основном, потому что это не деревья, а сортированные массивы большого размера. Поэтому тут мы мутим BTree, клоки которого тупо хранятся в LSM как K/V. Схема не лишена смысла сама по себе, если LSM (тот же RocksDB) уже есть «из коробки». Или если хочется эти блоки сохранять так же в С*/S3/DynamoDB/etc, а не только на локальном блочном устройстве.

У LSM проблема с чтением, и они требуют много памяти под bloom-фильтры. Они начали быстро набирать популярность 15 лет назад, когда памяти стало уже более менее «нормально», а SSD еще не было как класса. А до этого применялись AO-BTree. LSM лучше подходят для веб-магазинов, так как потенциально позволяют принимать миллионы случайных ключей в секунду в течение короткого времени. Что как раз и нужно веб-магазинам, которые испытывают внезапный кратковременный наплыв пользователей (после рекламных кампаний). Большой же storage делается по CoW-схеме. ZFS внутри (на уровне consistency points) — SWMR-CoW. Эту схему можно рассматривать так же как гибрид ФС и БД: высокая эффективность работы с блочным устройством ФС в сочетании развитой системой типов БД и транзакционной семантикой.

Не отношусь, именно потому, что не верю в эффективную реализацию оных.

Секрет тут состоит в том, чтобы не хранить графы именно как графы, а использовать граф как промежуточное и прикладное представления. Именно так сейчас графовые БД и работают (не все). Например, графы на уровне хранилища представлены как json-подобные документы. Разумеется, далеко не любой граф может быть эффективно представлен таким образом. Но нам «любой» и не надо. Нам надо что-то немного более гибкое, чем таблицы. Получаем и быстрое и компактное хранилище, и гибкость уровня моделирования.

В тех случаях, когда нам всё же нужна вся выразительность графа, хранить такие графы именно как графы и платить за это. Формат фундаментально «дорогой» (и по скорости, и по объему). Но идея в том, что таких гибких данных будет относительно немного. А основные массивы графовых данных будут физически представлены в специализированных форматах.

Есть такое понятие — пространство дизайна. В данном случае — пространство дизайна физических представлений графов. Задача инструмента моделирования данных — обеспечивать эффективный(*) обход этого пространства. У Btree пространство дизайна очень широкое, а вот у «реляционной модели» — откровенно убогое. В чем и есть её главная слабость с моей точки зрения.

(*) Postgresql следует именно этой парадигме, но так как он написан на С, то не может (непосредственно) использовать метапрограммирование для навигации по пространству дизайна. То, что на С они, условно говоря, будут писать «полгода», на С++ можно сделать инстанцированием шаблона.

И одна из причин, почему у нас так плохо с физическим моделированием данных, это то, что массовые языки программирования не поддерживают необходимые для этого мономорфные дженерики (и много чего еще, но остальное уже не так фатально). Писать же моделирование данных на С++ могут позволить себе не только лишь все.

Я стал замечать, что новые проекты СУБД делаются уже на Rust, а не на Go. Который, к слову, тоже обзавелся мономорфными дженериками. Но обоим в этом отношении до C++ пока еще далеко. Особенно расстраивает история Go, где Пайк со своими поклонниками 10 лет упорно сопротивлялся не только введению дежнериков в язык, но и метапрограммированию вообще.

В тупое key-value можно засунуть всё, что можно засунуть в RAM. Это такая же обобщенная модель памяти. Проблему могут представлять модели консистентности. В случае слабой модели прикладная структура данных над K/V просто «рассыпится» точно так же, как неогороженные блокировками контейнеры в RAM рассыпаются при параллельном доступе к ним.

И это чудесное уточнение, потому что оперативная память машины Тьюринга — это изначально максимально унылая абстракция, которая неактуальна последние 30 лет в свете распространения многозадачных систем, которые применяют прерывания и синхронизацию операций с памятью. Опираясь на модель RAM ты автоматически откатываешься на 30 лет назад по технологиям.

предположим, что K/V нам дает гибко настраиваемые уровни консистентности, от EC до сильной.

Предположим? Предположим, что я умею летать — да, можно предположить, но какой в этом смысл?

уровень моделирования данных, который преобразует структуры уровня приложения (массивы, очереди, таблицы, графы, деревья во всех ипостасях и т.д.) в блоки фиксированного размера, пригодные для сохранения в K/V. Это все можно сделать на базе BTree
BTree оказывается на удивление composable базовой структурой данных как для основной, так и для внешней памяти

А также удивительно неэффективной. Причем, для обоих типов памяти — просто для персистентных накопителей эффект выражен сильнее. Даже для индексированных данных есть более эффективные структуры: хэш-таблицы, префиксные деревья, сортированные массивы в конце-концов.

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

Универсальное хранилище для самых различных структур, которое ты описываешь, один индус годами лепит в самых разных проектах в одном и том же виде, перекочевывая между разными конторами.

Я в начале 10-х ожидал, что такие фреймворки над K/V появятся массово, но народ просто вернулся на SQL и «таблицы сразу из коробки», назвав это «NewSQL»

Потому что консистентность сама по себе из K/V не возникает.

SWMR-CoW — это способ атомарно и транзакционно сохранять блоки прикладных контейнеров, реализованных в виде BTree, прямо на блочное устройство, минуя всякие промежуточные слои типа RocksDB. Всё, что для этого надо (по минимуму) — это блочный аллокатор, который тоже можно сделать на Btree-bitmap. Схема частично реализована в LMDB, а так же в куче CoW FS. Её близкий аналог — это Append-Only BTree

Напоминаю, что LMDB — это очень тонкая прокладка над сложными механизмами кэшей ОС. Примерно как nginx является тонкой прокладкой над epoll. Эти механизмы далеки от совершенства, именно потому приходится создавать LevelDB — чтобы не кэшировать данные как попало, а делать это наиболее оптимальным образом.

В знаменитых бенчах в довольно специфических условиях LMDB в основном укатало остальное БД по единственной причине — потому что по сути бенчилась толщина прокладки к оперативной памяти. Естественно, у LMDB она тоньше всего. Если ты собрался делать RAM-only БД — ты движешься в правильном направлении. К слову, те же SAP HANA и вообще NewSQL СУБД тоже использует RAM как основное хранилище данных — на диски сбрасываются только неактуальные вспомогательные снимки на случай катастрофических сбоев. По этой причине сравнение с LevelDB совершенно некорректно.

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

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

Быстрый вопрос. Ты, наверное, решил, что под BTREE я имею в виду бинарные деревья? Я имею в виде именно b-tree, как семейство производных структур.

Если говорить про бинарные деревья и LSM, то асимптотика произвольного доступа у них одинаковая — O(log2(N)). Т.е. если какое-то бинарное дерево и «сливает» LSM, то это просто по причине того, что бинарное дерево адаптировано под модель памяти RAM(*), а не блочных устройств (DAM).

Асимптотика B-tree на много лучше, чем у бинарных деревьев — O(LogB(N)), где B >> 2. Они в этом плане заруливают и бинарные деревья в RAM, и LSM в DAM, так как требуют меньшего количества чтения блоков.

(*) В современной RAM с прозрачной иерархией кэшей, чтобы ты не «включал зануду».

Универсальное хранилище для самых различных структур, которое ты описываешь, один индус годами лепит в самых разных проектах в одном и том же виде, перекочевывая между разными конторами.

Я вовсе не его описываю. То, о чем я говорю, ближе к Apache Arrow или (но с другой стороны) к твоим PSO. Я говорю о проблемах моделирования высокоуровневой семантики данных. А попытки заваленных шальными деньгами интернет-компаний вырастить в себе инженерную культуру датабэейс-компаний — это отдельный сериал, полный черного юмора, да. Но, в конечном итоге, со счастливым концом. Некоторым удается.

Напоминаю, что LMDB — это очень тонкая прокладка над сложными механизмами кэшей ОС.

Я LMDB привел как существующий пример БД-ориентированного хранилища в модели SWMR-CoW. И, да, его минималистичность является его сильной стороной. У LMDB (как реализации) есть технические ограничения, которые не должны переноситься на SWMR-CoW в целом. Это упрощенный (и неэффективный) метод высвобождения памяти и, собственно, mmap. LMDB создавался для хранения конфигурационных данных, которые большей частью читаются и, ввиду относительно небольшого объема, помещаются в RAM. Использование LMDB за пределами этого случая даст обескураживающие результаты.

Нет никаких проблем реализовать SWMR-CoW напрямую (без mmap и даже FS) над SPDK, с блочным кэшем уровня приложения. В Мемории есть экспериментальный SWMRStore, но он пока что реализован над mmap в качестве блочного кэша, ради простоты и совместимости с приложениями, использующими потоки для конкуррентности. SPDK, liburing требуют использования файберов, а для файберов нужен соответствующий рантайм.

Ты много говоришь про распределенность и масштабирование, и я понимаю твои намеки. Я намекаю на то, что нам нужно сначала научиться по-максимуму использовать локально доступное железо. Т.е. заполнить нишу scale-up и scale-down. И только потом идти в scale-out. Это просто общая стратегия, а не прямое руководство к действию.

Что касается стратегий scale-out, на которых я ориентируюсь, то это «шардинг» или использование небольших строго-консистентных кластеров, в рамках которых возможно реализовать гораздо более развитую семантику данных уровня приложений, чем если сразу делать над слабой EC-моделью. Развитых библиотек прикладных типов данных на EC K/V за 15 лет так и не появилось из-за того, что народ счел эту затею непрактичной и вернулся к «шардингу». Я плыву в том же русле.

Ты, наверное, решил, что под BTREE я имею в виду бинарные деревья? Я имею в виде именно b-tree, как семейство производных структур

У тебя было два варианта: изъясняться так, чтобы тебя понимал собеседник, или выглядеть умным. Ты выбрал второе — не удивляйся, что тебя не понимают. Название B-tree выбрано от балды, но, хуже того, эстафета принята, и теперь у нас есть B+-tree и B*-tree.

Если говорить про бинарные деревья и LSM, то асимптотика произвольного доступа у них одинаковая — O(log2(N))
Асимптотика B-tree на много лучше, чем у бинарных деревьев — O(LogB(N)), где B >> 2. Они в этом плане заруливают и бинарные деревья в RAM, и LSM в DAM, так как требуют меньшего количества чтения блоков

Двоечка у логарифма? Часто авторы предпочитают даже не уточнять, какое основание логарифма для LSM, давай исправим эту ситуацию. Каждый уровень LevelDB содержит индекс блоков (как бы один уровень дерева), потому запрос по ключу для одной небольшой таблицы стоит O(2), а для k/2 таблиц на всём уровне — O(k). Строго математически это O(1), поскольку k — константа. Число уровней — logk(N). То есть, без верхних уровней (для горячих данных) чтение имеет такую же сложность, как у деревьев с k элементов на уровне.

Другое дело, что тут приходят огромные файлы верхних уровней, которые тупым бинарным поиском стоят O(log2(N)) — и они содержат подавляющий объем данных по сравнению с нижними уровнями, уровень ниже стоит уже O(log2(N/k)), так что мелкие нижние уровни по сравнению с вышестоящим всегда дают «+1» и в оценке сложности не отсвечивают.

Однако, что мешает построить более одного уровня индекса для одной таблицы, чтобы получить O(logB(N))? Ответ для конкретного случая LevelDB — наличие фильтра Блума, который по факту является немасштабирующимся дополнительным уровнем индекса и даст фору многим B в B-Tree (дает эквивалент B=100+).

Если размер блока 4096 байт, в него влазит 10 пар ключ-значение по 400 байт, сам ключ 40 байт и в блок индекса оных влазит 100 штук, тогда с блумом сложность по числу чтений блоков O(1) будет сохраняться до 100 000 блоков (или 1 000 000 ключей) на таблицу или 400 МБ. O(1), ололо!!! Расскажи мне больше про O(log2(N)). Почему оптимизировались под этот уровень? Потому что LevelDB разрабатывался для хрома, а редко у какого пользователя профиль в хроме занимает сотни гигабайт.

Да, на десятках миллионов ключей один уровень начнет давать O(log2(N)), но только N здесь будет кратностью превышения над максимальным оптимальным числом ключей в таблице, потому для 100 млн блоков (400 ГБ) это будет log2(1000). Я подчеркиваю, что это не какое-то принципиальное ограничение LSM — в таблицу уровня можно добавить многоуровневое дерево индексов, которое даст на одном уровне ту же сложность O(logB(N)). При этом на горячих данных сложность будет оставаться O(1), и именно в этом и заключается весь смысл LSM — для малых частых операций отойти от логарифма к O(1), и вернуться к логарифму только когда алгоритмы и железо больше O(1) поддерживать не могут.

То есть, LSM — это не «вместо дерева», LSM — это дерево + лог. Собственно, оно так и называется «Log-Structured Merge-tree».

И одна из причин, почему у нас так плохо с физическим моделированием данных, это то, что массовые языки программирования не поддерживают необходимые для этого мономорфные дженерики (и много чего еще, но остальное уже не так фатально). Писать же моделирование данных на С++ могут позволить себе не только лишь все

Макросы на Си замечательно работают. Входят и выходят. Да, не так удобно, как шаблоны крестов, но шаблоны делались как раз по образу и подобию макросов.

Особенно расстраивает история Go, где Пайк со своими поклонниками 10 лет упорно сопротивлялся не только введению дежнериков в язык, но и метапрограммированию вообще

Тем не менее, я согласен с Пайком в том, что метапрограммирование приносит в код сложность, которая редко когда оправдана. Большинство задач прекрасно решается и без метапрограммирования.

сразу 2 возражения:

1. по форме: O(log2(N))=O(LogB(N)) и так же O(LogB(N))=O(log2(N)), и так же О(1)=О(1000) и О(1000)=О(1) — но мысль твою я понял

2. по сути: твое В на практике будет равно 4, или даже 3, или даже 2.1

если мы рассмотрим случай, когда все адреса горячих дисковых данных лежат в памяти, то тут практически любое расположение данных (т.е. адресов) в памяти даст одно и то же быстродействие

если же памяти на адреса горячих данных не хватает — тогда да, допустим двоичное дерево может занять в 2 раза больше места, чем BTREE; пусть BTREE поместилось в память, а двоичное дерево поместилось наполовину — тогда придется делать 0.5 лишних чтения с диска, т.е. у BTREE 1 чтение, у двоичного дерева 1.5 чтения

то есть твое В=3 (даже точнее 2.8284)

если же двоичное дерево даст нам возможность поточнее обрезать область горячих данных, то оно может и обогнать BTREE

Тем не менее, я согласен с Пайком в том, что метапрограммирование приносит в код сложность, которая редко когда оправдана.

Пайк — тупой нытик, возможно так же не желающий повышать квалификацию.

А метапрограммирование надо уметь готовить — тут требуются способности и объем знаний выше средних.

Добавлю, что в метапрограммировании вертикально интегрированная среда, разумным образом *слегка* ограничивающая программиста, была бы возможно кстати.

Еще добавлю, что есть варианты получше метапрограммирования.

Квалификация? Она в чем изменяется? В нежелании изучать новые технологии и методики?

в данном конкретном случае квалификация измеряется в способности послать на 3 буквы своего вендора и сделать лучше него хотя бы для своего частного случая задачи

В нежелании изучать новые технологии и методики?

тут речь может идти о моем нежелании, или нежелании твоих слушателей — это несколько разные вещи, но мы можем обсудить и то, и другое

Макросы на Си замечательно работают.

это полное говно — они не тайпчекаются, в отличие от шаблонов с++ (хотя в некоторых случаях я бы их брал даже и в с++, поскольку нет иного выбора написать код покрасивее)

но даже программирование на шаблонах с++ по степени надежности оставляет у меня впечатление, близкое к впечатлению от программирования приложений в excel (речь о формулах в ячейках, защите ячеек и т.п.) — случайно сломать очень просто, и я бы даже сказал случайный слом почти гарантирован в рамках даже небольшого проекта

еще, если я не пропустил ничего, до сих пор нет макросов с переменным числом аргументов, которые раскрывались бы не в функцию с переменным числом аргументов

т.е. хотелось бы написать

#define  macro() ;
#define  macro(a, ...) int a=0; macro(...)

чтобы

macro(x,y,z)

раскрылось в

int x=0; int y=0; int z=0;

а вот хрен тебе

емнип в variadic templates так можно, хотя и извращенным способом (который не все сочтут повторением моего примера с macro выше)

А теперь представь, что «реальное b-tree» тоже обвешано кучей всяких оптимизаций, как и LSM.

Но, ладно. Ты меня уделал. Пойду дальше уныло заниматься никому ненужным метапрограммированием.

если же двоичное дерево даст нам возможность поточнее обрезать область горячих данных, то оно может и обогнать BTREE

Смотри, есть фундаментальные свойства структуры данных, которые определяют то, как она будет себя вести глобально, «в большом». И есть некоторое пространство оптимизаций, которые дают возможность ускорить эту структуру в частных случаях (иногда — за счет ухудшения в общем случае). Например, мы можем заложиться на некоторый предельный размер обрабатываемых на практике данных и сделать кэш в RAM, читая диск только 1 раз — красота. Но размер БД ограничен размером RAM.

Проблема в том, что такие вещи сильно повышают инженерную сложность реализации такой структуры данных. Если у тебя C* и одно только LSM, то ты можешь оптимизировать его до бесконечности. Но если у тебя набитый разными индексами Postgres, то вылизывать каждый из них таким образом будет слишком обременительно.

Суть в том, что если тебе нужна серия структур данных, а желания закапываться в программирование нет, то лучше выбирать то, что лучше работает в базовом варианте.