Кинетика больших кластеров / forpes.ru

Главная
Кинетика больших кластеров

Кинетика больших кластеров +17

06.04.2017 09:40

gridem 11 2500 Источник

Краткое содержание

Фатальная ошибка Мартина Клеппмана.
Физико-химическая кинетика уделывает математику.
Период полураспада кластера.
Решаем нелинейные дифференциальные уравнения, не решая их.
Ноды как катализатор.
Предсказательная сила графиков.
100 миллионов лет.
Синергия.

В предыдущей заметке мы подробно разбирали статью Брюера и его одноименную теорему. На этот раз займемся препарированием поста Мартина Клеппмана «The probability of data loss in large clusters».

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

Ответ приведен на этой картинке:

Data loss

Т.е. с ростом числа нод число потерянных данных растет прямопропорционально.

Почему это важно? Если мы рассмотрим размеры современных кластеров, то увидим, что их число с течением времени непрерывно растет. А значит возникает резонный вопрос: стоит ли беспокоиться за сохранность своих данных и поднимать фактор репликации? Ведь это напрямую влияет на бизнес, стоимость владения и проч. Также на этом примере можно замечательно продемонстрировать, как можно выдать математически корректный, но неправильный результат.

Моделирование кластера

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

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

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

Введем следующие обозначения:

$N$ : общее число нод кластера
$A$ : число работоспособных нод (available)
$F$ : число проблемных нод (failed)

Тогда очевидно, что:

$\begin{aligned} N = A + F \\end{aligned}$

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

Теперь запишем кинетические уравнения процессов поломки и восстановления нод кластера:

$\begin{aligned} A & \xrightarrow{k_f} F &(1) \ F & \xrightarrow{k_a} A &(2) \\end{aligned}$

Эти простейшие уравнения говорят следующее. Первое уравнение описывает процесс поломки ноды. Оно не зависит от каких-либо параметров и описывает изолированный выход ноды из строя. Другие ноды в этом процессе не участвуют. Слева используется исходный «состав» участников процесса, а справа — продукты процесса. Константы скорости $k_f$ и $k_a$ задают скоростные характеристики процессов для поломки и восстановления нод соответственно.

Выясним физический смысл констант скоростей. Для этого запишем кинетические уравнения:

$\begin{aligned} \frac{dA}{dt} &= -k_f A + k_a F \ \frac{dF}{dt} &= k_f A - k_a F \\end{aligned}$

Из этих уравнений понятен смысл констант $k_f$ и $k_a$ . Если предположить, что админов нет и кластер сам себя не исцеляет (т.е. $k_a = 0$ ), то сразу получаем уравнение:

$\begin{aligned} \frac{dA}{dt} = -k_f A \\end{aligned}$

Или

$\begin{aligned} A = N e^{-k_f t} \\end{aligned}$

Т.е. величина $1/k_f$ — это период полураспада кластера на запчасти, с точностью до $e/2$ . Пусть $\tau_f$ — характерное время перехода единичной ноды из состояния $A$ в состояние $F$ , а $\tau_a$ — характерное время перехода единичной ноды из состояния $F$ в состояние $A$ . Тогда

$\begin{aligned} \tau_f &\sim \frac{1}{k_f} \ \tau_a &\sim \frac{1}{k_a} \ \frac{\tau_a}{\tau_f} &= \frac{k_f}{k_a} \\end{aligned}$

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

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

$\begin{aligned} \frac{dA}{dt} = 0 \Rightarrow F = A \frac{k_f}{k_a} \\end{aligned}$

С учетом того, что $F \ll N$ (это вполне разумное предположение, в противном случае надо покупать более качественное железо или более продвинутых админов), получаем:

$\begin{aligned} A &\simeq N \ F &= N \frac{k_f}{k_a} \\end{aligned}$

Если положить, что время восстановления $\tau_a$ примерно 1 неделя, а время смерти $\tau_f$ примерно 1 год, получаем, что доля сломанных нод $p_f$ :

$\begin{aligned} p_f = \frac{F}{N} = \frac{\tau_a}{\tau_f} \approx 2\% \\end{aligned}$

Чанки

Обозначим через $U$ — количество недореплицированных (underreplicated) чанков, которые необходимо дореплицировать после выпадения ноды при переходе в состояние $F$ . Тогда для учета чанков, поправим наши уравнения:

