Проблема репликации баз данных с точки зрения BFS

Проблема репликации баз данных с точки зрения BFS

Аннотация

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

1. Постановка задачи репликации как графовой

1.1. Строки и внешние ключи

В реляционной базе строки связаны внешними ключами (FK): строка таблицы orders ссылается на строку таблицы customers, customers — на cities и countries, order_items — на orders и products. Формально это ориентированный граф:

• узлы — строки таблиц (идентифицируются первичным ключом);

• рёбра — внешние ключи «ссылающаяся строка → строка, на которую ссылаются».

Задача репликации: перенести строки из источника в приёмник так, чтобы в момент вставки каждой строки все её FK-зависимости уже были в приёмнике.

1.2. Почему это графовая задача

Если вставить order_items раньше orders, СУБД отклонит вставку по нарушению внешнего ключа. Если отключить проверку FK — получим «висячие» ссылки, которые сломают JOIN'ы, отчёты и приложение. Ссылочная целостность — необходимое условие корректной репликации.

Ссылочная целостность — это свойство порядка: для каждого ребра «ссылающаяся → целевая» целевая строка должна быть вставлена раньше ссылающейся. Это в точности топологическая сортировка графа.

1.3. Где здесь BFS

BFS (Breadth-First Search, поиск в ширину) — алгоритм обхода графа «волнами»: начинаем с корней, смотрим на их соседей, потом на соседей соседей, и так далее. BFS отвечает на вопрос: «какие узлы достижимы от заданных корней?»

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

Здесь и начинается проблема: BFS выглядит как решение, но является только картой. Карта показывает, что есть на местности, но не говорит, по какому маршруту идти.

2. Что BFS даёт и чего не даёт

2.1. Что BFS даёт

• Множество достижимых узлов от заданных корней.

• Фильтрацию по корням: если корень один — обходится только его подграф.

• Учёт пропусков: строки, помеченные как «уже доставленные», достигаются, но не разворачиваются.

• Естественную параллельность: обход можно вести по компонентам связности.

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

2.2. Чего BFS не даёт

• Порядка вставки: BFS отвечает «что достижимо», а не «в каком порядке вставлять».

• Обработки циклов: в графе с циклом BFS либо зациклится, либо соберёт множество узлов, для которых порядок невозможен.

• Различения типов строк: BFS не знает, справочная это таблица или транзакционная.

• Семантических зависимостей: BFS видит только FK, но не триггеры, бизнес-правила, вычисляемые поля.

• Блокировок: BFS не знает, какие строки конфликтуют за ресурсы.

• Версий и удалений: BFS не различает «уже есть в приёмнике» и «нужно вставить».

• Памяти и лимитов: BFS может «съесть» всю память на большом графе.

• Детерминизма: BFS на HashMap даёт разный порядок между запусками.

Именно это несоответствие — между простотой BFS и сложностью реальной репликации — порождает проблему. Разберём её по слоям.

3. Проблема первая: BFS даёт карту, а не маршрут

Это фундаментальное ограничение. BFS обходит граф, собирает множество узлов — и останавливается. Он не говорит, в каком порядке их вставлять.

Пример:

order_items_1 → orders_5 → customers_3
                         → products_10

BFS соберёт {order_items_1, orders_5, customers_3, products_10}. Но в каком порядке их вставлять — BFS молчит. Можно вставить order_items_1 первым — и получить нарушение FK на orders_5.

Следствие: после BFS нужен отдельный проход — топологическая сортировка и вычисление уровней. BFS — только первый этап. Если рассматривать BFS как «решение», это создаёт иллюзию, что задача решена, когда решена только её половина.

4. Проблема вторая: циклы ломают порядок

BFS хорошо работает на деревьях и DAG (направленных ациклических графах). Но в реляционных базах бывают циклы: строка A ссылается на B, а B — на A. Типичные примеры: employees.manager_id → employees.id, categories.parent_id → categories.id, взаимные FK между orders и invoices.

Наивный BFS на таком графе:

• либо зациклится (если не отслеживать посещённые);

• либо соберёт множество узлов, для которых порядок невозможен: «A раньше B» и «B раньше A» одновременно.

Формально это означает, что граф не является DAG, и топологическая сортировка на нём не определена. Нужен дополнительный шаг — схлопывание циклов (конденсация сильно связных компонент). Только после этого можно строить порядок.

Но и схлопывание не решает задачу до конца. В реляционной БД цикл нельзя «вставить вместе»: нельзя вставить A со ссылкой на B, если B ещё нет, и наоборот. Приходится использовать двухфазную вставку: вставить оба ряда с NULL в циклическом FK, потом обновить каждый, проставив ссылку на другого (или временно отключить проверку FK на время транзакции). Это не «схлопывание», а специальный протокол, которого в BFS-модели нет.

