Консистентно о Консенсусе
Здравствуйте, меня зовут Дмитрий Карловский. А вы на канале Core Dump, где мы берём различные темы из компьютерной науки и раскладываем их по полочкам.
И на этот раз мы постараемся прийти к согласию касательно согласованной классификации алгоритмов обеспечения консенсуса в системах со множеством участников. Разберём разные виды блокировок, бесконфликтных алгоритмов. А так же попробуем выявить их фундаментальные особенности, проявляющиеся на самых разных масштабах.
Вы можете смотреть это как видео, читать это как статью, либо открыть в интерфейсе проведения презентаций.
Согласованность данных
Начнём с консистентности или согласованности. Это — логическая непротиворечивость хранимых данных.
Например, если у Алисы родителем значится Боб, а у Боба родителем значится Алиса, то это явно какая-то лажа. Не могут они быть родителями друг друга одновременно. Данные не консистентны!
Согласованность часто путают с консенсусом. Особенно, когда данные частично хранятся на одном сервере, а частично на другом, но при этом должны быть согласованы друг с другом. Однако, консенсус немного о другом…
Согласие между участниками
Консенсус — это согласие группы участников касательно значения некоторого состояния. Например, если все считают Боба мужчиной, но сам он считает себя вертолётом, то согласия тут не наблюдается. Консенсус не достигнут!
Важно понимать, что даже если у каждого участника состояние само по себе консистентно, между участниками согласия при этом может и не быть. И наоборот, участники могут достигнуть консенсуса касательно несогласованного состояния. Тогда… Эта база данных сломалась. Несите следующую!
Достижение согласия
Все подходы по достижению консенсуса можно разделить на две большие группы…
Первая — это конкуренция за единый источник истины. Участники толпятся вокруг него, толкаются локтями и пытаются внести в него свои изменения. Транзакции в базах данных, атомарные операции в процессоре, протоколы консенсуса в распределённых системах — это всё из этой оперы.
Совершенно иной подход — конвергенция. Она же сходимость. Это когда участники независимо друг от друга меняют каждый своё и только своё состояние. Но при этом они могут подглядывать к соседям и подливать их изменения к себе. А алгоритмы слияния строятся так, чтобы состояния всех участников в конечном счёте сошлись к одному и тому же значению.
Конкуренция за источник истины
Разберём подробнее конкуренцию за источник истины. Это может быть мастер-реплика СУБД, оракул в распределённых системах, основной поток приложения или просто общий участок памяти.
Читать из источника все могут одновременно. Но при попытке записать участник может быть заблокирован, пропуская вперёд более удачливых соседей.
Тут можно выделить два вида блокировок: пессимистичная и оптимистичная.
В базах данных это соответственно пессимистичные и оптимистичные транзакции. В распределённых системах это мастер-слейв репликация и двухфазные коммиты. А во многопоточке это мьютексы и lock-free алгоритмы.
Пессимистичная блокировка
Идея пессимистичной блокировки простая: сначала участник запирает ресурс, затем производит его обновление, по завершении которого ресурс отпирается. Это если ему повезло прийти первым. Если же он пришёл, а ресурс уже кем-то заперт, то он сидит, ничего не делает, и ждёт его отпирания.
Это самый простой и надёжный подход. Однако у него есть проблемы с производительностью. Либо из-за постоянных ожиданий, либо из-за холостых запираний, которые так-то весьма не бесплатны.
Смертельное запирание
Кроме того, этот подход подвержен проблеме смертельного запирания или dead-lock. Это когда два участника успешно запирают два разных ресурса, а потом блокируются при попытке запереть ресурс уже запертый оппонентом. Получается, что при неосторожном обращении с запиранием, участники могут заблокироваться одновременно. Из-за чего не смогут освободить запертые ими ресурсы.
Запирание разве не блокировка?
Тут стоит подчеркнуть разницу между запиранием и блокировкой.
