From f520af860db1348fce35b02de9cba74fed1fd88c Mon Sep 17 00:00:00 2001 From: Rodrigo Eduardo Lazo Paz Date: Mon, 14 Feb 2011 14:04:51 -0200 Subject: [PATCH] First part of proposal wrote. --- mscMonografia.tex | 106 ++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 87 insertions(+), 19 deletions(-) diff --git a/mscMonografia.tex b/mscMonografia.tex index 116d6a2..efa674b 100644 --- a/mscMonografia.tex +++ b/mscMonografia.tex @@ -196,8 +196,8 @@ executam as mesmas solicitações, no mesmo ordem; e a passiva, onde um único processo recebe todas as solicitações, as aplica localmente, e depois seu estado é copiado pelas demais réplicas. Um dos métodos mais utilizados para a implementação da replicação ativa é a aplicação de -algoritmos de consenso -~\cite{Lamport:1998:PP:279227.279229,Schneider:1990:IFS:98163.98167,Oki:1988:VRN:62546.62549}. +algoritmos de consenso ~\cite{Lamport:1998:PP:279227.279229, + Schneider:1990:IFS:98163.98167,Oki:1988:VRN:62546.62549}. Nesta seção discute-se a fundamentação teórica da solução de replicação ativa, baseada em consenso com processos que podem falhar e @@ -295,12 +295,12 @@ dos processos \textit{ruins}: % apresentar o resultado de impossibilidade O resultado de impossibilidade obtido por Fischer, Lynch e Patterson ~\cite{fischer85} mostra que o problema não pode-se resolver de -maneira determinista num sistema distribuído assíncrono com apenas -um processo falho. Existem distintas soluções propostas: o uso de +maneira determinista num sistema distribuído assíncrono com apenas um +processo falho. Existem distintas soluções propostas: o uso de randomização~\cite{Chor89}, definição de problemas mais débeis e suas soluções~\cite{dolev87}, detetores de falhas não confiáveis -~\cite{Chandra:1996:WFD:234533.234549,Chandra:1996:UFD:226643.226647}, -etc. +~\cite{Chandra:1996:WFD:234533.234549, + Chandra:1996:UFD:226643.226647}, etc. \todo{Incluir a descrição de Paxos} @@ -518,13 +518,12 @@ são: \subsection{Detetores de falhas } \label{sec:detetores} Os detetores de falhas não confiáveis, propostos inicialmente por -Chandra e -Toueg~\cite{Chandra:1996:WFD:234533.234549,Chandra:1996:UFD:226643.226647}, -são, informalmente, um conjunto de módulos distribuídos, um por -processo do sistema, que possuem uma visão deste, i.e. uma listagem -dos processos que são suspeitos de ter falhado, mas não precisasse -garantir que a visão seja correta, e.g. pode-se incluir na lista de -suspeitos processos que não falharam. +Chandra e Toueg~\cite{Chandra:1996:WFD:234533.234549, + Chandra:1996:UFD:226643.226647}, são, informalmente, um conjunto de +módulos distribuídos, um por processo do sistema, que possuem uma +visão deste, i.e. uma listagem dos processos que são suspeitos de ter +falhado, mas não precisasse garantir que a visão seja correta, +e.g. pode-se incluir na lista de suspeitos processos que não falharam. Formalmente, a \textit{historia de um detetor de falhas} \(H\) é uma função de \(\Pi \times \mathcal{T}\) a \(2^\Pi\), onde \(H(p,t)\) é o @@ -540,9 +539,10 @@ execuções com o patrão de falhas. \(F\). % usar "decidem" e não "escolhem" em consenso Na proposta original de Chandra e -Toueg~\cite{Chandra:1996:UFD:226643.226647,Chandra:1996:WFD:234533.234549}, -se definiam duas propriedades de completude e quatro de precisão que -podiam cumprir os detetores de falhas: +Toueg~\cite{Chandra:1996:UFD:226643.226647, + Chandra:1996:WFD:234533.234549}, se definiam duas propriedades de +completude e quatro de precisão que podiam cumprir os detetores de +falhas: \begin{inparaenum}[\itshape a\upshape)] \item \textit{completude forte}, eventualmente todo processo que caiu é suspeito permanentemente por \textit{todos} os processos bons; @@ -596,14 +596,82 @@ ele falhou até o momento. \section{Treplica} \label{sec:treplica} -E melhor utilizar os relatório técnico -~\cite{vieira08a-tr,vieira10:implementing-tr} ou o artigo +E melhor utilizar os relatório técnico ~\cite{vieira08a-tr, + vieira10:implementing-tr} ou o artigo ~\cite{vieira08:_trepl}\todo{Vou incluir aspectos gerais do treplica, ou algum em particular?} \section{Proposta de pesquisa} \label{sec:proposta} -\todo{olhar os comentários do código fonte} +Pesquisas anteriores~\cite{gray07:empirical, + Schroeder:2007:DFR:1267903.1267904, 10.1109/SRDS.2008.9, + Pinheiro:2007:FTL:1267903.1267905} mostraram que, na prática, as +falhas dos componentes de hardware dos sistemas distribuídos de +produção são maiores às reportadas pelos fabricantes; além disso, +erros no software também causam quedas nos processos, portanto a +tolerância a falhas é vital. + + +As alternativas a avaliar são as seguintes: + +% hay que tener en consideracion que en este caso no se asume las +% fallas de disco dentro de la evaluacion. El metodo necesario para +% soportar esa situacion seria, por ejemplo, el uso de un sistema de +% archivos distribuido con replicacion, como hdfs. Aunque el impacto +% sobre el desempenho del sistema no es, necesariamente, despreciable, +% puede asumirse que afecta de manera uniforme a todos los nodos del +% sistema que utilizan la memoria estable. + +\paragraph{Armazenamento local} +Cada processo é responsável pela persistência de seu estado e do +estado de seu canal de comunicação. A data é escrita na memoria +estável, e portanto sua perdida por falhas é baixa. O custo da +recuperação do estado anterior é dominado pela latência da memoria +estável, e não tem impacto nenhum sobre os demais processos ou no +tráfego da rede. + +\paragraph{Armazenamento remoto} +A responsabilidade da persistência do estado do processo e de seu +canal de comunicação é delegada a outro nó, o qual pode ser: +\begin{inparaenum}[\itshape a\upshape)] +\item \textit{membro do sistema}, portanto cumpre duas funções + simultâneas; +\item \textit{processo dedicado}, sua tarefa é só armazenamento. +\end{inparaenum} +A motivação do armazenamento remoto, ou \textit{processo destino} +\todo{escolher nomes menos ambíguos}, é o uso da memoria volátil dele +para fornecer memoria estável, desde o ponto de vista local, ou +\textit{processo origem}. Se o processo destino mantém-se funcionando +durante a falha e recuperação do processo origem, ele é, para todo +propósito prático, tão permanente que um disco rígido. Nesse caso, o +custo da recuperação do estado anterior é dominado pela latência da +rede e a carga actual do processo destino. Os problemas com esta +aproximação é no caso da queda do processo destino, a qual pode +causar: +\begin{inparaenum}[\itshape a\upshape)] +\item \textit{Perdida de informação}, portanto é necessário o + armazenamento de alguns, não necessariamente todos, dos estados em + memoria estável. +\item \textit{Demora na recuperação do processo origem}, o qual + acontece quando o processo destino não está disponível durante a + recuperação do processo origem. Nesse caso o processo origem pode + armazenar copias de alguns de seus estados localmente, ou armazenar + seus estados em múltiplos destinos. +\end{inparaenum} +É importante considerar que a memoria volátil é finita, e portante +limitante da quantidade de informação armazenáveis por nó. + + +%comun a los dos +As distintas alternativas não são excluyentes, portanto soluções que +misturam o armazenamento local e o remoto. +%tambien notar que el costo del snapshot es constante +Se for necessaria a atualização do estado recuperado +em relação ao estado atual do sistema, o algoritmo de consenso vai-se +encarregar disso (ver seção \ref{sec:consenso}). Nesse caso, a +recuperado vai causar um incrementeo no trafego da rede e na carga de +trabalho dos processos vizinhos. + % descrever as distintas posibilidades de armazenamento, no disco % local, em outro dos processos que fazem o executam o algoritmo, % quais podem ser as combinaçoes. O requerimento de um melhor detetor -- 2.11.4.GIT