Следствие: BFS не только не решает циклы — он создаёт ложное впечатление, что достаточно «схлопнуть и вставить вместе». Реальность требует протокола из нескольких проходов.

5. Проблема третья: skip меняет семантику обхода

Повторная репликация не может каждый раз тащить весь граф. 99% строк уже есть в приёмнике в актуальных версиях. Нужен механизм пропуска — «эта строка уже там, не разворачивай её ветку».

Наивное решение — добавить в BFS флаг skip — ломает простую семантику. Появляются неочевидные вопросы.

5.1. Множественные пути

Строка достижима и через skip-узел, и через обычный. Включать её в план или нет?

Правильный ответ: включать, если есть хотя бы один путь без skip. Но наивный BFS этого не знает — он идёт по очереди и не различает, каким путём пришёл.

5.2. Приоритет корней

Строка одновременно в корнях и в skip. Пользователь явно указал её как точку входа — значит, хочет видеть. Skip говорит «не разворачивай». Конфликт.

5.3. Skip-узел как родитель

Не-skip строка ссылается на skip-строку. Skip-строка не разворачивается — её потомки не достигаются. Но при вставке ссылка на skip-строку всё равно указывается. Приёмник должен сам её разрешить — то есть она должна уже быть там. Если приёмник не гарантирует наличие — данные испорчены.

Следствие: skip — не «оптимизация BFS», а изменение модели данных. Он требует явных правил и уверенности, что приёмник содержит все skip-строки. BFS-модель этого не покрывает.

6. Проблема четвёртая: missing — это не «всё, чего нет в графе»

После BFS мы знаем множество достижимых узлов. Некоторые рёбра ведут за пределы этого множества — на строки, которых в графе нет.

order_items_1 → products_10 → suppliers_99

suppliers_99 — цель FK, но в графе его нет. Это missing? Или это skip-строка? Или строка, которую просто не передали?

Проблемы:

• Если считать missing всё, чего нет в графе — в missing попадут и skip-строки (они тоже «не в графе», потому что не развёрнуты). Ложные срабатывания.

• Если не считать missing skip-строки — нужно точно знать, что строка была достигнута и пропущена, а не просто отсутствует.

• Если у строки есть тип/метаданные, но она не была родителем — она «известна»? Или всё равно missing?

Следствие: missing — это не «всё, чего нет в графе», а сложное понятие с несколькими условиями. BFS сам по себе его не вычисляет — нужен отдельный проход с доступом к метаданным и множеству пропущенных.

7. Проблема пятая: BFS не различает типы строк

BFS видит рёбра «A → B», но не знает, что такое B — строка справочника, транзакционная запись, строка-связка many-to-many, партиционная запись.

От типа зависит:

• как вставлять: справочник — простой INSERT, транзакционная запись — INSERT с побочными эффектами (триггеры, каскады);

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

• можно ли вставлять параллельно: две транзакционные записи могут конфликтовать за счётчики/последовательности, два справочника — обычно нет.

Следствие: BFS по PK теряет тип. Нужен слой типизации — и правила вставки по типу. BFS-модель этого не покрывает.

8. Проблема шестая: BFS не видит семантических зависимостей

В реляционных БД зависимости не ограничиваются объявленными FK. BFS построит рёбра только по явным FK, но пропустит:

• Триггеры — AFTER INSERT может читать/писать другие таблицы, не связанные FK.

• Каскады — ON DELETE CASCADE, ON UPDATE CASCADE создают неявные зависимости.

• Вычисляемые поля и представления — зависят от других таблиц, но не выражены FK.

• Проверочные ограничения (CHECK) — могут ссылаться на другие таблицы через подзапросы.

• Логические ссылки — когда FK не объявлен, но приложение полагается на совпадение значений (например, orders.customer_code и customers.code).

• Бизнес-логику — приложение при вставке читает таблицы, не связанные FK.

Следствие: BFS по FK соберёт неполный граф. Часть зависимостей останется невидимой — и вставка упадёт на триггере или бизнес-правиле, а не на FK. Это принципиальное ограничение: BFS моделирует структуру, а не семантику.

9. Проблема седьмая: BFS не знает про блокировки и транзакции

СУБД при вставке блокирует строки, страницы, таблицы. Если вставлять «строго по уровням», можно получить:

• сериализацию — каждая вставка ждёт предыдущей;

• дедлоки — если два потока пишут в пересекающиеся таблицы в разном порядке;

