Базы данных обычно имеют полную поддержку транзакций, но ограничены хранилищем и производительностью одной машины, поэтому появились различные распределенные решения. Недавно я прочитал книгу "Designing Data-Intensive Applications", поэтому сделал краткое изложение для вашего ознакомления. Если что-то не так, пожалуйста, поправьте меня и обсудите это вместе.
модель данных
Модель данных, пожалуй, самая важная часть разработки программного обеспечения, поскольку она влияет на то, как мы думаем, решаем проблемы и пишем код. Большинство приложений создаются с использованием многоуровневых моделей данных, и ключевой вопрос для каждого уровня модели данных заключается в том, как он представлен моделью данных более низкого уровня.
Большинство приложений разрабатываются с использованием объектно-ориентированных языков программирования, поэтому нашим критерием выбора становится то, может ли модель данных хорошо представлять объекты и отношения между ними.
Объекты состоят из различных атрибутов, а отношения между объектами обычно имеют вид «один ко многим/многие к одному» и «многие ко многим».
реляционная модель
Реляционная модель использует таблицы, строки и поля для представления набора сущностей, сущности и атрибута сущности соответственно; идентификатор Id другой сущности хранится в поле одной сущности для представления множества-к-соответствию. одно отношение между сущностями. Используйте отдельную таблицу ассоциаций для хранения идентификаторов идентификаторов двух сущностей, чтобы указать, что сущности строят связь «многие ко многим».
Реляционная модель имеет строгую схему, которая должна быть определена перед записью данных, т. е. запись схемы, аналогичная статической проверке типов (во время компиляции) в языках программирования.
Следующий пример представляет собой реляционное представление резюме из Linked:
модель документа
Он хранится в формате, похожем на JSON, а сохраняемый контент имеет тип документа. Использование естественных вложенных отношений JSON может гибко представлять отношения сущностей один ко многим.Конечно, сохраняя идентификаторы документов, он также может представлять отношения многие к одному и многие ко многим.
Относительно реляционной модели, модель документа уменьшает импеданс между слоем памяти, а код приложения не совпадают, во многих отношениях, лучшая местность.
Модель документа имеет схему времени чтения и не требует схемы для записи. Динамическая (во время выполнения) проверка типов, как в языках программирования.
Для приведенного выше примера резюме представление с использованием модели документа выглядит следующим образом:
графовая модель
Модель графа подчеркивает связь между объектами.Когда приложение связано со многими объектами, и запросы и вычисления выполняются на этих соединениях, необходимо рассмотреть базу данных, использующую модель графа.
Граф состоит из вершин (представляющих объекты) и ребер (отношений между объектами).Сложная модель графа обычно состоит из миллиардов вершин и сотен миллиардов ребер.
Ниже приведен пример социальной сети: между двумя людьми и местом их проживания.
Каждая модель данных имеет соответствующий язык запросов, реляционный тип использует SQL, а модель графа также имеет соответствующий язык запросов для описания характеристик модели графа, но отраслевого стандарта пока нет.
| модель данных | Функции | сцены, которые будут использоваться | модель | база данных |
|---|---|---|---|---|
| модель документа | Используйте что-то вроде JSON для представления объектов, Другие объекты могут быть вложенными, Также можно ссылаться на другие идентификаторы документов сущности. |
Данные обычно автономны, Отношения между документами очень редкие |
режим чтения времени | MongoDB |
| реляционная модель | Используйте реляционные таблицы для представления сущностей и отношений сущностей, Поля реляционной таблицы мозаичны и не могут быть вложены друг в друга. Многие к одному могут быть представлены только путем включения идентификаторов других сущностей. |
онлайн-обработка транзакций, Умеренное количество связей между сущностями |
режим записи | MySQL, SQL-сервер, Oracle |
| графовая модель | Сетчатая структура, состоящая из вершин и ребер. Отношения между сущностями представлены ребрами, Кругом связи, независимые вершины бессмысленны |
сложные отношения сущностей, и будет продолжать увеличиваться |
слабый режим, режим подключения |
Neo4j |
механизм хранения
Мы знакомы с приведенной выше моделью данных, но понимание принципов внутреннего хранения и извлечения данных также очень полезно для нас при проектировании и разработке приложений и выборе базы данных.
Основной функцией базы данных является хранение данных и выполнение последующих запросов и обновлений.В настоящее время существует два основных типа баз данных: традиционные реляционные базы данных (ориентированные на страницы) и базы данных NoSQL (на основе лог-структуры).
ориентированный на страницы
B-дерево — это почти стандартная реализация индекса для баз данных, а B-число разбивает базу данных на блоки или страницы фиксированного размера, обычно в диапазоне 4k-32k, и только одна страница может быть прочитана или записана за один раз. время. Эта конструкция ближе к базовому оборудованию, поскольку диски также состоят из блоков фиксированного размера.
Каждая страница может быть идентифицирована с помощью адреса, при этом одна страница ссылается на другую, подобно указателю, но на диске, а не в памяти, как показано:
Количество ссылок на подстраницы на странице B-дерева называется коэффициентом ветвления. Коэффициент ветвления зависит от размера страницы и размера ключа индекса. Чем больше коэффициент ветвления, тем лучше. (Четырехуровневое дерево страниц размером 4 КБ с коэффициентом ветвления 500 может хранить до 256 ТБ)
При запросе данных начните с корневой страницы (обычно кэшированной в памяти) и ищите страницы, которые соответствуют диапазону условий на основе ссылок на страницы, вплоть до конечных узлов.
Когда данные обновляются, конечный узел находится, и страница диска перезаписывается новыми данными.
Когда данные вставляются и удаляются, это будет включать разделение и слияние страниц для поддержания баланса B-дерева.
Чтобы обеспечить высокую производительность запроса и записи данных, база данных обычно кэширует данные страницы в памяти.При обновлении данных данные на диске не будут обновляться немедленно, но сначала будут обновлены данные страницы в кэше памяти. , а журнал WAL будет добавляться и записываться синхронно (журнал упреждающей записи), который асинхронно сбрасывает грязные страницы из памяти на диск (заменяет случайную запись на диск последовательной записью). При восстановлении после сбоя базы данных этот журнал используется для восстановления B-дерева до согласованного состояния.
структура журнала
На основе режима хранения с журнальной структурой каждый раз, когда данные добавляются или обновляются, только данные добавляются в определенный файл журнала, и когда файл превышает определенный размер, новый файл открывается для записи.
Каждый сегмент хранения структуры журнала представляет собой серию пар ключ-значение, но для облегчения последующего запроса данных пары ключ-значение необходимо отсортировать по ключу в файле.Таблица сортированных строк (Sorted String Table) называется SSTтабл.
Чтобы сохранить определенное количество файлов журнала, несколько сегментов файлов объединяются (алгоритм слияния).При появлении нескольких одинаковых значений ключей старые перезаписываются новыми значениями, чтобы гарантировать, что объединенный сегмент имеет один и тот же ключ. однажды.
Разреженный индекс файла ключа к файлу журнала, хранящийся в памяти, достаточно ключа для каждых нескольких килобайт файла сегмента, поскольку несколько килобайт можно просканировать очень быстро. (Частичные записи можно группировать в блоки, сжимать и записывать на диск)
Как создавать и поддерживать SSTable (гарантированное хранение в соответствии с порядком ключей)
- При записи данных (добавить, удалить, изменить) добавить их в сбалансированную древовидную структуру (такую как красно-черное дерево) в памяти, это дерево памяти называется memtable;
- Чтобы избежать потери данных, журнал WAL будет записываться в таблицу памяти путем одновременного добавления (используется для восстановления базы данных после сбоя);
- Когда memtable превышает определенный порог (обычно несколько мегабайт), он записывается на диск в виде файла SSTable. Новый файл SSTable становится последней частью базы данных.
При запросе данных сначала пытайтесь найти в таблице памяти, а затем в нескольких сегментах файла. (путем объединения сегментов файлов для поддержания определенного числа для обеспечения эффективности поиска)
Этот механизм хранения, основанный на принципе слияния и сжатия отсортированных файлов, часто называют механизмом хранения LSM.
Алгоритм дерева LSM может работать медленно при поиске несуществующих ключей. Для оптимизации этого доступа обычно используются дополнительные фильтры Блума.
Основная идея LSM-дерева
Сохраните серию SSTables, объединенных в фоновом режиме, и продолжайте работать, даже если набор данных намного больше доступной памяти. Поскольку данные хранятся по порядку, запросы диапазона (сканирование всех ключей выше некоторых минимальных и максимальных значений) могут выполняться эффективно, а запись на диск выполняется последовательно, поэтому может поддерживаться очень высокая пропускная способность записи.
дела
В системе базы данных могут возникнуть различные проблемы:
- Программное и аппаратное обеспечение базы данных может выйти из строя в любое время (включая половину операции записи).
- Приложение может вылететь в любой момент (в том числе посреди серии операций)
- Отключение сети может разорвать соединение между приложением и базой данных или соединение между базами данных.
- Несколько приложений могут одновременно записывать в базу данных, перезаписывая изменения друг друга.
- Приложение может считывать бессмысленные данные, поскольку данные обновляются лишь частично.
- Условия гонки для применения QC могут привести к различным неожиданным результатам.
Транзакции всегда были предпочтительным механизмом для упрощения этих вопросов. Транзакция — это способ, с помощью которого приложение может объединить несколько операций чтения и записи в одну логическую единицу. Концептуально все операции чтения и записи в транзакции выполняются как одна операция: вся транзакция либо завершается успешно, либо терпит неудачу и откатывается. В случае сбоя приложение может безопасно повторить попытку. Для транзакций обработка ошибок приложения намного проще, и не нужно беспокоиться о частичных сбоях.
Безопасность, обеспечиваемая транзакцией, описывается ACID. А именно: атомарность, непротиворечивость, изоляция, долговечность и цель установить точные условия отказоустойчивости в базе данных.
Один объект против нескольких объектов
Под транзакцией обычно понимается механизм объединения нескольких операций над несколькими объектами в единую единицу выполнения. Но многие распределенные базы данных обеспечивают атомарность и изоляцию только одного объекта (атомарность обеспечивает восстановление после сбоя за счет синхронной записи журналов; изоляция обеспечивает однопоточный доступ путем блокировки каждого объекта), а также более сложные атомарные операции, такие как автоматическое увеличение и CAS. Поэтому обратите на это внимание и посмотрите, соответствует ли это вашему сценарию приложения.
Помимо работы со сложной атомарностью и изоляцией, многообъектные транзакции также предполагают кросс-секционирование в распределенных сценариях (разделы могут не находиться на разных машинах), то есть распределенные транзакции.
уровень изоляции
Если две транзакции не затрагивают одни и те же данные, они могут безопасно выполняться параллельно, поскольку ни одна из них не зависит от другой. Проблемы параллелизма возникают только тогда, когда одна транзакция считывает данные, одновременно измененные другой транзакцией, или когда две транзакции пытаются одновременно изменить одни и те же данные.
Ошибки параллелизма трудно обнаружить с помощью тестирования, потому что такие ошибки возникают только в определенное время и их трудно воспроизвести. По этой причине базы данных всегда пытались скрыть проблемы параллелизма от разработчиков приложений, обеспечивая изоляцию транзакций. Чем сильнее уровень изоляции транзакций, тем больше проблем с параллелизмом можно избежать.Например, сериализуемость гарантирует, что эффект транзакции такой же, как и при последовательном выполнении, но это означает снижение производительности параллелизма. Таким образом, системы баз данных часто используют более слабые уровни изоляции, чтобы предотвратить некоторые, но не все, проблемы параллелизма, поэтому понимание этого важно для разработки правильного приложения.
| уровень изоляции | грязное письмо | грязное чтение | неповторяемое чтение (Смещение чтения/фантомное чтение) |
потерянное обновление | писать предвзятость (Запись данных имеет пересечение) |
писать предвзятость (Запись данных без кроссовера) |
|---|---|---|---|---|---|---|
| читать незафиксированные | ✓ | — | — | — | — | — |
| чтение зафиксировано | ✓ | ✓ | — | — | — | — |
| Повторяемая изоляция чтения/снимка | ✓ | ✓ | ✓ | ✓ | ✓ | — |
| Сериализация | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
грязное письмо
Грязная запись означает, что транзакция перезаписывает незафиксированные данные другой транзакции, а существующий уровень изоляции гарантирует отсутствие грязной записи. Базы данных часто используют блокировки строк для предотвращения грязной записи.
грязное чтение
Грязное чтение означает, что транзакция записала часть данных без их фиксации, а это означает, что другая транзакция прочитала эту часть незафиксированных данных.
неповторяемое чтение
Данные, считанные дважды одной и той же транзакцией (отклонение чтения), или количество прочитанных записей (фантомное чтение) несовместимы.
потерянное обновление
Две транзакции одновременно читают данные и обновляют их. Обе транзакции успешно обновлены. Логика обновления основана на ранее прочитанном значении, но фиксация транзакции изменит ранее прочитанное значение, что приведет к потере обновлений. Типичный сценарий: чтение -> изменение -> запись.
писать предвзятость
Перекос записи можно рассматривать как обобщение проблемы потерянных обновлений. Перекос записи может возникнуть, если две транзакции читают одни и те же объекты, а затем обновляют некоторые из них (разные транзакции могут обновлять разные объекты).
чтение зафиксировано
Read commit предоставляет две гарантии
- При чтении из базы данных видны только зафиксированные данные (без грязных чтений).
- При записи в базу данных могут быть перезаписаны только те данные, которые уже были записаны (без грязных записей).
Повторяемая изоляция чтения/снимка
База данных, которая поддерживает изоляцию моментальных снимков, хранит разные зафиксированные версии объекта, потому что различным текущим транзакциям может потребоваться видеть состояние базы данных в разные моменты времени. Этот метод называется многоверсионным контролем параллелизма (MVCC, multi-version concurrency control).
Когда транзакция начинается, ей присваивается уникальный, постоянно увеличивающийся идентификатор транзакции (txid). Всякий раз, когда транзакция записывает что-либо в базу данных, записываемые ею данные помечаются идентификатором транзакции записи.
Транзакция может найти объект, если выполняются следующие два условия:
- Когда начинается транзакция чтения, транзакция, создавшая объект, зафиксирована.
- Объект не помечен для удаления, или если он помечен для удаления, транзакция, запрашивающая удаление, еще не была зафиксирована в начале транзакции чтения.
Для потерянных обновлений и отклонений записи с пересечением данных база данных может комбинировать интервалы моментальных снимков, чтобы автоматически обнаруживать потерянные обновления и прерывать соответствующую транзакцию. ноПовторяемое чтение MySQL/InnoDB не обнаруживает потерянные обновления. Некоторые авторы считают, что данные можно назвать изоляцией моментальных снимков только тогда, когда можно предотвратить потерю обновлений данных, поэтому в соответствии с этим определениемMySQL не обеспечивает изоляцию моментальных снимков.
На уровне изоляции повторного чтения MySQL/InnoDB вы можете использовать блокировку чтения (выбрать для обновления) или сравнить и установить CAS, чтобы избежать потери обновлений.
Важно отметить, что если база данных разрешает чтение предложений where из старых моментальных снимков, этот оператор может не защитить от потерянных обновлений, поскольку условие where может быть истинным, даже если происходит другая одновременная запись.
Сериализация
Однако для непересекающейся девиации записи записанных данных можно избежать только сериализованным уровнем изоляции, а объект блокировки можно искусственно внедрить в базу данных посредством материализованного конфликта на уровне приложения.
Существует три способа реализации уровня изоляции сериализации:
- Буквально последовательное последовательное выполнение транзакций
- двухфазный замок(2PL, двухфазные блокировки), добавляя общий замок на объект операции чтения и эксклюзивную блокировку на объект записи записи, общий замок может быть обновлен в эксклюзивный замок. Общие замки не являются взаимоисключающими, и общие замки являются взаимоисключающими с эксклюзивными замками и эксклюзивными замками. В то же время база данных автоматически определяет мышление между транзакциями и прервать. Двухфазный - это так называемый механизм контроля пассивного параллелизма.
- оптимистичные методы управления параллелизмом,Сериализуемая изоляция моментальных снимков SSI(сериализуемая изоляция моментальных снимков) — это оптимистичный механизм контроля параллелизма, который не блокируется при чтении и записи данных, но обнаруживает конфликты сериализации между операциями записи по определенному алгоритму при фиксации транзакции и определяет, какие из них следует прервать. Преимущество заключается в том, что операции чтения и записи не блокируют друг друга, а запросы только для чтения выполняются на согласованных моментальных снимках, что очень привлекательно для сценариев с большим количеством операций чтения. Но частота прерываний значительно влияет на общую производительность SSI. Транзакции, которые считывают и записывают данные в течение длительного времени, скорее всего, будут конфликтовать друг с другом, поскольку SSI требует, чтобы транзакции, которые считывают и записывают одновременно, были как можно короче.
Распределенная транзакция
В многообъектной транзакции, если разные объекты существуют в разных разделах, необходимо обрабатывать распределенную транзакцию. Когда дело доходит до распределенных транзакций, мы должны ввести двухфазную фиксацию, которая является основной идеей распределенных транзакций.
двухэтапная фиксация
Двухфазная фиксация 2PC (двухфазная фиксация) — это алгоритм реализации атомарной фиксации транзакции на нескольких узлах. Может использоваться внутри базы данных или доступен для приложений в виде транзакций XA.
Двухэтапная фиксация вводит роль координатора, которая в целом разделена на две фазы Конкретный процесс выглядит следующим образом:
- Когда приложение хочет запустить распределенную транзакцию, оно запрашивает у координатора глобально уникальный идентификатор транзакции.
- Приложение запускает одноузловую транзакцию для каждого участника, и каждая одноузловая транзакция несет этот глобальный идентификатор транзакции. Все операции чтения и записи выполняются индивидуально в транзакциях с одним узлом. Если на этом этапе что-то пойдет не так, координатор или любой участник может прервать.
- Когда приложение готово к фиксации, координатор отправляет запрос на подготовку всем участникам с глобальным идентификатором транзакции. Если какой-либо запрос завершается ошибкой или истекает время ожидания, координатор отправляет всем участникам запрос на прерывание для этого идентификатора транзакции.
- Когда участник получает запрос на подготовку, он должен убедиться, что транзакция действительно может быть зафиксирована при любых обстоятельствах. Это включает в себя запись всех данных транзакции на диск (сбой, сбой питания или нехватка места на диске не могут быть причиной для отклонения фиксации позже) и проверку любых конфликтов сумм или нарушений ограничений. После того, как обещание дано, отступать нельзя.
- Когда координатор получает ответы на все запросы на подготовку, он принимает явное решение зафиксировать или прервать транзакцию (зафиксировать, только если все участники согласны). Координатор должен записать это решение в журнал транзакций на диске.
- После принятия решения координатора всем участникам отправляется запрос на фиксацию или отказ. Если запрос истекает или завершается ошибкой, координатор должен постоянно повторять попытку.
Неотъемлемая стоимость двухэтапной фиксации: кроме того, весь процесс блокирует ресурсы из-за принудительной очистки и дополнительных сетевых циклов, необходимых для восстановления после сбоя.
Percolator
Percolator – это система, разработанная Google для поэтапной обработки и обновления кластеров больших данных. Она в основном используется для служб индексации веб-поиска Google. После замены исходной системы пакетного индексирования на систему инкрементной обработки на основе Percolator, Google сократил среднюю задержку поиска документов на 50 % при обработке документов с таким же объемом данных.
Percolator — это децентрализованная (без координатора) двухэтапная фиксация, основанная на однострочной транзакции BigTable и реализующая механизм межстрочных транзакций. Кроме того, с версией BigTable с несколькими отметками времени можно достичь уровня изоляции моментальных снимков.
Перколятор опирается на центральный таймер, а не на роль одноточечного координатора, он передается всем клиентам для согласования протокола блокировки, но блокировка протечет, если догонит крах. Percolator предпочитает лениво восстанавливать утекшие блокировки: когда другие клиенты получают () эту строку данных, если они сталкиваются с блокировкой, они выбирают ожидание отката для повторной попытки или очистку блокировки.
Однако, поскольку Percolator использует механизм обнаружения оптимистичных блокировок, он не подходит для одновременных обновлений горячих данных. Я думаю, что это можно решить, внедрив механизм пессимистической блокировки поверх Percolator.
раздел
Разделы, также известные как сегментирование, разбивают набор данных на несколько разделов, каждый из которых хранится на отдельной машине, увеличивая общую емкость хранилища и повышая производительность записи и чтения. Но это также создает новые трудности: база данных должна поддерживать запись и чтение между разделами.
Разделение
Цель секционирования — равномерно распределить данные и запросы по узлам. Если разделы несправедливы или не учитывают горячие данные, то некоторые разделы содержат больше данных или запросов, чем другие, что мы называем перекосом. Разделы данных обычно разбиваются на основе ключей.При рассмотрении перекоса данных особое внимание следует уделять дизайну ключей в соответствии с конкретным алгоритмом разделения базы данных.
Раздел в соответствии с диапазоном KeyУкажите непрерывный диапазон ключей для каждого раздела.Граница ключа раздела обычно автоматически выбирается базой данных. Хорошо, что сканирование диапазона очень простое. Однако, если дизайн ключа неразумен, он будет достигать горячих данных и влиять на эффективность запроса.
Раздел по хешу ключаПосле того, как ключ вычисляется хеш-функцией, он разделяется. Это устраняет риск перекоса и горячих точек, но теряет свойства исходного запроса диапазона ключей.
Некоторые базы данных, такие как Cassandra, используют стратегию компрометации, используя для объявления составной первичный ключ, состоящий из нескольких столбцов. Только первый столбец в ключе используется в качестве основы для хеширования, а остальные столбцы используются в качестве индексов соединения для сортировки данных в SSTables Cassandra. Хотя запрос не может просмотреть таблицу в первом столбце составного первичного ключа, он может выполнить эффективное сканирование диапазона в других столбцах этого ключа, если в первом столбце указано фиксированное значение. Подход с комбинированным индексом обеспечивает элегантную модель данных для отношений «один ко многим».
построение индекса
Мы обсуждали стратегию разделения первичного ключа выше, но на самом деле вспомогательный индекс/вторичный индекс также необходим, особенно в реляционной модели.
Существует два способа построения вспомогательных индексов: локальные индексы и глобальные индексы.
локальный индексРазделение документа Таким образом, при таком подходе к индексированию каждый раздел полностью независим, и каждый раздел поддерживает свой собственный вторичный индекс, который охватывает только документы в этом разделе. Когда данные записываются (добавляются, удаляются, обновляются), необходимо обрабатывать только обновления индекса для данных в разделе. При запросе данных вам необходимо отправить запрос во все разделы и объединить все возвращенные результаты.
Этот метод запросов к многораздельной базе данных иногда называют разбросом/сбором, и он может быть довольно дорогим для запросов на чтение вторичных индексов. Даже если раздел запрашивается параллельно, легко вызвать усиление хвостовой задержки. MongoDB, Cassandra, ElasticSearch, SolrCloud используют этот вторичный индекс разделения документов.
глобальный индексРазделение по ключевым словам, этот метод индексации аналогичен разделению по первичному ключу. По сравнению с индексом партиций документа чтение более эффективно, нет необходимости разбрасывать/собирать все партиции, а клиенту достаточно сделать запрос к партиции, содержащей ключевое слово. Недостатком является то, что запись выполняется медленнее и сложнее, поскольку запись одного документа может повлиять на несколько разделов индекса.
В идеале индекс должен быть всегда актуальным. Каждый документ, записанный в базу данных, немедленно отражается в индексе. В глобальных индексах на основе ключевых слов для этого требуются распределенные транзакции по разделам, которые поддерживаются не всеми базами данных. На практике обновления глобального вторичного индекса обычно асинхронны.
Перебалансировка разделов
По мере увеличения размера набора данных и увеличения пропускной способности запросов для его обработки требуется больше машин. Все это требует данных и запросов для перемещения с одного узла на другой, процесс, называемый ребалансировкой.
Ребалансировка обычно отвечает следующим требованиям:
- После ребалансировки нагрузка (хранение данных, запросы на чтение и запись) должна быть справедливо распределена между узлами в кластере.
- База данных должна продолжать принимать операции чтения и записи во время перебалансировки.
- Перемещайте только необходимые данные между узлами для быстрой перебалансировки и снижения нагрузки на сеть и дисковый ввод-вывод.
Стратегии балансировки можно разделить на несколько типов: фиксированное количество разделов, динамическое количество разделов и пропорциональное разделение узлов.
Фиксированное количество разделовСоздайте больше разделов, чем узлов, и назначьте несколько разделов каждому узлу. Если к кластеру добавляется узел, новый узел может украсть некоторые разделы с каждого текущего узла до тех пор, пока разделы снова не будут распределены справедливо. Таким образом, ElasticSearch использует стратегии секционирования.
Пока раздел перемещается между узлами, количество разделов не меняется, и раздел, соответствующий ключу, не меняется, меняется только узел, на котором расположен раздел. Это изменение происходит не в режиме реального времени (для передачи данных по сети требуется время).В процессе передачи исходный раздел по-прежнему будет принимать запросы на чтение и запись.
Количество разделов обычно определяется при первом создании базы данных и после этого не меняется. Каждый раздел содержит фиксированный процент от общего объема данных, поэтому размер каждого раздела увеличивается пропорционально общему объему данных в кластере. Выбор правильного количества разделов затруднен, если общий размер набора данных трудно предсказать. Слишком большой раздел и перебалансировка и восстановление после сбоя узла становятся дорогими; слишком маленький раздел — слишком большие накладные расходы.
Динамическое количество разделовДля баз данных, секционированных с использованием диапазонов ключей, фиксированное количество секций с фиксированными границами было бы очень неудобно: если произойдет ошибка границ, это может привести к отсутствию данных для некоторых секций. Базы данных, секционированные по диапазонам ключей, часто создают секции динамически.
Когда размер раздела превышает настроенный размер, он будет разделен на два раздела, каждый из которых будет содержать примерно половину данных. Преимущество динамического разделения заключается в том, что количество разделов адаптируется к общему объему данных и может сбалансировать накладные расходы во всех аспектах. Это стратегия, принятая HBase и MongoDB.
Набор данных начинается с малого, и пока он не достигнет точки разделения первого раздела, все записи должны обрабатываться одним узлом, в то время как другие узлы простаивают. Для решения этой проблемы HBase и MongoDB позволяют настроить начальный набор разделов (предварительное разбиение) на пустой базе данных. В случае разделения диапазона ключей для предварительного разделения необходимо заранее знать, как распределяются ключи.
Соотношение разделов по узламКоличество разделов пропорционально количеству узлов, т. е. каждый узел имеет фиксированное количество разделов. Размер каждого раздела увеличивается пропорционально размеру набора данных. При добавлении узлов фиксированное количество существующих разделов случайным образом выбирается для разделения, после чего половина каждого из этих разделенных разделов оказывается занятой.
маршрутизация запросов
Теперь, когда мы разделили набор данных на несколько сегментов, работающих на нескольких узлах, как клиент узнает, к какому узлу подключаться при выполнении запроса. По мере перебалансировки раздела назначение раздела узлам также меняется.
Не ограничиваясь базами данных, эту проблему можно обобщить как обнаружение службы, и обычно есть три решения:
- Клиентам разрешено подключаться к любому узлу, и если этот узел владеет запрошенным разделом, запрос обрабатывается напрямую; в противном случае запрос перенаправляется на соответствующий узел, результат принимается и возвращается клиенту.
- Клиент отправляет запрос на уровень маршрутизации, который решает, какой узел должен обработать запрос, и соответствующим образом перенаправляет его.
- Клиенты знают о назначении разделов и узлов и подключаются напрямую к соответствующему узлу.
Суть поставленного выше вопроса заключается в следующем: как компоненты, принимающие решения о маршрутизации, понимают изменения в отношениях распределения между узлами и разделами? Это сложный вопрос, поскольку он требует согласия всех участников.
Многие распределенные системы полагаются на отдельную службу координации, такую как ZooKeeper, для отслеживания метаданных кластера.
- Каждый узел регистрируется в ZooKeeper, который поддерживает надежное сопоставление разделов с узлами.
- Уровень маршрутизации может подписаться на эту информацию в ZooKeeper и в режиме реального времени отслеживать изменения распределения разделов.
копировать
Репликация означает хранение копий одних и тех же данных на нескольких компьютерах, подключенных через сеть. Репликация данных может принести следующие преимущества:
- Повышенная доступность, система продолжает работать, даже если часть системы выходит из строя
- Масштабирует количество машин, которые могут принимать запросы на чтение, тем самым увеличивая пропускную способность чтения
- Приносит данные ближе к пользователям географически, уменьшая задержку
Трудность с репликацией связана с изменениями в реплицированных данных. В настоящее время существует три популярных алгоритма репликации изменений:Один лидер, несколько лидеров и без лидера, почти все распределенные базы данных используют один из этих трех методов.
Процесс репликации с одним лидером:
- Каждая запись в базу данных должна распространяться на все реплики, иначе реплики будут содержать разные данные. Наиболее распространенное решение называется репликацией на основе лидера или репликацией ведущий-ведомый.
- Одна из реплик назначается ведущей (или главной), и когда клиент хочет произвести запись в базу данных, он должен отправить ее ведущей, которая запишет новые данные в свое локальное хранилище;
- Другие реплики называются последователями (репликами только для чтения, ведомыми), которые будут синхронизировать журнал изменений главной библиотеки и записывать в том же порядке, что и основная библиотека.
- Когда клиент считывает данные из базы данных, он может запросить лидера или ведомого.
синхронный или асинхронный
Важной деталью системы репликации является то, происходит ли репликация синхронно или асинхронно. Синхронная репликация увеличивает время записи данных, а асинхронная репликация приводит к несогласованности данных между репликами, клиенты могут считывать исторические данные, а данные могут быть потеряны при сбое первичной базы данных. Таким образом, ядро системы репликации заключается в том, как поддерживать согласованность реплик и автоматически переключаться при сбое основной базы данных.
Модель согласованности
Модель согласованности — это, по сути, контракт между процессом и хранилищем данных. То есть, если процесс согласен соблюдать определенные правила, то хранилище данных будет функционировать должным образом. Обычно, когда процесс выполняет операцию чтения элемента данных, он ожидает, что операция вернет результат данных после последней операции записи.
В отсутствие глобальных часов очень сложно точно определить, какая запись является последней. В качестве альтернативы нам нужно предоставить другие определения, что приведет к ряду моделей согласованности. Каждая модель эффективно ограничивает значение, которое должно быть возвращено операцией чтения элемента данных.
Примечание. Чтобы не путать с согласованностью транзакций базы данных, согласованность распределенных реплик относится к операциям записи и чтения одного объекта.
ориентированный на данные
Линейная согласованность
Линейная согласованность, также известная как строгая согласованность или атомарная согласованность, требует следующих двух условий:
- Любое чтение может прочитать последние записанные данные определенных данных.
- Порядок операций, наблюдаемых всеми процессами, такой же, как и порядок глобальных часов.
Идея линейной согласованности состоит в том, чтобы система выглядела так, будто у нее есть только одна копия данных, а все операции атомарны. Приложению не нужно беспокоиться о многих проблемах, вызванных множественными копиями, и это идеальная идеальная модель в качестве эталона для других моделей (самая строгая модель согласованности).
В линейно-непротиворечивом хранилище данных нет параллельных операций: должна быть одна и только одна временная шкала, и все операции находятся на этой временной шкале, образуя отношение полного порядка.
последовательная согласованность
Последовательная согласованность впервые появилась в автономной модели многопроцессорной системы с общей памятью, что дало программистам надежную гарантию видимости памяти. Модель последовательной согласованной памяти имеет две основные характеристики:
- Результат любого выполнения такой же, как если бы операции всех процессоров выполнялись в некотором порядке.
- Каждый отдельный процессор работает в порядке, заданном его программой.
- Все операции должны выполняться немедленно или атомарно (видны сразу) по отношению к каждому другому процессору.
Хронологически C1 следует за B2. Для линейной согласованности C1 должен идти после B2, но для последовательной согласованности B2 может стоять после C1.
Последовательная согласованность может иметь неопределенные результаты. Это связано с тем, что последовательность последовательных операций может различаться между процессорами во время разных запусков программы.
Для последовательной согласованности необходимо найти законный процесс последовательного выполнения, который сохраняет исходный порядок в потоке/процессе.
Для линейной согласованности необходимо также найти допустимый процесс последовательного выполнения. Однако этот процесс последовательного выполнения не только сохраняет последовательность внутри потоков/процессов, но также сохраняет последовательность операций между потоками/процессами.
Линейная согласованность может быть определена как имеющая ограничения в реальном времени (real-time constraint) последовательная согласованность.
Лично в области распределенных реплик невозможно найти порядок, о котором мог бы договориться каждый процесс, кроме времени. Поэтому отсылка в области распределенных реплик малозначительна и скорее вызовет путаницу.
причинно-следственная связь
Что касается линейной согласованности, операции чтения и записи гарантированно имеют глобальный порядок, в то время как причинно-следственная согласованность должна гарантировать, что взаимозависимые операции чтения и записи сохраняют один и тот же порядок. ФактическиПричинно-следственная согласованность — это наиболее эффективная и доступная модель строгой согласованности..
Трудность реализации причинно-следственной согласованности заключается в том, как определить и зафиксировать причинно-следственные связи: вам нужно знать, какая операция предшествует какой. Но эта причинно-следственная связь больше связана с приложением верхнего уровня, и нижележащее хранилище не может быть воспринято, поэтому отслеживать все причинно-следственные связи нецелесообразно.
Операции причинности должны иметь приоритет во временной последовательности, поэтому операции сортируются по сериализации или отметке времени (логические часы) в общем порядке, чтобы все операции имели причинно-следственную связь во времени. Таким образом, линейная согласованность заключается в том, что все операции удовлетворяют причинно-следственной согласованности (даже если большинство операций не имеют зависимостей).
окончательная согласованность
Эвентуальная согласованность — это не модель согласованности, гарантии согласованности нет, это просто означает, что при отсутствии обновлений реплики будут консистентными в течение определенного периода времени. Из-за задержки в сети приложение может считывать несогласованные данные в любое время. Возможно, самая слабая из приемлемых моделей согласованности.
клиентоориентированный
Непротиворечивость с точки зрения хранения данных, рассмотренная выше, в моделях причинно-следственной согласованности и более строгой согласованности со стороны клиента не будет неожиданных проблем чтения и записи. Но с более слабыми моделями согласованности возникают различные проблемы чтения и записи.
Согласованность, ориентированная на клиента, обеспечивает гарантии согласованности для одного клиента, чтобы обеспечить согласованность доступа клиента к хранилищу данных, но этоНе предоставляет никаких гарантий согласованности для одновременного доступа разных клиентов..
Клиентоориентированная согласованность состоит из четырех моделей:
- Консистенция монотонного чтения(Консистентность монотонного чтения): если процесс считывает значение элемента данных x, то процесс либо считывает первое прочитанное значение, либо считывает обновленное значение для всех последующих операций чтения x. То есть гарантируется, что клиент не прочитает старое значение.
- Монотонная согласованность записи(Консистентность монотонной записи): операция записи процесса в элемент данных x должна быть завершена до того, как процесс выполнит любые последующие операции записи в x. То есть операция записи клиента гарантированно будет последовательной.
- Согласованность чтения и записи(Согласованность чтения-записи): результат операции записи, выполненной процессом над элементом данных x, всегда виден последующим операциям чтения, выполненным этим процессом над x. Это делается для того, чтобы клиент мог прочитать свое последнее записанное значение.
- согласованность записи-чтения(Согласованность записи-следования-чтения): операция записи, следующая за операцией чтения, выполненной тем же процессом для элемента данных x, гарантированно будет выполняться с тем же или более новым значением, чем значение чтения x. То есть гарантируется, что операция записи клиента в элемент данных основана на последнем значении, прочитанном клиентом.
Но реальность такова, что клиентские сеансы будут переноситься из-за балансировки нагрузки сервера и сбоев сервера, поэтому модель согласованности, основанная на клиентском доступе, ненадежна.
протокол консенсуса
Временная метка Лэмпорта
Мы знаем, что в распределенной системе маловероятно, чтобы все машины имели одинаковые часы (глобальные часы). В 1978 году Лэмпорт предложил в статье логическую метку времени для решения проблемы определения времени событий в распределенных системах. Эта статья является одной из самых цитируемых статей в области распределенных систем.
Временная метка Лампорта представляет собой простую комбинацию двух: временная метка/счетчик + идентификатор узла, правила следующие:
- Каждое событие соответствует метке времени Лампорта, начальное значение равно 0.
- Если событие происходит внутри узла, метка времени в локальном процессе увеличивается на 1.
- Если событие относится к отправляющему событию, метка времени в локальном процессе увеличивается на 1, а метка времени включается в сообщение.
- Если событие принадлежит принимающему событию, временная метка в локальном процессе = Max(локальная временная метка, временная метка в сообщении) + 1
- Порядок событий сортируется по временной метке, и если временные метки совпадают, они сортируются по размеру идентификатора узла.
На рисунке выше общий порядок всех событий узла ABC выглядит следующим образом:
Идея временных меток Лампорта заключается в том, что предпосылка о том, что два события могут установить временную (причинную) связь, заключается в том, произошла ли передача информации между двумя событиями. Таким образом, отметка времени Лампорта гарантирует только правильность причинно-следственной связи (частичный порядок) и не гарантирует правильность абсолютного времени.
трансляция общего заказа
Временные метки Лампорта определяют временные отношения событий посредством доставки сообщений, что приводит к широковещанию общего порядка (протокол для обмена сообщениями между узлами). Вещание полного порядка должно удовлетворять двум свойствам безопасности:
- Надежная доставка, отсутствие потери сообщений: если сообщение доставлено на один узел, оно будет доставлено на все узлы
- Общая упорядоченная доставка, когда сообщения доставляются на каждый узел в одном и том же порядке.
Широковещательная рассылка полного порядка — это именно то, что требуется для репликации базы данных: если каждое сообщение представляет запись в базу данных, и каждая реплика обрабатывает одни и те же записи в одном и том же порядке, то реплики согласуются друг с другом (за исключением временных задержек репликации, которые могут быть связаны с операциями чтения). операция также используется в качестве сообщения для достижения согласованного чтения). Этот принцип называетсярепликация конечного автомата.
Поскольку операции записи и чтения базы данных согласовываются посредством взаимодействия сообщений, в соответствии с отметкой времени Лампорта все операции выполняются в полном порядке, поэтому может быть достигнуто хранение линейной согласованности.
Протокол плота
Raft — это алгоритм консенсуса, разработанный для облегчения понимания. Он эквивалентен Paxos по отказоустойчивости и производительности. Разница в том, что он разбивается на относительно независимые подзадачи и четко решает все основные части, необходимые для реальной системы, фактически разрабатывая вышеописанную трансляцию/репликацию конечного автомата полного порядка.
Демонстрация анимации протокола Raft:thesecretlivesofdata.com/raft/
В кластере Raft сервер может быть одним из трех идентификаторов: лидером, последователем или кандидатом. В нормальных условиях будет только один лидер, а остальные будут последователями. Лидер будет отвечать за все внешние запросы, и если его получит машина, не являющаяся лидером, то запрос будет направлен лидеру.
Raft разбивает проблему на несколько подзадач, которые нужно решать отдельно:
- Выборы лидера
- Репликация журнала
- Изменения членства в кластере
- Безопасность
Для получения подробной информации перейдите по ссылке:
TODO
Будет время проанализировать TiDB (распределенная база данных HTAP с открытым исходным кодом, принимая во внимание как транзакцию, так и анализ). К сожалению, OceanBase не имеет открытого исходного кода.
использованная литература
En. Wikipedia.org/wiki/consis…
En. Wikipedia.org/wiki/s E, но N…
GitHub.com/ohplatform/hermit А…