Обзор книги “Database Internals” (“Распределенные данные”) — часть 2 “Distributed Systems”

Рис.1 “Обложки книг английской и русской”
Рис.1 “Обложки книг английской и русской”
Рис.2 “Содержание книги — часть 2 «Distributed Systems»”
Рис.2 “Содержание книги — часть 2 «Distributed Systems»”

II. Distributed Systems

На самом деле для начала стоит определиться с тем, что считать распределенной системой. Автор дает такое определение

  • состояние (state)
  • шаги (steps)или фазы (phases)
  • и переходы (transitions)между ними
Рис.3 “Different purposes of distributed algorithms”Different purposes of distributed algorithms
Рис.3 “Different purposes of distributed algorithms”

8. Introduction and Overview

Эту главу автор начинает с того, что рассматривает конкурентное выполнение кода

int x = 1;
x += 2;
x *= 2;
Рис.4 “Fallacies of Distributed Computing”Fallacies of Distributed Computing
Рис.4 “Fallacies of Distributed Computing”
Рис.5 “Goals of process-local queues”
Рис.5 “Goals of process-local queues”
Рис.6 “Fair loss link”
Рис.6 “Fair loss link”
Рис.7 “Perfect link”
Рис.7 “Perfect link”
Рис.8 “Distributed Systems Abstractions — Links”
Рис.9 “Two General problem”
Рис.9 “Two General problem”
Рис.10 “Properties of correct consensus protocol”
Рис.10 “Properties of correct consensus protocol”
Рис.11 “System Synchrony”
Рис.11 “System Synchrony”
Рис.12 “Failure Models”
Рис.12 “Failure Models”

9. Failure Detection

Где рассматривается вопрос детектирования произошедших ошибок. Суть в том, что если мы сможем детектировать сбои, то у нас уже не будет проблем описанных в FLP Impossibility Problem.

Рис.13 “Failure detection”

10. Leader Election

Синхронизация все участников алгоритма на каждом шаге является дорогим удовольствием, поэтому часть алгоритмов полагается на наличие лидера (leader)или координатора (coordinator), который отвечает за координацию выполнения шагов распределенного алгоритма. Ожидаемые свойства такого алгоритма приведены на рисунке ниже.

Рис.14 “Properties of leader election algorithm”
Рис.14 “Properties of leader election algorithm”
Рис.15 “Leader election algorithms”
Рис.15 “Leader election algorithms”

11. Replication and Consistency

Модели консистентности важны и нужны для объяснения семантики и поведения системы, когда у нас существует множество копий данных. А множество копий данных помогает нам с отказоустойчивостью (fault tolerance) нашей системы.

Рис.16 “The most important events in the context of replication”
Рис.16 “The most important events in the context of replication”
  • consistency в форме линеаризуемости (linearizability), которую мы обсудим дальше
  • availability в форме ответа на каждый запрос успешно безотносительно свежести данных
  • partition tolerance — устойчивость к сетевому разделению без учета других режимов отказа
Рис.17 “Infamous CAP”
Рис.18 “Harvest and Yield”
Рис.19 “Sequential and concurrent operations”
Рис.19 “Sequential and concurrent operations”
Рис.20 “Types of register”
Рис.20 “Types of register”
Рис.21 “Consistency Model”
Рис.21 “Consistency Model”
Рис.22 “Session models”
Рис.22 “Session models”
Рис.23 “Tunable Consistency”
Рис.24 “Operations for Commutative Replicated Data Types (CmRDTs)”

12. Anti-Entropy and Dissemination

Эта глава посвящена механизмам, которые нужны для работы eventually consistent систем, в которых существуют реплики и расхождение их состояний. В случае tunable consistency вообще разрешается обменивать консистентность на доступность, поэтому требуется механизмы для устранения этих расхождений.

Рис.24 “Communication patterns”
Рис.25 “Communication patterns”
Рис.25 “Anti-entropy mechanisms”
Рис.26 “Anti-entropy mechanisms”

13. Distributed Transactions

В этой главе рассматривается то, как перейти от моделей консистентности с одним объектом и одной операцией к выполнению многих операций атомарно. Эта глава заслуживает самостоятельного прочтения, но если обобщать, то автор рассматривает два варианта алгоритмов atomic commitment algorithms и consensus algorithms.

Рис.27 “Подходы к Distributed transactions”
Рис.28 “Phases of 2 phase commit protocol (2PC)”
Рис.29 “System Architecture of Calvin”
Рис.30 “System Architecture of Spanner”

14. Consensus

Все предыдущие рассмотренные темы позволили нам приблизиться к вершине исследований на тему распределенных систем, а именно к теме консенсуса. Алгоритмы консенсуса позволяют распределенной системе из множества процессов достичь соглашения относительно какого-то значения. С точки зрения теории у таких алгоритмов должно быть следующие три свойства

Рис.27 “Consensus properties”
Рис.31 “Consensus properties”
Рис.32 “Atomic Broadcast properties”
Рис.33 “Zookeeper Atomic Broadcast (ZAB)”
Рис.34 “Participants in Paxos”
Рис.35 “Paxos with improvements”
Рис.36 “Participants in Raft”
Рис.37 “Main components of the Raft algorithm”
Рис.38 “Practical Byzantine Fault Tolerance (PBFT) algorithm phases”

Part II Conclusion

В качестве заключения автор делает recap тех классов алгоритмов, которые были рассмотрены во второй части

Рис.39 “Important classes of distributed algorithms, some of which can be used to implement these consistency models”

--

--

Director of digital ecosystem development department at Tinkoff. Bachelor at applied math, Master at system analysis, Postgraduate studies at economics.

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Alexander Polomodov

Alexander Polomodov

Director of digital ecosystem development department at Tinkoff. Bachelor at applied math, Master at system analysis, Postgraduate studies at economics.