В свободное время пишу на чистом Go порты CRDT-движков. CRDT — это структуры, на которых держится совместное редактирование в реальном времени, вроде гугл-доков: несколько человек правят один документ, и копии сходятся к одному состоянию без центрального арбитра. Эталонные реализации живут на других языках: Yjs на JavaScript, Loro и data model протокола Willow на Rust. Я переписываю их на Go, потому что FFI и CGO плохо ложатся на мобилку и WASM, а pure-Go порт собирается куда угодно. И смысл такого порта ровно один: говорить с оригиналом байт-в-байт. JS-клиент на Yjs должен синхронизироваться с моим Go-сервером и не заметить подмены, и наоборот.
Вот это «байт-в-байт» и есть вся боль. Можно написать полный набор обычных тестов, прогнать их зелёными и всё равно остаться тихо несовместимым с оригиналом. Статья про метод, который это ловит надёжнее всего, на трёх живых багах из трёх моих портов. Это не туториал: метод обобщается на любой «порт формата X на язык Y», CRDT тут просто мой материал.
В репозитории моего Go-порта Yjs было около полутора сотен кросс-языковых фикстур. Юнит-тесты зелёные, roundtrip зелёный, конвергенц-тесты зелёные: документы, собранные параллельно в Go и в JavaScript, сходятся к одному состоянию на десятках сценариев. Я был уверен, что порт совместим с оригиналом. Потом я удалил вложенный тип, реэнкоднул документ и сравнил байты с выводом канонической реализации. Канон сжал удалённое поддерево в компактные GC-runs, а мой порт честно таскал тумбстоуны дальше: даже на минимальных сценариях из двух-трёх элементов реэнкод выходил в 1.5-2.6 раза толще. По семантике всё сходилось идеально, а вот байты говорили, что я где-то наврал.
Звучит как conformance test vectors, которым лет тридцать? Так и есть, сам метод не новый. Дельта в другом. Для форматов, где байты зависят от истории операций, фикстура-снимок просто не воспроизводима, поэтому фикстура здесь — сценарий операций, а не пара вход-выход. И сверка идёт в обе стороны: канон должен съесть мои байты, а я должен байт-в-байт воспроизвести его вывод при реплее той же истории. Фикстура у меня — это именованный сценарий плюс фиксированный clientID плюс canonical hex от запиненной версии канона. Равенство держится, только пока совпадает всё: история с теми же границами транзакций, clientID всех участников, опции документа (gc и тому подобное) и версия энкодера канона. Магии «одинаковый документ значит одинаковые байты» тут нет, и для CRDT её в принципе быть не может: два одинаковых по содержимому документа легально кодируются по-разному.
В статье разберу конвейер и три находки из трёх разных портов. Первую поймала сама побайтовая сверка: баг прятался от всех семантических тестов. Вторую взял соседний оракул, сравнение размеров: документ выходил в 12 раз толще канона. Третья случилась ещё на спек-аудите: конфликт внутри формата, который молча портил бы все вещественные числа при кросс-языковом обмене, и фикстура закрепила правильный ответ замком. Все три кейса — мои собственные порты, и это осознанный выбор: только в своём проекте видна полная хронология бага, что было зелёным, когда и почему.
Вы портируете чужой формат
Ситуация: есть каноническая реализация какого-то бинарного формата, обычно на JS или Rust, а вам нужна вторая на Go, Java или Swift. FFI не подходит (мобильная сборка, WASM, нелюбовь к CGO — причины у всех свои), значит, реимплементация. Я так портировал три штуки: Yjs (CRDT для совместного редактирования, канон на JS), Loro (тоже CRDT, канон на Rust) и data model протокола Willow (канон на Rust). Дальше в тексте все примеры из них.
Как обычно проверяют такой порт, по нарастающей:
-
Юнит-тесты. Проверяют ваше понимание формата, а не совместимость. Если вы неправильно поняли спеку, тесты закрепят неправильное понимание.
-
Roundtrip внутри одного языка: encode, потом decode, потом сравнить. Слеп к систематическим ошибкам. Если я пишу little-endian там, где канон пишет big-endian, мой roundtrip сойдётся идеально: я одинаково неправ в обе стороны.
-
Конвергенц-тесты (для CRDT): два документа после обмена апдейтами приходят к одному состоянию. Слепы ко всему, что не влияет на семантику: сборка мусора, компакция, размер кодирования, представление на проводе.
-
Двунаправленная побайтовая сверка с каноном. Ловит все перечисленные классы слепоты — на тех путях, которые покрыты сценариями.
Дело в том, что у реплицируемых форматов байты — функция внутреннего состояния, а не только видимого содержимого. Сколько тумбстоунов осталось после удалений, как агрессивно squash склеил соседние блоки, что собрал GC — всё это в байтах есть, а в семантике нет. Снапшот-тест против самого себя тут ничего не доказывает, нужен внешний эталон. По моему опыту, для таких форматов побайтовая сверка с каноном — единственный честный оракул: либо ваши байты неотличимы от канонических, либо у вас есть конкретный разошедшийся байт, с которого начинается дебаг.
Откуда метод растёт
Культура тестовых векторов старая и разветвлённая, и тут стоит быть точным, потому что ветки реально разные:
-
Байт-точные вектора: NIST KAT/CAVP в крипте, вектора в RFC (в RFC 9001, например, лежит побайтовый пример защиты QUIC Initial-пакета). Вот это прямой предок.
-
Поведенческие вектора: Wycheproof от Google. Там в основном негативные кейсы (кривые подписи, граничные случаи), и проверяется в первую очередь вердикт accept/reject.
-
Семантический conformance: protobuf conformance suite. Интересно, что protobuf от байтового сравнения отказался намеренно: у формата нет канонического кодирования, одно сообщение легально сериализуется по-разному. Раннер репарсит вывод и сравнивает семантику.
-
Живой интероп: QUIC Interop Runner, матрица клиент-сервер пар, прогоняемая в онлайне.
Случай protobuf тут самый интересный, из него видно, почему у меня байтовое сравнение вообще работает. У protobuf нет канона-эталона, есть спека и десятки равноправных реализаций. А у порта канон есть по определению: конкретная версия конкретной реализации. Формат сам по себе неканоничный, но референс у меня один, запинен по версии и кодирует детерминированно. Этого хватает.
Для CRDT-форматов всё это нужнее, чем где-либо: байты зависят от истории операций и решений GC. Поэтому фикстуры у меня и записаны сценариями.
Конвейер на практике
Три части: генератор на языке канона, корпус в репе, CI-гейт.
Генератор — это скрипт, который гоняет канон по именованным сценариям и пишет JSON с hex’ом. Вот слегка сокращённый кусок генератора nested-GC фикстур (yjs запинен на 13.6.31):
import * as Y from "yjs";const scenarios = [ { name: "map_in_map", clientID: 21, build: (d) => { const root = d.getMap("root"); const child = new Y.Map(); root.set("child", child); child.set("a", "x"); child.set("b", "y"); child.set("c", "z"); root.delete("child"); }, }, // ... ещё сценарии];const out = scenarios.map((s) => { const d = new Y.Doc({ gc: true }); d.clientID = s.clientID; s.build(d); return { name: s.name, client_id: s.clientID, update_hex: toHex(Y.encodeStateAsUpdate(d)), };});
ClientID фиксированный, иначе байты не воспроизвести: он входит в кодирование. На Go-стороне тест реплеит те же логические операции с тем же clientID и сравнивает hex:
d := ygo.NewDocWithOptions(ygo.Options{ClientID: sc.ClientID})build(d) // те же операции, что в JS-генератореgot := hex.EncodeToString(ygo.EncodeStateAsUpdate(d))if got != sc.UpdateHex { t.Errorf("scenario %s mismatch:\n go = %s\n js = %s", sc.Name, got, sc.UpdateHex)}
Обратное направление: фикстуры, где Go энкодит с нуля, а скрипт на стороне канона декодит и проверяет, что всё понял. Для Yjs-порта у меня сейчас 158 таких сценариев в обе стороны (плюс 56 векторов на примитивы кодирования lib0), для Loro корпус генерится против loro-crdt 1.12.5, для Willow — 51 фикстура против willow_rs 0.7.0 плюс 4 цепочки делегирования Meadowcap плюс 176 официальных апстрим-векторов. Весь корпус лежит в testdata и коммитится в репу.
Дисклеймер про имена: мой Deln0r/ygo — не то же самое, что одноимённый reearth/ygo, это независимые проекты. Здесь везде речь про мой порт, а сравнение реализаций — не тема этой статьи.
Наверняка спросят: а почему не differential fuzzing, запустить канон рядом в CI и сравнивать напрямую. Можно, и одно другому не мешает. Но закоммиченный корпус детерминирован, ревьюится глазами через диф и, главное, не тащит Node и Rust-тулчейны в Go CI: генератор запускается один раз при регенерации корпуса, а тесты дальше гоняют чистый Go. Прогон всего корпуса занимает секунды. И да, когда апстрим сам публикует вектора, как Willow, их надо брать: но большинство канонов вектора не публикует, и генератор остаётся единственным способом их добыть.
Баг 1: under-GC, сертифицированный зелёными тестами
Состояние на момент бага:
|
Проверка |
Статус |
|---|---|
|
Юнит-тесты |
зелёные |
|
Roundtrip |
зелёный |
|
Конвергенция |
зелёная |
|
Все существовавшие фикстуры |
зелёные |
Когда yjs удаляет populated вложенный тип, он делает две вещи: превращает ссылку в ContentDeleted-маркер и схлопывает каждый дочерний элемент в garbage-collected run (ref 0). Мой порт делал первое и не делал второе: дочерние элементы оставались тумбстоунами. Конвергенции это не мешает совсем, семантически оба варианта эквивалентны. Размеру мешает: на минимальных сценариях из двух-трёх элементов реэнкод выходил в 1.5-2.6 раза толще канона (53 байта против 25 на map-in-map, 64 против 25 на двухуровневой вложенности). Механика дельты простая: тумбстоун на каждый вложенный элемент против одного GC-range у канона, чем толще удалённое поддерево, тем хуже.
Почему это не поймал ни один из существовавших тогда сценариев: все nested-фикстуры тестировали построение и конвергенцию, все delete-фикстуры тестировали плоские значения. Пересечение «удали populated вложенный тип и реэнкодни» не покрывал ни один, а это единственный путь, где баг виден. Дописал четыре сценария — все четыре сразу красные.
Самое неприятное тут не сам баг, такой кто-нибудь напишет всегда. Стандартная пирамида тестов сертифицировала сломанный порт как корректный. Баг пойман до единого пользовательского репорта только потому, что byte-equality превращает каждый сценарий в тест всех подсистем сразу: GC, squash, кодирование. А не только той, которую сценарий вроде как проверяет.
Баг 2: документ в 12 раз толще канона
У побайтовой сверки есть родственный второй оракул: сравнение размеров энкода на реальных данных. Этот баг пойман им.
Прогоняю стандартный editing-trace (реальная история набора LaTeX-статьи, четверть миллиона правок) через канон и через порт. Канон выдаёт V1-блоб около 160 КБ. Порт — 1.97 МБ. В 12 раз толще, при этом всё декодится, всё конвергирует, все фикстуры зелёные.
Причина: yjs на коммите транзакции склеивает соседние однотипные блоки (при наборе текста это даёт примерно байт на символ), мой порт хранил каждый кейстроук отдельным блоком со всеми заголовками. Формально всё совместимо, но в прод такое не потащишь: полная синхронизация документа для пользователя в 12 раз тяжелее, чем должна быть. После внедрения commit-time squash блоб упал до 223 КБ, в 1.4 раза от канона (остаток — неоптимальности помельче, у них своя очередь).
Причём этот класс проблем формату «не противоречит». Сверка тут работает строже спеки, я так и хотел, к этому ещё вернусь в граблях.
Баг 3: big-endian остров, пойманный до того, как стал багом
Этот кейс из Loro-порта, и он честно не war story, а спек-аудит, который сэкономил war story.
У Loro бинарный формат фактически определён исходниками: Rust-стек serde_columnar поверх postcard, формат рождается из derive-макросов. Документации на байты нет, реверсишь по исходникам и hexdump’ам. И вот при сверке слоёв обнаруживается конфликт внутри самого формата: postcard-конвенция говорит, что f64 кодируется little-endian, а в потоке VALUES change-блока стоит явный to_be_bytes. Big-endian остров в насквозь little-endian формате с LEB128-варинтами.
Если бы я реализовал по postcard-конвенции, не заглянув в эту строку исходника, получилось бы вот что. Внутриязыковой roundtrip проходит идеально: я пишу LE, я читаю LE. Все юнит-тесты зелёные. А при кросс-языковом обмене каждое вещественное число тихо превращается в мусор: ни panic, ни ошибки декодирования, просто другие числа. Вот 3.14, как его пишет канон:
40 09 1e b8 51 eb 85 1f // 3.14 в big-endian
Прочитай те же восемь байт как little-endian f64, и получится ≈8e-157.
По-моему, молчаливая порча данных — худший класс багов из существующих, и ловится он только кросс-имплементационной проверкой, байтовой или семантической против канона: внутриязыковой roundtrip слеп к нему по построению. Golden-фикстура на float-значения добавлена в корпус сразу же, конфликт запинен против реальных блобов loro-crdt 1.12.5.
Про сам формат скажу мягко: производные от serde-стека форматы — нормальный для Rust-экосистемы trade-off, не лень авторов. Часть big-endian мест там вообще рациональна (лексикографическая сортировка ключей в SSTable-сторе, насколько могу судить). Просто порт такого формата без побайтовой сверки — лотерея.
Грабли метода
Куда без них.
Метод строже спеки, и это надо проговаривать. Сверка флагает легальные кодирования как расхождения: тот же 12x-блоб формату не противоречил. Я считаю это фичей, потому что цена ошибки разная: ложное срабатывание разбирается за минуты, а молчаливую порчу данных ты узнаёшь уже из инцидента в проде. Но если ваша цель — формальная совместимость, а не неотличимость от канона, кое-где придётся ослаблять сверку руками.
Корпус только из валидных байтов. Все фикстуры сгенерены каноном, вход в них всегда корректный. Значит декодер, безупречный на валидных данных, может лечь на специально кривых, и байтовая сверка этого не покажет: канон кривых байтов не генерит. Это работа для фаззинга, отдельная. Когда я навесил на decode-пути ygo фазз-сьют, он сразу нашёл четыре дыры одного класса: длина слайса читалась из wire-поля без проверки, и 9-байтный апдейт заказывал make() на ~67 ТБ. Все фикстуры при этом зелёные. Лечится отдельно: каждое количество элементов, прочитанное с провода, проверяется против остатка входа, плюс фаззинг в CI.
Сценарий описан дважды. JS-генератор и Go-тест описывают одни и те же операции на двух языках, и они могут разъехаться. Тогда тест проверяет не то, что вы думаете. Чем лечится: именованные ключи сценариев, ссылка на генератор в комментарии теста, при любом расхождении первым делом сверять сценарии, а не байты. Полностью грабля не лечится, разве что декларативным DSL операций, до которого у меня руки не дошли.
Баг в каноне переедет в ваши фикстуры. Оракул не безгрешен. В Willow-кейсе официальные апстрим-вектора местами расходились с текстом спеки на сайте протокола, и пришлось разбираться, кто из них прав, вектор за вектором. Если канон зафиксил баг кодирования в новой версии, ваш корпус, сгенерённый старой, теперь учит порт воспроизводить баг.
Недетерминизм энкодера. Если канон рандомизирует хоть что-то (порядок обхода map — классика), нужна либо канонизация перед сравнением, либо фиксация сида. Мне повезло: все три канона детерминированы при фиксированном clientID. И это симметрично: ваш собственный энкодер тоже не должен итерировать map без сортировки, иначе флакать начнут уже ваши тесты.
Пиннинг версий. Корпус привязан к точной версии канона, и это должен быть честный пин, не caret-диапазон. Апгрейд канона — это регенерация корпуса плюс ревью дифа. Заодно бесплатно ловишь wire-изменения апстрима.
Цена. Корпуса крошечные: у Yjs-порта 33 файла и ~133 КБ контента, у Loro-порта 95 файлов и ~48 КБ, у Willow свои фикстуры ~117 КБ плюс 32 МБ официальных апстрим-векторов отдельным сабмодулем. Editing-trace для size-теста подтягивается скриптом и в закоммиченный корпус не входит. CI-прогон всего корпуса — секунды, полный пайплайн на push укладывается в полторы минуты. Дороже всего стоит дисциплина: написать генератор и не лениться добавлять сценарий на каждую новую фичу, трогающую провод.
Это работает не только для CRDT
Шаблон переносится на любой «порт X на язык Y»: совместимые кодеки, парсеры бинарных файлов, сетевые протоколы. Чек-лист:
-
найдите канон и запиньте его точную версию
-
генератор сценариев пишется на языке канона, корпус коммитится в testdata
-
сверка двунаправленная: ваши байты декодит канон, его байты байт-в-байт воспроизводите вы
-
CI-гейт: один разошедшийся байт — красный билд
-
при расхождении сначала подозревайте свой код, потом сценарий, потом канон
-
апстрим публикует свои вектора — берите и их тоже
Когда метод не нужен: формат ваш собственный и канона не существует, или формат намеренно недетерминирован и канонизация дороже пользы.
Короче
Пирамида «юнит, roundtrip, конвергенция» доказывает, что порт работает, но не что он совместим с оригиналом. Для форматов, где байты зависят от внутреннего состояния, между этими двумя утверждениями пропасть, и в ней живут баги вида «всё зелёное, а документ толще в 12 раз» и «все числа тихо превратились в мусор».
Побайтовая сверка с каноном закрывает пропасть почти бесплатно: корпус на сотни килобайт и секунды в CI, генератор пишется один раз. И доказывать совместимость приходится заново, на каждом коммите.
Код всех трёх фикстурных конвейеров публичный: ygo (Yjs), loro-go (Loro), willow-go (Willow). Корпуса лежат в testdata, генераторы рядом (у Willow — testdata/_genfixtures), можно глянуть как это выглядит на живых проектах.
Совместимость своего порта я давно не принимаю на веру, и вам не советую. Те полторы сотни зелёных фикстур смотрелись убедительно ровно до того, как я сравнил байты с каноном. Зелёные тесты, как выяснилось, обещают подозрительно мало.
ссылка на оригинал статьи https://habr.com/ru/articles/1049858/