uz
Feedback
Типы и Архетипы

Типы и Архетипы

Kanalga Telegram’da o‘tish

Корректность типами, сложность архетипами Deep Tech | Архитектура | R&D Management

Ko'proq ko'rsatish
Mamlakat belgilanmaganToif belgilanmagan
317
Obunachilar
Ma'lumot yo'q24 soatlar
+77 kunlar
+2330 kunlar

Ma'lumot yuklanmoqda...

O'xshash kanallar
Ma'lumot yo'q
Muammo bormi? Iltimos, sahifani yangilang yoki bizning qo'llab-quvvatlash boshqaruvchimizga murojaat qiling>.
Taglar buluti
Ma'lumot yo'q
Muammo bormi? Iltimos, sahifani yangilang yoki bizning qo'llab-quvvatlash boshqaruvchimizga murojaat qiling>.
Kirish va chiqish esdaliklari
---
---
---
---
---
---
Obunachilarni jalb qilish
Iyun '26
Iyun '26
+8
0 kanalda
May '26
+36
0 kanalda
Get PRO
Aprel '26
+255
0 kanalda
Get PRO
Mart '260
2 kanalda
Get PRO
Fevral '26
+25
2 kanalda
Sana
Obunachilarni jalb qilish
Esdaliklar
Kanallar
12 Iyun+1
11 Iyun0
10 Iyun0
09 Iyun0
08 Iyun+2
07 Iyun+2
06 Iyun0
05 Iyun+2
04 Iyun+1
03 Iyun0
02 Iyun0
01 Iyun0
Kanal postlari
[мысли] reconciliation loop или один из лучших паттернов в инфраструктурных системах Как-то мне довелось писать reconcilation
[мысли] reconciliation loop или один из лучших паттернов в инфраструктурных системах Как-то мне довелось писать reconcilation loop для того, что управлять инфраструктурными системами и, мне кажется, что это идеальный паттерн в таких случаях, особенно если мы говорим про "production-grade" масштабируемые системы. Традиционная request-response модель тут работает достаточно плохо, потому что реальность не синхронная, например, узел может быть недоступен, агент может применить конфиг, но не успеть обновить статус, сеть может разделиться, процесс может умереть между "почти сделал" и "успел сохранить статус". Т.е. класс модели "request-response" имеет слишком бедную онтологию и не учитывает реальные проблемы и состояния системы, которая управляет инфраструктурой. Его применение в некоторых случаях, связанных с управлением инфраструктурой, может быть таким же архитектурным преступлением, как и CORBA https://t.me/types_and_archetypes/34. И вот в таких случаях reconciliation loop оказывается, на мой взгляд, одним из самых правильных. Его идея очень простая: у системы есть desired state - то, как мир должен выглядеть, и actual state - то, как он выглядит сейчас. Контроллер снова и снова смотрит на разницу между желаемым и фактическим состоянием и делает следующий шаг во внутренней стейт машине, пока система не сойдется. Именно в этом, как мне кажется, и состоит настоящая техническая сила Kubernetes, т.е. это не в YAML, не в контейнеры и даже не в оркестрации как таковой, а в том, что вся модель построена вокруг вот такой сходимости. Почему это так хорошо работает? Во-первых, reconciliation loop естественно переживает сбои. Если контроллер упал, ничего страшного: он поднимется, снова посмотрит на мир и продолжит. Если агент не ответил, задача просто осталась в состоянии, из которого можно продолжить. Если кто-то руками поменял конфигурацию на хосте, это а drift, который можно обнаружить и исправить. Во-вторых, этот паттерн очень хорошо сочетается с идемпотентностью. Повторный запуск движка сравнения не создаёт новый стейт или новые состояния, он должен доводить текущий стей до нужной формы. В-третьих, reconciliation loop отлично дисциплинирует архитектуру. Как только эта модель принимается всерьёз, то приходится уже чётко разделять: - что пользователь хочет - что контроллер уже увидел - что реально применено - что только запланировано - и что делать при удалении или откате Отсюда появляются очень понятные и правильные вещи: спецификации, статусы, генерации, инварианты, стейт машины и прочее-прочее. Это делает систему не только надежнее, но и гораздо понятнее в эксплуатации. В-четвёртых, такой паттерн даёт хорошее масштабирование и более строгие инварианты. Но у паттерна есть и минусы: Главный минус в том, что reconciliation loop сложнее, чем условный CRUD. Намного сильнее сложнее. Нужно думать о стейт машинах, о повторных попытках, о статусах и так далее. Второй минус - eventual consistency. Для инженера это нормально, а для пользователя или продакт-логики уже сложновато. Третий важный минус - его легко сделать декоративным. Очень многие системы копируют внешнюю форму кубера: ресурсы, статусы, контроллеры, но не забирают суть. Если в модели нет четкого desired state, нет наблюдаемого actual state, нет идемпотентных действий и нет повторяемого reconcile, то это не reconcilation loop-модель, а какой-то просто более запутанный бекенд. Итог Reconciliation loop особенно хорош там, где система управляет внешними, ненадежными, медленными или частично наблюдаемыми сущностями. Кластеры, виртуальные машины, сетевые туннели, DNS, сертификаты - его естественная среда. Этот паттерн позволяет точнее описать операционную реальность такой, какая она есть: с лагами, сбоями, гонками, повторными попытками и частичной наблюдаемостью. И вместо того чтобы бороться с этой реальностью или заметать её под порог, он делает все эти проблемы first-class citizens, заставляя работать и думать про них. Это и делает reconciliation loop по-настоящему сильным для инфраструктурных задач.

