Библиотека сайта rus-linux.net
Кластеризация согласно консенсусу
Оригинал: Clustering by Consensus
Автор: Dustin J. Mitchell
Дата публикации: July 12, 2016
Перевод: Н.Ромоданов
Дата перевода: январь 2017 г.
Дальнейшие расширения
Конечно, есть много вариантов, как мы могли бы расширить и улучшить эту реализацию.
Протокол в стиле сплетен
В "чистом" алгоритме Multi-Paxos узлы, которые не в состоянии получать сообщения, могут на много слотов отставать от остальной части кластера. До тех пор, пока с помощью переходов машины состояний не будет достигнуто текущее состояние распределенной машины, эта конструкция будет продолжать работать. Чтобы прочитать состояние, клиент запросит выполнение перехода машины состояний, который фактически не изменит состояние, но возвратит нужное значение. Этот переход выполняется в масштабе кластера, гарантируя, что всем будет возвращено одно и то же значение, зависящее от состояния слота, в котором оно запрашивается.
Даже в оптимальном случае это происходит медленно и потребуется несколько обращений для того, чтобы просто прочитать значение. Если распределенное хранилище объектов делает такой запрос для каждого доступа к каждому объекту, то производительность будет весьма плачевной. Но когда узел, принимающий запросы, отстает, задержка запроса будет значительно больше, поскольку прежде, чем работа узла станет успешной, он должен догнать остальную часть кластера.
Простое решение заключается в реализации протокола в стиле сплетен, в котором каждая роль replica периодически обращается к другим ролям replica для того, чтобы воспользоваться самым приоритетным слотом и запросить информацию о неизвестных слотах. Тогда даже в случае, когда сообщение Decision было потеряно, роль replica будет быстре узнавать о решении от одной из своих коллег.
Согласованное использование памяти
Библиотека управления кластером обеспечивает надежность работы при использовании ненадежных компонентов. Поэтому не нужно увеличивать собственную ненадежность кластера. К сожалению, кластер не будет работать долго без сбоев из-за постоянно растущего использования памяти и увеличение размера сообщений.
В определении протокола роли acceptor и replica образуют "память" протокола, поэтому они должны помнить все. Эти классы никогда не знают, когда они получат запрос для старого слота, возможно, из-за отстающей роли replica или лидера. Поэтому для поддержки корректности, они хранят списки всех решений, принятых с того момента, когда был запущен кластер. Хуже того то, что эти решения передаются между репликами в приветственных сообщений, что для долгоживущего кластера делает эти сообщения огромными.
Один из способов решения этой проблемы заключается в периодической установки "контрольной точки" состояний каждого узла, сохраняющей информацию о каком-то ограниченном числе решений. Узлы, которые настолько устарели, что в них все слоты не достигли контрольной точки, должны сами "перезагрузиться" себя, отключившись от кластера и вновь к нему подключившись.
Долговременное хранение данных
Хотя такое решение будет хорошим для меньшинство членов кластера, с которыми возникают проблемы, оно будет плохим для принимающего узла, поскольку он должен будет "забыть" все значения, которые он принял, и все обещания, которые он давал.
К сожалению, это именно то, что происходит, когда элемент кластера выходит из строя и перезапускается: во вновь проинициализированном экземпляре Acceptor нет никаких записей об обещаниях, которые сделал его предшественник. Проблема заключается в том, что вновь запущенный экземпляр узла занимает место старого экземпляра.
Есть два способа решения этой проблемы. Простое решение заключается в записи состояния принимающего узла на диск и повторное его чтение в момент перезапуска узла. Более сложнее решение - удалить отказавшего членов из кластера и потребовать, чтобы в кластер были добавлены в кластер. Такой вид динамической регулировки членов кластера называется "изменением представления" ("view change").
Изменения представлений
У инженеров-операционистов должна быть возможность изменять размеры кластеров с тем, чтобы выполнять требования по нагрузке и доступности. Простой тестовый проект может начаться с минимальным кластером, состоящим из трех узлов, причем любой из них может выйти из строя без какого-либо существенного воздействия на кластер. Но по мере того, как этот проект продолжает "жить", для увеличивающегося кластера на систему будет возрастать нагрузка.
Кластер, как уже было указано, не может изменить набор своих членове без перезапуска всего кластера. В идеале, кластер сможет поддерживать консенсус в отношении своих членов точно также, как это он делает с переходами машины состояний. Это означает, что можно изменить множество членов кластера (представления — view). Это выполняется с помощью специальных сообщений, относящихся к изменению вида. Но алгоритм Paxos зависит от универсального соглашения о членах кластера, е, поэтому мы должны для каждого слота определить вид.
Лампорт решает эту задачу в последнем абзаце статьи "Paxos Made Simple":
Мы можем позволить лидеру получить α команд прежде, чем состояние множества серверов, которые выполняют i+α-й экземпляр алгоритма консенсуса, будет изменено в зависимости от состояния после выполнения i-й команды машины состояний (Лампорт, 2001).
Идея в том, чтобы каждый экземпляр алгоритма Paxos (слот) воспользовался представлением из более ранних α слотов. Это позволит кластеру в любой момент времени работать, самое большее, с α слотами и, поэтому, при очень малых величинах α все можно будет распараллелить, а для очень большого значения α делает так, что эффект от изменения представлений будет сказывать медленно.
В ранних версия проектах была реализована (и это хорошо запомнилось) поддержка изменений представления (значение α было равно 3). Такое, казалось бы, простое изменение добавило много сложности:
- отслеживание представления для каждого последнего α,
- запоминание состояния слотов и корректное их использование с новыми узлами,
- игнорирование предложений, для которых в наличии нет слота,
- обнаружение отказавших узлов,
- правильная сериализация множества конкурирующих изменений представлений и
- обмен информацией о представлении между лидером и ролью replica.
Результат оказался слишком большим для публикации в этой книге!
Ссылки
Кроме информации из оригинальной статьи об алгоритме Paxos и последующей статьи Лампорта "Paxos Made Simple" [2], в нашу реализацию были добавлены расширения, информацию о которых мы взяли из нескольких других источников. Имена ролей были взяты из "Paxos Made Moderately Complex" [3]. Статья "Paxos Made Live" [4] была полезной, в частности, при создании снимков состояний, а в статье "Paxos Made Practical" описана логика изменения представлений (хотя и не такая, как здесь). В статье "From Viewstamped Replication to Byzantine Fault Tolerance" [5] приведена еще одна точка зрения на изменение представления. Наконец, обсуждение в Stack Overflow оказалось полезным при изучении принципов добавления в систему и удаления из нее членов системы.
- L. Lamport, "The Part-Time Parliament," ACM Transactions on Computer Systems, 16(2):133–169, May 1998
- L. Lamport, "Paxos Made Simple," ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58
- R. Van Renesse and D. Altinbuken, "Paxos Made Moderately Complex," ACM Comp. Survey 47, 3, Article 42 (Feb. 2015)
- T. Chandra, R. Griesemer, and J. Redstone, "Paxos Made Live - An Engineering Perspective," Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (PODC '07). ACM, New York, NY, USA, 398-407.
- B. Liskov, "From Viewstamped Replication to Byzantine Fault Tolerance," In Replication, Springer-Verlag, Berlin, Heidelberg 121-149 (2010)
Перейти к началу статьи.