Пара блогов о распределенных системах

Есть люди, которые пишут много. В том числе и о распределенных системах.

Блог Уиттекера [ссылка] - Single-Decree Paxos, Visualizing Linearizability, Lamport's Logical Clocks,  Two Generals and Time Machines, An Illustrated Proof of the CAP Theorem

Блог Маркуса Чиу [ссылка]  - о распределенных алгоритмах (плюс миллион статей на другие темы).

Блог compiosition.al - здесь интересная статья про алгоритм снимков распределенной системы Чанди-Лэмпорта  [ссылка]

Страница семинара по распределенным системах (посты пишут сами студенты) [ссылка]

Гибридный консенсус

Proof of Stake and the History of Distributed Consensus: Part 1, Nakamoto Consensus, Byzantine Fault Tolerance, Hybrid Consensus, Thunderella [ссылка]

Линеаризуемость (ссылки)

A beginner’s guide to Linearizability [ссылка]
What is “Linearizability”? [ссылка]

Интересное о распределённых системах

On FLP Impossibility [ссылка]
Jeff Hodges Notes on Distributed Systems for Young Bloods [ссылка]
Забудьте САР теорему как более не актуальную [ссылка]

Paxos (ссылки)

1. Byzantine faults, Paxos, and consensus [ссылка]
2. Paxos by example [ссылка] 
3. Understanding Paxos [ссылка]

Логические часы

Про логические часы пишут много, иногда попадаются интересные вещи. Вот, например, некий Стивен Ван Допре сделал реализацию скалярных часов на Питоне [ссылка]. А на coursehero можно почитать про различие между скалярными, матричными и векторными часами [ссылка] (правда, дан только ознакомительный фрагмент лекции).

А какую такую проблему решают матричные часы, которую не могут решить векторные, обсуждают на stackoverflow [ссылка] ? Насколько я понял, матричные часы дают возможность понять, какие обновления достигли всех узлов и, соответственно, информацию о них можно не хранить (сделать чистку).

Некоторые протоколы, которые помогают поддерживать причинно-следственный порядок сообщений в системе, можно найти по [ссылке].  Это протоколы Бирмана-Шипера-Стефенсона и Шипера-Эггли-Сандоза.

О протоколе Бирмана-Шипера-Стефенсона  (а также об алгоритмах синхронизации физических часов) хорошо написано в лекции Бибхаса Гошаля [ссылка]

А ещё мне очень понравились лекции Виджея Гарга [ссылка] - строгая математика, отношения, рефлексивность-транзитивность и всё такое прочее:)

Лекция Николы Драгони (итальянец, преподающий в каком-то датском университете) про логические часы [ссылка]. План его курса по распределённым системам (названия лекций, рекомендуемая литература) - по ссылке. Курс хорош. Сами лекции находятся в Гугле по запросу Nicola Dragoni <название лекции из плана> pdf.

Лекция Антонио Корради (ун. Болоньи) [ссылка] Очень много о групповой рассылке (мультикаст)

Fundamentals of Distributed Computing: A Practical Tour of Vector Clock Systems [ссылка]

Хорошая лекция о логическом (виртуальном) времени и глобальных состояниях Венкатасубраманиана [ссылка]

Обход невозможности записи в контейнерах SquashFS (Singularity)

Скачал тут контейнер RabbitMQ (имя образа rabbitmq.simg), пытаюсь запустить кроличий сервер - ан нет, ошибка could_not_write_file (не может писать в лог). Оказалось, что в этом котейнере используется SquashFS - файловая система, допускающая только чтение. 

Чтоб это обойти, используем образ - подложку (overlay). Создадим образ:
singularity image.create rmq-overlay.simg
Теперь будем запускать экземпляр контейнера RabbitMQ, подложив этот наш новый образ (в который писать можно):
singularity instance.start --overlay rmq-overlay.simg rabbitmq.simg rmq1
Здесь rmq1 - имя экземпляра.

После этого запускаем шелл внутри экземпляра
singularity shell instance://rmq1

Теперь вызов rabbitmq-server отрыбатывает нормально, сервер запускается.

Полезные ссылки: 

• Документация Singularity - страница про overlay [ссылка]
• Обсуждение на github.io про проблемы с контейнерами squashfs [ссылка]

Контейнеры Singularity

Говорят, эта технология скоро унасекомит Докер - якобы работают сингулярные контейнеры быстрее, и с безопасностью всё гораздо лучше. Не очень верится. Изначально Singularity затевался как контейнеры для высокопроизводительных вычислений. Будут ли пользователи из других сфер переходить на них - посмотрим.

По долгу службы приходится разбираться с Singularity, так что время от времени в блоге будут появляться посты на эту тему. Информации об этой технологии гораздо меньше, чем по Докеру, поэтому, надеюсь, мои заметки кому-ниубдь пригодятся.

Рассинхронизация часов

Интересное исследование скорости расхождения показаний часов в распределённых системах: Internal Clock Drift Estimation in Computer Clusters [ссылка]

Из интересного: в спутниках GPS используются атомные часы, поэтому с синхронизацией времени там попроще.

Пара интересных каналов на Youtube

