Кодирование стирания Hadoop 3.0 - определение количества допустимых отказов узлов?

Question

В hadoop 2.0 коэффициент репликации по умолчанию равен 3. И допустимое количество отказов узлов составляло 3-1 = 2.
То есть на кластере из 100 узлов, если файл был разделен, говоря10 частей (блоков), с коэффициентом репликации 3, общее количество требуемых блоков хранения равно 30. А если какие-либо 3 узла, содержащие блок X и его реплики, потерпели неудачу, то файл не подлежит восстановлению.Даже если в кластере было 1000 узлов или файл был разбит на 20 частей, сбой в работе трех узлов в кластере все равно может иметь катастрофические последствия для файла.

Теперь перейдем к hadoop 3.0.
Благодаря кодированию с удалением, как говорит Hadoop, он обеспечивает такую ​​же долговечность с эффективностью хранения 50%.И основываясь на том, как работает метод Рида-Соломона (то есть для k блоков данных и n блоков четности, по крайней мере, k из (k + n) блоков должны быть доступны для файла, который можно восстановить / прочитать)
Так что длятот же файл выше - есть 10 блоков данных и для поддержания эффективности данных до 50%, можно добавить 5 блоков четности.Таким образом, из 10 + 5 блоков, по крайней мере, любые 10 блоков должны быть доступны для доступа к файлу.И в кластере из 100 узлов, если каждый из 15 блоков хранится на отдельном узле, то, как вы можете видеть, допустимо всего 5 отказов узлов.Теперь сохранение одного и того же файла (то есть 15 блоков) в кластере из 1000 узлов не будет иметь никакого значения по отношению к числу допустимых отказов узлов - это все равно 5.
Но интересная часть здесь - если тот же файл (или другой файл)) была разделена на 20 блоков, а затем были добавлены 10 блоков четности, а затем для сохранения 30 блоков в кластере из 100 узлов допустимое количество отказов узлов равно 10.

Точка, которую я хочуmake здесь -
в hadoop 2, число допустимых отказов узлов равно ReplicationFactor-1 и явно основано на коэффициенте репликации.И это свойство всего кластера.

, но в hadoop 3, скажем, если эффективность хранения была установлена ​​на 50%, то число допустимых отказов узлов, кажется, отличается для разных файлов в зависимости от количества блоковон делится на.

Так может ли кто-нибудь прокомментировать, если приведенный выше вывод является правильным?И как для любого кластера определяется допустимый отказ узла?

(И я не хотел делать его сложным выше, поэтому не обсуждал крайний случай файла только с одним блоком. Но алгоритм,Я думаю, он будет достаточно умен, чтобы реплицировать его как есть или с данными четности, чтобы гарантировать надежность данных.)

Редактировать: Этот вопрос является частью серии вопросов, которые яесть на EC - другие, как показано ниже -
Кодирование стирания Hadoop 3.0: влияние на производительность заданий MR?

Answer 1

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

Опять же, используя ваши номера, для Hadoop 3.0 каждый набор из 10 блоков данных и 5 блоков четностей хранится на 15 различных узлах. Таким образом, требования к пространству данных сокращаются до 50%, но количество узлов, для которых записываются данные и четности, увеличилось в 5 раз, с 3 узлов для Hadoop 2.0 до 15 узлов для Hadoop 3.0. Поскольку избыточность основана на коррекции стирания Рида-Соломона, то, пока любые 10 из 15 узлов не смогли прочитать определенный набор блоков, этот набор блоков можно восстановить (максимально допустимый сбой для набора блоков составляет 5 узлов ). Если это 20 блоков данных и 10 блоков четностей, то блоки данных и четности распределяются по 30 различным узлам (максимально допустимый сбой для набора блоков составляет 10 узлов).

Для представления всего кластера сбой может произойти, если отказывает больше чем n-k узлов, независимо от количества узлов, так как есть некоторый шанс, что набор блоков данных и блоков четности будет включать все отказавшие узлы. Чтобы избежать этого, следует увеличить n вместе с количеством узлов в кластере. Для 100 узлов в каждом наборе может быть 80 блоков данных, 20 блоков четности (избыточность 25%). Обратите внимание, что 100 узлов будут необычно большими. Пример с этой веб-страницы - 14 узлов RS (14,10) (для каждого набора: 10 блоков данных, 4 блока четности).

https://hadoop.apache.org/docs/r3.0.0

с вашими номерами размер кластера будет 15 (10 + 5) или 30 (20 + 10) узлов.

Для файла с 1 блоком или менее, чем k блоков, n-k блоков четности все равно потребуется, чтобы обеспечить отказ более чем n-k узлов, прежде чем произойдет сбой. Для кодирования Рида-Соломона это можно сделать, эмулируя нулевые начальные блоки для «пропущенных» блоков.

---

Я думал, что добавлю некоторую вероятность к числу узлов в кластере.

Предположим, что частота отказов узлов составляет 1%.

15 узлов, 10 для данных, 5 для четностей, используя гребень (a, b) для комбинаций вещей b одновременно:

Вероятность точно x сбоев узла:

6 => ((.01)^6) ((.99)^9) (comb(15,6)) ~= 4.572 × 10^-9
7 => ((.01)^7) ((.99)^8) (comb(15,7)) ~= 5.938 × 10^-11
8 => ((.01)^8) ((.99)^7) (comb(15,8)) ~= 5.998 × 10^-13
...

Вероятность 6 или более отказов ~ = 4,632 × 10 ^ -9

30 узлов, 20 для данных, 10 для четностей

Вероятность точно x сбоев узла:

11 => ((.01)^11) ((.99)^19) (comb(30,11)) ~= 4.513 × 10^-15
12 => ((.01)^12) ((.99)^18) (comb(30,12)) ~= 7.218 × 10^-17
13 => ((.01)^13) ((.99)^17) (comb(30,13)) ~= 1.010 × 10^-18
14 => ((.01)^14) ((.99)^16) (comb(30,14)) ~= 1.238 × 10^-20

Вероятность 11 или более отказов ~ = 4,586 × 10 ^ -15

Чтобы показать, что потребность в накладных расходах четности уменьшается с числом узлов, рассмотрим крайний случай: 100 узлов, 80 для данных, 20 для сторон (избыточность 25%):

Вероятность точно x сбоев узла:

21 => ((.01)^21) ((.99)^79) (comb(100,21)) ~= 9.230 × 10^-22
22 => ((.01)^22) ((.99)^78) (comb(100,22)) ~= 3.348 × 10^-23
23 => ((.01)^23) ((.99)^77) (comb(100,23)) ~= 1.147 × 10^-24

Вероятность 21 или более отказов ~ = 9,577 × 10 ^ -22