“A State Machine Approach for Problem
Detection in Large-scale Distributed System”
Kewei Sun, Jie Qiu, Ying Li, Ying Chen
IBM China Research Laboratory, Beijing, China.
Network Operations and Management Symposium - NOMS 2008
Apresentado por Katia Abreu
Tópicos em Redes
Pós-Graduação em Informática – UFPR – out/2008
Motivação

Detecção de problema é parte importante do
gerenciamento de um sistema de larga-escala


Problemas ainda são inevitáveis: bug da aplicação,
middleware instável, hardware


Sistemas distribuídos geram logs detalhados para
gravar suas atividades
Empresas: QoS reduzido, competitividade reduzida
Abordagens existentes:


Poucas consideram a análise de log de múltiplos hosts
de um sistema distribuído em larga-escala
Algumas detectam somente problemas conhecidos
Roteiro

Objetivos

Conceitos e Definições

Transação, Eventos e Transições em ME

Detecção de Anomalias e Padrões de Problemas

Um Estudo de Caso

Conclusão
Objetivos

Apresentar um novo modelo de análise de logs: PDSM
(Problem Detection State Machine)


Baseia-se na projeção do comportamento de um
sistema distribuído e mantém informações estatísticas
desse comportamento
Objetivo do método:




coletar logs de componentes do sistema,
construir uma Máquina de Estados,
e usá-la pra verificar o comportamento de um sistema.
Descrever como PDSM representa as atividades de um
sistema de larga-escala em execução.
Definição do Ambiente
O que é SD em largaescala?
SD
componentes
subsistemas
Requisição da
aplicação
Transação
O que é Maq. Estados?
Estados = componentes + transição
Controle de processamento é
passado de um componente a outro
Definições Para o PDSM

SD é composto por um conjunto de componentes
C = {c1,c2,…,cn}


Ponto de Log é o local onde log de eventos são gerados.


Um ci é componente atômico se ele não contém outros
componentes
O conjunto de pontos de log de um componente atômico é
L(ci) = {lp1,lp2,...lpm}
Para cada transação disparada por uma requisição r, ∃
um conjunto de componentes C(r), onde C(r) ⊂ C
Máquina de Estados de
Transação de Única Requisição

Define-se Máquina de Estados - Mr - de uma transação,
servindo uma única requisição, através da tupla:
Estados da
transação
Conjunto dos Eventos
que geram transições
A probab. de
um Estado de
Qr ser o estado
inicial
PDSM Global


Une todas as máquinas de estados de todas as
requisições.
Pode ser denotada por:
Questões com os Eventos

Logs são geradas por diferentes componentes


Não existe relógio global


Itens de log devem ter formato único
Um método deve determinar a ordem relativa
dos eventos
É requerido rastrear a transação e extrair os
eventos relacionados a ela
PDSM: Processamento de Eventos


Log de eventos são convertidos em um formato
único, isto é, eventos base comum
Para assegurar a abordagem adaptativa, não
assume que todos os relógios são sincronizados


Ordem parcial em um conjunto de eventos +
informações de tempo real
Para extrair os eventos relacionados à transação

Magpie, Pinpoint
Algoritmos
Construção de Máquina de Estados
Usando Log de Eventos


Agrupamento de eventos em Estados
 De acordo com suas especificações e informações de
mensagens
O algoritmo:
Detecção de Anomalia
num. Estados
de S4
num. transições de um
Estado para outro
99,9%
0,1%
Ponto de problema
ou execução de um
serviço acessado
raramente?
Como resolver?


Usar informações detalhadas da transição S2
e do Estado S5
S5
Algoritmo para avaliar a anomalia dos Estados


Idéia básica: visitar uma série de Estados ruins que se
desviam do percurso normal
O Estado mais suspeito de ser um problema é
distinguido dos demais
Algoritmo para Avaliar Estado Anormal

Classificação dos eventos em níveis de erro:
error/fatal, exception, warning, information e
unknown


É aplicada uma função para verificar o nível do
Estado de erro E(s)
Para cada Estado a partir do seu nível de erro é
calculado
 se o Estado é uma Anomalia,
 se é um estado Normal,
 ou se não é possível classificar.
Algoritmo para Detecção de
Padrão de Problema




Para erros que acontecem intermitentemente em
um ou mais Estados
Conectividade: Existe uma ligação entre esses
Estados com erros intermitentes
Verifica se o problema acontece em pares de
Estados conectivos e se ambos têm o problema
Saída: o conjunto de transições consideradas
padrões de problemas
Experimentação
4 máquinas
 Emprego do benchmark Trade 6
 A abordagem é validada sobre a aplicação
J2EE 3-tier

Problemas Introduzidos



Introduzidos separadamente
Com duração de 1 hora
Após 30 minutos de execução do sistema
Detecção de Problema
Individual

Projeção de um problema de shutdown acidental em DB2
Inserção de Um Problema


Um novo problema aumenta o número de Estados
PDSM fornece uma projeção em tempo real
Detecção de Múltiplos
Problemas

Máquina de Estados Global para todos os problemas
introduzidos
Inserção de Múltiplos
Problemas

Número de Estados e número de transições aumentam a
cada novo problema
Compressão de Logs


PDSM une informações redundantes
De milhões de logs/cententas de Estados para 1.200.000
logs/291 Estados
Conclusão





PDSM é um modelo de análise de log que representa a
execução de um sistema distribuído de larga-escala
Mantém informações estatísticas de comportamento
Reduz os esforços de análise de logs ao fazer
compressão
Não necessita de conhecimento de alguma base de
dados de problemas
É sensível a problemas desconhecidos