• эскалацию блокировок — блокировка строки превращается в блокировку таблицы при массовой вставке.

BFS даёт уровни, но не знает про блокировки. Две строки одного уровня могут конфликтовать за одну таблицу или индекс. Их нельзя вставлять параллельно — но BFS этого не видит.

Следствие: для параллельной вставки нужна группировка по доменам блокировок — какие таблицы/индексы трогают одни и те же строки. Это отдельный слой, которого в BFS-модели нет. BFS даёт «что вставлять», но не «как вставлять параллельно».

10. Проблема восьмая: широкие уровни

BFS и вычисление уровней дают «широкие» уровни: например, уровень 0 — 10 000 справочных строк, уровень 1 — 100 000 транзакционных, уровень 2 — 500 000 строк-связок.

Вставка уровня 2 «в один поток» — это 500 000 INSERT подряд. На это могут уйти часы. Параллельная вставка упирается в блокировки (см. п. 9).

Следствие: BFS даёт порядок, но не даёт стратегии исполнения. Нужно разбивать широкие уровни на батчи, группировать по доменам блокировок, учитывать лимиты СУБД (размер транзакции, размер WAL, autovacuum). BFS-модель этого не покрывает.

11. Проблема девятая: BFS не знает про версии и удаления

BFS отвечает: «что достижимо». Но не отвечает:

• устарела ли строка в приёмнике (версия изменилась);

• удалена ли строка в источнике (soft delete, tombstone);

• есть ли строка в приёмнике, которой нет в источнике (extra).

Если BFS просто соберёт достижимые узлы — он включит в план и те, что уже есть в приёмнике, и те, что удалены в источнике.

Следствие: нужен слой сверки версий и удалений — реконсайлер. BFS — только «что достижимо», а не «что нужно вставить с учётом состояния приёмника». Это разные задачи, и BFS не должен пытаться решить вторую.

12. Проблема десятая: BFS и согласованность в параллельной среде

Граф общий на все сессии. Разные процессы и потоки могут одновременно:

• добавлять рёбра (новые FK-связи),

• задавать корни,

• задавать skip,

• вызывать пересчёт,

• читать план.

Проблемы:

• два потока добавляют рёбра — граф не должен «терять» данные;

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

• два потока пересчитывают одновременно — результат должен быть одинаковым;

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

Следствие: BFS не может быть «просто функцией». Нужна модель согласованности: снапшоты, версии, блокировки, защита от lost-update. Это отдельный слой сложности поверх алгоритма, и BFS его не покрывает.

13. Проблема одиннадцатая: рассинхронизация между планом и исполнением

План репликации строится в два шага: сначала сводка (сколько уровней, какие группы), потом страницы (PK по уровням и типам). Между этими шагами граф может измениться.

Проблема: если не защититься, репликатор возьмёт страницу по старой сводке, а данные уже другие. Получит «не те» строки или пропустит нужные.

Следствие: нужен механизм версионирования плана — хэш от состояния графа, который проверяется при каждом запросе страницы. Это ещё один слой поверх BFS.

14. Проблема двенадцатая: память и лимиты

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

Проблема: без лимита граф может «съесть» всю память процесса. С лимитом — нужно решить, что делать при превышении: ошибка? усечение? разбиение на части?

Следствие: BFS требует явной политики по памяти. Это не алгоритмическая деталь, а архитектурное решение, которого в наивной BFS-модели нет.

15. Проблема тринадцатая: детерминизм

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

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

Следствие: BFS должен быть детерминированным по построению — сортировка узлов, детей, компонент, сильно связных компонент. Это ещё один слой сложности, которого в наивной BFS-модели нет.

16. Сводная картина: BFS как карта, а не маршрут

BFS решает одну задачу: «какие строки достижимы от корней по FK». Это необходимая часть, но не достаточная.

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

17. Как это отражается на 1С

Всё сказанное выше относится к любой реляционной БД, но 1С умножает каждый из этих слоёв на собственную платформенную модель — и проблема BFS-подхода становится ещё острее.

17.1. Зависимости в 1С не ограничиваются внешними ключами

Кроме FK на уровне СУБД, 1С добавляет платформенный слой зависимостей:

• Метаданные — состав объектов, подчинённость, табличные части, регистры. Это не FK, это описание модели, которое платформа проверяет при записи.

• Бизнес-логика проведения — документ при проведении читает и пишет регистры, не связанные FK. Это «семантические» зависимости, невидимые в графе ссылок.

• Предопределённые элементы — на них ссылаются по имени, а не по UUID. BFS по UUID их не увидит.

