предисловие

Распределенная система храненияПервоочередной вопрос, стоящий перед ним, заключается в том, какмассивные данныераспространяется вразличные узлы храненияначальство. Является ли интерфейс верхнего уровняKV место хранения,хранилище объектов,блочное хранилище, илихранилище столбцов, в целом согласны в этом вопросе. Эта статья покажет, какРаспределенная система хранениясерединаСтавьте цели по распространению данныхи необязательноплани попытаться обобщить и взвесить их взаимосвязь, преимущества и недостатки.

текст

(1) Показатели

Предположим здесьцелевые данныедаkeyидентифицированныйблок данныхилиобъект. в содержащемнесколько узлов храненияв кластере,Алгоритмы распределения данныхтребуется для каждого заданногоkeyуточнитьОдинилинесколькосоответствующийузел храненияБыть ответственным за,Алгоритмы распределения данныхЕсть две основные цели:

Единообразие: для разных узлов хранениянагрузкадолженсбалансированный;
Последовательность: один за разkeyпройти черезАлгоритмы распределения данныхпринадлежитРезультаты раздачидолжны держатьВ основном стабильно, даже если узел хранения изменится.

Можно видеть, что эти две цели в определенной степенипротиворечивыйиз. когда естьДобавление или удаление узла хранения, для сохранения стабильности следуеткак можно меньшепрогрессдвижение данныха такжеперераспределять, что неизбежно приведет кНесбалансированная нагрузка. такое же преследованиеЧрезвычайно однородныйтакже привести к большемуперенос данных.

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

масштабируемость производительности: Это основное соображение заключается в том, что алгоритм относительноМасштаб узла храненияизвременная сложность. Для масштабируемости всей системы алгоритм распределения данных не должен значительно увеличивать время работы по мере увеличения размера кластера.
Учитывайте неоднородность узлов: В реальном машиностроении разныеузел храненияможет быть большойпредставлениеилиРазница в емкости, хороший алгоритм распределения данных должен справляться с такимигетерогенный,поставкаформа взвешенных данных.
Изолировать домены сбоя:длявысокая доступность данных, алгоритм распределения данных должен быть для каждогоkeyоказатьсянабор узлов хранения, эти узлы могут обеспечиватьзеркальная копия данных, и, возможно, что-то вродеКод стиранияметод копирования. Алгоритм распределения данных должен пытатьсяизолироватьДомены сбоя для этих реплик, такие какразные компьютерные комнаты,разные стойки,разные переключатели,разные машины.

(2) Эволюция

После прочтения показателей оценки алгоритма мы представим некоторые возможные варианты решения и проанализируем их преимущества и недостатки. Предположим здесьkeyстоимость достаточно рассеяна.

1. Hash

Простая и интуитивно понятная идея состоит в том, чтобы напрямую использоватьHashрассчитать, простоKeyДелатьхэшназадпо модулю количество узлов. Видно, что вkeyдостаточно рассеянный,единообразиедоступно, но один разсоединение узлаилипокидать, будут затронуты все исходные узлы.стабильностьНе о чем говорить.

2. Согласованный хэш

последовательностьHashможно очень хорошо решитьпроблемы со стабильностью, вы можете конвертировать всеузел храненияустроен в концеHashкольцо, каждыйkeyв вычисленияхHashпозжепо часовой стрелкенайти первыйузел храненияхранить. И когда есть узлыПрисоединяйсяилипокидать, влияет только на узел вHashзвонитьрядом по часовой стрелкеизпоследующий узел. Но это принеслоединообразие, даже если узлы хранения можно расположить равноудаленно,количество узлов хранениявнести изменениянеоднородность данных. И эта возможностьмножественная неоднородностьВ инженерной практике это неприемлемо.

3. Постоянный хеш с ограничением нагрузки

последовательностьHashимеютНеравномерно при смене узловПроблема.Googleсуществует2017Согласованное хеширование с ограниченными нагрузками было предложено для контроля этогостепень неравномерности. Проще говоря, алгоритм даетHashПо одному на каждый узел в кольцепредел нагрузкиза1 + eразсредняя нагрузка,этоeМожет быть настроен. когдаkeyсуществуетHashзвонитьпо часовой стрелкеНайдя подходящий узел, он оценит егонагрузкаБыло ли этодостичь верхнего предела,еслидостигнут предел, нужно продолжить поискузел послевыделить.

Как показано выше, предполагая, что каждое ведротекущая кепкада2, доступ к красным шарам осуществляется по серийному номеру, когда номер6Когда прибудет красный шар, найдите первый встречный по часовой стрелке.B（3，4）,C（1，5）ужедостичь верхнего предела, так что он, наконец, помещается в ведроAвнутри.

Наиболее привлекательной частью этого алгоритма является то, чтокогда узел меняется, объем данных, которые необходимо перенести, составляет1/e^2относится кколичество узловиликоличество данныхне имеют значения.

