\section{\textit{Linux Virtual Server} - LVS}
\label{lvs}
%\cutname{lvs.html}
% \chapter{Introdução}

\textit{Linux Virtual Server} (LVS) é uma tecnologia que permite a construção de sistemas com alta disponibilidade e altamente escaláveis, a partir do uso conjunto de vários servidores. A arquitetura é totalmente transparente para o usuário final, serviços providos por um conjunto de máquinas são acessados através de um único servidor. O LVS pode oferecer serviços de maior capacidade/desempenho, ou serviços redundantes (quando servidores individuais tiverem que sair do ar para manutenção) em relação aos serviços disponíveis em servidores únicos (LVS-HOWTO \cite{LVS}).

O LVS é como um roteador da camada 4 do modelo OSI (vide a sessão ~\ref{modeloosi}). A semântica padrão do cliente-servidor continua preservada, onde cada cliente pensa que está diretamente conectado a um servidor real e este pensa que está conectado diretamente a um cliente. Nem o cliente nem o servidor sabem que as conexões sofrem a intervenção do direcionador. Um servidor real do LVS não coopera e nem sabe da existência de outros servidores reais no LVS, um LVS não é um \textit{beowulf} ~(vide \ref{beowulf}) e também não é um cluster, mas se comporta como um agregador de serviços que possibilita o atendimento de uma demanda grande em um serviço (LVS-HOWTO \cite{LVS}).

O código IPVS, que possibilita a construção do sistema LVS, é uma coleção de modificações para kernel Linux, que combinadas com as capacidades de roteamento e filtragem de pacotes de uma máquina Linux, transformam-na em um roteador com características especiais, capaz de balancear sessões TCP e UDP entre várias máquinas. Este roteador especial (balanceador de carga), chamado Linux Director (ou simplesmente Director) distribui a carga de requisições de serviços entre as máquinas que os provêem. Com isso, o sistema constituído pela máquina Linux com o código IPVS e as outras máquinas que hospedam os serviços é chamado \textit{Linux Virtual Server} (LVS), vide figura \ref{fig:lvsvirtualserver}.

\begin{figure}[!htb]
\centering
\insimg{0.5}{imagens/virtualserver.png}
\caption{Esquema geral de um Linux Virtual Server}
\label{fig:lvsvirtualserver}
\end{figure}

O sistema LVS não necessita de nenhuma modificação nos Servidores Reais (que podem estar interconectados na mesma LAN ou geograficamente dispersos em uma WAN) ou nos clientes. Estes por sua vez, enviam suas requisições apenas para uma máquina (Director) não importando quantos Servidores Reais estejam provendo os serviços, que podem ser os comuns HTTP e HTTPS, servidores de email, bancos de dados, CVS, SSH, ou seja, em geral todas as aplicações TCP/IP usufruem desse sistema.

O LVS provê, de maneira transparente e simples, um ambiente altamente escalável de alta disponibilidade. Seu ponto único de falha (ponto crítico) é o Director, mas mesmo assim, em conjunção com outras ferramentas (como \textit{Heartbeat} e \textit{LDirectord}) pode-se construir um sistema de alta-disponibilidade para o Director, aumentando ainda mais sua confiabilidade e eliminando seu ponto único de falha.

