\documentclass[12pt]{article}
% vim: tw=80
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}

\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphics}
\usepackage{verbatim}
\usepackage[matrix,arrow,curve]{xy}

\usepackage{a4wide}
\usepackage{indentfirst}
\usepackage{cpindex-lhs}
\usepackage{appendix}
\usepackage{url}
\usepackage{xcomment}

\newtheorem{thm}{theorem}[section]
\newtheorem{lem}[thm]{Лемма}
\newtheorem{prop}[thm]{Утверждение}
\newtheorem{foll}[thm]{Следствие}

\input{git-pageid.inc}
\usepackage{git-pageid}

\bibliographystyle{tinyurl}

\begin{document}
\sloppy

\newcommand{\gitlinks}[1]{
\label{src:#1}
\noindent
Git: \url{git://grid.pp.ru/psha/#1/} \\
GitWeb: \url{http://grid.pp.ru/git/?p=psha/#1/.git} \\
}

\def\corr{\rightarrow}
\def\hyp{\mathbb{A}}

\def\gand{\mbox{And}}
\def\gor{\mbox{Or}}

\section{Введение}
На работу географически распределённых информационно-вычислительных систем
оказывают влияние не только технические, но и административные факторы. Поэтому
к вопросу мониторинга их работоспособности не всегда возможно подходить с
методами применимыми в централизованных, хотя и сложных структурах. Так, в
распределённых средах не всегда возможно создать выделенный центр, регулирующий
работу других компонент. Поэтому систему мониторинга для таких систем нужно
разрабатывать исходя из тех условий, в которых ей предстоит работать.

\section{Что такое система мониторинга?}
Система мониторинга состоит из двух крупных компонент --- коллекторной части и
обработчика. В ее задачу входит не столько сбор информации, сколько ее
обработка, принятие решений об оповещении или совершении каких-нибудь
действий. При этом непосредственно коллекторная часть может быть
внешней. 

Что хочется от системы мониторинга? Прежде всего она должна быть такой, чтоб ее
можно было использовать в распределенных структурах. Из этого уже
вытекают два требования --- распределенность и компактность. Компактной
здесь называется система, которая не требует установки множества дополнительных
пакетов, запуска нескольких демонов и потребляющая больше количество
ресурсов. Кроме этого, система должна поддерживать свои базы данных
собственными силами, то есть, не иметь зависимостей на СУБД (типа MySQL, pSQL и
тд), а использовать какие-нибудь локальные БД (например \texttt{rrd},
\texttt{sqlite}, \texttt{bdb}).


Исходя из этого можно можно выделить следующие требования к системе мониторинга:

\begin{itemize}
\item распределенность, возможность обменитьваться данными с другими, отсутствие
центральной незаменимой управляющей точки;
\item компактность, возможность хранить данные средствами системы;
\item расширяемость, возможность добавлять новые типы/источники в работающую
систему; расширяемость может быть достигнута за счет того, что система не
имеет привязки к какому-то конкретному типу данных, а работает с абстрактными
сообщениями вида <<работает>>, <<не работает>>, <<недоступно>>, \ldots;
\item внешний интерфейс доступа или простой и понятный формат хранения данных.
\end{itemize}

\subsection{Коллекторная часть}
Задача коллектора в системах мониторинга --- не столько сбор данных,
сколько приведение их к какому-то внутреннему виду. Учитывая сколько чисто
коллекторных систем сейчас существует (\texttt{Ganglia}, \texttt{cacti},
\texttt{mds}, \ldots) писать свою смысла нет; скорее надо внимательно
рассмотреть имеющиеся и выбрать наиболее подходящую.

При использовании внешней коллекторной части возможна минимальная установка
системы практически без конфигурирования, если она будет забирать информацию из
кластерной системы очередей (\texttt{PBS}, \texttt{SGE}, \ldots), из кластерной системы
мониторинга (\texttt{Ganglia}) или из какой-нибудь коллекторной системы
(\texttt{collectd},\ldots). 

\subsubsection{\tt collectd}
Особый интерес представляет использование \texttt{collectd}. Это демон сбора
информации о системе. Он не претендует на какую-то сложную функциональность
(выдержка с сайта {\tt http://collectd.org}):
\begin{quotation}
It does not do monitoring. The data is collected and stored, but not
interpreted and acted upon. 
\end{quotation}
Однако он отличается несколькими важными качествами:
\begin{itemize}
  \item распределенный сбор информации --- несколько серверов могут отсылать
    друг--другу данные;
  \item достаточное количество уже написаных плагинов для сбора разного типа
    данных: от трафика до изменения частоты процессора;
  \item малое количество зависимостей на дополнительное ПО;
  \item простой протокол обмена и простая база данных\footnote{
      Вообще говоря \texttt{rrd} не является базой данных в общепринятом
      понимании, однако для задач мониторинга базы с агрегацией устаревших
      данных вполне подходят.
    }.
\end{itemize}

Систему мониторинга можно подключить к \texttt{collectd} в качестве
потребителя информации (при этом коллектор еще и обеспечит построение красивых
графиков):
\begin{itemize}
\item через UNIX--сокет, посылая запросы на нужную информацию;
 подробнее этот протокол описан в \texttt{collectd-unixsock(5)}
\item получать multicast или unicast сообщения от других демонов \texttt{collectd}\footnote{
    В данный момент реализован клиент к \texttt{collectd}--серверу, обрабатывающий
    поток результатов и приводящий к внутреннему виду. Подробнее описано в \ref{impl}
  }.


\end{itemize}

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

\subsubsection{\texttt{syslog}}
Вообще говоря, \texttt{syslog} представляет из себя хороший <<коллектор>>. 
По крайней мере, выполняемая им задача --- сбор информации из разных источников (возможно,
удаленных) и складирование ее в каком-то одном месте, совпадают с задачей
коллекторной части системы мониторинга.

Однако, у \texttt{syslog} есть несколько черт, которые делают его неприменимым в
качестве коллектора. Одна из них --- сложность <<разбора>> записей. Их
смысловая часть не имеет фиксированного формата и без предварительной
работы с источником этих данных нельзя определить, что они означают. 
Без предварительного анализа источников можно только сказать, какой узел, когда
и с каким уровнем создал эту запись. К этому 
добавляется еще и то, что многие демоны либо не пользуются \texttt{syslog}, либо сваливают
свои данные в отдельные файлы (например есть <<устоявшийся>> формат \texttt{xferlog} для
FTP серверов).

\subsection{Гипотезы и корреляции}

В автоматических системах зачастую не хватает двух вещей --- гипотез и корреляций.
\textbf{Гипотезой} будем называть следующее. Пусть есть зависимость $C \corr B
\corr A$ (где $B \corr A$ обозначает, что узел $B$ зависит от узла $A$). В случае если
из строя выходит $C$, оператор сразу предполагает, что возможно это произошло
из-за сбоев в $A$ или $B$. То есть, появляются гипотезы $A^?$ и $B^?$.

\textbf{Корреляцией}\footnote{на данный момент эта часть не рассматривалась}
(или связанными сбоями) будем называть сбои, происходящие в
одно и то же время по одной и той же причине, но связь между которыми нельзя
установить располагая лишь информацией известной системе. Например, отключение
питания в здании приведет к отключению всего и вся (на упсах сколько-то
протянет, но тоже выключится), при этом никаких зависимостей между узлами скорее
всего найти не удастся. Это задача не очень сложная для оператора, но довольно
тяжелая для автоматических систем.

\section{Гипотезы}
В системе мониторинга имеется информация о
зависимостях между узлами, поэтому при возниковении сообщения о недоступности
она может создавать или отбрасывать предположения о том, на каких узлах
произошли сбои. 

Введем формальное понятие гипотезы. Пусть у нас есть
ориентированнй граф $G$ без циклов с единственной вершиной без исходящих ребер, в котором
вершины соответствуют узлам, а ребра ---
зависимостям между ними. Вершина без зависимостей соответствует системе мониторинга,
а листовые вершины в графе $G$ соответствуют тем узлам,
о которых поступила информация о недоступности. 
Определим три типа гипотез:
\begin{itemize}
\item простой гипотезой $A_i^?$ назвем предположение о том, что узела $A_i$ не
  работает;
\item сложной назовем $A^? = \bigwedge_{i\in h} A_i^?$, где $A_i$ ---
  простые гипотезы (такие гипотезы возникают в графе, когда существует хотя бы
  одна точка ветвления);
\item составной назовем $A^? = \bigvee_{i\in h} A_i^?$, где $A_i$ ---
  сложные гипотезы (такие появляются в графах с зависимостями типа И, подробнее в
  \ref{gr-romb-hypo}).
\end{itemize}
При этом должны выполняться
еще два свойства: никакие два $A_k$ из тех, которые входят в сложную\footnote{
  для составных гипотез утверждение чуть более сложное и мы его пока не будем
  приводить
}
гипотезу
$A^?$, не имеют зависимостей друг от друга и 
что для любой листовой вершины $A_l$ не существует пути\footnote{
  путь строится в соответствии с типом зависимостей, то есть, если $A$ зависит от
  $B$ и $C$, то путь из $A$ будет содержать и $B$ и $C$
} до корневой вершины, не проходящего через множество $h$.

Система обработки гипотез может выглядеть следующим образом. Пусть существует некое
множество гипотез $H(G)$. Система работает
с множеством пар $(a, p) \in H(G) \times (0, 1]$, где $a$ --- гипотеза, а $p$
--- вероятность того, что она верна. Каждое приходящиее в систему событие
(сообщение о том, что что-то работае, не работает или недоступно) может порождать или
опровергать гипотезы. Например если для узла $A_i$ приходит сообщение о том, что
он работает нормально (обозначим его $A_i^+$), гипотеза $A_i^?$ и все выше неё
по графу будут удалены, так как они не верны.
Если же приходит сообщение $A_i^-$, то нужно породить и
проверить гипотезы о сбоях на узлах, от которых зависит $A_i$ и, если они не
верны, объявить $A_i^?$ истинной. В случае если порождается какая-то гипотеза,
но она уже находится на обработке, ее вероятность повысится. Таким образом
в системе все время находится некоторый список гипотез и их вероятностей.
В случае, если вероятность превысила критическую, система оповещает оператора.

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

\subsection{Сообщения}
\label{msg-types}
Типы сообщений в системе бывают следующими:
\begin{itemize}
\item <<узел $A_i$ работает>> --- узел $A_i$ не ломался, восстановился или стал доступен;
\item <<узел $A_i$ не работает>> --- сообщение о том что именно узел $A_i$
  \textbf{гарантированно} не работает;
\item <<узел $A_i$ недоступен>> --- информация об узле по каким-то причинам не
  может быть получена.  Сообщение не указывает напрямую на то, что не работает
  именно $A_i$. Ниже <<сбоем>> называется именно сообщение о недоступности.
\end{itemize}

Следует различать сообщения <<недоступен>> и <<не работает>>, хотя для сетевого
мониторинга, как правило, они путаются. Например, ответ на ICMP запрос <<Destination
Host Unreachable>> не является индикатором того, что узел не работает, хотя по
адресу отправителя этого ICMP ответа можно предположить на каком участке сбой.

\subsubsection{Преобразование информации}
Когда данные из какого-то числового вида приводятся к абстрактном виду
описанному выше? Это преобразование специфично для каждого узла и
типа данных (если все делать правильно), или хотя бы только для типа
данных. Например, ICMP запрос со временем отклика больше 10 секунд в большинстве
случаев сигнализирует о том, что система находится на грани сбоя. Хотя для
некоторых сетей этот показатель может считаться нормой. При этом, то же число
<<10>> может обозначать приемлемую загрузку процессора.

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

\subsection{Вероятности}

\subsubsection{Обозначения}
\begin{itemize}
\item $T$ --- дерево с вершинами $A_i$.
\item $p_i$ --- вероятность (точечная) сбоя для узла $A_i$.
\item $A_i^?$ --- простая гипотеза о том, что $A_i$ сломался (именно сломался,
  а не недоступен).
\item $A_{i,\ldots,j}^? = A_i^? \wedge \ldots \wedge A_j^?$ --- сложная
  гипотеза об одновременном сбое $A_i,\ldots, A_j$. При этом
  должно соблюдаться условие, что ни одна $A_k$ не имеет зависимостей от $A_l$.
\item $H(T)$ --- множество гипотез в дереве $T$.
\item $P(A^?)|_T$ --- вероятность истинности гипотезы $A^?$ в дереве $T$.
\item $W(T)$ --- вес дерева $T$, то есть сумма вероятностей гипотез по дереву.
\end{itemize}

\subsubsection{Построение дерева}

Рассмотрим две <<образующие>> структуры в дереве --- последовательную $S_n$ (\ref{tree-seq}) и
точку ветвления $P_n$ (\ref{tree-par}).
\begin{equation}
  \label{tree-seq}
  \xymatrix{
    A_n\ar[r] & A_{n-1} \ar@{.>}[r] & A_1 \ar[r] & A_0 \\
  }
\end{equation}

\begin{equation}
  \label{tree-par}
  \xymatrix{
    & &A_0& &\\
    A_1\ar[urr]& A_2\ar[ur] &A_3\ar[u] & \ldots  & A_n\ar[llu]
  }
\end{equation}

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

\textbf{Случай $S_n$.}
Пусть произошло событие $A_n^-$.
Оно породило гипотезы $A_i^?$ с вероятностями
$$
P(A_0^?) = p_0,\ P(A_1^?) = (1-p_0) \cdot p_1,\ \ldots,\ P(A_i^?) = \prod_0^{i-1} (1 - p_j) \cdot p_i
$$
Сумма этих вероятностей меньше 1

$$
W(S_n) = p_0 + p_1 (1-p_0) + \ldots + p_i \prod_0^{i-1} (1 - p_j) = 1 - \prod_0^i (1 - p_j)
$$

\textbf{Случай $P_n$.}
Пусть произошли сбои $A_1, \ldots, A_n$. Рассматривается одновременный сбой
всех узлов, потому что нам интересно лишь та часть дерева, про которую у нас
есть информация. Если про какую-то листовую вершину $A_k$ мы ничего не знаем,
то и в дереве она не будет представлена.

$$
P(A_0^?) = p_0,\ P(A_{1,\ldots,n}^?) = (1 - p_0) \prod_1^n p_i
$$

Сумма этих вероятностей также меньше единицы и равна
$$
W(P_n) = p_0 + (1 - p_0) \prod_1^n p_i = 1 - (1 - p_0) (1 - \prod_1^n p_i)
$$

Как несложно заметить, в случае $n = 1$ случаи (\ref{tree-seq}) и (\ref{tree-par}) эквивалентны.

\textbf{Композиция.} Для того чтобы рассматривать кроме $S_n$ или $P_n$,
необходимо научиться строить из простых элементов более сложные.
\begin{prop}
  \label{compose}
  Пусть есть какое-то дерево $T$, и его листовую вершину
  $A_k$ заменили на дерево $T'$. Гипотезы в дереве $T'' = T +_{A_k} T'$
  будут иметь вероятности
$$
P(A^?)|_{T''} = P(A^?)|_T, \mbox{для}\ A^? \mbox{не содержащих вершин из}\ T'
$$
$$
P(A^? \wedge B^?)|_{T''} = P(A^?)|_T \cdot P(B^?)|_{T'}, \mbox{для}\ A^? \in
T,\ B^? \in T'
$$
\end{prop}

\begin{proof}
Сначала рассмотрим вспомогательное утверждение.
\begin{prop}\label{prob-mult}
  Вероятность $P(A_{\ldots,k,\ldots}^?)$ в дереве $T$ имеет вид $p_k \cdot f(T \setminus A_k)$,
  где в двухкомпонентном графе $T \setminus A_k$ рассматривается только
  компонента содержащая корень.
\end{prop}
\begin{proof}
  Следует из независимости событий и соображений размерности ;)
\end{proof}
\begin{foll}\label{prob-mult2}
  Вероятность $P(A_{i,\ldots,j}^?)$ имеет вид $\prod_{i,\ldots,j} p_k \cdot
  f(T')$, где $T'$ --- дерево $T$ без всех вершин $A_i,\ldots, A_j$.
\end{foll}

Для этого необходимо для дерева $T'$
посчитать его <<вес>> $W(T')$, то есть сумму вероятностей для гипотез
в $T'$. Эта величина всегда меньше 1. Соответственно, это вероятность <<сбоя>>
в поддереве $T'$. Положим $p_k = W(T')$ и пусть вероятность гипотезы $A_k^?$ 
(в дереве $T$) $P(A_k^?) = p_k \cdot f(T \setminus A_k) = W(T') \cdot f(T
\setminus A_k)$, а вес дерева $W(T) = w(p_0, \ldots, p_k, \ldots) = w(p_0,
\ldots, W(T'), \ldots)$. 

Рассмотрим дерево $T'' = T +_{A_k} T'$, то есть дерево $T$, у которого
листовая вершина $A_k$ заменена на дерево $T'$. Рассмотрим
подмножество $H_{A_k}(T)$ множества гипотез $H(T)$ такое, в которое входят все
гипотезы из $H(T)$ содержащие предположение о сбое узла $A_k$. Тогда множество
$H(T'')$ это $H(T\setminus A_k) \cup (H_{A_k}(T) \times H(T'))$, то есть каждое
вхождение предположения о сбое в $A_k$ заменяется множеством гипотез о сбое в
поддереве $T'$. 

Посчитаем вероятности в дереве $T''$. Для гипотез из $H(T\setminus A_k)$ они не
изменятся (следует из \ref{prob-mult}). Рассмотрим теперь гипотезы из
$H_{A_k}(T) \times H(T')$. Они имеет вид 
$A_{i_0,\ldots,i_n,j_0,\ldots,j_k} = A_{i_0,\ldots,i_n}^? \wedge
A_{j_0,\ldots,j_k}^?$, где первая компонента (обозначим их для краткости $A_0^?$
и $A_1^?$) принадлежит дереву $T \subset A_k$, а вторая --- $T'$. Поскольку
гипотезы независимы, вероятность $P(A_{i_0,\ldots,i_n,j_0,\ldots,j_k}) =
f(A_0^?)\cdot g(A_1^?)$. 
\begin{prop}\label{prob-subtree}
$g(A_1^?) = P(A_1^?)$ в дереве $T'$.
\end{prop}
\begin{proof}
Не доказательство, но рассуждение\ldots

Просуммируем $P(A_0^?\wedge A_1^?)$ по всевозможным $A_1^?$. Поскольку они
независимы, а $P(A_0^?\wedge A_1^?)$ представимо в виде 
$f(A_0^?)\cdot g(A_1^?)$, то сумма будет равна 
$f(A_0^?) \sum g(A_1^?)$. Поскольку результат это $P(A_0^? \wedge A_k^?)$,
а $g(A_k^?)$ равна $c \cdot p_k$. Константу можно вынести в $f(A_0^?)$ и
получить, что $\sum g(A_1^?) = p_k = W(T')$.
\end{proof}

\end{proof}

\textbf{Пример}. Пусть дерево $T$ состоит из двух вершин $A_0$ и $A_1$, дерево
$T'$ --- из $A_1$ и $A_2$. Тогда $p_1' = W(T') = 1 - (1 - p_1)(1 - p_2)$,
$W(T) = p_0 + (1 - p_0) \cdot (1 -  (1 - p_1)(1 - p_2)) = 1 - \prod_0^2 (1 - p_i)$,
вероятности гипотез 
\begin{eqnarray*}
P(A_0^?)|_T & = & p_0 = P(A_0^?)\\
P(A_1^?)|_T & = & (1 - p_0) \cdot p_1' = (1 - p_0) W(T') = 
(1 - p_0) (P(A_1^?)|_{T'} + P(A_2^?)|_{T'}) \\
P(A_1^?) & = & (1 - p_0) P(A_1^?)|_{T'} = (1 - p_0) \cdot p_1 \\
P(A_2^?) & = & (1 - p_0) P(A_2^?)|_{T'} = (1 - p_0) \cdot p_2 (1 - p_1) \\
\end{eqnarray*}

Как видим, это совпадает со случаем \ref{tree-seq}.

\subsection{Расширение на графы}
В реальности часто встречаются структуры, которые нельзя описать деревом,
например когда узел $A_i$ зависит и от узла $A_j$, и от $A_k$. Для этого нам
придется несколько модифицировать изложенные выше.

\subsubsection{Обозначения}
Некоторые новые обозначения
\begin{itemize}
\item $G$ --- граф с выделенной начальной вершиной $A_0$.
\item $\hat A^?_{i,\ldots,j}$ --- сложная гипотеза вида $A_i^? \vee \ldots \vee
  A_j^?$.
\item $W(G, A_k)$ --- вес пути из $A_0$ в $A_k$, то есть вероятность сбоя между
  этими двумя вершинами (включительно).
\end{itemize}
Как несложно заметить, для деревьев $W(T, A_k) = W(A_k \cup T\setminus A_k)$, где в
$T\setminus A_k$ берется компонента содержащая корень. Напомним, что в
графе (или в дереве) есть листовая вершина только тогда, когда у нас есть
информация, что она недоступна. То есть, должна быть верна хотя бы одна
гипотеза о сбое на пути между корнем и этой вершиной (включительно).

\subsubsection{Дополнительные конструкции}
\label{gr-romb-hypo}

Кроме случаев \ref{tree-seq} и \ref{tree-par} рассмотрим еще одну конструкцию $R_n$
\begin{equation}
  \label{gr-romb}
  \xymatrix{
    & &A_0& &\\
    A_1\ar[urr]& A_2\ar[ur] &A_3\ar[u] & \ldots  & A_{n-1}\ar[llu]\\
    & &\ar[ull]\ar[ul]A_n\ar[u]\ar[rru]& &
  }
\end{equation}
При этом зависимости $A_n$ от $A_i$ могут быть двух видов: $A_n$ работает,
когда работают \textbf{все} вершины над ней (И), или хотя бы одна (ИЛИ). Обозначим
соответственно конструкцию (\ref{gr-romb}) с зависимостями вида И как
$\gand_n$, с зависимостями ИЛИ --- $\gor_n$.

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

\textbf{Случай $\gor_n$.} В этом случае есть три гипотезы --- $A_0^?$,
$A_{1,\ldots,n-1}^?$ и $A_n^?$. Соответственно
$$
P(A_0^?) = p_0,\ 
P(A_{i,\ldots,n-1}^?) = (1 - p_0) \prod_{i = 1}^{n - 1} p_i,\ 
P(A_n^?) = (1 - p_0)(1 - \prod_{i = 1}^{n - 1}p_i) p_n.
$$
Этот результат можно было получить, заметив что для первой и второй гипотез
этот случай эквивалентен случаю (\ref{tree-par}).
В случае, если хотя бы одна из $A_1,\ldots,A_{n-1}$ работает, мы не можем
установить какая без дополнительной информации.

\textbf{Случай $\gand_n$.} Он несколько сложнее. В нем есть три гипотезы ---
$A_0^?$, $\hat A_{i,\ldots,n-1}^?$ и $A_n^?$. Соответственно
$$
P(A_0^?) = p_0,\ 
P(\hat A_{i,\ldots,n-1}^?) = (1 - p_0)(1 - \prod_{i = 1}^{n - 1} (1 - p_i)),\ 
P(A_n^?) = (1 - p_0)\prod_{i = 1}^{n - 1} (1 - p_i) \cdot p_n.
$$
При этом, в случае если вторая гипотеза верна, вероятности сбоев
соответствующих вершин
$$
P(A_j^?) = \frac{p_j}{1 - \prod_{i = 1}^{n - 1}(1 - p_i)}.
$$

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

Таким образом, имея (\ref{compose}) мы можем\footnote{
  в случае выше были деревья, поэтому надо перепроверить 
}
строить более сложные графы, уже не являющиеся деревьями. Однако ее надо
расширить до следующего метода.
\begin{prop}
\label{compose-graph}
Возможна замена промежуточной вершины на граф.
\end{prop}
\begin{proof}
Пусть у нас был граф $G$ и мы хотим заменить в нем вершину $A_1$ на граф $G'$,
с начальной вершиной $A_1'$ и листовой $A_1''$.
\begin{equation}
  \label{gr-compose}
  \xymatrix{
    G \ar@{.>}[d]& A_0 & A_1\ar[l]\ar@{.>}[d]\ar@{.>}[rd] & & A_2\ar[ll] \\
    G +_{A_1} G' & A_0 & A'\ar[l] & A''\ar@{:>}[l]^{G'} & A_2\ar[l] \\
  }
\end{equation}

Посмотрим, как при этом изменятся вероятности. Обозначим новый граф $G''$. Как и
в (\ref{compose}) положим $p_1$ в графе $G$ равной весу вставки $W(G',A'')$.
Рассмотрим следующее множество $H'(G'')$. Рассмотрим в $G'$ компоненту
$L(A'')$, удаление которой приведет к удалению лишь листовой вершины $A''$, то
есть наибольшая компонента, содержащая $A''$ в качестве единственной листовой
(например, если $A'' = A_n$, для $S_n$, $\gor_n$, $\gand_n$ это весь граф, а в $P_n$ --- лишь
сама вершина $A''$). Тогда множество $H(G')$ распадаяется на два подмножества:
\begin{itemize}
\item множество $H'(G'\setminus L(A''))$ гипотез из $H(G')$, которые лежат в 
  $H(G'\setminus L(A''))$, то есть множество из гипотез, в которые не входят 
  вершины из $L(A'')$;
\item $(H(G')\setminus H'(G'\setminus L(A'')))|_{G'\setminus L(A'')} \times H(L(A'')) $, 
  то есть произведение множества гипотез из $L(A'')$ и гипотез из 
  $H(G')\setminus H'(G\setminus L(A''))$, суженых на $G'\setminus L(A'')$.
\end{itemize}
Тогда множество гипотез $H(G'')$ распадается на следующие компоненты
\begin{itemize}
\item $H'(G\setminus A_1)$, где из графа выкидываются вершины, недостижимые из
  корневой после удаления $A_1$;
\item $H_{A_1}(G)|_{G\setminus A_1} \times H(G')$, где $H_A(G)$ --- множество
  гипотез из $G$, содержащих предположение $A^?$;
\item $H_G'' \times H_{G'}''$, где первый множитель --- оставшиеся гипотезы из
  $H(G)$, а второй --- второе подмножество из $H(G')$ описаное выше.
\end{itemize}
Можно заметить, что в эти множества входят гипотезы покрывающие все листовые
вершины, то есть они лежат в $H(G'')$. Осталось показать, что нет гипотез из
$H(G'')$, не лежащих в этих множествах. Пусть есть какая-то гипотеза $A^?$, в
которую входят вершины $A_i$. Возможны следующие случаи:
\begin{itemize}
\item среди вершин есть такая, которая лежит <<над>>\footnote{по зависмостям}
  вершиной $A_1$, тогда эта гипотеза принадлежит первому подмножеству;
\item есть вершина, находящаяся <<между>> $A'$ и $A''$, тогда это эквивалентно
  второму подмножеству, поскольку можно выделить подгипотезу из $H(G')$;
\item есть такая, которая лежит <<под>> $A_1$, тогда для <<закрытия>> листовых
  вершин из $G'$ должны быть предположения о сбоях в $G'$, то есть подгипотеза
  из $H''_{G'}$ (не любая из $H(G')$, так как по предположению гипотезы $A''$
  работает).
\end{itemize}
\end{proof}

\begin{xcomment}{}
\subsection{Метод}
Покажем, как изложеное выше можно применить к вычислению вероятностей гипотез в
какой-то структуре. Пусть у нас есть список узлов с заданными для них
зависимостями вида <<зависит от $\bigvee_i A_i$>> или <<зависит от $\bigwedge_i
A_i$>>. Покажем теперь, как можно обрабатывть поток сообщений вида $A_i^-$ или
$A_i^+$. Начальное состояние $G(0) \equiv \{A_{mon}\}$, содержащее единственную
мета-вершину, обозначающую систему мониторинга. Пусть в момент времени
$t_0 > 0$ приходит сообщение $A_i^-$. Тогда граф $G(t_0)$ будет содержать
единственную листовую вершину $A_i$. 
Рассмотрим какой-нибудь путь $(A_{mon}, A_i)$, положим $G_1$ состоящим из
вершин $A_{mon}, A_i$ и ребра их соединяющего. Рассмотрим множество $D(A_i)$
вершин, от котрых зависит $A_i$. Проведем замену вершины $A_i$ на граф
$R_{|D(A_i)|}$ ($\gand$ или $\gor$, если зависимость вида И или ИЛИ
соответственно). Рассмотрим какую-нибудь вершину $A_j \in D(A_i)$ и произведем
замену $A_j \leftarrow R_{|D(A_j)|}$. Далее будем производить такие замены до
тех пор, пока все не будут произведены. Покажем как разрешать
конфликты. 

Конфликтом первого вида является ситуация, когда вершина $A_i$, уже существующая на
одной из ветвей, появляется среди зависимостей $A_j$ при перестройке какой-то
другой ветви. Этот случай мы можем можем обработать, <<опустив>> ветвь, то есть
заменив ребро $A_{mon} \leftarrow A_j$ на ребро $A_i \leftarrow A_j$. 
При этом могут возникать ошибки вида (\ref{graph-err}).
\begin{equation}
  \label{graph-err}
  \xymatrix{
    A_0 & \ar[l]A_1 &\ar[l]A_2\\
    A_0'\ar[u] & \ar[l]A_1'\ar[u] &\ar[l]A_2'\ar[u]
  }
\end{equation}

Назовем <<степенью>> вершины разницу числа входящих ребер и числа исходящих.
Как несложно заметить, для любого графа без висящих ребер сумма степеней вершин
по графу нулевая. Таким образом, чтобы проверить что подграф замкнут,
достаточно посчитать сумму степеней его вершин. Покажем как можно определить на
этапе построения, может ли у нас появиться структура вида
(\ref{graph-err}). Пусть у нас добавляется ребро $A_i \leftarrow
A_j$. Посчитаем сумму степеней вершин в графе, порожденном $A_i$. Если она
нулевая, то таких структур не возникло. Действительно, для возникновения такой
структуры должна возникнуть связь $A_1 \leftarrow A_1'$ или $A_1 \leftarrow
A_2$. В этих случая сумма степеней вершин ненулевая из-за ребра $A_0' \leftarrow
A_1'$.
\end{xcomment}

При добавлении новой вершины, начнем от нее строить граф вверх. В некоторый
момент на очередном шаге $A_j$ нам потребуется подсоединиться к уже существующей
вершине $A_i$ графа. Если на этом шаге $|D(A_j)| \neq 1$, мы не можем продолжить
построение. Иначе произведем замену вершины $A_i$ на граф состоящий из вершины
$A_i$ и уже построеного графа $G'$. Для такой конструкции множество гипотез
совпадает со множеством гипотез $H(G')$, дополненого гипотезой $A^?_i$.

Тогда гипотезы в новом графе $G +_{A_i} G'$, как мы показали выше, представимы
в виде трех компонент:
\begin{itemize}
\item гипотезы из $G$, в которые входит гипотеза <<над>> $A_i$
\item гипотезы из $G$, в которые входит $A^?_i$ дополненные всеми гипотезами из
  $H(G')$
\end{itemize}

Существуют конструкции, которые мы не можем создать таким образом, например
(\ref{graph-unable}).
\begin{equation}
  \label{graph-unable}
  \xymatrix{
    A_1\ar[r] & A_0 &\ar[l]A_2\\
    A_1'\ar[r]\ar[u] & A_0'\ar[u] &\ar[l]A_2'\ar[u]
  }
\end{equation}


\section{Реализация}
\label{impl}

В данный момент реализован (см. \ref{src:hcollect})
клиент к \texttt{collectd} серверам, обрабатывающий поток сообщений рассылаемый ими в сеть. 
Разбор данных сделан относительно 4 версии демона. В качестве языка реализации
был выбран Haskell и сервер HAppS, позволяющий в то же время предоставить
удобный отладочный HTTP интерфейс \cite{happs:url}.

\subsection{Внутреннее представление}
\input{../hcollect/Monitor/Types.ths}

\subsection{Обработка сообщений}

В данный момент поддерживаются только сообщения от \texttt{collectd}. Сначала
они преобразуются к внутреннему виду (см. \ref{impl-msg}), при этом состояние
декодироуется только для сообщений типа \texttt{ping} и \texttt{hddtemp}. После
приведения оно модифицирует состояние системы как описано ниже.

\input{../hcollect/Monitor/Update.ths}

\input{../hcollect/Monitor/Decide.ths}

\subsection{Возможная архитектура}

Обработка сообщения может выглядеть следующим образом
\begin{itemize}
\item декодируется и преобразуется в родной для системы формат (\ref{impl-msg});
\item проходит через фильтр и ненужные выкидываются;
\item поступает на обработку и модифицирует состояние системы (\ref{impl-update});
  \begin{itemize}
  \item агрегируется, что-то типа \texttt{rrd} (\ref{impl-aggr}).
  \item отправляется куда-нибудь в другую систему;
  \end{itemize}
\end{itemize}

\input{../hcollect/Monitor/Process.ths}

\section{Не рассмотренные проблемы}

\begin{itemize}
\item замена дерева на ориентированный граф без циклов;
\item преобразование данных из родного формата \texttt{collectd}
  (см. \ref{ext-collectd}) в данный момент производится только для плагинов
  \texttt{ping} и \texttt{hddtemp}.
\end{itemize}

\appendix
\section{Внешний источник \texttt{collectd}}
\label{ext-collectd}

В качестве внешнего источника данных используется \texttt{collectd}
\subsection{Внутреннее представление}
\subsubsection{Разбор}
Разбор данных производится с использованием \texttt{Data.Binary} по схеме,
похожей на функцию \texttt{parse\_packet} из \texttt{src/network.c} исходных
кодов демона \texttt{collectd} версии 4.1.2.

\input{../hcollect/HCollect/Types.ths}

\section{Обработка Lisp--выражений}
\label{impl-lisp}
В качестве языка для описания функций приведения данных от сенсоров к
внутреннему представлению (\ref{impl-state}) используется Lisp. Рассматривались
еще несколько альтернатив, такие как Haskell или Lua (\cite{lua:url}), но по
ряду причин был выбран Lisp. В частности потому, что его интеграцию с системой 
просто реализовать на достаточно хорошем уровне. В качестве основы была взята
работа \cite{eval-lisp:url} и в изрядной степени переделана. К наиболее
существенным изменениям следует отнести:
\begin{itemize}
\item введение оператора \texttt{quote} (') и строк;
\item введение механизма передачи данных между Lisp и Haskell;
\item приведение диалекта в какой-то мере к виду Scheme;
\item переработка кода, позволяющая получить чистое вычисление выражения (ошибки
  обрабатываются типом \texttt{Either String a});
\end{itemize}

Хотя реализованный диалект в целом близок к Scheme, у него есть некоторые
отличия:
\begin{itemize}
\item нет макросов;
\item обработка логических значений сделано как в Common-Lisp, то есть
  \texttt{()} --- это ложь, все остальные значения --- истина;
\item добавлен элемент \texttt{T}, ссылающийся на самого себя, обозначающий
  логичское значение <<истина>>;
\item операторы сравнения \texttt{eq} и \texttt{=} рекурсивно сравнивают
  S--выражения, то есть сравнение \texttt{(eq '(1 2 3 (4)) 5.24)} корректно,
  хотя и вернет <<ложь>>;
\item конструкции \texttt{let} и \texttt{letrec} эквивалентны;
\end{itemize}

\section{Исходные коды}
\subsection{hcollect}
\gitlinks{hcollect}
\subsection{haskell-lisp}
\gitlinks{haskell-lisp}

\bibliography{phyl}

\end{document}
