Upload
internet
View
106
Download
2
Embed Size (px)
Citation preview
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 escolhido
Minimiza 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
dtt
rm
dqt
)(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
q
settlerotdisk
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
rQrm
rrmtttQdsum
sum
dd
drdisk
disp
dispdisk
CCdmdr
rQm
mrQ
rd
)(
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
dtt
r
dqt )(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 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
• 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