Local-first и децентрализация – Telegram
Local-first и децентрализация
712 subscribers
140 photos
19 videos
3 files
312 links
Replicated Object Notation,
CRDT, распределёнщина и децентрализация.
Ведёт @gritzko
Чат @Ronzgovory
Download Telegram
# 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
Раскрашивание хекса - незаменимый трюк при отладке бинарных форматов и протоколов. Почерпнул когда-то у человека, который занимался реверсом. Мой случай проще - я могу сразу писать код сериализации так, чтобы он мог раскрасить всё, что сам же пишет.
Всего-то прошло 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. Ощущения как в шутере каком-то.
🔥2
# Хронофолд - годовасик

Народная мудрость: не обобщай, пока у тебя нет трёх похожих случаев. Хронофолд вырос из следующего наблюдения: у коллаборативных структур данных, систем контроля версий и обычных редакторных движков есть очень сильный оверлап.
Поэтому возникла мысль сделать структуру данных, пригодную для всех трёх случаев. Основным вдохновением послужили 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.

Так что пока думаю.
Некоторые считают, что египетские пирамиды построены из гигантских блоков, потому что египтянам помогали инопланетяне. Нет. Из гигантских блоков строили, потому что если строить из кирпича, египтяне всё быстро растащат. А так тащить неудобно, так что до сих пор стоит.
И относительно одних недавних дебатов про монорепо: да, принцип тот же. В большой компании должен быть гигантский монорепо с невероятным количеством перекрестных зависимостей. И софт должен быть такой глыбообразный, как браузер Хром.
По тем же самым абсолютно причинам.
👍1
Я много раз пел дифирамбы фаззингу, спою ещё раз. На экране - фаззер успешно атаковал хэш-таблицу через коллизии в (слабой) хэш-функции. Я вот сижу и пытаюсь понять, как он нашёл эту ситуацию. Работал полчаса, в 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.
🔥1
Сегодня прочитал замечательный текст про стариковское ворчание[1][4], и, по забавному совпадению, доклад Andy Pavlo про волну NewSQL баз данных[2]. Первое, вкратце: молодежь решает все те же проблемы заново с помощью все более высокоуровневой и дорогой технологии. Второе, вкратце: десятилетняя волна NewSQL стартапов сошла, ничего не прилипло, продолжаем использовать MySQL, PostgreSQL и все что на их основе.
Лично я отчетливо осознал этот эффект довольно давно, когда столкнулся с обидным фактом, что многие вещи на node.js делаются сложней, чем на C и bash (и сделал про это доклад на fronttalks [3]).

Теперь введем формальное определение, чтобы придать дискуссии строгость. Пердунотехнологией будем называть то, что прекрасно работало в 2000 году. Что входит в эту категорию? MySQL, PostgreSQL, SQLite и прочие Oracle. Из языков C, C++, Java, Erlang, Python. JavaScript номинально тоже уже был, но использовался для анимации менюшек; первое нашумевшее Ajax приложение это GMail в 2004. А хорошая VM появится в 2008 (v8). Так что js исключаем. HTTP, HTML, CSS - безусловно были.

И тут мы приходим не к самому приятному выводу: пердунотехнология продолжает прекрасно работать. Без докеров и кубернетисов. Не переписанная на Rust. Все Хромы и v8 написаны на пердуническом C++. Сеть продолжает работать с пердуническим HTTP поверх архипердунического TCP.

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

Когда я выбирал, на чем писать RON, разные были варианты, но C и C++ - единственные рабочие; да и преимуществ при работе с байтовыми потоками высокоуровневые языки не давали. А если подняться хотя бы до golang, то embedded library уже не сделать никак. Так что выбрал C++ и потом частенько подумывал, что C мог бы быть более подходящим вариантом.

P.S. в дальнейших дискуссиях предлагаю использовать термин "перунотехнология"

[1]: https://news.1rj.ru/str/reinforced_sc/53
[2]: https://assets.ctfassets.net/oxjq45e8ilak/5rdaQwruVOjycswCUhLORk/56f89872e742d28644472e1f3695b922/newsql2021.pdf
[3]: https://www.youtube.com/watch?v=jeg-RpXjdZ4
[4]: https://news.1rj.ru/str/nikitonsky_pub/171
# Оффтоп - про технику

Я приобрёл тут Legion 5 Pro с восьмиядерным AMD и очень результатом доволен. Первым делом разобрал, конечно. В детстве я тоже так часто делал, но с годами мастерство росло, так что в результате всё хорошо работает. Система теплоотвода - примерно как у грузовика, много металла. Три трубки и теплорассеивающие щитки на всех деталях. Вообще, устройство габаритное и по современным меркам тяжелое. Но мощное. Экран шикарный. Клавиатура на уровне ThinkPad!

Хочу сказать, что в номинации мощных ноутбуков это для меня огромный шаг вперёд, по сравнению с прежним ThinkPad P1, например. У того чуть что - процессор перегревался и уходил в троттл. Работа в CLion была тем ещё развлечением. И шаманства для настройки Linux нужно было невероятно много. Тут Ubuntu встал сразу, как родной (с Fedora пока всё сложно).

Но вот забавный парадокс: получается, что лучший ноутбук для работы - игровой ноутбук! Самая массовая категория пользователей, которым важна производительность - это игроманы. И с рабочими станциями похожая картина. Собирал два года назад, основной ассортимент деталей явно маркетят для геймеров. Большое им спасибо за то, что покупают всё за свой счёт, а не как корпораты. Там в результате имеем линейку очень дорогих профессиональных ноутбуков, которые профессионально выглядят и в стильную дорогую сумку хорошо помещаются, ибо тонкие.
# Тяжелый этап

В разработке я вижу четыре основных этапа - проектирование, кодирование, отладка, фаззинг. Проектирование - это этап радуг и единорогов, он эйфоричен и беспроблемен, если только вы нормальный человек. Именно поэтому, хороший проектировщик - зануда и даунер, ненормальный человек. Далее кодирование, где вылазят все нестыковки проектирования. Это тяжелый этап, но там есть свои депрессии и эйфории, такие крутые горки, так что несмотря на тяжесть, это может сильно затягивать. Потом самый тяжелый для меня этап - отладка. Все крутые идеи придуманы на проектировании, потом все интересные головоломки решены на кодировании, а теперь нужно, не выпуская всей картины из головы (неприятно), пройтись по всему коду и исправить все ляпы и нестыковки (тяжело). Работа настолько увлекательная, что для увиливания от нее я готов заняться готовкой, приборкой, мытьем унитазов и написанием постов в социальных медиа. Потом фаззинг, но фаззинг это как охота или игра, это круто и увлекательно.
Но что делать с отладкой?
Кстати, идея со скриптовым языком получила продолжение. Что-то между bash и Erlang, называется Ronish. Бюджет времени очень ограничен и во многом это способ прокрастринировать одну большую отладку. Я аргументировал, что если систему можно скриптовать и мучать в REPL, то и отладка заспорится. Единственная проблема - Ronish тоже надо отлаживать...
Кажется, к докладу придется готовиться