Upload
temira
View
42
Download
1
Embed Size (px)
DESCRIPTION
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: - PowerPoint PPT Presentation
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 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