RON, DaRWiN и diff'ы по Майерсу

Одно из демо-приложений RON это система контроля версий DaRWiN. На данный момент эта система хранит документацию RON, ну и понятно, работает подопытным кроликом. Мерж там, понятное дело, бесконфликтный, на основе CRDT (CT Chronofold).

Поскольку система реал-таймовая, то контроль версий, неизбежно, посимвольный. Исторические diff и patch, и всё что их использует (git, например), отслеживают изменения построчно (есть нюансы). Во многом это из-за того, что сложность алгоритма у diff это O(ND), где N размер текстов и D количество изменений. Понятно, что при посимвольном разборе N будет больше, да и D тоже. На глазок, раз в 60-70 :) Исторически, вероятно, компьютеры не тянули столько. Тем более, есть вероятность, что какой-нибудь маньяк засунет в систему не только Войну и Мир (все 2.5MB), но и какой-нибудь CSV файл с результатами всекитайской переписи.

Вторую проблему DaRWiN решает просто: CSV это другой тип данных и diff для него другой, не посимвольный. DaRWiN хранит структуры данных (текст, таблица), а не буковки.

А первую проблему интересно было проверить. Поэтому я взял Войну и Мир и все запятые там заменил на точки с запятой. Это максимально неприятный сценарий, 30тыс изменений и нельзя отрезать неизменные голову и хвост, упростив задачу. Что ж, некоторое время алгоритму пришлось подумать. Но не так долго.

Вывод? Нет причин не использовать посимвольные diff'ы в DaRWiN. Это сильно упрощает вычитку и коррекцию текста. Это позволяет показать нормальные diff-ы после re-wrap'а текста. И это работает в реальном времени.

Но если вам не нравятся запятые у Льва Толстого, то, конечно, придётся медленно вдохнуть и выдохнуть.

Толстой против Майерса

Вчера было интересно. Меня немного занесло и я сделал скриптовый язык поверх RON. То есть, весь парсинг и типы RON'ом уже решены, так что добавить нужно было немного. Тем более что язык сам прорастал через асфальт, разные тулзы уже использовали свои маленькие микроязычки команд. А конкретно сейчас меня подтолкнул маленький случай кодогенерации на awk, который выглядел, как плевок. Все эти грязные сепараторы и липкая пунктуация... нехорошо.
За день работы язык научился выполнять заклинания вроде
for id string in 'ron/status.ron', write _1 _2;
где большая часть слов, технически, 128 битные UUID-ы в Base64 записи, но это станет заметно только тогда, когда мы попытаемся объявить переменную с именем длиннее 20 символов. Чем такой язык лучше awk и прочих? В первую очередь, типизацией. Все переменные это туплы RON из RON атомов (UUID, INT, STRING, FLOAT). Вся обычная возня с парсингом уходит, данные ощущаются скорее как Excel, чем как командная строка UNIX.
Назвал Drone (произносится "дрын").
Для простой кодогенерации пока достаточно, развивать буду по мере необходимости.

# B-tree, LSM tree и хэш таблицы

Весь мир баз данных покоится на двух китах: B-trees и LSM-trees. Это две структуры данных, которые позволяют хранить значения упорядоченно и находить значение по ключу за O(logN). B-деревья мутабельны и представляют из себя просто дерево с большим раздувом. Новые значения просто вписываются в свободную ячейку. LSM-деревья иммутабельны и представляют из себя набор "кирпичей" с отсортированными значениями, которые периодически мержатся. Но есть классический контейнер, который в базах данных не популярен - хэш-таблица. Хотя она и позволяет читать значения по ключу за O(1), в хэш-таблице невозможны range scans, так как значения не упорядочены. Теперь допустим, что вам не нужны range scans. Вы просто пишете и читаете точечные значения. Что получается? А получается довольно интересно.

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

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

Пожалуй, следующий логоческий шаг - обобщить до hash set. Если в наивном хэшмапе есть "ключ" и "значение", желательно одинаковой длины, то в hash set есть просто entries, для которых определены хэш-функция и равенство (ключей). В hash set уже можно складывать всякие забавные entries, например по 32 бита, где 31 бит это ключ и 1 бит это значение.
Получившаяся структура данных чем-то напоминает автомат ППШ - могучее оружие, собранное на коленке из говна и палок.

Примечания.
Ода хэш-таблице написана, пока фаззилась её очередная итерация. Объём кода - 350 строк (это cpp шаблон). Под "говном и палками" я подразумевал "штамповка без фрезеровки" :)

подготовка доклада для HighLoad

RON oplog

Раскрашивание хекса - незаменимый трюк при отладке бинарных форматов и протоколов. Почерпнул когда-то у человека, который занимался реверсом. Мой случай проще - я могу сразу писать код сериализации так, чтобы он мог раскрасить всё, что сам же пишет.

Доклад про RON на HighLoad++ Весна 2001
https://www.youtube.com/watch?v=x88RCCRV48o

Всего-то прошло 10 лет (ровно) с той заметки, где я разобрал BitCoin. В том числе, я тогда сказал, что этот протокол "not green at all" по самому принципу своего действия. И вот уже Сам Гениальнейший Илон Маск вынужден был это признать.
Вывод. Читайте мой канал, что появится тут - Маск допетрит лет через 10.
Кстати, я и по блокчейну скоро кое-что напишу интересненькое.
https://web.archive.org/web/20180624093746/http://www.ds.ewi.tudelft.nl:80/~victor/bitcoin.html

Другое мое заключение - что анонимности BitCoin не предоставляет - недавно было подтверждено экс-директором ЦРУ. Что неплохо. Также недавно вычислили и арестовали основателя BitCoin Fog - через его транзакцию 10 летней давности.
https://m.habr.com/ru/company/globalsign/blog/556590/

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