$\begin{aligned} A & \xrightarrow{k_f} F + U &(1) \ F & \xrightarrow{k_a} A &(2) \ U + A & \xrightarrow{k_r} H + A &(3) \\end{aligned}$

где $k_r$ — константа скорости репликации процесса второго порядка, а $H$ означает здоровый (healthy) чанк, который растворится в общей массе чанков.

3-е уравнение необходимо пояснить. Оно описывает процесс второго порядка, а не первого:

$\begin{aligned} U & \xrightarrow{k_r} H \\end{aligned}$

Если бы мы так сделали, то получили бы кривую Клеппмана, что не входит в мои планы. На самом деле в процессе восстановления участвуют все ноды, и чем больше нод, тем быстрее идет процесс. Связано это с тем, что чанки с убитой ноды распределяются примерно равномерно по всему кластеру, поэтому каждому участнику необходимо отреплицировать в $A$ раз меньше. Это означает, что итоговая скорость восстановления чанков с убитой ноды будет пропорциональна количеству доступных нод.

Стоит также отметить, что в уравнении (3) слева и справа стоит $A$ , и при этом он не расходуется. Химики бы сразу заявили, что в данному случае $A$ выступает в роли катализатора. И если внимательно подумать, то так оно и есть на самом деле.

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

$\begin{aligned} \frac{dU}{dt} = 0 = k_f A - k_r U A \\end{aligned}$

или

$\begin{aligned} U = \frac{k_f}{k_r} \\end{aligned}$

Удивительный результат! Т.е. количество чанков, которые необходимо отреплицировать, не зависит от количества нод! А связано это как раз с тем, что увеличение числа нод увеличивает результирующую скорость реакции (3), тем самым компенсируя большее количество $F$ нод. Катализ!

Оценим это значение. $\tau_r$ — время восстановления чанков, как если бы у нас была только одна нода. Пусть на ноде надо отреплицировать 5ТБ данных, при этом поток репликации в байтах зададим как 50МБ/с, тогда получим:

$\begin{aligned} U = \frac{\tau_r}{\tau_f} \approx \frac{1 \times 10^5}{3.2 \times 10^7} \approx 3 \times 10^{-3} \\end{aligned}$

Т.е. $U \ll 1$ и можно не бояться за сохранность данных. Тут стоит учесть, что потеря одного чанка из 3-х не приводит к потере данных.

Планирование репликации

В предыдущем расчете мы сделали неявное предположение о том, что ноды мгновенно узнают о том, какие конкретно чанки необходимо отреплицировать, и сразу же начинают процесс их репликации. В реальности это совершенно не так: мастеру необходимо понять, что нода умерла, затем понять какие конкретно чанки необходимо отреплицировать и запустить процесс репликации на нодах. Все это не мгновенно и занимает какое-то время $\tau_s$ (scheduling).

Для учета запаздывания воспользуемся теорией переходного состояния или активированного комплекса, которая описывает процесс перехода через седловую точку на многомерной поверхности потенциальной энергии. С нашей точки зрения у нас будет некоторое дополнительное промежуточное состояние $U^*$ , которое означает, что этот чанк запланировали на репликацию, но процесс репликации еще не начат. Т.е. в следующую наносекунду репликация точно начнется, но не пикосекундой раньше. Тогда наша система примет окончательный вид:

$\begin{aligned} A & \xrightarrow{k_f} F + U &(1) \ F & \xrightarrow{k_a} A &(2) \ U & \xrightarrow{k_s} U^* &(3) \ U^* + A & \xrightarrow{k_r} H + A &(4) \\end{aligned}$

Решая его, находим, что:

$\begin{aligned} \frac{dU}{dt} &= k_f A - k_s U \ \frac{dU^*}{dt} &= k_s U - k_r U^* A \\end{aligned}$

Применяя метод квазистационарных концентраций, находим:

$\begin{aligned} U &= A \frac{k_f}{k_s} \ U^* &= \frac{k_f}{k_r} \ U_{sum} &= U + U^* = \frac{\tau_r}{\tau_f} \bigg( 1 + \frac{A}{\widetilde{A}} \bigg) \\end{aligned}$

где:

$\begin{aligned} \widetilde{A} = \frac{\tau_r}{\tau_s} \\end{aligned}$

