Вычисление вероятности системного отказа в распределенной сети
Я пытаюсь создать математическую модель доступности файла в распределенной файловой системе. Я отправил этот вопрос в MathOverflow, но это могло бы также быть классифицировано как вопрос CS, таким образом, я даю ему выстрел здесь также.
Система работает как это: узел хранит файл (закодируйте использующие коды стирания) в r*b узлах пультов ДУ, где r является фактором репликации и b, целочисленная константа. Кодированные стиранием файлы имеют свойство, что файл может быть восстановленной эквивалентностью, по крайней мере, b удаленных узлов, доступны и возвращают ее часть файла.
Самый простой подход к этому должен предположить, что все удаленные узлы независимы друг от друга и имеют ту же доступность p. С этими предположениями доступность файла следует за Биномиальным распределением, т.е. Биномиальным распределением http://bit.ly/dyJwwE
К сожалению, эти два предположения могут представить non-neligible ошибку, как показано данной статьей: http://deim.urv.cat/~lluis.pamies/uploads/Main/icpp09-paper.pdf.
Один способ преодолеть предположение, что все узлы имеют ту же доступность, состоит в том, чтобы вычислить вероятность каждой возможной комбинации availaible/non-available узла и взять сумму всех этих результатов (который является видом того, что они предлагают в газете выше, просто более официально, чем, что я просто описал). Вы видите этот подход как двоичное дерево с глубиной r*b, и каждый отпуск является одной возможной комбинацией available/not-available узлов. Доступность файла является тем же самым как вероятностью, что Вы прибываете в отпуск с> =b доступные узлы. Этот подход более корректен, но имеет вычислительную стоимость Церковного календаря http://bit.ly/cEZcAP. Кроме того, это не имеет дело с предположением о независимости узла.
Вы у парней есть какие-либо идеи хорошего приближения, которое представляет меньше ошибки, чем биномиальное-распределение-aproximation, но с лучшей вычислительной стоимостью, чем http://bit.ly/d52MM9 http://bit.ly/cEZcAP?
Можно предположить, что данные доступности каждого узла являются рядом кортежей, состоящих из (measurement-date, node measuring, node being measured, succes/failure-bit). С этими данными Вы могли, например, вычислить корреляцию доступности между узлами и различием доступности.
2 ответа
Для больших r и b вы можете использовать метод под названием Monte -Интеграция Карло, см., Например, Интеграция методом Монте-Карло в Википедии (и / или в главе 3.1.2 SICP) для вычисления суммы. Для малых r и b и значительно различающихся вероятностей отказа узлов p [i] точный метод лучше. Точное определение малого и большого будет зависеть от нескольких факторов, и его лучше всего проверить экспериментально.
Конкретный пример кода : это очень простой пример кода (на Python) для демонстрации того, как может работать такая процедура:
def montecarlo(p, rb, N):
"""Corresponds to the binomial coefficient formula."""
import random
succ = 0
# Run N samples
for i in xrange(N):
# Generate a single test case
alivenum = 0
for j in xrange(rb):
if random.random()<p: alivenum += 1
# If the test case succeeds, increase succ
if alivenum >= b: succ += 1
# The final result is the number of successful cases/number of total cases
# (I.e., a probability between 0 and 1)
return float(succ)/N
Функция соответствует биномиальному тесту и запускает N проверяет, живы ли b узлов из r * b узлов с вероятностью отказа p . Несколько экспериментов убедят вас, что вам нужны значения N в диапазоне тысяч выборок, прежде чем вы сможете получить какие-либо разумные результаты, но в принципе сложность составляет O (N * r * b) . Точность результата масштабируется как sqrt (N) , т.е., чтобы увеличить точность в два раза, необходимо увеличить N в четыре раза. Для достаточно больших r * b этот метод будет явно лучше.
Расширение приближения : очевидно, что вам нужно разработать тестовый пример таким образом, чтобы он уважал все свойства системы. Вы предложили несколько расширений, некоторые из которых могут быть легко реализованы, а другие нет. Позвольте мне дать вам пару предложений:
1) В случае отдельных, но некоррелированных p [i] , изменения в приведенном выше коде минимальны: в заголовке функции вы передаете вместо этого массив одного числа с плавающей запятой p , и вы заменяете строку , если random.random ()
if random.random()<p[j]: alivenum += 1
2) В случае коррелированного p [i] вам нужна дополнительная информация о системе. Ситуация, о которой я говорил в своем комментарии, может быть такой сетью:
A--B--C
| |
D E
|
F--G--H
|
J
В этом случае A может быть «корневым узлом», а отказ узла D может означать автоматический отказ со 100% вероятностью узлов F , G , H и J ; в то время как отказ узла F автоматически приведет к отключению G , H и J и т. д. По крайней мере, это был тот случай, о котором я имел в виду в моем комментарии (что является правдоподобной интерпретацией, поскольку вы говорите о древовидной структуре вероятностей в исходном вопросе). В такой ситуации вам потребуется изменить код, который p относится к древовидной структуре и для j в ... проходит по дереву, пропуская нижние ветви от текущего узла, как только тест не проходит. В результате, конечно же, получается, что alivenum> = b , как и раньше.
3) Этот подход потерпит неудачу, если сеть представляет собой циклический граф, который не может быть представлен древовидной структурой. В таком случае вам нужно сначала создать мертвые или живые узлы графа, а затем запустить алгоритм маршрутизации на графе, чтобы подсчитать количество уникальных достижимых узлов. Это не увеличит временную сложность алгоритма, но, очевидно, сложность кода.
4) Временная зависимость - нетривиальная, но возможная модификация, если вы знаете mtbf / r (среднее время наработки на отказ / ремонт), поскольку это может дать вам вероятности p любого древовидная структура или некоррелированная линейная p [i] суммой экспонент. Затем вам придется запускать MC-процедуру в разное время с соответствующими результатами для p .
5) Если у вас есть просто файлы журнала (как указано в вашем последнем абзаце), потребуется существенная модификация подхода, выходящая за рамки того, что я могу сделать на этой доске. Файлы журнала должны быть достаточно подробными, чтобы позволить реконструировать модель для сетевого графа (и, следовательно, графа p ), а также индивидуальных значений всех узлов p ]. В противном случае точность была бы ненадежной. Эти файлы журналов также должны быть значительно длиннее, чем временные рамки отказов и ремонтов, предположения, которые могут быть нереалистичными в реальных сетях.
Предполагая, что каждый узел имеет постоянный, известный и независимый коэффициент доступности, на ум приходит подход "разделяй и властвуй".
Допустим, у вас есть N узлов.
- Разделите их на два набора по
N/2узлов. - Для каждой стороны вычислите вероятность того, что любое количество узлов (
[0,N/2]) не работает. - Умножьте и просуммируйте их, как нужно, чтобы найти вероятность того, что любое число (
[0,N]) из полного набора не работает.
Шаг 2 может быть выполнен рекурсивно, и на верхнем уровне вы можете суммировать по мере необходимости, чтобы найти, как часто больше некоторого числа не работает.
Я не знаю сложность этого, но если бы мне пришлось угадать, я бы сказал, что на уровне или ниже O(n^2 log n)
Механику этого можно проиллюстрировать на конечном примере. Скажем, у нас есть 5 узлов со временем работы . Мы можем разделить их на сегменты
A с и
B с . Затем мы можем обработать их, чтобы найти время "N узлов вверх" для каждого сегмента:
Для A:
Для B:
Окончательные результаты для этого этапа могут быть найдены путем умножения каждого из a с каждым из b и соответствующего суммирования.
v[0] = a[0]*b[0]
v[1] = a[1]*b[0] + a[0]*b[1]
v[2] = a[2]*b[0] + a[1]*b[1] + a[0]*b[2]
v[3] = a[2]*b[1] + a[1]*b[2] + a[0]*b[3]
v[4] = a[2]*b[2] + a[1]*b[3]
v[5] = a[2]*b[3]