Mais informações e documentações detalhadas sobre o LVS podem ser obtidas nos seguintes endereços:\\
\www{http://www.linuxvirtualserver.org}\\
\www{http://www.ultramonkey.org}\\
\www{http://www.austintek.com/LVS/LVS-HOWTO/}\\


\subsection{Nomenclatura e abreviações}

Em textos sobre LVS, tornou-se comum o uso de termos específicos para designar os componentes do sistema, segue a descrição de alguns deles:

\begin{enumerate}[.]

\item \textbf{LVS, Linux Virtual Server} - designa a combinação Director+Servidores Reais, que juntos compõem o Servidor Virtual, sendo visto pelos clientes como uma única máquina.

\item \textbf{Director} - a máquina que roda o código \textbf{ipvs}. É um roteador com regras especiais que recebe requisições de serviços de clientes e as repassa para máquinas que disponibilizam os serviços.

\item \textbf{Servidor Real} - a máquina que hospeda os serviços, é quem de fato trata requisições de clientes.

\item \textbf{Métodos de Redirecionamento (LVS-Nat, LVS-DR, LVS-Tun)} - Sendo o Director um roteador com regras específicas de redirecionamento, estes métodos determinam como os pacotes dos clientes são redirecionados para os Servidores Reais.

\item \textbf{Métodos de escalonamento (\textit{scheduling})} - algoritmos usados pelo Director para selecionar o Servidor Real que vai tratar uma nova conexão estabelecida por um cliente.

\item \textbf{VIP (Virtual IP)} - endereço IP usado pelo Director para fornecer os serviços aos clientes.

\item \textbf{RIP (Real IP)} - designa os endereços IP usados pelos Servidores Reais.

\item \textbf{DIP (Director's IP)} - endereço IP usado pelo Director para se comunicar com os Servidores Reais. 
\end{enumerate}

\subsection{Tipos de Cluster LVS}

Os sistemas montados com o uso de LVS são, normalmente, descritos pelo tipo de método de redirecionamento das requisições para os nós do cluster. Há três métodos disponíveis:

\begin{enumerate}[.]
\item LVS-NAT (\textit{Network address translation})

\item LVS-DR (\textit{Direct Routing})

\item LVS-TUN (\textit{IP tunneling})
\end{enumerate}

Mais de um método pode ser usado em um único Director, tendo por base as características dos nós do cluster. O método mais simples de se implementar é o LVS-NAT.

\subsubsection{\textit{Network Address Translation} (LVS-NAT)}

Em uma configuração LVS-NAT, o Director usa a habilidade do kernel Linux de mudar o endereço IP e porta dos pacotes que passam por ele. Neste método, o Director recebe uma requisição de um cliente e a repassa para um Servidor Real, que a processa, enviando o resultado de volta para o Director, que então faz as mudanças necessárias para converter o IP dos pacotes no endereço de servidor virtual, dando resposta ao cliente, dando a este a impressão que está tratando apenas com uma máquina, conforme figura \ref{LVS-NAT}.

\begin{figure}[!htb]
\centering
\insimg{0.5}{imagens/lvsnat.png}
\caption{LVS-NAT}
\label{LVS-NAT}
\end{figure}

\paragraph{Propriedades de LVS-NAT}


\begin{enumerate}[.]
\item Os Servidores Reais devem estar na mesma subrede do Director,

\item Os endereços dos nós (Servidores Reais) normalmente estão em conformidade com a RFC 1918,

\item As conexões (de entrada e saída) passam todas pelo Director,

\item O Director deve ser o \textit{gateway} padrão dos Servidores Reais,

\item O Director pode remapear números de portas, isto é, uma requisição recebida em uma porta dele e pode ser redirecionada para uma porta diferente de um Servidor Real,

\item Qualquer sistema operacional pode ser usado nos Servidores Reais,

\item O gargalo do ambiente pode ser um único Director configurado para atender a demanda, embora uma rede saturada normalmente seja o problema mais comum.
\end{enumerate}

\subsubsection{Direct Routing (LVS-DR)}

Neste modelo, baseado no NetDispatcher\footnote{Software de roteamento da IBM usado para balancear carga entre servidores TCP, mais informações podem ser obtidas em: \www{http://www.cs.princeton.edu/courses/archive/fall03/cs518/papers/networkdispatch.pdf} }, o Director repassa as conexões para os Servidores Reais e estes respondem diretamente para os clientes que fizeram as requisições. Para isto, os Servidores Reais deverão estar no mesmo segmento de rede que o Director, assim como todas as máquinas (Directors e Servidores Reais) que usam o mesmo VIP.%, a despeito disto os clientes ainda enviam suas requisições apenas para o Director.

Todos os Servidores Reais possuem uma interface virtual de \textit{loopback}(lo:0) configurada com o VIP que não responde a requisições ARP, redirecionando as conexões que receber para uma porta local e respondendo diretamente ao cliente, o que implica que o Director não necessita estar no caminho de volta.

Os Servidores Reais podem ser acessados de fora da rede, caso haja falha no balanceador de carga. No caso de ser usado apenas um Director e não houver outro que atue como ''backup'', os servidores reais podem ser acessados de fora da rede diretamente.

\begin{figure}[!htb]
\centering
\insimg{0.5}{imagens/lvsdr.png}
\caption{LVS-DR}
\label{LVS-DR}
\end{figure}

\paragraph{Características do LVS-DR }

\begin{enumerate}[.]
\item Os Servidores Reais devem estar na mesma rede que o Director,

\item Os RIP não necessitam estar em conformidade com a RFC 1918,

\item Somente as requisições passam pelo Director, as respostas são enviadas diretamente aos clientes pelos Servidores Reais,

\item As portas não podem ser remapeadas no Director,

\item LVS-DR permite mais Servidores Reais que LVS-NAT,

\item Não há sobrecarga no Director como no LVS-NAT.

\end{enumerate}

\subsubsection{Encapsulação IP-IP(\textit{Tunneling})(LVS-Tun)}

IP \textit{tunneling} (RFC 2003) é uma técnica que permite que pacotes IP sejam colocados dentro de outros pacotes IP, permitindo que pacotes destinados a um determinado endereço IP sejam redirecionados para outro endereço. Neste método de configuração de LVS o Director e os Servidores Reais não necessitam estar no mesmo segmento de rede, mesmo estando geograficamente distantes (como no caso de \textit{mirrors} de ftp). Dessa forma, os Servidores Reais podem usar qualquer endereço de rede e não apenas endereços privados.

\begin{figure}[!htb]
\centering
\insimg{0.5}{imagens/LVS-Tun.png}
\caption{LVS-Tun}
\label{LVS-Tun}
\end{figure}

\paragraph{Características do LVS-Tun}

\begin{enumerate}[.]
\item Os Servidores Reais não necessitam estar no mesmo segmento de rede que o Director,

\item Os RIP não necessitam estar de acordo com a RFC 1918,

\item O Director apenas recebe requisição dos clientes, as respostas são enviadas diretamente dos Servidores Reais,

\item O Director não pode remapear portas,

\item Os sistemas operacionais dos Servidores Reais precisam suportar IP \textit{tunneling}.
\end{enumerate}




\subsection{Algoritmos de escalonamento}

Existem vários algoritmos utilizados para a implementação do LVS e seus métodos de escalonamento para o balanceamento de carga. Os métodos de escalonamento regulam a maneira como a carga é distribuída entre os nós que compõem o sistema. Quando o Director recebe uma requisição de um cliente, é através dos algoritmos de escalonamento que ele decide qual nó deverá trata-la.

Existem métodos de escalonamento dinâmico que dão maior controle sobre a carga de chegada, com pouco ou nenhum custo adicional em processamento. O Director mantêm uma lista do número de conexões ativas e inativas para cada nó do cluster e usa esta informação para determinar qual nó irá receber uma nova conexão. %Uma conexão permanece ativa (em estado ESTABILISHED) enquanto houver troca de informação entre o computador cliente e um servidor, por sua vez, a conexão torna-se inativa quando não esta em estado ESTABILISHED.

Os métodos são discutidos nas sessões a seguir.


\subsubsection{\textit{Round-Robin} (RR)}

O Director mantém uma lista com os endereços de cada Servidor Real, assim que recebe uma conexão, ele a redireciona para um servidor dessa lista, onde uma próxima conexão será enviada para o servidor seguinte e assim continua percorrendo essa lista de forma circular atendendo todas as requisições. Todos os servidores da lista são tratados de igual maneira, não importando quantas conexões estão sendo manipuladas por um servidor específico, nem seu tempo de resposta e/ou capacidade de processamento.

\subsubsection{\textit{Round-Robin} com pesos (WRR)}

Cada nó do sistema LVS possui um peso (inteiro associado à sua capacidade de processamento e atribuído pelo administrador do ambiente), baseado na quantidade de carga que ele pode manipular (capacidade de processamento). O peso é então usado, em conjunção com o método round robin, para selecionar o próximo nó que será usado quando uma nova conexão chegar, sem levar em consideração o número de conexões que ainda estão ativas. Servidores Reais com pesos maiores terão prioridade no recebimento e quantidade de requisições, se comparados com Servidores Reais com pesos menores.

\subsubsection{\textit{Destination hash} (DH)}

Neste método, o Director sempre envia requisições de um mesmo endereço IP de origem para o mesmo Servidor Real no sistema LVS, usando uma lista estática de endereços de destino. O método é útil quando o Servidor Real é um servidor \textit{proxy} ou \textit{cache}.

% \subsubsection{Source hashing (SH)}
% 
% Este método pode ser usado quando o Director precisa certificar-se que os pacotes de resposta são enviados de volta pelo mesmo roteador ou firewall do qual a requisição veio. Este método de escalonamento é apenas necessário quando o Director possui mais de uma interface física de rede e precisa saber para qual firewall ou roteador enviar os pacotes de resposta.

% \subsection{Métodos de escalonamento dinâmico}



\subsubsection{\textit{Least-Connection} (LC)}

Com este método, quando uma nova conexão chega, o Director verifica o número de conexões ativas e inativas para determinar para qual nó irá enviar a requisição.

Para realizar esta escolha, o Director multiplica o número de conexões ativas do nó por 256 (atribuição interna do algoritmo em sua implementação) e adiciona ao resultado o número de conexões inativas resultando num \textit{overhead}\footnote{Métrica definida no algoritmo utilizada para realizar a distribuição da carga.} para cada nó. O nó com menor \textit{overhead} receberá a conexão. Caso haja nós com mesmo \textit{overhead}, o primeiro nó encontrado na tabela do IPVS será selecionado.

\subsubsection{\textit{Weighted Least-Connection} (WLC)}

Este método combina o \textit{Least-Connection} com um peso para cada nó (este é o método padrão se nenhum for selecionado), útil para ser usado com nós de diferentes capacidades de processamento.

O Director determina para qual nó uma requisição será enviada, calculando o \textit{overhead}, como no método anterior, dividindo este número pelo peso associado ao nó. O nó com menor valor associado após esta operação receberá a conexão. Caso haja nós com mesmo valor associado, o primeiro da tabela do IPVS será selecionado.

\subsubsection{\textit{Shortest Expected Delay} (SED)}

Este método pode oferecer uma sensível melhoria em relação ao método WLC em serviços que usam TCP e mantêm a conexão ativa enquanto o nó processa a requisição.

O cálculo do valor do \textit{overhead} para o SED é feito adicionando-se 1 ao número de conexões ativas, dividido pelo peso associado a cada nó. O nó com menor \textit{overhead} recebe a requisição.

Deve-se notar o seguinte neste algoritmo:

\begin{enumerate}[.]
\item Ele não usa o número de conexões inativas enquanto determina o \textit{overhead} para cada nó.

\item Adiciona 1 ao número de conexões ativas para antecipar como o \textit{overhead} irá parecer quando uma nova conexão for realizada.
\end{enumerate}

O algoritmo SED tenta minimizar o tempo de espera para cada trabalho até sua  finalização. O tempo de espera é $(Ci+1)/Ui$, sendo $Ci$ o número de conexões do servidor e Ui o peso fixado para este servidor.

A diferença entre SED e WLC é que SED inclui a conexão que chega na função de custo, incrementando 1. Ele apresenta melhor qualidade em grandes sistemas heterogêneos, cujos pesos variam muito.

\subsubsection{\textit{Never Queue} (NQ)}

Este método apresenta uma melhoria em relação ao SED, pois caso um nó não possua conexões ativas ele receberá uma nova requisição de serviço. Apesar do resultado apresentado no cálculo do SED podem ocorrer situações que uma máquina que não possua nenhuma conexão ativa apresente um \textit{overhead} maior que outra que possua.

\subsubsection{\textit{Locality-Based Least-Connection} (LBLC)}

Directors também podem direcionar o tráfego de saída para o conjunto de servidores \textit{proxy} transparentes. Nesta configuração, os nós do cluster são \textit{proxy} transparentes ou servidores de web \textit{cache} que estão entre os clientes e a Internet.

Quando o LBCL é usado, o Director tenta enviar todas as conexões de um endereço IP particular para o mesmo servidor \textit{proxy} transparente (nó do cluster). Ou seja, a primeira vez que uma requisição chegar, o Director irá escolher um Servidor Real para atendê-la usando um versão um pouco modificada do método WLC e todas as requisições subseqüentes deste cliente continuarão a ser enviadas para o servidor escolhido.

\subsubsection{\textit{Locality-Based Least-Connection with Replication Scheduling} (LBLCR)}

É semelhante ao método anterior com uma melhoria, o Director mantém um mapeamento de um cliente para um conjunto de servidores que podem atendê-lo. Se todos os nós do conjunto estiverem sobrecarregados, o Director apanha um servidor com menos conexões e o adiciona ao conjunto. Caso este conjunto não se modificar em um intervalo de tempo específico (seis minutos, intervalo padrão como definido no código do IPVS), o servidor com maior carga será excluído.

\subsection{Casos de uso de LVS}

Muitas empresas utilizam o LVS para suprir a demanda por uma grande capacidade de processamento de requisições e para poder dividir/balancear a carga de seus sistemas por outras localidades (máquinas remotas), melhorando assim o atendimento das demandas de acesso a seus sistemas e sítios WEB.

Alguns exemplos de sítios e empresas que utilizam a tecnologia são listados abaixo. Mais casos de uso podem ser encontrados em \www{http://www.linuxvirtualserver.org/deployment.html}.


\begin{small}\begin{table}[!htb]
\begin{center}
% use packages: array
\begin{tabular}{p{6.0cm} | p{8.0cm}}
\hline
Sítio & Forma de utilização \\ \hline

\www{http://linux.com} & Balanceamento de carga HTTP\\ \hline

\www{http://sourceforge.net} & Balanceamento de carga HTTP, HTTPS, FTP, SSH, CVS\\ \hline

\www{http://themes.org} & Balanceamento de carga HTTP\\ \hline

\www{http://wwwcache.ja.net} & 40 servidores Squid em 3 clusters LVS\\ \hline

\www{http://www.zope.org} & Balanceamento de carga HTTP\\ \hline

\www{www.songn.com} & Um Director rodando em modo VS/DR com mais de 6 nós de servidores Windows 2000\\ \hline


\end{tabular}
\end{center}
\caption{Exemplos de Sítios que utilizam LVS}
\end{table} 
\end{small}
\newpage

% 
% \subsection{Referências}