Как видим, результат совпадает с предыдущим за исключением множителя $(1+A/\widetilde{A})$ . Рассмотрим 2 предельных случая:

$A \ll \widetilde{A}$ . В этом случае все рассуждения, приведенные ранее, сохраняются: количество чанков не зависит от числа нод, а значит не растет с ростом кластера.
$A \gg \widetilde{A}$ . В этом случае $U_{sum} \simeq A \tau_s / \tau_f$ и растет линейно с ростом числа нод.

Для определения режима оценим, чему равна $\widetilde{A}$ . $\tau_s$ — это характерное суммарное время обнаружения недореплицированного чанка и планирование его репликации. Грубая оценка (используя методику «пальцем в небо») дает значение 100 с. Тогда:

$\begin{aligned} \widetilde{A} = \frac{1 \times 10^5}{100} = 1000 \\end{aligned}$

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

Что можно сделать для улучшения ситуации? Казалось бы, можно улучшить асимптотику сдвинув границу $\widetilde{A}$ путем увеличения $\tau_r$ , однако это лишь увеличит значение $U_{sum}$ без какого-либо реального улучшения. Самый верный способ: это уменьшение $\tau_s$ , т.е. время принятия решения для репликации чанка, т.к. $\tau_f$ зависит от характеристик железа и на это программными средствами повлиять тяжело.

Обсуждение предельных случаев

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

К первому лагерю примыкают сравнительно небольшие кластера с количеством нод < 1000. В этом случае вероятность получить недореплицированный чанк описывается простой формулой:

$\begin{aligned} U = \frac{\tau_r}{\tau_f} \\end{aligned}$

Для улучшения ситуации можно применять 2 подхода:

Улучшать железо, тем самым увеличивая $\tau_f$ .
Ускорять репликацию, уменьшая $\tau_r$ .

Эти способы в целом являются достаточно очевидными.

Во втором лагере мы имеем уже крупные и сверхкрупные сервера с числом нод > 1000. Здесь зависимость будет определяться следующим образом:

$\begin{aligned} U = A \frac{\tau_s}{\tau_f} \\end{aligned}$

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

Продолжать увеличивать $\tau_f$ .
Ускорять детектирование недореплицированных чанков и последующее планирование репликации, тем самым уменьшая $\tau_s$ .

2-й подход по уменьшению $\tau_s$ уже не является очевидным. Казалось бы, какая разница, пройдет 20 секунд или 100 секунд? Однако эта величина существенно влияет на вероятность появления недореплицированных чанков. Также неочевидным является тот факт, что пропадает зависимость от $\tau_r$ , т.е. сама скорость репликации не играет роли. Оно и понятно в этой модели: с ростом числа нод эта скорость только увеличивается, поэтому на репликацию чанка начинает существенно влиять константная добавка «разгона» процесса репликации, направленная на обнаружение и планирование репликации.

Стоит остановиться немножко подробнее на $\tau_f$ . Помимо непосредственного вклада в жизнедеятельность чанков, увеличение $\tau_f$ благотворно сказывается на количестве доступных нод, т.к.

$\begin{aligned} A = N - F \simeq N \bigg( 1 - \frac{\tau_a}{\tau_f} \bigg) \\end{aligned}$

Тем самым увеличивая число доступных нод. Таким образом, улучшение $\tau_f$ напрямую сказывается на наличие доступных ресурсов кластера, ускоряя вычисления и одновременно повышая надежность хранения данных. С другой стороны, улучшение качества железа напрямую влияет на стоимость владения кластера. Описанная модель позволяет количественно оценивать экономическую целесообразность такого рода решений.

Сравнение подходов

В заключении я хотел бы привести сравнение двух подходов. Про это красноречиво скажут следующие графики.

Data loss

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

Потеря чанка

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

$\begin{aligned} A & \xrightarrow{k_f} F + U \ F & \xrightarrow{k_a} A \ U & \xrightarrow{k_s} U^* \ U^* + A & \xrightarrow{k_r} H + A \ U & \xrightarrow{k_f} F + U_2 \ U^* & \xrightarrow{k_f} F + U_2 \ U_2 & \xrightarrow{k_s} U_2^* \ U_2^* + A & \xrightarrow{k_r} U + A \ U_2 & \xrightarrow{k_f} F + L \ U_2^* & \xrightarrow{k_f} F + L \\end{aligned}$