• Составные типы — одно поле может ссылаться на разные типы объектов; BFS теряет тип и не знает, как загружать.

• Иерархии справочников — самоссылающийся FK (родитель → элемент → подэлемент).

• Последовательности — хронологический порядок документов важнее топологического; BFS про даты ничего не знает.

BFS по FK увидит только часть этого графа. Остальное — «невидимые» зависимости, которые проявятся при проведении, а не при вставке. То есть BFS гарантирует ссылочную целостность — но не гарантирует, что документ проведётся.

17.2. Циклы в 1С — норма, а не исключение

Иерархические справочники — это самоссылка по определению. Взаимные ссылки документов (Заказ → Реализация → Заказ) — типичный сценарий учёта. Схлопывание циклов и двухфазная загрузка — не «редкий случай», а основной режим работы. BFS-модель, рассчитанная на DAG, в 1С упирается в циклы постоянно.

17.3. Блокировки в 1С — многоуровневые

Поверх блокировок СУБД платформа накладывает управляемые блокировки: объектные, регистровые, на уровне разделителей данных. BFS не знает ни про них, ни про их иерархию. Два документа одного уровня могут конфликтовать за регистр — и BFS этого не увидит. Параллельная загрузка «по уровням» в 1С упирается в дедлоки, которых в BFS-модели нет.

17.4. Проведение — отдельная фаза со своими зависимостями

Документ можно записать (INSERT), но не провести. Проведение запускает платформенный код, который читает остатки, проверяет последовательности, пишет движения. Это вторая фаза, которая может упасть независимо от ссылочной целостности. BFS гарантирует только первую фазу — запись. Вторая фаза требует retry, догрузки, откатов — всего того, чего в BFS-модели нет.

17.5. Конфигурации источника и приёмника должны быть совместимы

Если версии метаданных расходятся — репликация не начнётся вообще, независимо от графа. Это ещё один слой выше BFS: совместимость конфигураций. BFS его не видит и не может увидеть.

17.6. Итог для 1С

В 1С BFS-подход упирается не в один, а в несколько барьеров одновременно — метаданные, бизнес-логику, блокировки, последовательности, проведение, совместимость конфигураций. Каждый из них требует отдельного слоя поверх BFS. Именно поэтому «взять BFS и применить к 1С» не работает: BFS — это только карта ссылок, а 1С — это карта ссылок плюс метаданные плюс бизнес-логика плюс блокировки плюс проведение плюс совместимость конфигураций. Каждый из этих слоёв — отдельная задача, и BFS не должен пытаться решить их все. Он должен оставаться тем, чем является: картой достижимости, на которой строятся остальные слои.

18. Что это означает для архитектуры

Если рассматривать BFS как «решение», архитектура получится хрупкой: попытка «впихнуть» в BFS всё, чего он не умеет, превращает простой алгоритм в монстра с неявными связями. Skip начинает влиять на missing, блокировки — на порядок, версии — на достижимость. Каждое новое требование добавляет ветвление в BFS и ломает его чистоту.

Если рассматривать BFS как «первый шаг», архитектура получается слоистой:

1. BFS — карта достижимости.

2. Конденсация циклов — превращение графа в DAG.

3. Топосорт и уровни — маршрут вставки.

4. Типизация и семантика — правила по типам строк.

5. Сверка версий и удалений — что именно вставлять.

6. Модель согласованности — как вставлять параллельно.

7. Стратегия исполнения — батчи, домены блокировок, retry.

8. Защита от рассинхронизации — версионирование плана.

9. Платформенный слой (для 1С) — метаданные, проведение, последовательности, совместимость конфигураций.

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

Заключение

Проблема репликации реляционных БД с точки зрения BFS — это проблема несоответствия масштаба. BFS — простой, элегантный, хорошо изученный алгоритм. Репликация реляционной БД — сложная, многослойная задача с десятком измерений: типы, семантика, блокировки, транзакции, версии, последовательности, память, согласованность, детерминизм. Для 1С к этому добавляется ещё платформенный слой — метаданные, проведение, управляемые блокировки, совместимость конфигураций.

BFS решает одно измерение — достижимость по FK. Остальные измерения лежат за его пределами. Попытка свести всё к BFS создаёт иллюзию простоты, которая разбивается о реальность при первом же цикле, первой же блокировке, первой же устаревшей строке — а в 1С ещё и при первом же непроведённом документе.

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

Понимание этой границы позволяет строить архитектуру, в которой BFS остаётся простым и чистым, а сложность репликации распределяется по слоям. Без этого понимания любая реализация — даже самая тщательная — рано или поздно упрётся в ограничения, заложенные в самой модели BFS.