Расчет вероятности сбоя системы в распределенной сети

Я пытаюсь построить математическую модель доступности файла в распределенной файловой системе. Я разместил этот вопрос на MathOverflow, но его также можно отнести к категории CS-вопросов, поэтому здесь я тоже его опишу.

Система работает следующим образом: узел хранит файл (закодированный с использованием кодов стирания) на удаленных узлах r * b, где r - коэффициент репликации, а b - целочисленная константа. Файлы с закодированным стиранием обладают свойством, что файл может быть восстановлен, если, по крайней мере, b удаленных узлов доступны и возвращают свою часть файла.

Самый простой подход к этому - предположить, что все удаленные узлы независимы друг от друга и имеют одинаковую доступность p. С этими допущениями доступность файла следует за биномиальным распределением, т.е. http://bit.ly/dyJwwE

К сожалению, эти два предположения могут привести к ошибке, которая не допускается, как показано в этой статье: http://deim.urv.cat/~lluis.pamies/uploads/Main/icpp09-paper.pdf.

Один из способов преодолеть предположение о том, что все узлы имеют одинаковую доступность, состоит в том, чтобы рассчитать вероятность каждой возможной комбинации доступного / недоступного узла и взять сумму всех этих результатов (что-то вроде того, что они предлагают в статье выше, просто более формально, чем то, что я только что описал). Вы можете увидеть этот подход как двоичное дерево с глубиной r * b, и каждый отпуск является одной из возможных комбинаций доступных / недоступных узлов. Доступность файла - это то же самое, что и вероятность того, что вы получите отпуск с>=b доступными узлами. Этот подход является более правильным, но имеет вычислительную стоимость http://bit.ly/cEZcAP. Кроме того, это не касается предположения о независимости узла.

Ребята, есть ли у вас идеи хорошего приближения, которое вносит меньшую ошибку, чем биномиальное распределение-приближение, но с лучшими вычислительными затратами, чем http://bit.ly/cEZcAP?

Можно предположить, что данные о доступности каждого узла представляют собой набор кортежей, состоящий из (measurement-date, node measuring, node being measured, succes/failure-bit), С помощью этих данных вы можете, например, рассчитать корреляцию доступности между узлами и дисперсии доступности.

Источник

2 ответа

Решение

Для больших r а также b Вы можете использовать метод, называемый интеграцией Монте-Карло, см., например, интеграцию Монте-Карло в Википедии (и / или главу 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 и вы заменяете линию if random.random()<p: alivenum += 1 от

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 относится к древовидной структуре и for j in ... обходит дерево, пропуская нижние ветви текущего узла, как только тест не пройден. Полученный тест еще alivenum >= b как и раньше, конечно.

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

4) Зависимость от времени - нетривиальная, но возможная модификация, если вы знаете mtbf/r (среднее время между отказами / ремонтами), поскольку это может дать вам вероятности p либо древовидной структуры или некоррелированной линейной p[i] по сумме экспонент. Затем вам нужно будет запустить процедуру MC в разное время с соответствующими результатами для p,

5) Если у вас есть только файлы журналов (как указано в вашем последнем абзаце), это потребует существенного изменения подхода, который выходит за рамки того, что я могу сделать на этой доске. Лог-файлы должны быть достаточно тщательными, чтобы позволить реконструировать модель для графа сети (и, следовательно, графа p), а также отдельные значения всех узлов p, В противном случае точность была бы ненадежной. Эти лог-файлы также должны быть значительно длиннее, чем временные масштабы сбоев и ремонтов, предположения, которые могут быть нереальными в реальных сетях.

Источник

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

Скажи у тебя N узлы.

  1. Разделите их на два набора N/2 узлы.
  2. Для каждой стороны вычислите вероятность того, что любое количество узлов ([0,N/2]) вниз.
  3. Умножьте и сложите их по мере необходимости, чтобы найти вероятность того, что любое число ([0,N]) из полного комплекта вниз.

Шаг 2 может быть выполнен рекурсивно, и на верхнем уровне вы можете суммировать по мере необходимости, чтобы найти, как часто больше, чем некоторое число вниз.

Я не знаю сложности этого, но если я угадаю, я бы сказал на или ниже O(n^2 log n)

Механика этого может быть проиллюстрирована на терминале. Скажем, у нас есть 5 узлов со временем работы p1... p5, Мы можем разделить это на сегменты A сp1 p2... а также B с p3... p5, Затем мы можем обработать их, чтобы найти время "N узлов вверх" для каждого сегмента:

Для:

a_2

a_1

A_0

Для Б:

B_3

Би 2

Окончательные результаты для этого этапа можно найти, умножив каждый из 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]
Источник
Другие вопросы по тегам