Здесь через $U_2$ обозначено количество недореплицированных чанков, которым не хватает двух копий, $U_2^*$ — промежуточное состояние, аналогично $U^*$ , соответствующее состоянию $U_2$ , а $L$ означает потерянный (lost) чанк. Тогда:

$\begin{aligned} \frac{dL}{dt} &= k_f \big( U_2 + U_2^* \big) \ \tau_l &= \frac{1}{k_f \big( U_2 + U_2^* \big) } \\end{aligned}$

Где $\tau_l$ — характерное время образования потерянного чанка. Решим нашу систему для 2-х предельных случаев для случая, когда $A = 1000$ .

$A \ll \widetilde{A}$ , тогда

$\begin{aligned} \tau_l = A \frac{\tau_f^3}{\tau_r^2} \approx 100\ 000\ 000\ years \\end{aligned}$

Для $A \gg \widetilde{A}$ получаем:

$\begin{aligned} \tau_l = \frac{\tau_f^3}{A \tau_s^2} \approx 100\ 000\ 000\ years \\end{aligned}$

Т.е. характерное время образования потерянного чанка 100 миллионов лет! При этом получаются примерно сходные значения, т.к. мы находимся в переходной зоне. Величина характерного времени $\tau_l$ говорит сама за себя и каждый может сделать выводы сам.

Стоит, однако, обратить внимание на одну особенность. В предельном случае $A \ll \widetilde{A}$ в то время, как $U$ является константой и не зависит от $A$ , в выражении для $\tau_l$ мы получаем обратную зависимость, т.е. с ростом кластера тройная репликация даже улучшает сохранность данных! С дальнейшим ростом кластера ситуация меняется ровно на противоположную.

Выводы

Статья последовательно вводит инновационный способ моделирования кинетики процессов больших кластеров. Рассмотренная приближенная модель описания динамики кластера позволяет посчитать вероятностные характеристики, описывающие потерю данных.

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

Тем не менее, предложенный подход позволяет более точные и достоверные результаты, основанные на тонком учете различных факторов и анализе реальных данных работы кластера. Ниже приведен далеко не исчерпывающий список по улучшению модели:

Ноды кластера могут выходить из строя из-за различных сбоев оборудования. Поломка конкретного узла как правило имеет различную вероятность. Более того, поломка, например, процессора, не теряет данные, а лишь дает временную недоступность ноды. Это легко учитывать в модели, вводя различные состояния $F_{proc}$ , $F_{disk}$ , $F_{mem}$ и т.д. с различными скоростями процессов и различными последствиями.
Не все ноды одинаково полезны. Разные партии могут отличаться разным характером и частотой сбоев. Это такое можно учитывать в модели, вводя $A_1$ , $A_2$ и т.п. с разными скоростями соответствующих процессов.
Добавление в модель нод различных типов: с частично поврежденными дисками, забаненные и др. Например, можно детально проанализировать влияние выключения целой стойки и выяснения характерных скоростей перехода кластера в стационарный режим. При этом, численно решая дифференциальные уравнения процессов, можно наглядно рассмотреть динамику чанков и нод.
Каждый диск имеет несколько отличающиеся характеристики чтения/записи, включая латентность и пропускную способность. Тем не менее, можно более точно оценивать константы скоростей процессов, интегрируя по соответствующим функциям распределения характеристик дисков, по аналогии с константами скоростей в газах, проинтегрированные по максвелловскому распределению по скоростям.

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

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

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

Григорий Демченко, разработчик YT

Литература

[1] Cap Theorem Myths
[2] Spanner, TrueTime and the CAP Theorem
[3] The probability of data loss in large clusters
[4] Химическая кинетика
[5] Активированного комплекса теория
[6] Приближенные методы химической кинетики
[7] Распределение Максвелла
[8] YT: зачем Яндексу своя MapReduce-система и как она устроена

Поделиться с друзьями

-->

Комментарии (11)

0x0FFF
06.04.2017 18:20
#10158598
+1
Дано:
3-кратная репликация, размер чанка 1 Мб, 4 ТБ диски, 1000 серверов в кластере, каждый сервер с 12 дисками, ARR для диска составляет 1%, 1 день на замену сломавшегося диска.