Интересно также подумать, что я упустил в 2011. Во-первых, динамику схемы Понци (пирамиды) - это оказалось наиболее важным нововведением BitCoin.

Также, я упустил такой важный момент: майнинг это perfect commodity, поэтому он неизбежно будет концентрироваться у небольшого количества крупных операторов, вплоть до монополизма. Economies of scale! Степень концентрации в индустрии майнинга на сегодня является страшной-страшной тайной, но многие известные лица подозревают, что она очень-очень высокая.

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

При правильной постановке процесса, фаззинг превращает работу в игру.
Отладка сложных двоичных протоколов всегда была адcким адом. Особенно на C++, при прямой работе с чанками памяти.
Но вот я наладил раскраску хекса, приделал фаззинг и сижу, собираю баги. То есть я запускаю фаззер, он находит расхождение, минимизирует инпут, я переношу этот инпут в юнит тесты, прохожу в дебаггере - и вуаля, fixed. Ощущения как в шутере каком-то.

# Хронофолд - годовасик

Народная мудрость: не обобщай, пока у тебя нет трёх похожих случаев. Хронофолд вырос из следующего наблюдения: у коллаборативных структур данных, систем контроля версий и обычных редакторных движков есть очень сильный оверлап.
Поэтому возникла мысль сделать структуру данных, пригодную для всех трёх случаев. Основным вдохновением послужили piece table и causal tree CRDT. Понимание проблематики было из прежнего опыта написания коллаборативного редактора для Яндекса, а также из ковыряния в исходниках других редакторов и IDE и написания всевозможных CRDT. Приятной остроты добавлял тот факт, что незадолго перед тем похожие проекты редакторов xi (Google) и xray (github) провалились, а разработчики заработали нервный срыв. Знаем, знаем. Обычное дело.
В результате получился код и прошлогодняя статья https://arxiv.org/abs/2002.09511
Сейчас код используется только в режиме системы контроля версий в DaRWiN, но биг-О выглядит хорошо и для целей коллаборативного редактора.
Правда, кое за чем я всё-таки не уследил: код использует ordered map, которой нет в JavaScript. Так что впереди вторая ревизия алгоритма, на hash map.
Также, С. В. Булгаков сделал реализацию на. Kotlin https://github.com/decentralized-hse/collab-edit и где-то на просторах github я ещё видел реализацию на Rust.
В общем, развиваем тему.

Одна из проблем Unicode в том, что какую кодировку ни используй, всё равно придётся перекодировать. В сети и для хранения используется UTF-8, для внутреннего представления большинство платформ используют UTF-16 (v8, jvm,. net, Windows, итд) , а чтобы гарантировать фиксированную ширину символов, необходимо UTF-32. Этот зоопарк является, на мой взгляд, просчетом проектирования, но, как говорится, тут поздно пить Боржоми.

RON сейчас использует 32 в каноническом представлении, 8 в текстовом. Вероятно, я буду переводить каноническое на 8, по следующим причинам:

+ строки (атом STRING) всё равно атомарны, поэтому нам не важно, где там какой символ внутри,
+ даже 32 толком ничего не гарантирует - ведь есть grapheme clusters и прочий креатив, т.е. codepoint может быть лишь частью символа,
+ экспорт в текстовые форматы сможет копировать строки as is,
+ если держать в памяти много RON tuples, то 8 или 32 имеет большое значение (а tuples стали сильно удобней последнее время; я вовсю использую RON контейнеры, вроде map<Tuple, Tuple>; раньше предполагалось, что только текущая операция в итераторе будет представлена канонически)

Но есть и минусы:
- при получении 8 извне, его необходимо канонизировать, т. е. перекодировать 8 в 8!
- двоичный формат для фреймов это по сути поток варинтов; вкрапления utf8 могут усложнить/замедлить перекодирование, исключить использование AVX итд
- биндинги практически всех языков берут строки в 16.

Так что пока думаю.

Некоторые считают, что египетские пирамиды построены из гигантских блоков, потому что египтянам помогали инопланетяне. Нет. Из гигантских блоков строили, потому что если строить из кирпича, египтяне всё быстро растащат. А так тащить неудобно, так что до сих пор стоит.
И относительно одних недавних дебатов про монорепо: да, принцип тот же. В большой компании должен быть гигантский монорепо с невероятным количеством перекрестных зависимостей. И софт должен быть такой глыбообразный, как браузер Хром.
По тем же самым абсолютно причинам.

Я много раз пел дифирамбы фаззингу, спою ещё раз. На экране - фаззер успешно атаковал хэш-таблицу через коллизии в (слабой) хэш-функции. Я вот сижу и пытаюсь понять, как он нашёл эту ситуацию. Работал полчаса, в 16 потоков.

Посмотрел на интересный забавный проект absurd-sql. Компилирует sqlite в wasm, запускает в браузере, используя IndexedDB для хранения. При этом IndexedDB реализован поверх настоящего sqlite. То есть, как если запускаем виртуалку в виртуалке; или сериализуем protobuf в JSON; и тому подобное. https://jlongster.com/future-sql-web
С хранением данных в браузере я плотно работал в 2014-2015 и вижу, что проще с тех пор не стало. И не факт, что ситуация улучшается. Например, история WebSQL началась примерно в 2009 году, решение было предложено простое ("прикрутим sqlite"), но, как видим, ничего простого в Вебе не бывает. Сначала долго выкатывали, потом долго закатывали. https://nolanlawson.com/2014/04/26/web-sql-database-in-memoriam/
На дворе, между тем, 2021.