Базы данных. Алгоритмы Paxos

preview_player
Показать описание
Курс «Методы использования СУБД в интернет-приложениях».
Лекция № 10 «Репликация ДКА, алгоритмы Paxos».
Лектор — Константин Осипов.

В этом видео
Задача репликации журнала. Требование к распределённому алгоритму в применении к Paxos. Распределённый ДКА: подход Paxos. Компоненты Paxos. Постановка проблемы взаимоисключающего выбора. Идентификация предложений. Основы, шаги, сценарии работы Paxos. Свойство Liveness. Multi-Paxos, его задачи. Выбор LSN для предложения. Способ выбора лидера. Оптимизация PREPARE-запросов. Протокол клиента. Изменение состава кворума.

VK Team — это миллион возможностей проявить себя. Мы делаем современные и быстрые интернет-сервисы, доступные каждому. На этом канале делимся опытом компании VK, рассказываем о технологиях, наших образовательных проектах и жизни команды.

  1. VK Team
  2. Техносфера
  3. яндекс
  4. гугл
  5. МГУ им. М.В. Ломоносова
  6. google
Рекомендации по теме
Базы данных. Алгоритмы 1:26:42

Базы данных. Алгоритмы Paxos

Алгоритмы распределенного консенсуса 1:10:45

Алгоритмы распределенного консенсуса (RAFT, PAXOS) // Демо-занятие курса «Highload Architect»...

TFTDS / Лекция 1:46:06

TFTDS / Лекция 5 / Single-Decree Paxos

TFTDS / Лекция 1:38:38

TFTDS / Лекция 6 / Multi-Paxos

TFTDS. Семинар 6. 0:59:32

TFTDS. Семинар 6. Алгоритм RAFT. Сравнение с Multi-Paxos

Базы данных. Алгоритм 1:20:20

Базы данных. Алгоритм RAFT

TFTDS. Семинар 5. 0:48:47

TFTDS. Семинар 5. Single-Decree Paxos

Паксос в картинках 0:46:27

Паксос в картинках / Константин Осипов (ScyllaDB)

TFTDS 5. Multi-Paxos 1:23:11

TFTDS 5. Multi-Paxos

Алгоритм консенсуса RAFT: 0:14:08

Алгоритм консенсуса RAFT: подробное объяснение принципов работы...

TFTDS. Семинар 6. 1:19:17

TFTDS. Семинар 6. Алгоритм RAFT

TFTDS 4. Single-Decree 1:32:48

TFTDS 4. Single-Decree Paxos

Алгоритмы согласования // 1:50:09

Алгоритмы согласования // Демо-занятие курса «Microservice Architecture»...

Базы данных. Протокол 1:30:39

Базы данных. Протокол 2РС

L9: Paxos Simplified 0:35:33

L9: Paxos Simplified

TFTDS 6. Paxos 1:33:19

TFTDS 6. Paxos Made Live

Базы данных, лекция 2:27:00

Базы данных, лекция №8 (2013 г.)

What is Paxos? 0:01:32

What is Paxos?

10. Использование баз 2:35:09

10. Использование баз данных. Key-value conflict resolution. | Технострим...

Консенсус на пальцах, 0:43:45

Консенсус на пальцах, или Как договориться в распределенной системе / Владимир Протасов...

Базы данных. Вводная 2:37:42

Базы данных. Вводная лекция

8. Использование баз 2:32:18

8. Использование баз данных. Distributed Consensus. | Технострим

Достижение согласованности. Алгоритмы 1:14:45

Достижение согласованности. Алгоритмы консенсуса

11.8 The final 0:11:47

11.8 The final Sequence Paxos Algorithm

Комментарии
Автор

Классная лекция! Отдельное спасибо лектору!

asvitin
Автор

Огромный респект лектору, так доступно paxos еще никто не объяснял. Просто на пальцах.

АндрейВоробьев-ты
Автор

Не до конца понял как именно нам следует поступать в момент, когда два разных узла одновременно принимают решение отослать сообщение другим узлам
Например:

Дано:
Есть узел А - ServerId = 1
Есть узел Б - ServerId = 2
Есть узел С (он у нас будет только слушать, поэтому нам не важен его Server Id)
У нас Round = 0

Ситуация:
Узел А решает отправить сообщение с Proposal Number "0.1"
Узел Б решает отправить сообщение с Proposal Number "0.2"
Узел С принимает сообщение от узла А и от узла Б

Вопрос:
Каким образом мы решаем эту конфликтную ситуацию, чье сообщение мы принимаем на узле С?
То, которое пришло первым, допустим, первым пришло сообщение с Proposal Number "0.1", следом идет сообщение с Proposal Number "0.2", которое мы бросаем в топку, т.к. его Round не больше уже имеющегося?


На 1:03:30 как раз-таки такая ситуация и происходит у нас одна нода отсылает сообщение "3.1", а другая "3.5"
Есть узел S3, который почему-то сначала принимает сообщение "3.1", а потом также принимает сообщение "3.5"

Константин говорит, что все окей, т.к. сообщение с Proposal Number "3.5" (зеленого цвета) имеет бОльший Proposal Number чем сообщение с Proposal Number "3.1", однако это не так, мы ведь сами до этого говорили о том, что Server Id нужен только, чтобы различать сообщения с одинаковым Round от разных серверов


И второй вопрос:
Что делать если у нас есть узел, на который мы отправили сообщение с Prepare, но который мы не подтвердили, т.е. не дослали на него сообщение Accept?
Мы просто оставляем этот Prepare висеть на узле в надежде, что когда-нибудь этот узел примет более свежий Prepare, а старый отбросит как неподтвержденный?

Dhaizkcnekxockrnr