Расчет:
- 1000 серверов, каждый с 12 дисками, итого в кластере 12'000 дисков. Отдельные диски вмещают до 4 ТБ / 1 МБ = 4'000'000 чанков.
  Когда один диск ломается, 4'000'000 его чанков становятся недоступными. Каждый из оставшихся в кластере дисков будет содержать приблизительно 4'000'000 / 12'000 = 333 чанка данных, хранившихся на сломанном диске. Это означает, что любые 2 отказавших диска в кластере приведут к тому, что 333 чанка в кластере останутся с единственной репликой. Эти 333 чанка должны лежать на разных дисках. Итого, когда любые 2 жестких диска в кластере одновременно выходят из строя, отказ любого из 333 жестких дисков, содержащих последнюю реплику наших данных, приведет к потере данных.
- 12000 дисков в кластере и ARR 1%, дает нам 12000 * 1% = 120 отказов жестких дисков в год. Если замена происходит в течение 1 дня, то когда один жесткий диск вышел из строя, вероятность того, что сломается еще один, равна 11999 * 1% * 1/365 ~= 33%. Поскольку у нас 120 сломанных дисков в год, каждый из которых требует ремонта в течение 1 дня, примерно 120 * 33% ~= 39,5 дней в году, мы будем работать в кластере с двумя отказавшими дисками.
- В кластере с двумя отказавшими дисками мы зависим от 333 других дисков, содержащих последнюю живую реплику данных. Какова вероятность того, что один из них откажет? 333 диска * 1% ARR * 39,5 дней в году без 2 дисков / 365 = 36%, в год. Таким образом, примерно раз в три года вы потеряете один чанк своих данных. Для многих приложений недоступность одного чанка — это уже проблема.
Так или иначе, это никак не 100'000'000 лет. Теперь добавим сверху падения других компонент кроме дисков, проблемы с сетью, перезагрузки серверов (накатываем обновления, например), когда часть чанков тоже становится недоступна, время на обнаружение проблемы с диском и восстановление данных, и т.д. Итоговая цифра намного больше соотносится с реальностью, чем ваши вычисления. Уж вы-то в Яндексе должны знать на основании своего опыта, что для кластера с 1000 машин и 3-кратной репликацией потеря данных будет происходить раз в год или чаще.
1. gridem
  06.04.2017 18:42
  #10158652
  +1
  Вы делаете ровно ту же ошибку, что и Клеппман в оригинальной статье. А именно: не учитывается динамика.
  
  Это проявляется в том, что вы неявно предполагаете, что время жизни диска и время жизни чанка — одинаковое. Понятно, что выпадание диска — это выпадание чанков этого диска. Однако характерное время восстановления чанка не совпадает со временем замены дисков и является сильно меньшей величиной. Поэтому даже если во время поломки диска сломается другой с этим же чанком, то это может быть не фатально, т.к. чанк с этого диска уже мог отреплицироваться на третий за существенно меньшее время.
  
  Таким образом, расчет сломанных дисков без учета механизма репликации — странная затея, которая дает фундаментально неверные результаты.
  1. 0x0FFF
    06.04.2017 18:59
    #10158690
    Я закладывал 1 день на замену. Даже если все будет работать идеально, системе все равно потребуется время на восстановление потерянных чанков, и в зависимости от нагрузки на кластере это время может быть довольно значительным, полчаса-час. Но как я сказал, я не учитывал множество других факторов. Например, Яндекс в силу объемов данных наверняка использует commodity диски, у которых ARR около 4-5%. Плюс диск не всегда отказывает и исчезает, иногда он начинает просто отдавать битые данные. Диск в наличии, а данные на нем неправильные, на диагностику такой проблемы тоже нужно время.
    
    Вы работаете с реальными кластерами подобных размеров, и сами используете LRC-8-2-2 (то есть можно потерять до 2 реплик из группы без потери данных) — какая у вас статистика по потерям чанков? Неужели действительно ни одной потери? Как следует из вашей формулы с 100 000 000 лет, даже вы имея 100 кластеров в течении 10 лет, получите вероятность отказа вероятность отказа всего 0.001%
    
    gridem
    06.04.2017 20:26
    #10158810
    В предложенном подходе я хотел продемонстрировать качественный анализ системы без привязки к конкретному железу. Если хочется посчитать для конкретных параметров — то сделать это можно легко, просто подставив соответствующие цифры.
    
    в зависимости от нагрузки на кластере это время может быть довольно значительным, полчаса-час
    А может быть и другим. Не суть. Просто получатся другие числа. Модель при этом не поменяется.
    
    Плюс диск не всегда отказывает и исчезает, иногда он начинает просто отдавать битые данные. Диск в наличии, а данные на нем неправильные, на диагностику такой проблемы тоже нужно время.
    Да, это действительно проблема. И такое поведение можно включить в модель без проблем.
    
    Вы работаете с реальными кластерами подобных размеров, и сами используете LRC-8-2-2 (то есть можно потерять до 2 реплик из группы без потери данных)
    Мы используем разные подходы. Конкретные цифры я бы не хотел называть по понятным причинам. В данной статье используются некоторые цифры, приближенные к какой-то реальности.
    
    В любом случае, я хотел продемонстрировать моделирование и подход, позволяющий делать выводы о поведении системы. Простые подходы и рассуждения, подобные этому, к сожалению, неверны. Думаю, по цифрам и количеству учитываемых факторов становится понятно, почему.
    
    0x0FFF
    07.04.2017 11:27
    #10159726
    Модель хорошая, но боюсь, что из вашей статьи могут сделать неверные выводы. Особенно режет глаза цифра в 100'000'000 лет для кластера в 1000 нод.
    
    Люди могут прочитать, и пойти деплоить кластеры Hadoop на 1000 нод с r=3 и думать, что они могут спать спокойно. Но, например, при выпадении ToR свича вы потеряете сразу всю стойку. Та же HDFS хранит r=3, но при этом 2 копии по умолчанию приземляются на одну стойку, значит при выпадении стойки приблизительно треть хранимых ей блоков оказывается в единственном экземпляре. Треть полной стойки двухюнитовых серверов — это до 320'000'000 чанков, соответственно каждый из оставшихся в кластере дисков будет в среднем хранить 27'210 чанков, у которых осталась одна последняя живая реплика. Если у сети нет oversubscription, то дореплицироваться эти чанки в идеальном случае будут: 27210 чанков * 1MB / 50 MB/sec ~= 9 минут. Плюс время на обнаружение проблемы. Плюс заметим, что в используемой у вас LRC-8-2-2 нужно еще и контрольные чанки пересчитать, то есть при восстановлении вам придется прочитать раз в 6 больше данных, то есть мы уже говорим о почти часе на абсолютно пустом кластере. Плюс в критический момент оказывается, что Hadoop сам не инициирует восстановление коэффициента репликации, и делать это нужно ручками на уровне файлов или директорий. А во время восстановления кластера выпадение еще одного любого диска — это недоступность данных.
    
    Поэтому я склонен считать что ваши рассуждения, к сожалению, тоже не верны. Автор критикуемой вами статьи не учитывает динамику. Вы учитываете динамику, но не учитываете другие возможные причины отказа — проблемы сетевого оборудования, проблемы питания, возвращение нодами некорректных данных, ошибки памяти, человеческий фактор и т.д. Не учитываете также то, что «динамика» — вещь относительная, и для вашего кластера и кластера Hadoop динамика восстановления будет отнюдь не одинаковая. Добавление же всех этих факторов в модель сделает её настолько сложной, что практическая польза от нее будет весьма спорной. Но на бумаге выглядит хорошо.
    
    gridem
    07.04.2017 15:46
    #10160464
    Модель хорошая, но боюсь, что из вашей статьи могут сделать неверные выводы
    Не надо бояться. Цифра получена исходя из предположений о величинах констант скоростей процессов. Для других величин может получиться другая цифра.
    
    Особенно режет глаза цифра в 100'000'000 лет для кластера в 1000 нод.
    Аргументация в стиле: "мне цифра не нравится", конечно, имеет право на существование, но полезность этого крайне сомнительна. Гораздо конструктивнее, если вы найдете, например, изъян в модели и обоснуете его.
    
    Люди могут прочитать, и пойти деплоить кластеры Hadoop на 1000 нод с r=3 и думать, что они могут спать спокойно. Но, например, при выпадении ToR свича вы потеряете сразу всю стойку.
    Для этого есть rack awareness, который присутствует во всех уважающих себя крупных системах.
    
    Вообще, мне не очень нравится рассуждать в категориях "а вдруг кто-то что-то подумает".
    
    Плюс заметим, что в используемой у вас LRC-8-2-2 нужно еще и контрольные чанки пересчитать
    Очень рад, что вы знаете, что я использую. Может еще расскажете, сколько чанков мы теряем? Думаю, всем было бы интересно.
    
    Поэтому я склонен считать что ваши рассуждения, к сожалению, тоже не верны.
    К сожалению, не могу разделить вашу склонность.
    
    Вы учитываете динамику, но не учитываете другие возможные причины отказа — проблемы сетевого оборудования, проблемы питания, возвращение нодами некорректных данных, ошибки памяти, человеческий фактор и т.д.
    Давайте я процитирую свою статью. Оказывается, не все в состоянии прочитать написанное.
    
    Конечно, данная модель является лишь первым приближением к тому, что реально происходит на кластере. Здесь мы лишь учитывали наиболее значимые процессы для получения качественного результата…
    Ноды кластера могут выходить из строя из-за различных сбоев оборудования. Поломка конкретного узла как правило имеет различную вероятность. Более того, поломка, например, процессора, не теряет данные, а лишь дает временную недоступность ноды…
    Добавление в модель нод различных типов: с частично поврежденными дисками, забаненные и др. Например, можно детально проанализировать влияние выключения целой стойки и выяснения характерных скоростей перехода кластера в стационарный режим.
    Каждый диск имеет несколько отличающиеся характеристики чтения/записи, включая латентность и пропускную способность. Тем не менее, можно более точно оценивать константы скоростей процессов, интегрируя по соответствующим функциям распределения характеристик дисков...
    Если добавить все это в модель, она была бы еще более сложной. Задача стояла в демонстрации нового подхода на вполне понятном и простом примере. Это первый подход к снаряду, который можно и нужно развивать и дополнять.
    
    0x0FFF
    07.04.2017 16:29
    #10160528
    Вопрос не в «цифра не нравится», а предсказание предложенной вами модели расходится с практически наблюдаемыми значениями на 7-8 порядков. 7-8 порядков — это не просто статистическая погрешность
    
    gridem
    07.04.2017 16:36
    #10160538
    Очень сильно зависит от параметров кластера. Без конкретных цифр и обстоятельств тут невозможно что-то утверждать более аргументированно.