Ken Shamir [ссылка] - распределенные системы, блокчейн, Neo, Ripple
Computerphile [ссылка] - всё на (компьютерном) свете - пакетное радио, большие данные, иск. интеллект, SSH изнутри. Масса всего интересного.

Исследуем elf-файлы

Если захотелось покопаться в бинарниках формата elf, нужно вооружиться тремя инструментами - readelf, nm, objdump. И почитать статьи: How is a binary executable organized? Let's explore it! [ссылка] (из блога одной канадской барышни) и Linux 101: Understanding the insides of your program [ссылка]. Подробнее об nm - в статье 10 Practical Linux nm Command Examples [ссылка] .

Живость и безопасность в распределённых системах

Нашел тут другую формулировку результата FLP (надо уже саму статью почитать наконец) - в полностью асинхронной системе невозможно создать алгоритм консенсуса, который одновременно гарантировал бы отказоустойчивость, живость и безопасность (liveness and safety). Поскольку отказоустойчивостью обычно стараются не жертвовать, выбор приходится делать между живостью и безопасностью. Ситуация очень похожа на ту, что мы видим в CAP-теореме.

Мне очень понравилось видео на эту тему профессора Гупты из Иллинойского университета [ссылка]. А на medium.com есть хорошая статья Safety and Liveness — Blockchain in the Point of View of FLP Impossibility [ссылка], где рассматриваются разные алгоритмы консенсуса.

Линеаризуемость

Это одна из самых строгих моделей согласованности. Кстати, под consistency в CAP-теореме подразумевается именно линеаризуемость.

Оказывается, есть популярное введение в эту тему: A beginner’s guide to Linearizability [ссылка]. Спасибо автору - Владу Михалчеа

Детекторы отказов в распределенных системах

Согласно теорем FLP консенсус невозможен в системах с асинхронными коммуникацией. Чандра и Туэг в статье  Unreliable failure detectors for reliable distributed systems показали, что ситуацию можно исправить за счёт добавления в распределённую систему специального сервиса - детектора отказов. 

С чего начать знакомство с этой темой? Книги по распределённым алгоритмам могут отпугнуть своими формулами и теоремами. Хочется чего-нибудь попроще.

Могу порекомендовать пост Failure Detection in Distributed Systems [ссылка] - довольно приятно и легко написано.

Страх и ненависть в распределённых системах

Очередная лекция  - обзор распределенных систем в целом (автор - Роман Гребенников). Получилось интересно и весело. Много о линеаризуемости, CAP-теореме. Код на Scala, тесты с помощью Jepsen. Видео и текстовая версия. Вот [ccылка].

Пассивная и активная репликация

Два основных подхода к отказоустойчивости при репликации - пассивный (primary-backup, подход с главной репликой) и активный (state machine, машина состояний - или конечный автомат?). В первом случае все обновления идут через главную реплику, они ретранслируются на вторичные реплики. При падении лидера, вторичные реплики выбирают нового. Во втором случае обновления могут идти на любую реплику. Для обеспечения согласованности реплики с помощью некоторого алгоритма консенсуса устанавливают общий порядок примененения обновлений.

Мне понравилось, как это всё изложено у Дермота Келли (из какого-то ирландского университета) в его курсе по параллельным и распределённым системам [ссылка на курс], [ссылка на лекцию об отказоустойчивости].

Покороче - в лекции Донгмана Ли [ссылка].

Португало-бразильский дуэт написал интересную статью об активном подходе [ссылка] под названием A Guided Tour on the Theory and Practice of State Machine Replication.

Некто Альваро Видела написал пост о моделях отказов [ссылка] процессов с выжимкой из  книги  Fault-Tolerant Real-Time Systems: The Problem of Replica Determinism. У него целый ряд постов по этой книге, надо почитать.

Лексемы, идентификаторы, литералы

Вот эти все термины хорошо объяснены в курсе С++ для 9 класса [ссылка]. Думаю, для других языков данные в тексте определения тоже подойдут.

Бессерверные вычисления

Чего?! Бессерверные?!! На пальцах, что ли?

Нет, компьютеры всё еще нужны. Serverless - это просто красивое название для технологии автоматического масштабирования приложений в облаке. Пользователь просто описывает своё приложение в виде набора связанных между собой функций (а-ля микросервисы), грузит их в облако, а платформа сама решает, сколько выделять ресурсов в зависимости от нагрузки. Хорошее введение в предмет: Serverless по стоечкам [ссылка].

PAXOS

блог Understanding Paxos [ссылка] - всего один пост, но зато написано замечательно
Кластеризация согласно консенсусу [ссылка] - описано несколько вариантов Паксоса, дан код

Двухфазная и трёхфазная фиксация

Шехар Джулати о 2PC [ссылка] - краткое описание, как выполняется требование атомарности, связь с CAP
Балрайа Суббиа о 2PC и 3PC [ссылка] - больше об различных видах отказов
Лекция Принстонского университета [ссылка] - отказоустойчивость, живость и безопасность, как это всё связано с 2PC, протокол Straw Man и атомарной фиксации
Разница между протоколами 2PC и X/Open XA [ссылка] - из документации NuoDB