Distribuição de Mídia Contínua
Projeto de Servidores
Jussara M. Almeida
Abril 2004
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
Projeto de Servidores de Mídia Contínua
• 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
Armazenamento de MC em Discos
• 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)
O Servidor de Videos TIGER
Arquitetura TIGER
Cub 0 Cub 1 Cub n
Controlador
Switch ATM
Fluxos de saida para os clientes
Rede de baixa velocidade
Rede de alta velocidade
• 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
Arquitetura TIGER
• 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
Escalonamento de Acesso aos Discos
• 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 escolhidoMinimiza latência inicial do cliente
Tratamento de uma Requisição
• 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
Tolerância a Falhas
• 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
Componente de Rede do Sistema TIGER
• 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 para Servidores de Video [OzRS96]
• 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
Disk Striping
• Unidade de striping (su) tipica: – 1 bit, byte ou setor
• Cada leitura envolve os m discos que atuam como um disco unico com banda mrdisk
– 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)
Striping com Granularidade Fina
dispsettlerot
diskseek r
dttrmdqt
)(2
Dqd 2
• Qual valor de d que max q, para dados m e D?
Aumenta d, aumenta q, mas aumenta tambem demanda por memoria que e
limitada por D Calcular valor otimo de d solucionando equacoes
Striping com Granularidade Fina
Ddq
ttmrd
trd
qsettlerot
disk
seekdisp
max
max
2
2
• 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
Projeto de Servidores com Striping com Granularidade
Fina
)()2)((^
^
dispdisk
dispdiskseeksettlerot
rQrmrrmtttQ
dsumsumdd
drdisk
disp
dispdisk
CCdmdrrQ
m
mrQr
d
)(
1
• 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:
Projeto de Servidores com Striping com Granularidade Grossa
dispsettlerot
diskseek r
dttrdqt )(2
Dqd 2
• 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
Projeto de Servidores com Striping com Granularidade Grossa
• 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 de Dados Aleatoria
• 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
Alocacao aleatoria vs. 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
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 Striping
• 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
Avaliacao de 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 melhorSe 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
• 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
Striping vs. Alocacao Aleatoria: Conclusao