youROCK
06.04.2017 21:43
#10158930
У меня только одно замечание (вероятно, я что-то недопонял, потому что все остальное, включая результаты, выглядит очень хорошо) — скорость репликации одного чанка ограничена сверху скоростью записи на диск (и сетью), а значит, при достаточном числе нод, все же должен начаться линейный рост вероятности потери одного чанка. Но у вас он тоже начинается, только из-за другой причины, обусловленной задержкой обнаружения. Не должны ли эти факторы складываться?
1. gridem
  06.04.2017 23:26
  #10159064
  Скорость репликации задается параметром 50МБ/с. Обычные крутящиеся диски дают производительность на уровне 100МБ/с, а твердотельные еще выше. Таким образом, пропускная способность репликации задает константу скорости репликации k_r. Можно возразить, что пропускная способность репликации не учитывает время, необходимое на первый seek диска, установку соединения и т.п. Эти факторы можно учесть в константе планирования репликации k_s, просто просуммировав соответствующие времена. При этом k_s — это не константа скорости обнаружения, а константа скорости планирования процесса репликации, включая обнаружение, постановку в пул задач, обработку, получение метаинформации и т.п.
  
  Тут есть другой интересный момент: а что будет, если кластер будет настолько большим, что весь объем не сможет равномерно распределиться по всем нодам из-за дискретного характера чанков. Простой расчет показывает, что количество чанков при размере одного чанка 1 МБ в рассматриваемом случае с размером 5 ТБ на ноду будет равно 5 000 000, что с большим запасом покрывает существующие размеры кластеров. Если же окажется, что это не так (очень большие чанки, мало места на дисках и т.п.), то эффективно такое также можно учесть, просто добавив некоторую константу к времени планирования репликации.
  1. youROCK
    07.04.2017 09:13
    #10159398
    Да, ошибочность моего предположения была в том, что дореплицирование недостающих чанков происходит только на новые «чистые» ноды (которых на поряд меньше общего числа). Если восстановление фактора репликации может добавлять недостающие чанки равномерно по кластеру, тогда только время обнаружения влияет. Спасибо за объяснение.