Distribuição de Mídia Contínua
Projeto de Servidores
Jussara M. Almeida
Abril 2004
Projeto de Servidores de Mídia Contínua
Projeto de Servidores de Mídia Contínua
• Métrica chave para desempenho de servidores:
– B = Largura de Banda do Servidor: # fluxos simultâneos o
servidor consegue sustentar
– B = min (Brede, Bdisco)
• Barramento de memória não é normalmente o gargalo
• Brede: depende da interface de rede (e.g. 100Mbps)
• Bdisco: depende da banda efetiva que os discos sustentam,
que por sua vez depende do método de armazenamento
• Componente essencial: Subsistema de Armazenamento
– Como armazenar vídeos e áudios em um dado número de
discos de forma a maximizar Bdisco?
– Como armazenar vídeos e áudios com custo-benefício
(max Bdisco, min # discos)
Projeto de Servidores de Mídia Contínua
Armazenamento de MC em Discos
• Armazenamento sequencial
– Armazena cada arquivo, inteiramente, em um disco
– Método muito simples, tradicionalmente usado
– Problema em potencial : hot spot
• Grande parte da largura de banda necessária pode ser
para uma pequena fração do conteúdo armazenado
– Arquivos populares demandam maior largura de banda
• Alocação da largura de banda e do espaço
disponíveis no sistema estão fortemente acopladas
– Número de fluxos simultâneos para um arquivo é
limitado pela largura de banda total do disco onde
ele está armazenado.
• Desbalanceamento de carga
Armazenamento de MC em Discos
• Para max Bdisco, precisa balancear carga total
entre os vários discos
• Solução natural:
– Distribuir cada arquivo pelos vários discos
• Armazenamento por faixas (striping)
– Arquivo é dividido em vários blocos e blocos são
armazenados nos vários discos, em round robin
– A demanda por largura de banda para cada
arquivo é distribuída entre todos os discos:
balanceamento
O Servidor de Videos TIGER
• Servidor de vídeo/áudio da Microsoft
– Inclui restrições de tempo real
– Objetivo: prover grande número de fluxos CBR a baixo custo,
alta disponibilidade e com grande escalabilidade
• Arquitetura distribuída
– Um número de PC’s (cubs), interconectadas por uma rede
ATM de alta velocidade
– Cada cub com um número de discos para armazenamento de
dados e um disco para o Sistema Operacional
• Tolerância a falhas
– Replicação dos dados (mirroring)
• Premissas:
– Máquinas homogêneas (mesmo hardware, mesmo # discos)
– Arquivos homogêneos (mesma bitrate)
Arquitetura TIGER
Controlador
Cub 0
Cub 1
Rede de baixa
velocidade
Cub n
Rede de alta
velocidade
Switch ATM
Fluxos de saida
para os clientes
Arquitetura TIGER
• Armazenamento por faixas (striping)
– Arquivo i: bloco 0 armazenado no disco 0, bloco 1 no
disco 1 … bloco k no disco k …
• Tamanho do bloco entre 64 KB e 1MB (fixo para o servidor)
– Se n cubs, cub i tem discos i, n+i, 2n+i, …
– Balanceamento do espaço e banda para todos os usuários
• Controlador Central:
– Ponto de entrada dos clientes, gerenciador
– Dados dos arquivos não passam pelo controlador
• Rede ATM:
– Alta velocidade
– Provê garantia de qualidade de serviço
– UDP sobre ATM
Escalonamento de Acesso aos Discos
• Como escalonar os acessos aos discos para max
Bdisco?
• Escalonador trabalha com uma agenda de slots
– # slots = # fluxos simultâneos sistema suporta
– Slot i atribuído a um cliente ci que requisitou arquivo fi
• Slot i marca quando o próximo bloco de fi deverá ser
enviado para ci
• Agenda compartilhada por todos cubs
• Acesso a arquivos tradicionais não é gerenciado
pela agenda e pelo escalonador
– São tratados quando houver banda disponível
Escalonamento de Acesso aos Discos
• Definições:
– Block play time: tempo necessário para visualizar um
bloco no bitrate do arquivo
– Block service time: tempo necessário para um disco
recuperar um bloco (pior caso)
• Cada disco percorre a agenda de cima para baixo,
processando um slot a cada block service time.
• Discos espaçados na agenda por um block play time
• Slot s e processado por um disco diferente a cada
block play time
– Slot s é processado por disco k no tempo t, se s foi
processado por disco k-1 no tempo t – block play time
Escalonamento de Acesso aos Discos
• Figura 2 no artigo
• Discos processam slots antes do deadline para
minimizar jitter
– Transmissão na rede feita no deadline
• Premissas:
– Espaço suficiente para buffers no servidor
– Arquivos são longos em relação ao número de discos
• Cada arquivo tem blocos em cada disco
– Todos os fluxos têm mesmo bitrate (mesma banda)
• Simplicidade: slots tem mesmo tamanho
Tratamento de uma Requisição
• Requisição do cliente para um arquivo é recebida
pelo controlador
• Controlador envia requisição para cub onde o
primeiro bloco do arquivo requisitado está
armazenado.
• Cub seleciona o próximo slot livre que será
processado pelo disco onde o primeiro bloco está
armazenado
• Cub adiciona cliente no slot escolhido
Minimiza latência inicial do cliente
Tolerância a Falhas
• Sem tratamento especial, a falha em um disco causaria
interrupção de serviço para todos os clientes
• Replicação por mirroring: duas cópias do mesmo dado
são armazenadas em dois discos diferentes
– Cópia primária e cópia secundária
– Sobrevive falhas em cubs e discos
– Não usa codificação com bit de paridade
• Complexo de gerenciar em um sistema distribuído: atrasos
• Discos são baratos
– Desvantagem: sobrecarga
• Um disco deve conseguir servir a sua carga primária e a sua
carga secundária, na presença de falhas.
Tolerância a Falhas
• Solução: espalhar cópia secundária de um bloco por
d discos
– Um bloco cuja cópia primária está no disco i tem sua cópia
secundária dividida em d pedaços que são armazenados
nos discos i+1… i+d.
– Quando um disco falha, sua carga secundária é
distribuída por d discos
• Qual o valor de d?
– Maior d:
• Menos banda deve ser reservada para o caso de falhas
• Maior a vulnerabilidade a catástrofes: se os discos que
armazenam duas cópias do mesmo dado falham, o
sistema falha completamente.
• Menor eficiência no uso dos discos
– Sugestão: d = 4 ou 8
Tolerância a Falhas
• Localização dos blocos em cada disco
– Cópias primárias: trilhas mais externas (+ rápidas)
– Cópias secundárias: trilhas mais internas (+ lentas)
• Tolerância
– Falha em 1 disco ou em múltiplos discos
(somente se discos que falharam espaçados por  d)
– Falha em um cub
• Deteção: pings periódicos
• Cada cub i contém discos i, i+n, i+2n…, n = # cubs
• TIGER sobrevive a falha em cub se n  d
– Nenhum disco em um cub contém cópias secundárias
de um dado cuja cópia primária está em um outro
disco no mesmo cub
Componente de Rede do Sistema TIGER
• TIGER network switch: reagrupa os blocos
recuperados dos vários discos em um fluxo contínuo
para o cliente
– Funnel: circuito virtual multi-ponto a ponto.
– Uso de um protocolo de token para garantir integridade
dos dados
– Direct Memory Access para minimizar cópias
Disk Striping
para Servidores de Video [OzRS96]
• Distribui armazenamento de cada video em multiplos
discos
– Balanceamento de carga entre os videos
– Maximizar largura de banda efetiva do disco (e servidor)
• Desafio: Projetar servidor com baixo custo, max #
fluxos simultaneos servidos, min latencia.
– Parametro d: quantidade de dados otima a ser recuperada
em cada acesso a disco (em cada round ou ciclo)
– Dado: latencia de cada acesso e relativamente alta
• Se d pequeno: latencia alta, Bdisco pequena
• Se d grande: demanda por muita RAM, aumenta custo.
Disk Striping
• Proposta: metodos de striping com
granularidades fina e grossa, sem inanicao
– Acesso sequencial,arquivos com mesma bitrate
• Modelo de Sistema:
– Servidor com m discos.
• Cada disco: rdisk, tsettle, tseek, trot, Cd
• Memoria RAM: D, Cr
– Cada video recuperado e transmitido a taxa rdisp < rdisk
• Cada ciclo tem duracao maxima de d/rdisp
– Cada video: buffer de tamanho 2d em memoria principal
– Request list
Striping com Granularidade Fina
• Unidade de striping (su) tipica:
– 1 bit, byte ou setor
• Cada leitura envolve os m discos que atuam como
um disco unico com banda mrdisk
– Ex: RAID- 3
• Service list: lista com todos os videos que estao
sendo recuperados
Striping com Granularidade Fina
• Distribuicao dos dados de um video
– Video e uma sequencia de blocos de tamanho d
– Cada bloco e uma sequencia de sub-blocos de
tamanho m*su
– Cada sub-bloco e espalhado pelos m discos
• As unidade de striping de um mesmo sub-bloco estao na
mesma posicao em seus discos respectivos
• Unidades de striping de sub-blocos consecutivos estao
armazenados uma atras da outra, no mesmo disco
Striping com Granularidade Fina
• No inicio de cada ciclo: servidor ordena videos na
service list em funcao das posicoes no disco do
bloco corrente a ser lido
– Min seeks aleatorios (algoritmo SCAN)
• Equacoes chaves: (q = # fluxos simultaneos)
d
d
2  t seek  q(
 trot  t settle ) 
m  rdisk
rdisp
2 d  q  D
Striping com Granularidade Fina
• Qual valor de d que max q, para dados m e D?
d
qmax
 2t seek
rdisp

d
 t rot  t settle
m rdisk
2dqmax  D
Aumenta d, aumenta q, mas aumenta tambem
memoria que e limitada por D
demanda por
Calcular valor otimo de d solucionando equacoes
Projeto de Servidores com
Striping com Granularidade Fina
• Qual o numero de discos m ideal para suportar um
numero pre-definido Q de fluxos simultaneos?
– Min custo total C(m)
(figura 2)
C(m) = Cr  2  Q  d + Cd  m
 ^ 
d 

d
 m  su
 m  su 


d
rdisk 
m
d
(Q(t rot  t settle )  2t seek )m  rdisk  rdisp
(m  rdisk  Q  rdisp )
1
Q  rdisp
Q  rdisp
rdisk
^
m
d 
 m  d ( Cr )  Cd
Projeto de Servidores com
Striping com Granularidade Grossa
• Unidade de striping: quantidade de dados d tipicamente
recuperada durante um acesso a disco (d ~ 1 Mb)
– Em cada ciclo: somente um disco esta involvido na leitura de
dados para um arquivo
– Ex: RAID 5
• Armazenamento:
– Cada arquivo tem tamanho multiplo de d.
– Arquivos concatenados para formar super-arquivo.
– Unidades de striping de tamanho d do super-arquivo sao
armazenados em m discos, em round robin
• Disk(Vi): disco onde esta 1o bloco do arquivo Vi
• Disk(Vi) e disk(Vj) podem ser diferentes
Projeto de Servidores com
Striping com Granularidade Grossa
• Recuperacao:
– Cada disco tem uma service list
– Ao final de um cico, a service list do disco i e passada
para o disco (i+1)%m
• Banda disponivel circula por todos os discos
• Equacoes chaves:
d
d
2  t seek  q(
 trot  t settle ) 
rdisk
rdisp
2 d  q  D
Projeto de Servidores com
Striping com Granularidade Grossa
• Questao chave: quando inserir um video, correntemente
esperando na request list para ser tratado, na service list de
um disco?
• Algoritmo Simplista:
– Insere video Vi na service list do disco disk(Vi) se houver
banda no disco disk(Vi) suficiente (restricao de banda valida)
• Pode causar inanicao
– FIFO
• Pode causar desperdicio de banda
– Algoritmo Currently Available Bandwidth (CAB)
• Compromisso: nao causa inanicao, minimizando desperdicio
de banda
Alocacao de Dados Aleatoria
• Random I/O ou RIO
• Arquivo dividido em varios blocos e cada bloco e
armazenado em uma posicao aleatoria de um disco,
escolhido aleatoriamente
• Motivacao:
– Desacoplar alocacao e padroes de acessos
– Permitir heterogeneidade de aplicacoes, clientes,
comportamento
• VBR, interatividade, realidade virtual, multi-resolucao
– Facilita reconfiguracao do sistema
Alocacao de Dados Aleatoria
• “Soft” real-time systems:
– Garantias estatisticas para latencia maxima
– Precisa minimizar latencia maxima (tail)
• Replicacao de dados: uma fracao r dos blocos,
escolhida aleatoriamente, e replicada em discos
escolhidos aleatoriamente (mas diferentes)
– Roteamento para disco com menor fila de requisicoes
Melhor balanceamento de carga
– Minimiza latencia maxima
• Por que replicacao e nao bit de paridade?
– Custo de espaco cai mais rapido do que custo de banda
• Servidores sao limitados pela banda e ha espaco disponivel
– Facilidade para implementacao de arquiteturas distribuidas
com clusters de maquinas
Alocacao aleatoria vs. Striping
• Como alocacao aleatoria se compara a
striping?
– Cargas interativas, heterogeneas: deve ser
melhor (?)
– Mas e para acesso sequencial a videos CBR????
• Neste caso, pode-se imaginar que striping possa ser
significativamente melhor, ja que este metodo explora
exatamente este tipo de trafego.
• Comparacao com cargas sequenciais para
videos CBR: favorecer striping
Striping
• Granularidade grossa: blocos dos arquivos
armazenados em D discos consecutivos, em
round robin
• Recuperacao de dados em ciclos de duracao fixa T,
que e funcao da carga e de caracteristicas do
sistema de I/O
– T tem que ser super-estimado (ociosidade dos discos)
– Alocacao aleatoria nao e baseada em ciclos de
duracao fixa e acessos aos discos nao sao
sincronizados.
• Duracao do ciclo determina numero maximo de
blocos lidos por disco, o que limita numero de fluxos
por disco (Nd)
Striping
• Banda disponivel percorre todos os discos, em ciclo.
– Novo fluxo e admitido sempre que houver pelo menos
um disco com banda suficiente livre
– Latencia: tempo que a banda disponivel gasta para
circular ate o disco onde o primeiro bloco do arquivo
esta armazenado
• Numero total de fluxos N = Nd*D
– Striping: numero total de fluxos e multiplo do numero
de discos.
– Alocacao Aleatoria: numero de fluxos por disco pode
nao ser inteiro
Avaliacao de Striping
• Modelo de disco detalhado incluindo:
– Componentes de desempenho do disco : seek, latencia, settle,
taxa de transferencia pra cada trilha
– Escalonamento com algoritmo SCAN
– Atrasos no barramento SCSI
– Atrasos na chamada de sistemas
• Modelo calibrado para Seagate Barracuda
ST15150W a partir de manual e experimentos reais
com o disco
Avaliacao de Striping
• Distribuicao do tempo de leitura de bloco (Fig. 3)
– Validacao do modelo com disco real
– Inclusao de garantias estatisticas para o atraso maximo,
o que determina o tempo de ciclo T
• Probabilidade Pmiss= 10-6 de uma requisicao nao ser servida
porque ciclo estourou T (alguns blocos nao sao lidos)
– Estimar T com base em garantias estatisticas leva a
melhor desempenho do disco do que escolher pior caso.
• Tempo medio pra tratar 10 requisicoes, bloco 128KB:
Tavg = 319 ms
• Pior caso de tempo de leitura: Tpior = 447 ms -> na media,
disco ocioso 29% do tempo
• Com garantias estatisticas (Pmiss= 10-6 ): Tstat = 373 ms -> na
media, disco ocioso por somente 14% do tempo
Avaliacao de Alocacao Aleatoria
• Prototipo e simulacao
• Avaliacao com fluxos CBR com bitrate fixa
– Somente trafego agregado importa (Fig 4)
• Arquitetura do Simulador (Fig 5)
– Fila de servicos em cada disco: FIFO
• Minimiza variancia do tempo de leitura
• SCAN pode ser melhor (analise favorece striping)
– Tempo de leitura de bloco obtido a partir da PDF
• Validacao a partir de experimentos com discos reais
(Tabela 3, Fig 6)
Avaliacao de Alocacao Aleatoria
• Avaliacao com diferentes tamanhos de blocos
(curvas normalizadas na Fig 7)
– Desempenho relativo e insensivel a tamaho do
bloco
– Desempenho tambem insensivel a # discos, para
# discos grande (> 7)
– Resultados para um tamanho de bloco e numero
de discos podem ser usados para prever
desempenho para outros valores dos mesmos
parametros.
Avaliacao de Alocacao Aleatoria
• Numero maximo de fluxos?
– Para cada fluxo: um buffer circular, com nb  2
blocos, cada um com tamanho B
• Escalonamento nao e baseado em ciclos
• Buffer contem blocos bi, bi+1… bi+nb-1
– Quando bloco bi esta sendo enviado para cliente
• Espaco do bloco bi usado para armazenar bloco bi+nb
– Bloco bi+nb tem que ser lido do disco para memoria
antes que cliente precise do dado
• Isto e: enquanto cliente consome blocos bi+1… bi+nb-1
Avaliacao de Alocacao Aleatoria
• Numero maximo de fluxos?
– Se bitrate e Rs: tempo para consumir cada
bloco e B/Rs
– Tempo de leitura de um bloco tem que ser entao
limitado por DB = B/Rs * (nb-1)
– Dado Db, calcula carga maxima LD por disco
usando curvas da Fig 7, usando valores
absolutos da Tab 3
– Numero de fluxos por disco = LD/Rs
Striping vs. Alocacao Aleatoria
• Numero maximo de fluxos por disco em
funcao do tamanho do bloco (Fig 8)
– # fluxos aumenta com tamanho do bloco
– RIO, nb=2, sem replicacao: aprox. mesmo
# fluxos que striping com Tpior
– If nb  4 ou r  0.25:
• RIO and striping com Tstat equivalentes para B pequeno
• RIO melhor que striping com Tstat para B grande
Striping vs. Alocacao Aleatoria
• Mais espaco (buffer maior ou replicacao) leva a
maior custo para RIO: Comparacao justa?
• Numero maximo de fluxos em funcao do tamanho do
buffer de RAM por fluxo (Fig 9)
– Se r >= 0.25 ou buffer maior que 3.5 MB por fluxo: RIO
superior a striping
– Se r = 0 e buffer pequeno, striping e superior (ate 10%)
Se buffer pequeno, melhor maximizar tamanho do bloco:
RIO usa nb = 2, striping ligeiramente melhor
Se buffer grande, desempenho pouco sensivel a tamanho do
bloco: RIO usa nb > 2 o que leva a melhor desempenho.
• Conclusao: usando mesmo quantidade de espaco em
memoria, RIO e preferivel a striping
Striping vs. Alocacao Aleatoria
• Justificativa pra replicacao:
– Se servidor e limitado por espaco: ha banda extra,
desempenho nao e critico, usa r= 0
– Se servidor limitado por banda: tem espaco disponivel
para replicacao
– Custo de espaco cai mais rapido que custo de banda
– Striping nao leva vantagem com replicacao: carga ja esta
balanceada entre discos
Striping vs. Alocacao Aleatoria
• E quanto a latencia inicial SL?
– SL: intervalo de tempo entre instante em que o servidor
admitiu um novo fluxo e instante em que video comeca a
ser transmitido para cliente
– Limitar tamanho do buffer BF pela latencia desejada
• Striping: SLmax = D * B/RS + B/RS = (D+1) * BF/2RS
– Latencia aumenta linearmente com numero de discos
• RIO: SLmax = nb * B/RS = BF/RS
– Latencia independente do numero de discos
• RIO suporta maior numero de fluxos simultaneos
para uma dada latencia maxima que striping (Fig 10)
Striping vs. Alocacao Aleatoria: Conclusao
• Por que striping nao e superior a RIO para acessos
sequenciais a fluxos CBR?
– Striping:
• Ciclos com duracao constante sincronizados com todos
os discos
– Tpior ou Tstat: ociosidade do disco
• # fluxos por disco inteiro: desperdicio de banda
– Alocacao aleatoria:
• Discos nao tem que estar sincronizados para iniciar o
processamento de novo bloco: min ociosidade
• # fluxos por disco pode nao ser inteiro: max utilizacao
de banda