То есть когдаМасштабирование кластерачас,перенос данныхсущественно не увеличивается. Кроме того, пользователь может настроитьeзначение для контроляединообразиеа такжестабильностьБаланс междуобмен времени на пространствоалгоритм. В общем, будь топоследовательность Hashвсе ещес ограничением нагрузкиизпоследовательность Hash, не могу решитьНеоднородность узловПроблема.

4. Согласованный хеш с виртуальными узлами

чтобы решитьнеравномерная нагрузкаа такжегетерогенныйпроблему можно найти впоследовательность Hashвведены на основаниивиртуальный узел. которыйhashна рингекаждый узелнетдействительныйизузел хранения, новиртуальный узел. действительныйузел храненияСогласно егоразные веса,соответствоватьОдинилинесколько виртуальных узлов, все попадающие на соответствующий виртуальный узелkeyпосредствомУзел хранения отвечает за.

Как показано на рисунке ниже, узел храненияAответственный(1,3],(4,8],(10, 14], узел храненияBответственный(14,1],(8,10].

Проблема этого алгоритма в том, чтофактический узел храненияизПрисоединяйсяилипокидать,повлияетнесколько виртуальных узловперераспределениемного узловучаствовал вперенос данныхприходить.

Кроме того, на практикевиртуальный узелпереназначить нановый фактический узел, эта часть данных должна бытьтраверспублично заявитьотправить на новый узел. нам нужен более подходящийсегментация виртуальных узлова такжеРаспределение,То естьФрагментация.

5. Шардинг

Фрагментациябудетхэш кольцосократить доОсколки одинакового размера, затем поместите этиФрагментациясдаватьразные узлыБыть ответственным за.

Обратите внимание на упомянутое вышевиртуальный узелимеет оченьсущественная разница:Разделение осколков и выделение осколков не связаны.

Одинвыход узлакогда он отвечает заФрагментацияЭто не нужносливаться по часовой стрелкеДля более поздних узлов это может быть более гибкимразделить всекакв общем и целомсдаватьлюбой узел. На практикеФрагментацияСделать большеМинимальная миграция данныха такжеРезервный блок.

И именно из-за вышеупомянутогоразъединение, что эквивалентно преобразованию исходногоkeyприбытьузелизкартаРазделить на два слоя. нужен одинновый механизмвыполнятьФрагментацияприбытьузел храненияизкарта. потому чтоколичество осколковотносительноkeyместа уже мало иКоличество определяется, который можно инициализировать более точно, и ввестиЦентральная служба каталоговприйти в соответствии сузел живИсправлятьОтображение осколков. В то же время этокартографическая информацияуведомить всехузел храненияа такжеклиент.

Картинка вышеРаспределенное хранилище KV ZeppelinсерединаФрагментация,Key Spaceпройти черезHashприбытьФрагментация,Осколки и их копиисопоставляется сконечный узел хранения Node Server.

6. Алгоритм CRUSH

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

Количество информации о сопоставлении фрагментов:избегатьЦентральная служба каталогова такжеузел храненияа такжемежду клиентамимного взаимодействияИнформация о сопоставлении осколков, вместоузел храненияиликлиентпо себенебольшое количествоа такжестабильностьТопология узлов кластера и определенные правила вычисляют карту сегментов сами по себе.
Идеальное разделение домена сбоя:служба поддержкиИерархияизуправление доменом сбоя,будеттот же осколокизразные копииРазделить по конфигурацииразные уровниизв домене сбоя.

клиентилиузел храненияиспользоватьkey,узел храненияизТопологияа такжеАлгоритм распределения, независимоМестоположение осколкарасчет для получения набора ответственных соответствующихФрагментацияа такжекопироватьизместо хранения.

Как показаноодно позиционированиепроцесс и, наконец, выбралиrowвнизcab21,cab23,cab24Три узла хранения в трех корпусах.

когдаИзменения узловкогда из-заТопология узлаизменения коснутсянесколько осколковДанные переносятся, как показано на следующем рисунке:новый узелвызванныйперенос данных. через доброАлгоритм распределения, ты можешь поправитьсябалансировки нагрузкиа такжестабильность,CRUSHпри условииUniform,List,Tree,StrawЧетыре алгоритма распределения.

(3) Случаи применения

ОбщийРаспределенная система храненияв основном используя что-то вродеФрагментацияизРаспространение данных и методы позиционирования:

Cassandra/Dynamo:использоватьФрагментацияпуть и черезGossipПротокол связывается между одноранговыми узлами;
Redis Cluster:будетkey Spaceбыть разделен наslots, также используяGossipпротокол связи;
Zeppelin: разбивает данные наPartition,пройти черезMetaКластер предоставляетЦентральная служба каталогов;
Bigtable: разрезать данные наTablet, аналогично изменяемому сегментированию,Tablet ServerФрагментация может быть выполнена, и окончательная информация о фрагментации записывается вChubbyсередина;
Ceph:использоватьCRUSHкстати, поцентральный кластер Monitorобеспечивать и поддерживатьТопология кластераИзменение.

Добро пожаловать в технический публичный аккаунт: Zero One Technology Stack

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