Использование Paxos для синхронизации большого файла между узлами

Как Питер упомянул в комментариях, вероятно, лучше подойдет окончательно согласованный. Вот один из таких алгоритмов, основанный на протоколе сплетен.

У каждого узла есть какая-то версия файла. Каждые N секунд каждый узел подключается к другому узлу, и они меняют номера версий. Если один узел находится за другим, он загружает файл от однорангового узла.

Это сходится замечательно быстро, я думаю, в пределах 10-20 раундов сплетен на 1000 узлов.

Обновлять

(Добавляем плот или очередь сообщений.)

Плот

Из ваших комментариев видно, что у вас в руках есть хранилище ключей и значений. Вы можете думать об этом как о распределенном конечном автомате, в котором вы обрабатываете обновление каждого ключа как отдельную команду. Это отлично подходит для протокола консенсуса, такого как paxos или raft (сейчас я предпочитаю raft для количество реализаций с открытым исходным кодом). Более того, они часто реализуются так, чтобы действовать как атомная система широковещательной передачи. Короче говоря, несколько узлов действуют как основные лица, принимающие решения, а остальные узлы слушают результаты.

(Конечно, я не знаю, как обновляется ваш файл; т.е. обновляется ли он только на главном узле, а остальные являются подчиненными.)

Одной из основных проблем будет разветвление до 1000 узлов. Для этого вам, вероятно, понадобится иерархическое разветвление. Существуют различные схемы, чтобы помочь в этом; Вот несколько идей. A) Каждый узел должен подключаться к двум случайным одноранговым узлам; и поток от однорангового узла с кратчайшим путем к главному узлу (это называется сила двух вариантов); или Б) с некоторой вероятностью p выбрал однорангового узла с кратчайшим маршрутом. C) Пусть каждый узел подключается к одному случайному узлу, и с некоторой вероятностью p поток от этого узла вместо этого подключается к его вышестоящему узлу. Эти вероятности предназначены для создания n-арного дерева, которое является хорошим балансом между каждым узлом, подключенным к главному узлу, и каждым узлом в связанном списке.

Очередь сообщений

Теперь paxos и raft дают довольно серьезные гарантии. Специально для этого случая каждое обновление будет обрабатываться по порядку - по всем ключам. Если вам не нужна эта гарантия, вы можете спроектировать гораздо более простую систему.

Каждое обновление ключа может транслироваться в очередь распределенных сообщений (например, SQS, RabbitMQ и т. Д.). Версия каждого обновления ключа и применение обновления только в том случае, если оно превышает версию, которая у вас есть. Это дает вам красивую и быструю, в конечном итоге последовательную систему.

Я бы пошел с этим подходом выше, используя raft / paxos, если система позволяет это.

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

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