2
[вторник] Heartbeat failure detector Предыдущий вторник: https://t.me/types_and_archetypes/61 В прошлый мы говорили про детек
[вторник] Heartbeat failure detector Предыдущий вторник: https://t.me/types_and_archetypes/61 В прошлый мы говорили про детекторы Ω и Σ, а теперь давайте посмотрим на ещё один объект из failure detector theory: HB, или heartbeat failure detector. Он появляется у Aguilera, Chen и Toueg в статье "Heartbeat: A Timeout-Free Failure Detector for Quiescent Reliable Communication", а затем обобщается ими для partitionable networks и quiescent consensus. На практике heartbeat обычно означает простой цикл: ping, ожидание, таймаут или иногда suspect-list. Но в этой статье смысл почти противоположный (и тут инверсия, ага). HB выдаёт процессу вектор монотонных счётчиков: hb_p[q], heartbeat значение процесса q с точки зрения процесса p. Если q остаётся достижимым из p через т.н. fair path, этот счётчик может стать сколь угодно большим. Если же q выходит за компоненту достижимости p или падает, последовательность значений у p становится ограниченной. В partitionable networks это превращается в такую семантику: счётчик q у p растёт для процессов из partition(p) и стабилизируется для процессов вне этой partition. Грубо говоря, HB даёт информацию о том, где ещё наблюдается прогресс связи в системе. Зачем это вообще нужно? В статье основной объект quiescent reliable communication (что-то типа спокойных надёжных коммуникаций). Quiescent алгоритм после ограниченной активности приложения порождает только ограниченный хвост протокольных сообщений. Для одного RPC, одного броадкаста или одного раунда алгоритма это очень естественное требование: приложение сделало какую-то конечную работу, транспортный слой тоже должен прийти к покою через какое-то время. Но потеря связи создаёт именно такой конфликт. Ведь надёжная доставка через канал с потерями обычно достигается ретраями до ACK, при этом сам ACK сам идёт через канал с потерями. Получается потенциально неограниченный хвост служебного трафика ради одного сообщения, в терминах статьи это ровно место, где failure detector становится способом отделить активность приложения от активности системного сервиса. Статья предлагает решить это вопрос через дополнительный слой, который может жить постоянно и рассылать heartbeats, а конкретный алгоритм надёжной передачи использует рост счётчика как триггер повторной отправки. Например, p хочет доставить m процессу q. p отправляет m каждый раз, когда hb_p[q] увеличивается и завершает локальную пересылку после ACK от q. Если q корректен и достижим, его heartbeat у p растёт бесконечно, значит попытки доставки будут возникать снова и снова, а fair path в итоге пропустит m и ACK. Если q выпал из достижимой компоненты, рост счётчика у p ограничен, значит ретраи конечны. HB в partitionable networks по сути кодирует сильно связную компоненту процесса в графе корректных процессов и fair links, но делает это не через явный список вершин, а через монотонные счётчики, где неограниченный рост означает принадлежность той же партиции. В обычных системах heartbeat часто используется как часть знания о недоступности, а в теории HB он становится частью знания о доступности. Это различие особенно важно для partitionable networks: падение процесса и потеря достижимости - разные события с разными последствиями для алгоритма. Мне нравится думать об этом, как о третьей минимальной асимметрии в этой серии: Ω - асимметрия координатора: в пределе все смотрят на одного лидера Σ - асимметрия власти: достаточные множества обязаны пересекаться HB - асимметрия прогресса: рост счётчика задаёт достижимую связь между участниками Итог Failure detector theory интересна тем, что она декомпозирует "надёжность" на минимальные виды информации, которые необходимы системе для работы. И если Ω отвечает на вопрос "кто ведёт?", а Σ "какая коалиция имеет право зафиксировать состояние?", то HB отвечает на вопрос "где коммуникация ещё производит наблюдаемый прогресс?". Т.е. вместо того, чтобы как-то полагаться на ненадёжную информацию о том, что пир недоступен, мы полагаемся на надёжную информацию о том, что он доступен. И это красивая и простая инверсия.
287
3
[мысли] как узнать сильную книгу по криптографии Когда-то во время учёбы в универе я сталкивался с большим количеством книг по криптографии, которые были написаны инженерами или программистами, но не математиками или "настоящими" криптографами. Часто такие книги дают только рецепты вида "делай раз-два-три и получишь подпись", не облажайся с ключами вот тут и тут. И они дают только два варианта работы с ними: как с RFC или просто выучить это просто наизусть. Я бы даже предложил простой вероятностный тест на такую книгу: если в книге в описании протокола в какой-то момент написано возьмём "большое простое число", то она почти наверное не стоит своих денег. Большое простое число - это не понятный и не специфицированный объект. Оно большое как? Если записать в двоичном виде или может на клингонском? В каком кольце? В этом примере хочется сразу понять: почему оно должно быть простым, какая структура появляется, какие операции становятся обратимыми, какая задача становится трудной. А вот с определением эллиптических кривых чуть сложнее, когда автор определяет кривую сразу через короткую форму Вейрштрасса (а так делают почти все книги по криптографии, которые я видел, часто даже не говоря про характеристику поля и прочее), то это, конечно, не точно, но смириться с этим можно. Иначе нужно слишком много знать, чтобы понять "настоящее" определение. А вот в хороших книгах, на мой взгляд, изложение может быть примерно таким: какая-то математическая структура рождает трудную задачу, трудная задача входит в модель атаки, модель атаки связывается с доказательством, доказательство держит протокол и только в конце протокол уже становится инженерией. И сильная книга, имхо, учит видеть инварианты: что скрывается, что связывается, что проверяется, где живут гарантии и чем они обеспечиваются. Такие книги можно понять и не нужно заучивать. После них алгоритмы выглядят уже не просто последовательностью действий, а следствием математических законов и аксиом.
298
4
[мысли] Вайбкодинг как взятие технического долга Сейчас в твиттерах стало модно писать, что код превратился в commodity и поч
[мысли] Вайбкодинг как взятие технического долга Сейчас в твиттерах стало модно писать, что код превратился в commodity и почти ничего не стоит. Мне кажется, это одновременно и так, и не так. Если под кодом понимать первичную текстовую реализацию, то да, её стоимость сократилась до стоимости потраченных токенов и доступа к контексту, в котором этот код генерируется. LLM умеют очень дёшево производить текст, похожий на код. Но если под кодом понимать надёжный, понятный, сопровождаемый и проверенный артефакт, то он дешевле не стал. То есть commodity стала не программа как таковая, а скорее заготовка под программу. Из-за этого, кажется, важнее стало различать не просто "код" и "не код", а хотя бы такие вещи: навайбкоженный код и ненавайбкоженный, проаудированный и непроаудированный, локальный и уже где-то поживший, код как черновик и код как часть долговременной семантики системы. Мне кажется, что в будущем появится экономика внимания. Ценность кода будет определяться не только тем, сколько усилий ушло на его написание, но и тем, сколько качественного внимания в него уже конденсировано. Кто-то его долго думал, кто-то читал, кто-то ронял в проде, кто-то чинил крайние случаи, кто-то проверял инварианты, кто-то проводил аудит. В этом смысле хороший код чем-то похож на криптографический примитив, он становится надёжнее не потому, что его быстро однажды написали, а потому что на него долго и качественно смотрели. А LLM радикально меняет именно это соотношение. Она позволяет очень дёшево получить код, на который ещё не было потрачено соответствующее количество человеческого внимания. И в этом смысле использование LLM очень часто является взятием технического долга. Красивый и опасный момент здесь в том, что раньше такой долг обычно брался через отказ от работы: не успели отрефакторить, не дописали тесты, отложили спецификацию, "потом разберёмся". С LLM происходит та самая инверсия, теперь технический долг можно брать через производство работы. Возникают модули, адаптеры, тесты, миграции, обвязки, куски бизнес-логики. Внешне это выглядит как прогресс, но очень часто это только материализация будущих обязательств: понять, что именно здесь имеется в виду, проверить корректность, выровнять стиль и инварианты, научиться безопасно это менять через полгода. То есть LLM делает технический долг ликвидным. Она позволяет выпустить сейчас объём реализации, который потом придётся выкупать пониманием, аудитом и сопровождением. Но тут важно не впасть и в другую крайность. LLM - это не всегда долг, мне кажется, тут есть как минимум три разных режима. Первый - собственно технический долг. Это случай, когда код попадает в долговременный контур, а понимание и верификация откладываются на потом. Второй - покупка опциона. Это прототипы, одноразовый glue code, черновые интеграции и внутренние утилиты. Здесь систему не столько строится, сколько покупается право быстро проверять гипотезы. Такой код может вообще никогда не стать частью "настоящего" софта, и тогда долг либо не возникнет, либо окажется дешёвым. Третий - усиление уже существующего мышления. Когда LLM используется не как автономный автор, а как очень умный grep`/`awk`/`sed с семантическим анализом: найти место, показать зависимость, проложить путь по call graph, предложить аккуратный рефакторинг. Здесь она может не увеличивать долг, а наоборот уменьшать его, потому что ускоряет понимание (rank drop). Поэтому главный вопрос сейчас, имхо, заменяла ли LLM понимание или усиливала его. Если заменяла, то почти наверняка растёт долг. Если усиливала, то нередко наоборот. Поэтому, имхо, код не стал commodity в сильном смысле, commodity стала его первичная генерация. А вот внимание, аудит, переиспользование и доверие к коду стали ещё более дефицитными и потому ещё более ценными. В этом смысле будущее, возможно, вообще не про экономику кода, а про экономику внимания к коду. И тогда один из главных навыков инженера - это умение отличать три вещи: где LLM помогает взять оправданный долг, где она помогает купить опцион на скорость, а где её надо использовать только как рычаг на понимание.
477
5
[рамка] Оркестрация и хореография: кому принадлежит continuation На мой взгляд, если говорить очень грубо, то задача архитект
[рамка] Оркестрация и хореография: кому принадлежит continuation На мой взгляд, если говорить очень грубо, то задача архитектора при проектировании заключается в том, чтобы понять, среди чего выбирать и, собственно, сделать сам выбор. Для первого как раз важна насмотренность (а для чего она не важна:)) и фундаментальные знания. И некоторые понятия, например, continuation и его принадлежность, являются как-будто не совсем очевидными предметами для выбора. Но при этом это понятие и свойство есть в любой системе, в которое есть понятие вызова или похожее на него и, соответственно, есть какая-то сущность, которую можно вызвать. Например, оно есть у любой распределённой системы: после того как некоторый участник сделал свой шаг, кто конкретно определяет следующий шаг системы? Имхо, именно здесь и проходит граница между оркестрацией и хореографией: - если continuation протокола принадлежит выделенной сущности, это оркестрация - если выделенной сущности нет, а continuation передаётся между самими участниками, это хореография Тут мне стоит сразу сказать, что это вроде бы не распространённый способ различения этих понятий, а только моя рамка мышления о них. Из-за названия "хореография" часто возникает ложная ассоциация, будто речь идёт о жёстко прописанном сценарии, а оркестрация и хореография различаются по степени свободы или импровизации. Это не так. Здесь важно не смешивать три разных вопроса: 1. Кто принимает решение о следующем шаге? Это и есть оркестрация vs хореография. 2. Как вычисляется следующий шаг? Это уже другая ось: простой if, таблица переходов, rules engine, DSL, полноценная вычислимая логика. 3. В каком контексте принимается решение? Какие есть инварианты, общие правила, таймауты, политики, ограничения протокола. То есть, оркестрация может быть как полностью детерминированной, так и сильно динамической. Хореография тоже может быть как строго ограниченной протоколом, так и весьма гибкой. Как-то мы сравнивали это с брейк-данс батлом. Есть общий бит, есть круг, есть правила игры, а тот, кто сейчас в круге, на основании текущего состояния танца фактически влияет на то, кто и как пойдёт дальше. Владение кругом в текущий момент - это и есть владение continuation. Сам танец - локальное вычисление агента. Оценка предыдущего шага и выбор следующего участника - логика маршрутизации. А общий бит и формат батла - это базовый протокол, который не даёт всей системе распасться в шум. С джазом ещё интереснее. Тут тоже важны эти три вопроса: - кто принимает решение - нет единого дирижёра, control распределён - как принимается решение - через импровизацию, перехват соло, локальную реакцию - в каком контексте - в рамках общего ритма, тональности, паттерна, то есть некоторого общего протокола С точки зрения control plane это можно сформулировать это так: оркестрация - centralized control plane хореография - distributed control plane На практике чистые формы встречаются редко. Реальные системы обычно гибридны. У них есть общий слой правил игры, например, контракт протокола, политика маршрутизации, согласованные таймауты, механизм выбора лидера или другой источник асимметрии - а поверх него уже могут существовать и оркестрационные, и хореографические участки. Это важно, потому что хореография не означает анархию. Чтобы распределённая система вообще делала прогресс, ей обычно нужен некоторый общий контекст и хотя бы минимальная асимметрия. Итог В оркестрации continuation принадлежит выделенному координатору. В хореографии continuation не имеет одного владельца и передаётся между участниками по правилам системы. А значит, различие между ними - это по сути различие между двумя способами организации control plane: централизованным и распределённым.
340
6
[кейс] ROP-программирование как IoC В прошлом посте continuation выглядела достаточно абстрактно, как ответ на вопрос что дел
[кейс] ROP-программирование как IoC В прошлом посте continuation выглядела достаточно абстрактно, как ответ на вопрос что делать дальше после текущего вычисления. В этом посте давайте рассмотрим сразу две вещи: почему владелец continuation важен, а также на ещё один пример IoC в виде ROP-программирования. В обычном стековом вызове одной из низкоуровневых материализаций continuation является адрес возврата. Думаю, что почти всем читателям этого блога известен самый простой класс бинарных уязвимостей - переполнение буфера в стеке. Обычно он возникает в ситуации, когда атакующий переполняет расположенный на стеке буфер, изменяя при этом адрес возврата. В простейших случаях (если на дворе были бы 2000-е) атакующий изменяет адрес возврата на шеллкод (то, что атакующий хочет исполнить), расположенный также на стеке. И после окончания выполнения функции ret берёт со стека текущее значение и интерпретирует его как continuation, передавая на него управление. Существует много так называемых exploit mitigations, способов защиты от эксплуатации, для данного класса уязвимостей. Одним из самых первых был способ, основанный на том, чтобы сделать страницы памяти в стеке неисполнямыми. Это достаточно элегантное решение, потому что оно препятствует исполнению шеллкода на стеке и при этом не нарушает работу почти всех легитимных программ. Первым методом обхода такой защиты являлся так называемый return-to-library, методика, в которой атакующий изменяет адрес возврата не на адрес шеллкода в стеке, а на адрес какой-то функции внутри, например, libc. Страницы памяти библиотек помечены флагом x и r и, соответственно, передача управления приведёт к нормальному исполнению этой вызванной функции. В качестве такой функции часто используют функцию system, принимающую аргументом строку команды, которая будет исполнена. Более общим и, на мой взгляд, реально красивым методом является так называемое ROP-программирование. Его идея заключается в том, чтобы рассматривать небольшие фрагменты функций в уже загруженных в процесс исполняемых файлах, оканчивающиеся инструкцией ret, как гаджеты. Каждый такой гаджет делает обычно что-то небольшое, например, перекладывает значение между регистрами, загружает что-то со стека и так далее. Примером гаджетов, например, являются xor eax, eax; ret или pop eax; ret. Одно из ключевое тут - инструкция ret, потому что она берёт адрес с текущего rsp и интерпретирует его как continuation. За счёт чего каждый гаджет вызывает следующий. В такой модели атакующий заранее преобразует свой шеллкод в такую ROP-цепочку, которая состоит из адресов гаджетов в библиотеках. Достаточно богатый набор таких гаджетов позволяет выражать Тьюринг-полную логику без инъекции нового кода. Существуют даже специальные ROP-компиляторы, которые позволяют как раз выразить делаемые действия через последовательность ROP-гаджетов. И вот тут стек, по сути, становится внешней программой управления. То, что в обычном исполненнии было скрытым control plane рантайма, становится управляемым атакующим сценарием дальнейших переходов. В обычном исполнении ret означает "вернись туда, откуда тебя позвал вызывающий код при обычном исполнении", а в ROP означает "возьми следующий шаг исполнения, контролируемого атакующим". Инструкции при этом по-прежнему легитимны, но композиция их уже нет. Именно поэтому удобно думать про ROP как про форму hostile IoC. В нормальной программе текущий код и так не полностью владеет своим будущим: следующее continuation управляется соглашением вызова, стековой дисциплиной, ABI и рантаймом. Т.е. control и без того частично инвертирован, а ROP захватывает эту логику, подменяя поставщика continuation. Там, где раньше слоем управления выступали рантайм и соглашения о вызове, теперь управлением владеет атакущий стек. Итог ROP - наглядный пример того, что control - это отдельный ресурс, который в данном случае выражен во владении continuation. Более явно мы это обсудим в следующем посте, посвящённом отличиям оркестрации от хореографии.
251
7
[рамка] call/cc: проявленный continuation Продолжая тему IoC, хочется сделать её дальнейшее рассмотрение более формальным. Дл
[рамка] call/cc: проявленный continuation Продолжая тему IoC, хочется сделать её дальнейшее рассмотрение более формальным. Для этого давайте поговорим про то, что называется continuation. Вообще у любого формализованного вычисления, как части общего вычисления, есть обычно скрытый параметр: а что делать дальше после того, как оно завершилось. Это как раз упомянутый выше continuation или продолжение вычисления или "остаток" общего вычисления, который ждёт текущий результат. Пусть у нас есть выражение, записанное в такой нотации: (+ 1 (f x)) f в нём всегда вызывается в конкретном контексте, ведь её результат потом будет применён в (+ 1 []). Вот эта "дырка" в, по сути, будущем и есть continuation. В наиболее распространённых парадигмах программирования она скрыта в стеке и способе организации вызовов, и мы почти никогда явно о ней не думаем. И если мы захотим проявить этот continuation, то получим то, что иногда называется call/cc, call with current continuation. Оператор берёт текущее продолжение и передаёт его программе как обычное значение, чаще всего как функцию, делая его first-class citizen. Простейший пример: (+ 1 (call/cc (lambda (с) (c 41)))) В точке вызова call/cc текущий continuation примерно такой: возьми значение v и вычисли (+ 1 v). При выполнении (c 41) мы не продолжаем выполнение тела lambda. Наоборот, текущее продолжение отбрасывается, и управление переносится в сохранённый контекст вызова call/cc. Поэтому 41 подставляется на место всего (call/cc ...), и выражение сводится к (+ 1 41), то есть к 42. В языке с call/cc функция больше не обязана нормально возвращаться своему вызывающему, вместо этого она может: не вернуться вовсе, вернуться не туда, вернуться позже, а в Scheme - даже использовать одно и то же продолжение многократно. То есть стек становится чем-то вроде программируемого графа переходов. В онтологии этого блога: стек - это скрытый control plane программы, а call/cc делает его явным. Поэтому, имхо, call/cc не просто экзотическая фича из Scheme, а очень глубокая идея управления вычислениями. С call/cc программа получает доступ не только к данным, но и к собственному будущему, control становится data. Многие из этих механизмов можно понимать как частные или дисциплинированные формы работы с continuations, в современных языках их часто удобнее моделировать через delimited continuations или effect handlers, а не через полный call/cc. Есть ещё одна красивая перспектива - это CPS. В continuation-passing style каждая функция и так уже получает continuation явно. Если в обычном варианте у нас функция выглядит как f : A -> B, то в CPS f: A -> (B -> R) -> R, где A - вход функции B - результат, который в direct style был бы просто возвращён R - финальный результат всей оставшейся программы (B -> R) - continuation, т.е. что делть дальше с результатом типа B Итог В обычном ЯП continuation обычно скрыт. В CPS continuation вынесена в сигнатуру. В call/cc continuation легализована языком.
0
8
[кейс] SpacetimeDB как IoC бэкенда В посте https://t.me/types_and_archetypes/52 я писал про "природные" проявления инверсии к
[кейс] SpacetimeDB как IoC бэкенда В посте https://t.me/types_and_archetypes/52 я писал про "природные" проявления инверсии контроля. Перед чтением этого поста рекомендую посмотреть визуально на пример озера - острова. SpacetimeDB - очень интересный пример IoC, обычно эта база данных позиционируется как database + server in one. Но, по сути, это инверсия контроля на уровне всего бэкенда. В обычном стеке приложение владеет жизненным циклом данных (вода вокруг острова). Оно читает базу, держит кэш, запускает API слой, отдельно тащит realtime синхронизацию, но SpacetimeDB сама база становится runtime для логики и синхронизации (теперь приложение становится озером, окружённом сушей). Архитектурная инверсия выглядит примерно так: база экспортирует таблицы и reducers, модуль с бизнес логикой живет внутри хоста, а клиент подключается через SDK, вызывает серверные функции и получает реалтайм обновления состояния. Клиентские чтения идут из локального cache, который контролируется с помощью механизма подписок, а изменения состояния проходят через reducer вызовы и фиксируются транзакционно. Т.е. в классической схеме код приложения дергает базу и сам решает, когда слать данные клиентам, а в SpacetimeDB код скорее описывает допустимые переходы состояния, а платформа сама решает, когда открыть транзакцию, когда закоммитить результат, как сохранить состояние и какие строки отправить в подписки. По сути, control flow тут переместился из уровня приложения внутрь рантайма базы данных. Data plane тут, по сути, это таблицы и зеркалируемые строки у клиента. Control plane тут host, транзакционный runtime, reducer entrypoints, identity контекст вызова и движок подписок. Именно там находится контроль над исполнением. Есть еще один важный разворот Клиент мыслится уже как локальная реплика интересующего среза данных, подписка говорит серверу, какой кусок состояния нужен клиенту, сервер присылает начальный набор строк и дальше пушит обновления. Получается формула read = local replica, write = reducer. Для игр, чатов и коллаборативного софта это очень сильный сдвиг модели. Reducer в SpacetimeDB это основной путь мутации таблиц. Он выполняется внутри атомарной транзакции и при ошибке откатывает изменения целиком. Процедуры существуют как более широкий метод взаимодействия с внешним миром, включая HTTP наружу, но там транзакционность уже ручная и сами разработчики рекомендуют оставлять обычные операции изменения состояния на reducers. SpacetimeDB - это другой класс решений по сравнению с ORM и BaaS. База забирает к себе серверную логику, транзакции, правила доступа и realtime раздачу состояния. И красота такого подхода в резком уменьшении числа границ. Цена решения, имхо, в такой же резкой онтологической гравитации (https://t.me/types_and_archetypes/15). Приложение начинает думать в терминах таблиц, reducer, подписок и хоста. То есть платформа убирает огромный объем механики, а взамен задает форму мира и будет являться невороятно жёстким lock-in для всей архитектуры. Тип тут довольно красивый. Если база пассивна, архитектура тянется к слоистому серверу. Если база владеет исполнением, архитектура тянется к state machine с зеркалируемыми клиентскими репликами. Инверсия тут применяется в самом дорогом месте современного бэкенда, в точке, где сходятся слой хранения, бизнес логика и синхронизации.
0
9
В эту пятницу в 18:30 буду рассказывать про свои результаты в том, что я называю "алгебраической теории координации". В частности, расскажу про как обеспечичить гарантии сходимости (convergence) и strong eventually consistency в распределённых системах. https://t.me/c/1970172456/373 Аннотация: Conflict-free Replicated Data Types (CRDT) гарантируют схождение данных без консенсуса, опираясь, в основном, на коммутативность операций слияния. Однако на практике мы часто имеем дело с так называемой наблюдаемой некоммутативностью (NC): это двойные траты UTXO, конкурентные перемещения узлов в деревьях, пересекающиеся права доступа или протоколы MPC. В таких случаях порядок применения операций напрямую определяет финальный результат, но система всё равно должна быть сходимой. В этом докладе мы разберём следующий результат: в присутствии NC гарантии схождения, независимости выполнения и строгой точности спецификации являются недостижимыми одновременно. Чтобы обойти это фундаментальное ограничение, архитектура распределенной системы вынуждена пойти ровно по одному из трех путей: - Commutativize: пожертвовать точностью спецификации, убрав порядок через факторизацию наблюдений (как это делает LWW-регистр, стирая реальную историю событий) - Causalize: отказаться от асинхронной независимости операций, введя строгие зависимости и построив причинно-следственный DAG, увеличивая объем метаданных - Reject: сузить пространство допустимых состояний, генерируя верифицируемые сертификаты конфликтов (например, для double-spend) и делегируя разрешение на уровень приложения
0
10
(быстрые мысли) Возможно, человечество столкнулось с самым лучшим маркетингом современности, основанном на массовой продаже с
(быстрые мысли) Возможно, человечество столкнулось с самым лучшим маркетингом современности, основанном на массовой продаже страха. А всё такое на первом уровне пирамиды Маслоу, как мы увидели, отлично работает. Представляете, ребята просто берут и выпускают списки профессий с вероятностями их исчезновения, которые превышают 90% и все начинают обсуждать в духе "ну да, теперь математики и инженеры больше не нужны". Это просто недостижимый уровень маркетинга, имхо.
0
11
Kelp, LayerZero и ещё одно подтверждение закона Конвея для рисков Когда-то я писал, почему 50 серверов - это не всегда децент
Kelp, LayerZero и ещё одно подтверждение закона Конвея для рисков Когда-то я писал, почему 50 серверов - это не всегда децентрализация: https://t.me/types_and_archetypes/6 История с Kelp, если опираться на их публичное описание инцидента вот тут https://x.com/KelpDAO/status/2046332070277091807, почти каноническое подтверждение этого тезиса. По версии Kelp, в атаке были скомпрометированы два RPC-узла, размещённые LayerZero, а по третьему прошёл DDoS. Этого оказалось достаточно, чтобы через forged cross-chain message вывести rsETH из бридж-адаптера. При этом важно отметить и другое: судя по их описанию, команда Kelp быстро среагировала, поставила контракты на паузу, заблокировала связанные с атакующим адреса и тем самым смогла остановить ещё одну попытку атаки на дополнительные 40 000 rsETH (~$95 млн). И главный урок - в архитектуре доверия. На схеме у нас могут быть несколько узлов, несколько эндпоинтов и даже "децентрализованная" инфраструктура. Но если эти компоненты размещаются, конфигурируются и операционно контролируются внутри одного административного домена, то это не настоящая децентрализация. Это только один логический узел, размноженный на несколько адресов. И ещё показателен момент с 1-of-1 DVN. По словам Kelp, именно такая конфигурация была задокументирована в LayerZero как default для новых OFT-деплоев и отдельно подтверждалась как допустимая при L2-экспансии. И это очень важный архитектурный вывод: default-настройка - это уже зашитая модель доверия и риска! Если default фактически означает, что система опирается на один верификационный домен, то скрытая централизация уже встроена в дизайн. То же самое работает, например, для default фич в проектах на расте - очень малый процент пользователей будет действительно разбираться, а что там вообще настраивается и на что настройки влияют. Вспомните, что мы делаем с инструкцией к телевизору, пока он работает. Поэтому при архитектурировании и аудите таких систем нужно задавать примерно такие вопросы: Сколько у нас реально независимых административных доменов? Кто владеет узлами? Кто держит ключи? Кто выкатывает конфигурацию? Кто подтверждает изменения? И переживёт ли система компрометацию одного оператора без каскадного отказа всего остального? Иначе это не уже децентрализация, а скорее репликация одного и того же доверительного допущения.
0
12
LLM для поиска семантически близких функций в бинарном коде И также хочу рассказать о второй работе, которая была представлен
LLM для поиска семантически близких функций в бинарном коде И также хочу рассказать о второй работе, которая была представлена Кучериным Георгием на той же конференции. Она касается поиска семантических близких функций в бинарном коде с помощью LLM. Это важная и совсем не тривиальная задача, потому что, например, один и тот же исходный код, собранный разными компиляторами или даже одним компилятором с разными флагами, может порождать заметно различающийся бинарный код. При этом в бинаре исчезают имена, типы, структура программы, а декомпилятор строит одну из возможных высокоуровневых интерпретаций. Поэтому прямое сравнение машинных инструкций, графов потока управления или даже декомпилированного псевдокода само по себе не даёт устойчивого критерия семантической близости. У нас на кафедре уже было опробовано несколько подходов к этой задаче. Например, перед этим в до-llm эпоху использовался подход, основанный на работе inst2vec и подход, основанный на Value Set Analysis. И вот в 2025–2026 годах начали появляться работы, где для для этой задачи используют llm. И тут стоит сказать, что эта задача поиска является NP-полной, а llm тут стоит рассматривать как эвристический решатель таких NP-полных задач, который или может с какой-то вероятностью решить её, или дать адекватное приближенное к правильному результату решение. Но если сравнивать каждую пару функций просто напрямую, то это становится слишком дорого и долго. Поэтому ключевая техническая идея и инновация работы состоит в том, чтобы не подавать модели полный декомпилированный код и не сравнивать функции как текст вообще, а сначала переводить каждую функцию в набор компактных DSL-представлений, отражающих разные аспекты её поведения. Т.е. получить то, что было нами названо многовидовой DSL-абстракцией. В работе для каждой декомпилированной функции строятся пять DSL-описаний: - поток данных - поток управления - вызовы вспомогательных функций - константы, используемые в битовых операциях - строки, встречающиеся внутри функции То есть вместо одного полного представления функции, мы получаем несколько "проекций" на разные семантические оси, которые подчёркивают какие-то аспекты. В текущей версии были выбраны вот эти 5 DSL, но их список может быть любым. Теперь к самому предлагаемому алгоритму: 1. Каждое непустое DSL-представление переводится в эмбеддинг. После этого для пары функций f и g вычисляется агрегированная векторная похожесть: - по каждому виду DSL считается косинусная близость - затем эти близости усредняются с весами - пустые представления аккуратно исключаются из оценки Получается быстрая метрика S_vecsim (f,g), которая позволяет для функции f взять только top-k кандидатов 2. Затем llm используется как локальный модуль переранжирования. Для некоторого числа отобранных кандидатов вычисляется дополнительная функция близости J(f,g), а затем финальный score задаётся как S_final(f,g)=(1−λ)*S_vecsim(f,g) + λ*J(f,g). 3. Дополнительно ещё можно использовать адаптивное отсечение кандидатов: если лучший кандидат по быстрой метрике S_vecsim оторвался от следующего кандидата достаточно сильно, то llm вообще можно не вызывать: уже гарантируется, что он останется лучшим и по финальной метрике. Более того, можно не фиксировать k заранее, а выбирать минимальную длину префикса ранжированного списка, достаточную для того, чтобы не потерять точный максимум по S_final. Практический смысл Также мне кажется, что похожий подход можно использоваться и для разработки и написания кода и архитектуры вместо вайбкодинга. В первом приближении он мог выглядеть примерно вот так: естественный язык -> вероятностный аппроксиматор (LLM) -> context-specific DSL/IR -> (детерминированно) код на языке высокого уровня Но тут очень много нюансов с потерей связи разработчика с кодом и необходимостью мелких итераций, чтобы успевать "проживать" проект и понимать, что там вообще происходит. Но как-будто большую часть распределённых систем (а это почти все важные) можно описать алгебраически и на основе этого сделать алгебро-типизированный слой DSL/IR.
0
13
PhantomHash: специализированная zkVM для zk-пруфов SHA-256 На прошлой неделе была конференция "Ломоносовские чтения-2026" (ht
PhantomHash: специализированная zkVM для zk-пруфов SHA-256 На прошлой неделе была конференция "Ломоносовские чтения-2026" (https://cs.msu.ru/news/4390), где Артём Николайчук, студент магистратуры, научным руководителем которого я являюсь, представил нашу работу по оптимизации размера и скорости доказательства sha-256 в STARK-подобных сценариях. По сути, это так называемая специализированная zkVM, оптимизированная только для доказательства работы sha-256 хэш функции. В рассматриваемом в работе сетапе она была оптимизирована в первую очередь по размеру доказательства, хотя эта схема может быть использована и для оптимизации по времени работы (latency/throughput). Sha-256 не является zk-friendly для реализации, потому что её алгоритм определён через 32-битные побитовые операции (XOR, AND, ROTR, SHR и сложение по модулю), а для STARK-систем такие операции являются ненативными и очень дорогими, потому что значение сначала нужно преобразовывать в бинарный вид и попутно доказывать, что это преобразование является верным. Потом делать саму побитовую операцию, а дальше преобразовывать результат обратно. В предлагаемой zkVM ключевым атомарным объектом является байт, что само по себе достаточно необычно по дизайну. Из-за чего каждое 32-битное слово кодируется четырьмя байтами как элементами нашего внутреннего поля Fp, а не тридцатью двумя битами. Основная побитовая логика затем реализуется в фиксированных lookup-таблицах (смотрите картинку): - для XOR и AND используется объединённая таблица BITOP8 - для побайтовых сдвигов и вращений используется таблица SHRPAIR, которая по паре соседних байтов восстанавливает выходной байт после сдвига на заданное число бит 4 столпа архитектурной оптимизации - форма функции Majority через Maj(a,b,c)=(a∧b)⊕(c∧(a⊕b)) Она требует всего двух AND-lookup на байт вместо стандартных трёх и даёт экономию 256 AND8-событий на один блок сжатия. - fan-out-safe access bus: для расписания сообщения W[t] слово записывается один раз, но затем многократно читается и в расписании, и в раундах сжатия, для этого строятся два списка обращений (L1 и L2), а корректность связывания доказывается через permutation/grand-product аргумент в стиле Cairo memory model. - формальная схема byte coverage: позволяет полностью отказаться от отдельного глобального lookup на таблицу U8 (проверка диапазона 0..255). - унификация lookup-архитектуры: таблицы спроектированы так, чтобы уменьшить число interaction arguments и тем самым напрямую снизить размер конечного доказательства. Отмечу ещё два момента: - арифметизация сложения по модулю 2^32: она реализована через байтовые гаджеты ADDk с явными переносами между байтами. В сбалансированном профиле мы используем "склеенные" суммы ADD6/ADD7, что позволяет не материализовывать лишние промежуточные слова (например, T1 и T2) и не делать дополнительные проверки диапазона. - теорема об исключении глобального U8: если байтовая переменная уже участвует в BITOP8 или SHRPAIR, то она неявно сертифицируется как элемент множества {0,…,255}. Для оставшихся "сиротских" столбцов добавляются лишь редкие dummy-checks. В самой работе мы доказываем теорему, что проверку байтовости - это структурное следствие архитектуры трассы. Итоговые параметры и бенчмарки Описанный подход приводит к следующим параметрам на блок: - 137 столбцов в исполнительной таблице - 257 переходных ограничений (включая ограничения шины) - 164 граничных утверждения Для размера входа в 2^20 байт сериализованный размер пруфа составляет 122.5 KB. В качестве ориентиров при том же числе security bits: Winterfell (наша реализация): 152.8 KB Binius: 404 KB Заключение Насколько мне известно, это одна из немногих специализированных zkVM, мне кажется, что в будущем их будет становиться всё больше и больше. Надеюсь, работа по созданию алгебраической основы для этого будет продолжена в аспирантуре. При этом получившийся размер в текущей схеме можно ещё сократить на ~30%, но это в следующих сериях. P.S. Если кому-то будут интересны подробности, могу скинуть пейпер и презентацию в комментариях.
0
14
KAN как IoC Давайте вернёмся к идее инверсии контроля, хочу рассказать ещё про несколько интересных примеров IoC in the wild.
KAN как IoC Давайте вернёмся к идее инверсии контроля, хочу рассказать ещё про несколько интересных примеров IoC in the wild. Неделю назад рассказывал другу про IoC и почему это важно для CS и его первой реакций было, что сети Колмогорова-Арнольда - отличный пример такой инверсии. И, действительно, давайте посмотрим на них под таким углом. В классическом MLP слой нейросети в первом приближении выглядит примерно вот так y = \sigma (\sum wx + b). В этой формуле ребро тупое и "умеет" только умножать сигнал на число, а вся выразительная сила сконцентрирована в вершине: нейрон сначала собирает все входы в одну сумму, а потом общей нелинейностью решает, как искривить пространство признаков. В онтологии моего блога ребро - data plane, который только выполняет работу по переносу и масштабированию результата вершина - control plane, который решает, а как именно искривить сигнал MLP сначала смешивает каналы, а потом делает нелинейное решение уже над агрегатом, т.е. различие между отдельными вкладами стирается рано уже на уровне суммы. При этом существуют разные фишки: learnable activations, gated MLP, spline-активации, PReLU, - но с ними мы только делаем уровень активации умнее, но не меняем место принятия решения, структура зависимости сохраняется: сначала merge, а потом nonlinear decision. А вот в KAN происходит как раз настоящая инверсия, в грубом виде там вычисление выглядит так y = \sum f(x), где f - это обучаемая одномерная функция на ребре (а не вес, как в MLP). Т.е. вместо веса на ребре находится параметризованная кривая (например, B-сплайн), и градиентный спуск оптимизирует её контрольные точки. В KAN нелинейность больше не сконценрирована в вершине, а распределяется по рёбрам, т.е. рёбра становятся умными, а вершины глупыми. С инженерной точки зрения теорема Колмогорова-Арнольда может звучать так: сложное многомерное поведение можно конструировать из суперпозиции более простых одномерных преобразований и сумм. Т.е. вместо mix -> bend в MLP, мы делаем bend per channel -> mix в KAN. Вот тут как раз меняется носитель связности (ну или геометрия модели), о чём я говорил в посте https://t.me/types_and_archetypes/52. Но у любой инверсии есть цена Умножение на скаляр - почти идеальная операция для современного железа. Матрицы прекрасно ложатся на GPU и на весь стек оптимизаций, который человечество десятилетиями строило вокруг них. Набор маленьких функций на каждом ребре - гораздо менее удобный объект, мы получаем лучшую локализацию геометрии, но платим сложностью ядра, векторизацией и памятью. Тип определяет архетип Если параметр на ребре - просто число, архитектура естественно тянется к централизованной нелинейности в узлах. Если параметр на ребре - функция, архитектура естественно тянется к распределённой геометрии взаимодействий. Ну или монолит/централизованный роутер vs edge computing Итог KAN, как мне кажется, один из самых красивых примеров инверсии контроля в современной архитектуре нейросетей. А следующий интересный вопрос отсюда уже такой: какие ещё модели в ML на самом деле являются не новыми "слоями", а скорее удачными инверсиями носителя выразительности? Спойлер: mechanism of attention, LoRa, диффузионные модели
0
15
Распределённый вторник: Σ - оракул кворумов и защита от split-brain Прошлый распределённый вторник: https://t.me/types_and_ar
Распределённый вторник: Σ - оракул кворумов и защита от split-brain Прошлый распределённый вторник: https://t.me/types_and_archetypes/57 В прошлый раз мы говорили про Ω, оракул, который в пределе приводит все корректные процессы к одному лидеру. Но в этой линии результатов есть ещё один очень красивый объект: Σ, или, познакомьтесь, quorum failure detector. Σ позволяет ответить на вопрос "а какие множества подтверждений вообще допустимо считать достаточными?". В работах Delporte-Gallet, Fauconnier и Guerraoui именно Σ оказывается минимально достаточным детектором для реализации атомарного регистра в произвольной среде, а пара Σ×Ω - минимально достаточной для консенсуса в произвольной среде. Семантика Σ такая: в каждый момент времени каждый процесс получает некоторое доверенное множество процессов, т.е. некоторый текущий кворум доверия, для которого требуются два свойства: - intersection: любые два таких множества, даже у разных процессов и в разные моменты времени, пересекаются - completeness: после некоторого момента любое множество у корректного процесса содержит только корректные процессы И вот здесь начинается самое интересное, процессы могут бесконечно менять мнение о точном составе множества - лишь бы все допустимые множества власти попарно пересекались. Или формально, split-brain возникает в тот момент, когда две части системы могут независимо сказать: "у нас достаточно полномочий, чтобы двигаться дальше", - и затем зафиксировать эти несовместимые состояния. Σ в условиях запрещает как раз это. В этом смысле Σ можно воспринимать как минимальную анти-split-brain абстракцию. Но это уже моя интерпретация. При наличии большинства корректных процессов Σ естественно реализуется через привычные majority-кворумы. Авторы прямо отмечают, что в этом режиме его можно получить почти бесплатно: процессы периодически опрашивают всех и доверяют любой majority, от которой получили ответы. Любые две majority пересекаются, а после некоторого момента множества у корректных процессов состоят только из корректных узлов. Поэтому про majority кворум в Paxos-подобных системах можно думать, как про практическое воплощение Σ. И отсюда очень интересно воспринимается связь Σ с Ω: Ω — кто координирует и на ком eventually заканчивается конкуренция лидеров через ассиметрию (отвечает за liveness) Σ — какие коалиции подтверждения вообще имеют право считаться достаточными через пересечение по источникам легитимности (отвечает за safety) В работах про eventual consistency авторы пишут так: для strong consistency в общем случае нужен не только Ω, но и Σ, потому что Ω даёт eventual common steering, а Σ даёт то дополнительное структурное ограничение, без которого сильная согласованность может разойтись в несколько независимых локальных "правд". В прошлый раз у меня была интуиция, что для консенсуса нужна устойчивая асимметрия лидерства, а с Σ появляется другая, не менее важная асимметрия: не всякая коалиция имеет право быть достаточной, и более того, все допустимые коалиции обязаны пересекаться. Это, по сути, про "какие множества подтверждений нельзя развести как-то так, чтобы они превратились в независимые миры". Итог Ω — это оракул устойчивого лидера Σ — это оракул пересекающихся кворумов Поэтому задачу защиты от split-brain в кворумных протоколах можно свести к задаче обеспечения не пустого пересечения источников истины.
0
16
Проблемы современных кастодиальных решений На прошлой неделе я выступал на митапе и рассказывал про современные кастодиальные решения. Мой главный тезис был таким: современное кастоди решение - это вообще не про то, что мы храним ключ в распределённом виде, а про управление жизненным циклом и ключей, и политик. Потому что ошибки чаще всего возникают именно в control plane, identity plane и границах рантайма. Например, HSM/Vault отвечают только на вопрос, где хранится ключ и почему злоумышленник с физическим доступом не может получить к нему неавторизованного доступа. Но сами по себе они не отвечают на ключевой вопрос: а кто и при каких условиях имеет право заставить его подписать. В своём выстулпении я как раз раскладывал это на policy/quorum, strong identity, non-exportable root, attested signer, audit/anomaly detection и явное разделение storage trust, authorization trust и computation trust. Без грамотных политик буквально нет смысла в хранении ключа в каком-то специальном защищённом месте. При этом политики ещё и должны быть удобными, потому что иначе никто не будет ими пользоваться. И вот на той неделе случился Drift. Около $285M скоропостижно покинули этот протокол. По разбору BlockSec, атакующий заранее получил 2 из 5 апрува в мультисиге через социальную инженерию, а durable nonce позволил держать эти арувы валидными без обычного короткого окна истечения. При этом у Drift был zero timelock, т.е. решение после мультисига принималось сразу без задержки и возможности его откатить другими подписантами. А сам admin path позволял в рамках штатной логики завести коллатерал, переключить оракул на подконтрольный адрес и ослабить политики вывода средств. И это очень важный момент: уязвимость была именно в модели говернанса, т.е. в политиках. Durable nonce здесь был скорее усилителем, он только отделил момент подписи от момента исполнения. И это уже не единичный случай за последнее время. 22 марта ликвидность покинула и протокол Resolv из-за компрометации off-chain ключа, который позволил наминтить десятки миллионов необеспеченных USR и вывести ликвидность. Проблема тут была в избыточном доверии к off-chain инфраструктуре. В зрелой кастодиальной архитектуре недостаточно просто положить ключ в HSM или сделать multisig, нужны политики, явный контур исполнения, локальный secret plane, аудит, recovery, сильная идентичность (например, из HSM), детектирование аномалий и нормальная декомпозиция доверия. И самое главное - нужно отдельно проектировать не только custody секрета, но и custody права на подпись. При этом дисциплина подписи и управления ключами в DeFi намного более значима, чем в традиционных банках, потому что транзакции являются неоткатываемыми и нет никакого права на ошибку. Более того, кажется, что в связи с приходом инстуциональных игроков в DeFi, это становится всё более и более важным, но текущие "заработаем-а-потом-нормально-сделаем" подходы не соответствую этой тендеции.
0
17
NP+: here be dragons Эта картинка, конечно, сильно преувеличивает, всё-таки про классы сложности мы знаем довольно много: опр
NP+: here be dragons Эта картинка, конечно, сильно преувеличивает, всё-таки про классы сложности мы знаем довольно много: определения P, NP, PH, PSPACE, EXPTIME, RE давно формализованы, а про их свойства накоплена большая теория. Но с инженерной точки зрения будет верным сказать, что почти весь "обычный" софт живёт в очень узком классе вычислительной сложности, близком к небольшому фрагменту P. По сути, архитектуре мы часто хотим изменить постановку задачи так, чтобы она решалась в рамках ограниченного вычислительного бюджета и обычно под алгоритмом мы на практике понимаем что-то, что укладывается в такой P бюджет. Это особенно видно на задачах, которые по природе могут очень быстро деградировать по сложности: - управление расписаниями - роутинг - формальная верификация - синтез ппрограмм - генерация и проверка констрейнтов - планирование в условиях противодействия (adversarial planning) В этих задачах общая задача часто слишком дорогая, поэтому рабочая система почти всегда делает одно из двух: всячески сужает общий случай до подзадачи или платит за сложность вне горячего пути, например, предпосчётом. В этом смысле хороший продовый софт - это очень часто аккуратно спроектированная редукция к частному случаю, который можно быстро и надёжно вычислять. NP+ is where the dragons are, at least for now.
0
18
Палеонтология коммуникационных диалектов: закон Конвея на уровне языка После поста про архитектурную палеонтологию (https://t
Палеонтология коммуникационных диалектов: закон Конвея на уровне языка После поста про архитектурную палеонтологию (https://t.me/types_and_archetypes/37) у меня появилась одна исследовательская гипотеза, которую может быть кому-то будет интересно происследовать (она описана в конце). Когда-то на своей первой "нормальной" работе в CQG меня по-настоящему удивило количество разных IPC-механизмов внутри CQG Integrated Client. Мне казалось очень необычнм, что существует много совершенно разных онтологий (тогда я, конечно, не использовал это понятие в таком контексте) для, как казалось мне тогда, одной и той же задачи. Потом похожий паттерн я обнаружил в ядре Windows, а потом и почти во всех других крупных продуктах (например, браузерах). Сейчас я бы описал это иначе: как читаемый след нескольких независимых онтологий, которые долго жили рядом. Отсюда у меня появилась провокативная формула: # serialization formats × # IPC mechanisms ~ # autonomous org units Разнообразие способов, которыми разные части системы общаются между собой, часто хранит в себе отпечаток организационной автономии. При этом эту схему ещё можно читать как закон сохранения сложности: если IPC ~один (как в Chrome), то нужно много форматов, чтобы сохранить количество автономных единиц в компании, и наоборот. Эта формула через произведение чисел имеет несколько важных неточностей и мне она нравится скорее как эвристический крючок. Первая проблема в том, что форматы и IPC почти никогда не комбинируются независимо. Реальная матрица скорее будет разреженной: gRPC естественно тянет protobuf, Kafka живёт с несколькими схемными культурами, но тоже не со всеми одинаково органично и так далее. Поэтому важна скорее структура реальных сочетаний и какие комбинации действительно образуют устойчивые способы общения. Вторая проблема связана с частотой использования: одни и те же числа могут описывать очень разные продукты. Если 90% системы живёт на protobuf+gRPC, а в дальнем углу ещё сохранился XML+SOAP для одного исторического интеграционного канала, то формулой это не отражается. Третья проблема в источниках разнообразия. На картину влияют возраст продукта, слияния и поглощения, внешние интеграции. Иногда в системе много IPC просто потому, что она пережила несколько эпох и несёт наследие каждой из них. Четвёртая проблема лежит в самой целевой переменной. "Команды" - слишком слабое слово, гораздо точнее здесь говорить про что-то типа автономных кластеров принятия архитектурных решений. Поэтому в более зрелом виде мне нравится уже не арифметическая, а структурная формулировка: Чем больше в продукте устойчивых автономных архитектурных контуров, тем выше разнообразие его коммуникационных диалектов И здесь полезно вместо отдельных IPC и отдельных форматов удобнее смотреть на коммуникационные диалекты - устойчивые комбинации вида: {transport, serialization, error model, discovery model, auth model} Например: gRPC + protobuf + status codes + service discovery X, HTTP + JSON + своя система ошибок + auth model Y, shared memory + binary layout + lock-free ring semantics, Kafka + Avro + schema registry + at-least-once. Если идти ещё дальше, то более сильная версия гипотезы звучит так: По графу коммуникационных диалектов системы можно приблизительно восстановить число и границы независимых архитектурных цивилизаций внутри продукта В практическом плане отсюда следует возможно красивая исследовательская программа. Можно взять крупный продукт, вытащить из репозиториев используемые IPC и форматы сериализации, собрать карту устойчивых диалектов, затем наложить на неё модели владения, co-change clusters и граф ревью. Если получившиеся "языковые острова" начинают совпадать с автономными кластерами разработки, то мы получим след организационной структуры. Итог В больших продуктах число устойчивых коммуникационных диалектов может служить прокси для числа реально автономных архитектурных контуров, а их распределение по модулям, моделям владения и совместного изменения - способом восстанавливать скрытую оргструктуру системы.
0
19
Распределённый вторник: асимметрия для консенсуса Предыдущий распределённый вторник: https://t.me/types_and_archetypes/54 FLP
Распределённый вторник: асимметрия для консенсуса Предыдущий распределённый вторник: https://t.me/types_and_archetypes/54 FLP теорема (https://t.me/types_and_archetypes/35) даёт очень важный impossibility result, но дальше возникает естественный вопрос: а какую минимальную информацию про состояние системы нужно добавить, чтобы консенсус снова стал достижимым? Самые первые ответы на эти вопросы были получены в работах Chandra–Toueg и Chandra–Hadzilacos–Toueg про failure detectors. Failure detector в этой теории довольно красивая абстракция, в которой у процессов появляется внешний оракул, возвращающий список процессов в текущий момент времени, которые считаются подозрительными. Под "p подозревает q" имеется ввиду только то, что по какому-то критерию q сейчас находится в suspect-list у p, при этом подозрение может быть ошибочным и потом исчезнуть. Из-за этого классификация свойства подозреваемости строится по двум осям: completeness и accuracy. Первая ось отвечает за то, будут ли упавшие процессы в конце концов подозреваться, а вторая - насколько сильно оракул ошибается насчёт живых. Это весьма полезная формальная линза, которая вместо хартбитов и таймаутов позволяет оценить, а сколько информации о мире вообще доступно и необходимо алгоритму для принятия решения. А дальше начинается самое неожиданное Для консенсуса оказывается достаточно очень слабого детектора, который в статье обозначен как W (стандартно часто пишут ♦W). Он должен обладать двумя весьма скромными свойствами: - после некоторого момента каждый реально упавший процесс навсегда подозревается хотя бы каким-то одним корректным процессом - после некоторого момента существует хотя бы один корректный процесс, которого больше никто из корректных процессов не подозревает. При условии n > 2f (т.е. при наличии большинства корректных пиров) этого уже хватает, чтобы прийти к консенсусу в асинхронной системе. Но при n <= 2f требуется детектор, который строго сильнее W. Но самый красивый шаг, на мой взгляд, происходит в companion paper от Chandra–Hadzilacos–Toueg. Там появляется детектор Ω, смысл которого ещё интереснее: каждый процесс в каждый момент "доверяет" какому-то кандидату в лидеры, и после некоторого момента все корректные процессы навсегда начинают доверять одному и тому же корректному процессу. И вот тут возникает сильнейший результат: любой failure detector, который вообще позволяет прийти к консенсусу, можно алгоритмически преобразовать в Ω И второй сильнеший результат: из Ω можно алгоритмически получить W. А вместе с уже известной достаточностью W при n > 2f это даёт очень жёсткую границу минимального количества информации, нужной для консенсуса. Интуитивный смысл у этого, мне кажется, очень системный (это моё прочтение и интуиция): cистеме для консенсуса нужна устойчивая асимметрия (информация). И здесь возникает явная рифма с другой моей интуицией про архитектуру как борьбу с энтропией (https://t.me/types_and_archetypes/27), потому что если говорить совсем грубо, консенсус - это тоже производство порядка из мира, где слишком много неопределённости. Отсюда и роль лидера в Paxos-подобных алгоритмах начинает читаться чуть иначе. Лидер нужен как механизм устойчивой асимметрии, на которой заканчивается бесконечная конкуренция между равноправными участниками. Я думаю, что это также справедливо не только для распределённых систем, но и, например, для социальных или экономических. Итог FLP - это теорема о запрете в общем случае. Failure-detector theory - ответ на вопрос, а какую минимальную информацию стоит добавить в систему, чтобы снять запрет. Для консенсуса системе хватает очень небольшого знания: некоторого предельного согласия о лидере и условий, при которых это согласие перестаёт расходиться. В такой постановке задачи таймауты, хартбиты и выборы лидера - это попытка дотянуть реальный мир до той тонкой теоретической границы, где консенсус (порядок) снова становится возможным.
0
20
Почему мир Gothic кажется живым: social state machine Давайте немного переключимся с темы инверсии контроля, но останемся в д
Почему мир Gothic кажется живым: social state machine Давайте немного переключимся с темы инверсии контроля, но останемся в домене игр. Готика - одна из моих самых любимых игровых серий (включая третью часть), одной из ключевых особенностей которой является атмосфера и так называемый "живой" мир. Живой мир, который был доведён до пика в Новом Балансе, включает то, что можно назвать социальной стейт машиной: NPC помнят, грабил ли ГГ их, бил, помогал ли им, замечают действия ГГ, обсуждают их и передают новости дальше, а также меняют своё поведение в зависимости от ГГ (например, не обращают внимание на нахождение в их жилище, если у ГГ высокий "положительный" статус в обществе (паладин, маг огня)). Но если кто-то видел, как ГГ нарушил правила, то у такого поступка появляется социальный след. То есть в мире есть социальное состояние: кто доверяет, кто боится, кто считает своим, кто ждёт повода отомстить, кто знает о поступках, кто ещё не знает, и какие последствия уже зафиксировались в системе. Если сжать идею в одну формальную формулу, получится что-то вроде: social state machine = memory + witnesses + gossip + faction logic + persistent consequences memory - мир помнит, что сделал ГГ witnesses - важно не только действие, но и кто его видел gossip - информация не остаётся локальной и начинает распространяться faction logic - реакция зависит в том числе и от группы, к которой принадлежит ГГ persistent consequences - событие меняет будущие переходы системы И вот здесь начинается самое интересное "Ударил NPC", "обокрал", "помог", "убил человека из фракции", "тебя заметили", "о тебе рассказали другим" - это буквально переходы этого социального автомата. А реплики, агрессия, доступ к квестам, торговле, помощи, наказанию или принятию в свой круг - это уже результат работы этого автомата. Живой мир возникает не только из количества реакций или состояний, а из того, что реакции завязаны на распределённую память о действиях и их социальных последствиях. И тут, как мне кажется, лежит урок сильно шире самой Готики. Когда мы слышим state machine, мы обычно думаем о чём-то сугубо техническом: parser, protocol handler, workflow engine, replication logic. Но state machine - это вообще очень общая линза, через неё можно описывать не только сетевой протокол, но и репутацию, доверие, права доступа, эскалацию конфликта, поведение фракций и вообще память системы о пользователе. Очень часто качество архитектуры определяется тем, видит ли архитектор эту скрытую стейт машину там, где она реально нужна. Если не видит, то могут получаться разные неконсистентные состояния, геймдев знает массу таких примеров-антипаттернов: - надетый на голову торговца котелок в Skyrim позволяет обокрасть его, т.к. его линия обзора закрыта https://www.youtube.com/shorts/URGCxk7fomA - локальная память полиции на разыскиваемую машину в Cyberpunk 2077 https://www.youtube.com/shorts/7Ys09teshWI - знаменитый инцидент с чумой в WoW https://www.youtube.com/shorts/gJUav3YudYs А если видит, то появляется связность и накопление отношений. Например, если в Готике достать оружие в присутствии дружественного NPC, то он не отреагирует. А если NPC нейтральный, то сначала последует словесное предупреждение, потом доставание оружия в ответ и потом атака. Это консистентная и очень логичная стейт машина, из-за чего мир реально ощущается как живой и, что лично для меня важнее, логичный. Готика в этом ключе интересна как ранний и очень сильный пример того, что многие хорошие системы (игровые, социальные, финансовые, распределённые) выигрывают, когда в них проектируется не только механика действий, но и автомат отношений. И эта достаточно простая идея является, возможно, одной из самых недооценённых идей в проектировании. P.S. Более того, можно уточнить, что социальная стейт машина в Готике - это в том числе распределённая система. Но об этом в следующем посте.
0