один,Опыт исследований и разработок Paxoskv
Внутри BIGO система хранения в основном включает систему хранения таблиц MyShard, распределенные системы хранения ключей/значений ssdb [1] и pika [2] и другие распределенные системы хранения объектов. Хранилище ключей/значений использует большое количество ssdb и pika.Хотя ssdb и pika являются отличными системами хранения, в конкретной практике бизнес-сценариев BIGO технология BIGO столкнулась со многими проблемами и трудностями. Например, и ssdb, и pika используют первичную/резервную [3] модель репликации на основе binlog.Первичная/резервная модель хорошо решает проблему расширения чтения, но также создает некоторые проблемы, как показано на следующем рисунке:
1) Синхронизация данных между основным и резервным включает в себя не только вопрос о том, будут ли данные потеряны, но и вопрос о том, какую модель согласованности может обеспечить извне весь кластер хранения. Однако один метод синхронизации, будь то асинхронная, полусинхронная или строгая синхронизация, не может удовлетворить дифференцированные потребности различных служб.
2) Атомарность операций с данными и операций с бинарными журналами на первичном сервере связана не только с управлением ходом репликации, но и с согласованностью в системе с несколькими копиями. Например, в MySQL для решения этой проблемы используются внутренние XA-транзакции между innodb и binlog, но решить эту проблему в существующей системе сложнее.
3) Первичная/резервная модель сложнее справиться с проблемой записи в несколько регионов. Простая многоточечная запись не только не обеспечивает правильную границу согласованности, но также может вызвать такие проблемы, как тихая потеря обновлений, что увеличивает нагрузку на обнаружение ошибок, эксплуатацию и обслуживание.
4) Когда основная/резервная модель развернута в нескольких регионах, возможны проблемы, такие как разветвление основного узла, избыточная передача межрегионального трафика и ограниченное использование ресурсов резервного узла.
5) pika также обеспечивает модель репликации, аналогичную NRW [25], но даже если принята конфигурация кворума R+W > N, она не может обеспечить линейную согласованность, если не используются такие средства, как восстановление чтения.
Короче говоря, по сравнению с диверсифицированными типами бизнеса BIGO и быстро растущим масштабом данных существующие системы хранения не смогли удовлетворить требования внутренних бизнес-систем BIGO с точки зрения согласованности данных, доступности системы, производительности и возможностей развертывания между регионами. В частности, основные требования бизнеса BIGO к системам хранения включают:
● Благодаря множеству моделей согласованности, от линейной согласованности до согласованности в конечном счете, различные бизнес-сценарии могут выбирать между RTO и RPO в соответствии с их собственными SLA;
● Он имеет возможность многоточечной записи, то есть макроскопически это система с несколькими мастерами, и сбой узла в отказоустойчивой конструкции не повлияет на доступность системы;
● Благодаря возможностям глубокого контроля/настройки он может перенести некоторые часто используемые бизнес-сценарии на уровень хранения, упрощая разработку и способствуя повышению основной конкурентоспособности бизнеса;
● Благодаря удобному горизонтальному расширению, он может быстро увеличивать/уменьшать мощность, что делает его еще более эффективным с точки зрения эффективности доставки и использования ресурсов;
Основываясь на вышеизложенном, мы разработали paxoskv. Цели его разработки: иметь дополнительную возможность линейной согласованности/причинно-следственной согласованности/окончательной согласованности, иметь возможность многоточечной записи, иметь возможность горизонтального масштабирования и иметь такую же производительность чтения и записи, что и ssdb и пищуха.
два,Техническая реализация Paxoskv
2.1 Архитектура системы
Системная архитектура Paxoskv показана ниже.Каждый набор соответствует логическому разделу данных, и каждый набор имеет несколько реплик на сервере (в качестве примера на рисунке используются 3 реплики: реплика1/реплика2/реплика3). Ключи в каждом наборе разделены на несколько пространств ключей в соответствии с согласованным хэшем, и каждое пространство ключей соответствует определенной реплике. Цель этого состоит в том, чтобы каждая реплика могла обрабатывать запросы.Соответственно, существует сильный протокол лидера, такой как raft [23].Все запросы на запись должны направляться на узел-лидер и инициироваться узлом-лидером. Таким образом, использование ресурсов узла-последователя недостаточно, что в определенной степени снижает вычислительную мощность всего кластера.
Каждый сервер реплик может содержать реплики нескольких наборов и одновременно обслуживать несколько наборов. Количество реплик, обслуживаемых сервером реплик, может время от времени меняться из-за таких факторов, как миграция и расширение физической машины. Метаданные всего кластера хранятся в etcd [16], а смарт-клиент воспринимает изменения топологии всего кластера во времени с помощью часов.
2.2 Выбор дизайна
При проектировании и выборе paxoskv мы в основном сочетаем текущую ситуацию, описанную в «Истории исследований и разработок Paxoskv», требования внутреннего бизнеса BIGO и более передовые технологии распределенных систем хранения, чтобы сделать всесторонние суждения и компромиссы. В дизайне технология BIGO позаимствовала многие идеи из WPaxos [24] и, наконец, выбрала paxoskv для теоретической поддержки и проектирования инженерной практики следующим образом:
● С точки зрения модели репликации, paxoskv между узлами RW использует архитектуру multi-paxos без лидера, которая не только допускает многоточечную запись, но и обеспечивает согласованность состояния между несколькими репликами с помощью multi-paxos;
● Чтобы избежать проблемы атомарности операций с данными и операций binlog, paxoskv между узлами RW и RO и между узлами RO и узлами RO позволяет избежать этой проблемы, копируя WAL механизма хранения, а также дает некоторые преимущества с точки зрения стоимости. и репликация в реальном времени. ;
● Чтобы удовлетворить потребности мультирегионального развертывания, аналогично облачному гаечному ключу [5], внутренние узлы paxoskv разделены на две роли: RW (чтение-запись) и RO (только чтение).Синхронная репликация, асинхронная репликация между регионами через RO и цепная репликация между несколькими регионами, чтобы избежать избыточного межрегионального трафика;
● Кроме того, paxoskv — это независимая последовательность журналов для нескольких Paxos с ключом. Различные журналы для нескольких Paxos полностью изолированы. Лучше разрешить параллельное выполнение большого количества экземпляров paxos, тем самым улучшив возможность одновременного ответа на кластерный уровень;
2.3 Глубокая оптимизация
2.3.1 Leaderless
В настоящее время все основные системы хранения с несколькими копиями на основе нескольких паксосов используют метод разделения наборов.Один набор управляет одним сегментом данных, а один набор соответствует одному журналу с несколькими паксосами. При реализации Paxoskv, чтобы удовлетворить требования горизонтальной масштабируемости системы, также принята идея набора, но набор содержит несколько журналов мультипаксосов. В частности, каждый ключ имеет свой собственный независимый журнал multi-paxos. В одном и том же наборе, когда интеллектуальный клиент инициирует запрос, он равномерно распределяет разные ключи в одном наборе между несколькими копиями в соответствии с согласованным хэшем. Таким образом, paxoskv представляет собой безлидерную архитектуру с возможностью многоточечной записи.На микроуровне для одного и того же ключа, если топология кластера стабильна, выбирается путь быстрого приема, в противном случае выбирается путь медленного приема, то есть двухэтапный процесс собственного алгоритма paxos.
Одним из преимуществ безлидерной схемы является то, что она может обеспечить лучшие гарантии доступности на уровне кластера. в системе одновременно. Узлы, чтобы избежать проблем с «многоглавным» в таких ситуациях, как сетевые разделы. Недостатком метода аренды является то, что если период аренды установлен слишком малым, легко сделать ошибочную оценку, а дрожание сети считается недоступностью узла; если установить слишком большой период аренды, это приведет к реальному сбою. . Предыдущая аренда истекает, и выбирается новая аренда для сохранения.Интервал между узлами велик, и весь кластер недоступен в течение этого переходного окна, что повлияет на SLA системы.
Как показано на рисунке ниже (источник изображения [7]), алгоритм Paxos естественным образом обладает свойством безлидерности.Независимо от того, существует ли стабильный ведущий узел-предлагатель, безопасность алгоритма может быть гарантирована, а некоторой живучестью можно пожертвовать. в большинстве. В инженерной практике живучесть экземпляров paxos можно повысить за счет случайного избегания и повторных попыток. Это одна из причин, по которой мы выбираем paxos в качестве алгоритма консенсуса:
В реальном бизнес-сценарии BIGO один и тот же ключ запрашивается одновременно у разных клиентов, и некоторые клиенты и соответствующие им узлы paxoskv сталкиваются с сетевыми разделами (и затем считают, что узел недоступен, и переключаются на другие узлы для повторной попытки). встречаемость очень низкая. . Таким образом, после истечения времени ожидания запроса к узлу вы можете быстро переключать узлы, чтобы инициировать повторный запрос, что значительно сокращает время недоступности системы.
2.3.2 Log is data
Самым ранним и более формальным источником Log is data является статья «LogBase: масштабируемая система базы данных с логической структурой в облаке», подготовленная VLDB NUS в 2012 году [8], которая теперь стала одной из важных концепций проектирования облачных технологий. Архитектура базы данных.Решить проблему, заключающуюся в том, что запись ввода-вывода легко стать узким местом в традиционной архитектуре базы данных WAL + страница данных. Как показано ниже:
В реализации paxoskv само значение является частью журнала paxos, что является подходящим сценарием для идеи log is data. То есть технология BIGO интегрирует журнал paxos, который запускает консенсус paxos, и значение, которое в конечном итоге обеспечивает чтение / запись для бизнеса.. Нет необходимости сначала записывать журнал paxos, а затем воспроизводить журнал paxos в механизме хранения. Тем не менее, в текущей реализации paxoskv он по-прежнему будет в определенной степени усиливать чтение/запись, особенно для сценариев с большими значениями.
2.3.3 Fast accept
Как показано на рисунке ниже (источник изображения [9]), нативный алгоритм paxos разделен на два этапа: первый этап включает в себя фазу 1a предложения и фазу 1b обещания; второй этап включает фазу 2a принятия и фазу 2b. accept; Каждый этап потребляет 1 RTT. Хотя Paxoskv использует архитектуру без лидера, реализация опирается на оптимизацию стабильного лидера в основной инженерной реализации с несколькими Paxos. Для того же ключа, если инициатором последнего выбранного журнала является текущий узел (идентификатор предлагающего будет записан в метаинформации журнала paxos), то нет необходимости выполнять первую фазу собственного paxos. алгоритм (фаза-1a предлагает/фаза-1b обещание), непосредственно инициирует запрос на принятие фазы-2a, мы называем этот процесс в paxoskv быстрым принятием (в конкретной реализации проекта, чтобы обеспечить правильность соглашения, предложение быстрое принятие будет 1: Идентификатор предложения инициируется как номер предложения, а предложение без быстрого принятия будет инициировано с 2: Идентификатор предложения в качестве номера предложения). Поэтому в большинстве случаев, когда топология кластера стабильна, paxoskv может выбрать путь быстрого принятия.
2.3.4 Fast chosen
Как показано на следующем рисунке (источник изображения [9]), в родном алгоритме paxos есть три роли Proposer/Acceptor/Learner. Типичный поток выполнения алгоритма paxos показан на следующем рисунке:
Мы видим, что даже если мы выберем путь быстрого принятия, требуется 1,5 RTT (Предлагающий → Принимающий → Выдающийся предлагающий/Ученик → Принимающий) от инициирования запроса на принятие до определения того, что предложение было выбрано. предложение на спине. Обратите внимание, что если каждый акцептор принимает предложение, оно может быть передано всем акцепторам, чтобы быстро определить, было ли достигнуто большинство для достижения выбранного состояния, но это обычно не делается в инженерных реализациях, потому что сложность сообщения слишком высока.
При реализации paxoskv, в случае 3 копий, предлагающий сначала примет локальный, а затем отправит запрос на принятие акцепторам.Таким образом, если какой-либо акцептор удовлетворяет принятым условиям локально, плюс количество принятых Предложившего, это будет Можно определить, что условия большинства приняты, чтобы быстро войти в выбранное состояние. По сравнению с выбранным методом уведомления о совмещении предыдущего предложения выше следующего запроса, упомянутого выше, задержка записи значительно не улучшается, но ее можно сочетать с идеей журнала данных.Для акцептора после определения выбранного Одна запись на диск завершает процесс этого paxos, экономя одну операцию ввода-вывода записи Rocksdb [10]. Конечно, быстрый выбор может действовать только при конфигурации из 3 копий (при фактическом развертывании BIGO в настоящее время это конфигурация из 3 копий).
2.3.5 WAL replication
В системе, использующей бинлог для репликации, узел, генерирующий бинлог, сталкивается с проблемой атомарности обновления данных и бинлога. Бинлог обычно делится на два формата на основе оператора и на основе ROW.Вопросы, связанные с этим, включают в себя то, как гарантировать, что одна и та же страница данных создается после воспроизведения бинлога на других копиях, а также учитывать размер синхронизированного бинлога и может ли бинлог быть распараллелен.воспроизведение и другие вопросы.
При реализации paxoskv, поскольку окончательным механизмом хранения данных является Rocksdb [10], технология BIGO использует репликацию на основе журнала Rocksdb WAL. Как показано ниже:
Реализация репликации paxoskv WAL в основном зависит от двух API-интерфейсов GetLatestSequenceNumber() и GetUpdatesSince() Rocksdb [10]. Во время инициализации или восстановления после прерывания репликации для выравнивания сайтов синхронизации используется комбинированный режим pull/push.Конкретная реализация аналогична репликации binlog на основе GTID в MySQL 5.7 [11].
2.3.6 Linearizable quorum read
В строго непротиворечивой системе хранения линейно непротиворечивое чтение и запись обычно достигается за счет реализации основной аренды на лидере предложения paxos или за счет реализации большинства операций чтения из кластера. В приведенных выше основных реализациях узел-лидер, скорее всего, станет узким местом кластера, а ресурсы узла-последователя трудно использовать в полной мере. В ответ на эту проблему paxoskv использует алгоритм "Linearizable Quorum Reads in Paxos" [12] для оптимизации процесса линейно последовательного чтения paxoskv. Фактическая проверка показывает, что производительность повышается более чем на 80+%.
Простое чтение кворума не гарантирует линейную согласованность, такую как традиционные модели NRW, даже в конфигурациях со строгим кворумом, где выбрано R + W > N, оно нарушит линейную согласованность. Как показано на рисунке ниже, считыватель A сначала инициирует запрос на чтение и возвращает новую версию значения x=1, после этого считыватель B инициирует запрос на чтение в определенный момент времени, но возвращает старую версию значения x=0, что разрушает ограничения линейной согласованности. Изображение взято из «Проектирование приложений с интенсивным использованием данных»:
Конкретным алгоритмом реализации является Paxos Quorum Reads (называемый PQR), а изображение взято из статьи «Linearizable Quorum Reads in Paxos» [12]:
Алгоритм разбит на два этапа: чтение кворума и полоскание. На этапе чтения кворума интеллектуальный клиент считывает последний принятый слот от большинства, кроме лидера. Независимо от того, есть ли пробел в принятом слоте, каждая реплика напрямую возвращает самый большой принятый слот, который она видела.Например, если принятые слоты реплики равны [1, 4] и 6, то верните 6 смарт-клиенту. . Интеллектуальный клиент собирает самый большой принятый слот во всех ответах в качестве принятого слота, который инициирует фазу полоскания. Значением этого слота будет значение, которое в конечном итоге возвращается в вызов; но принятый слот может не завершить фиксацию, поэтому смарт-клиент должен подождать, чтобы убедиться, что этот слот завершил постоянную фиксацию, и таким образом достигается строгая согласованность точки зрения клиента.
На этапе полоскания смарт-клиент отправляет запрос любой реплике в наборе реплик на этапе чтения кворума, чтобы проверить, зафиксирован ли соответствующий принятый слот. Если выбранный ответ реплики был зафиксирован, интеллектуальный клиент возвращает значение этой фиксации вызывающей стороне.
Этот метод по-прежнему требует 2 RTT для завершения сильно согласованного чтения.Когда paxoskv реализован, на этапе чтения кворума он возвращает последний принятый слот и последний зафиксированный слот. Если основная реплика возвращает один и тот же принятый слот и зафиксированный слот, это фактически самые последние данные в кластере, другими словами, ограничение линейной согласованности гарантируется. Поэтому в большинстве сценариев в paxoskv линейная согласованность может быть достигнута только с одним RTT.
три,Резюме и перспективы
С момента появления алгоритма Paxos в 1989 году [9] многие тяжеловесные продукты в отрасли обеспечивают высокую доступность и улучшенную согласованность данных на основе алгоритма Paxos или его вариантов, таких как знакомый Google Chubby [14], Apache Zookeeper [15]. ] ], относительно новые etcd [16] и consul [17] и т.д. Однако эти реализации сильно зависят от централизованного ведущего узла, поэтому такие системы в основном могут быть развернуты только в IDC или между IDC в одном городе.Мы называем этот тип протокола протоколом на основе лидера.
Алгоритм Paxos [9] всегда был горячей темой в академическом мире.Относительно новые результаты исследований включают протокол Mencius [18] и протокол EPaxos [19], оба из которых являются протоколами без лидеров. цель многоточечной записи, его задержка фиксации по-прежнему зависит от самого медленного узла в кластере. В то время как протокол EPaxos используется в практических проектах, основной недостаток заключается в том, что он обычно требует 3/4 (больше, чем обычное большинство [n/2]+f) узлы нормально взаимодействуют, за чем следует высокая сложность разработки протокола. Поэтому, хотя Mencius [18] и EPaxos [19] лучше решают проблему многоточечной записи, из-за указанных выше ограничений их нельзя развернуть в сценариях с высокой задержкой между репликами, например, между несколькими IDC в разных местах.
Еще один способ справиться с протоколами на основе лидеров, которые могут быть написаны только в одной точке, — это шардинг, такой как Google Spanner [20], ZooNet [21] и Bizur [22], но ложка дегтя в этих решениях заключается в том, что данные статически секционированы, и создание журнала с несколькими пакетами с разделением в качестве детализации в определенной степени снижает возможность параллелизма. При реальных бизнес-нагрузках местоположение данных обычно динамически меняется время от времени, поэтому для системы хранения идеально применять соответствующие политики для динамической настройки доступа для чтения/записи к объектам данных в соответствии с такими параметрами, как шаблоны бизнес-доступа и нагрузка на сервер Точка доступа. На следующем этапе итерации paxoskv сосредоточится на создании следующих двух основных функций:
3.1 Access patterns/Load aware
Как было сказано выше, внутри одного набора paxoskv использует последовательное хеширование для разбрасывания разных ключей по разным узлам, но если распределение ключей бизнеса относительно стабильно, то есть определенная часть ключей стабильна в фиксированном IDC для чтения Write, то более естественной корректировкой будет отправка запросов на чтение и запись этой части ключа ближайшему к клиенту узлу, чтобы добиться более оптимизированной сквозной задержки. Подобно дизайну кражи работы [13], более общая абстракция заключается в динамической настройке ближайшей точки доступа для каждого ключа с использованием различных стратегий распределения ключей в соответствии с различными шаблонами доступа. Точно так же мы можем динамически мигрировать некоторые ключевые точки доступа в соответствии с нагрузкой между узлами, чтобы добиться более разумного эффекта использования ресурсов на уровне всего кластера.
3.2 Lightweight Multi-Key Transaction
После того, как paxoskv был запущен в рамках BIGO, он получил много отзывов и требований, большинство из которых касаются усиления возможностей производства.Среди них, наиболее насущным требованием с технической стороны является реализация атомарности нескольких ключевых операций, таких как в бизнес-сценариях, связанных с подарками. По сути, это процесс A минус B плюс. В следующей итерации paxoskv будет обеспечивать облегченные транзакции с несколькими ключами для нескольких наборов.
Четыре,урожай и спасибо
От проектирования и разработки paxoskv до запуска и внедрения технология BIGO глубоко осознала проблемы и компромиссы, возникающие при разработке надежной распределенной системы хранения. Например, как протестировать и проверить правильность системы и как проверить способность системы к самовосстановлению после обнаружения неисправности. В качестве другого примера мы выбрали журнал multi-paxos с детализацией ключей.Хотя он дает преимущества с точки зрения многоточечной записи и улучшения параллелизма, он также усложняет изменения членов кластера и глобальные резервные копии моментальных снимков. Мы подробнее остановимся на этих вопросах в последующих введениях, и я хотел бы воспользоваться этой возможностью, чтобы поблагодарить всех студентов, которые дали нам ценные предложения и отзывы!
использованная литература
[1]:http://ssdb.io/zh_cn/
[2]:https://github.com/pika/pika
[3]:https://en.wikipedia.org/wiki/Replication_(computing)#Primary-backup_and_multi-primary_replication
[4]:https://www.cs.cornell.edu/courses/cs6410/2017fa/slides/22-p2p-storage.pdf
[5]:https://cloud.google.com/spanner/docs/replication
[6]:http://muratbuffalo.blogspot.com/2018/11/sdpaxos-building-efficient-semi.html
[7]:https://www.slideshare.net/InfoQ/consensus-why-cant-we-all-just-agree
[8]:http://vldb.org/pvldb/vol5/p1004_hoangtamvo_vldb2012.pdf
[9]:https://en.wikipedia.org/wiki/Paxos_(computer_science)
[10]:https://github.com/facebook/rocksdb
[11]:https://dev.mysql.com/doc/refman/5.7/en/replication-gtids-howto.html
[12]:https://www.usenix.org/system/files/hotstorage19-paper-charapko.pdf
[13]:https://en.wikipedia.org/wiki/Work_stealing
[14]:Chubby,https://static.googleusercontent.com/media/research.google.com/zh-CN//archive/chubby-osdi06.pdf
[15]:Zookeeper,https://github.com/apache/zookeeper
[16]:etcd,https://github.com/etcd-io/etcd
[17]:consul,https://github.com/hashicorp/consul
[18]:Mencius,https://www.usenix.org/legacy/events/osdi08/tech/full_papers/mao/mao.pdf
[19]:EPaxos,https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf
[20]:Spanner,https://www.usenix.org/system/files/conference/osdi12/osdi12-final-16.pdf
[21]:Zoonet,https://www.usenix.org/system/files/conference/atc16/atc16_paper-lev-ari.pdf
[22]:Bizur,https://arxiv.org/abs/1702.04242
[23]:Raft,https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro
[24]:WPaxos,https://cse.buffalo.edu/tech-reports/2017-01.pdf
[25]:http://courses.cse.tamu.edu/caverlee/csce438/readings/dynamo-paper.pdf
(Источник рукописи из BIGO technology из СМИ)