02 - Armazenamento V-0'7201

Prévia do material em texto

BANCO DE DADOS II 
Armazenamento de Dados 
 
Versão dos Slides: 0.7201 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Hierarquia de Armazenamento 
 Modelo I/O de Computação 
 Regra dos 5 Minutos 
 Características de Discos Magnéticos 
 Acelerando o Acesso ao Disco 
 Lidando com Falhas 
 RAID 
2 
3 
armazenamento externo 
serviços de arquivos 
controle de propagação 
estruturas de 
armazenamento 
caminhos de 
acessos lógicos 
estruturas de 
dados lógicas C5 
C4 
C3 
C2 
C1 
Armazenamento Externo 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Meios de Armazenamento Físico 
 Sistemas de computadores dispõem de uma 
pletora de mídias físicas para armazenamento de 
dados 
 Diversos critérios de classificação: 
• Tempo de acesso (diferenças estimadas de até 7 
ordens de magnitude entre o dispositivo mais rápido e 
o mais lento) 
• Custo por unidade de dados (diferenças estimadas de 
até 3 ordens de magnitude entre o dispositivo mais 
caro e o mais caro) 
• Confiabilidade 
4 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Meios de Armazenamento Físico 
 Cache: 
• Tipicamente localizado no mesmo que chip que o 
processador 
• Meio de armazenamento mais rápido e também o mais 
caro 
• Armazena volumes pequenos de dados 
− Instruções, inteiros, ponto-flutuante, strings curtas, etc 
 Memória principal: 
• Armazena dados disponíveis para serem processados por 
instruções de máquina de propósito geral 
• Assim como cache, acesso a qualquer byte da memória 
requer praticamente o mesmo tempo 
• Assim com o cache, é um meio de armazenamento volátil : 
dados são perdidos quando a alimentação de energia 
elétrica é interrompida 
5 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Meios de Armazenamento Físico 
 Disco magnético: 
• Meio principal para armazenamento permanente 
de um banco de dados 
• Memória não-volátil 
• Capacidade cresce aproximadamente 50% ao ano 
• Tempo de acesso pode depender da posição dos 
dados no disco 
6 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Meios de Armazenamento Físico 
 Memória flash: 
• Memória não volátil: dados armazenados não são perdidos na 
ausência de energia elétrica 
• Dois tipos: NAND e NOR flash 
• Atualmente, NAND apresenta melhor relação 
armazenamento/preço 
− Popularmente usada como meio de armazenamento para câmeras 
fotográficas, players de som, smarphones, etc 
• Menor custo que a memória principal 
• Popularmente usadas para amazenar dados em pendrives que 
podem ser conectados na interface USB de computadores 
• Cada vez mais usadas como substitutas de disco magnéticos 
onde são chamadas de discos de estado sólido 
• Podem também ser usadas como cache intermediário entre a 
memória principal e o disco 
7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Meios de Armazenamento Físico 
 Mídias óticas: 
• Apenas leitura: CD-ROM, DVD-ROM 
• Write-once, read-many (WORM): CD-R, DVD-R 
• Escritas arbitrárias: DVD-RW, DVD+RW, DVD-RAM 
• Sistemas jukebox: discos óticos são carregados sob 
demanda por um braço mecânico 
 Fita 
• Usada primariamente para backup e arquivamente 
− Cada vez mais substituida por discos magnéticos 
• Acesso sequencial: acesso deve ser feito através de 
uma busca sequencial a partir do ínicio da fita 
8 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Hierarquia de Armazenamento 
 Modelo I/O de Computação 
 Regra dos 5 Minutos 
 Características de Discos Magnéticos 
 Acelerando o Acesso ao Disco 
 Lidando com Falhas 
 RAID 
9 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Hierarquia de Armazenamento 
 Meio de armazenamento ideal teria as seguintes características: 
• Capacidade praticamente ilimitada 
• Baixo custo 
• Baixo tempo de acesso 
• Altas taxas de transferência 
• Não-volatilidade 
• Capacidade de executar operações lógicas, aritméticas e outras 
operações básicas 
 Hierarquia de armazenamento: procurar obter uma aproximação ao 
meio de armazenamento ideal usando propriedades de localidade 
• Buffer/Alocação de dados possuindo grande probabilidade de acesso 
em mídia rápida (e com, relativamente, menor capacidade de 
armazenamento) 
• A maior parte dos dados permanece em meios de armazenamentos 
mais lentos e baratos 
10 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Hierarquia de Armazenamento (2) 
 Princípio recursivo: 
• Meios de armazenamentos menores, mais rápidos 
e mais caros são usados como buffer para meios 
maiores, mais lentos e mais baratos 
 Contrapartida preço/performance 
• Armazenamento mais rápido são mais caros e por 
isso menores 
• Armazenamento com maior capacidade é 
tipicamente mais lento 
11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Hierarquia de Armazenamento (3) 
12 
cache 
Capacidade de armazenamento 
mem. principal 
discos 
fitas 
Atualidade dos dados, 
rapidez,custo 
registradores 
> 1ns 
100ns 
10ms 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Hierarquia de Armazenamento (4) 
13 
cache 
Capacidade de armazenamento 
mem. principal 
flash 
discos 
Atualidade dos dados, 
rapidez,custo 
registradores 
> 1ns 
100ns 
10ms 
0.5 ms 
Tape is Dead, Disk is Tape, Flash is Disk, RAM Locality is King (J. Gray) 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Hierarquia de Armazenamento (5) 
 Tarefas similares em cada nível da hierarquia 
de armazenamento: 
• Localização de objetos de dados 
• Alocação de espaço 
• Substituição de objetos com a camada de baixo 
• Estratégia de atualização das camadas de baixo 
− Write-through: atualização imediata 
− Write-back: atualização (possivelmente) postergada 
• Ajuste de granularidade (tamanho dos objetos) 
 
 
14 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Hierarquia de Armazenamento (6) 
 Por que hieraquia de armazenamento 
funciona? 
• Aproximação pelo princípio da localidade 
• Localidade temporal: objetos acessados 
recentemente são mantidos no buffer 
• Localidade espacial: objetos adjacentes ao objeto 
requisitado são mantidos no buffer 
15 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Lei de Moore 
 Gordon Moore (co-fundador da Intel) observou em 1965 
que as melhorias na tecnologia de circuitos integrados 
seguiam uma curva exponencial cujo valor duplicava a cada 
18 meses. Esta tendência é chamada Lei de Moore e ainda 
é observada nos dias atuais 
 Seguem a Lei de Moore: rapidez dos processadores, 
capacidade de memória e disco 
 Entretando, outros aspectos como a rapidez para acesso de 
dados na memória princial e a rotação dos discos 
magnéticos não seguem a Lei de Moore: a evolução é bem 
mais lenta 
 Resultado: aumento do tempo para mover dados entre 
diferentes níveis na hierarquia de armazenamento 
16 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Hierarquia de Armazenamento 
 Modelo I/O de Computação 
 Regra dos 5 Minutos 
 Características de Discos Magnéticos 
 Acelerando o Acesso ao Disco 
 Lidando com Falhas 
 RAID 
17 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo I/O de Computação 
 Modelo RAM 
• Assume dados na memória principal 
• Tempo uniforme para acesso a itens de dados 
 Implementação de SGBDs: dados não “cabem” na mémoria 
principal: Modelo I/O 
• Acessos à memória secundária (disco) devem ser considerados 
 De maneira geral, os melhores algoritmos para resolver um 
determinado problema no modelo RAM são diferentes dos 
melhores algoritmos para resolver o mesmo problemano 
modelo I/O 
• Ordenaçao-> Modelo RAM: Quicksort, Modelo I/O: Merge-Sort 
 Técnicas desenvolvidas para o modelo I/O podem ser úteis 
em outros níveis da hierarquia de memória 
• Exemplo: Exploração da localidade de cache 
18 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo I/O de Computação 
 Assunção Básica: Dominância de I/O 
• Se um bloco precisa ser movido entre o disco e a memória 
principal, então o tempo necessário para ler ou escrever este 
bloco no disco é bem maior que o tempo necessário para 
manipular este bloco na memória principal. Portanto o número 
de acessos ao disco (leitura ou escrita) é uma boa aproximação 
do tempo gasto pelo algoritmo e deve ser minimizado 
 Exemplo: 
• Assuma que para acessar os valores de uma tupla, um bloco é 
acessado do disco e que o tempo de leitura deste bloco é 10ms 
• Processadores modernos podem executar centenas de milhões 
de instruções neste tempo; tempo para encontrar a tupla no 
bloco requer milhares de instruções 
• Portanto, o processamento na memória principal corresponde a 
bem menos de 0,1% do tempo total de processamento 
19 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Hierarquia de Armazenamento 
 Modelo I/O de Computação 
 Regra dos 5 Minutos 
 Características de Discos Magnéticos 
 Acelerando o Acesso ao Disco 
 Lidando com Falhas 
 RAID 
20 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Regra dos 5 Minutos (J. Gray) 
 A chamada regra dos 5 minutos (Five Minutes 
Rule, Gray 87, Gray 97) 
• Define um critério objetivo para decidir se um 
bloco de dados deve permancer no disco ou em 
memória principal (buffering) 
 Baseia-se na frequência de acesso aos dados e 
em fatores econômicos e tecnológicos 
21 
Regra dos 5 Minutos: Intuição 
 Analisando o custo (em termos de R$) de acessos ao disco: 
• O preço de um HD para servidor de 1T é R$ 1k (valores aproximados obtidos em 2013) 
• HDs atuais são capazes de realizar aproximadamente 100 acessos randômicos ao discom 
em um segundo 
• Portanto, podemos dizer que o custo de cada acesso randômico por segundo ao disco é R$ 
10 
 Analisando o custo (em termos de R$) de acessos à memória: 
• O preço de um 1GB de memória é R$ 100; portanto um 1 MB de memória custa 
aproximadamente 10 centavos 
 Portanto, se um bloco de dados de 1MB é acessado a cada segundo, é 
preferível mante-lo em memória, ao custo de R$ 0.10, do que no HD, 
economizando R$ 10 em acessos randômicos ao disco 
 Se este bloco fosse acessado uma vez a cada 10 segundos, então o custo de 
acesso ao disco para este bloco seria de R$ 1, e ainda valeria a pena investir 
10 centavos em memória para armazenar este bloco 
 Seguindo esta lógica, seria mais interessante manter um bloco de dados em 
memória caso a frequência de acesso do mesmo for 0.01 segundos (ou 1 
acesso a cada 100 segundos) 
 Observação: na época que o artigo descrevendo esta regra foi publicado, os 
valores obtidos eram próximos a 5 minutos, daí o nome da regra 
Regra dos 5 Minutos: Generalização 
 Frequência de acesso por bloco = 𝑓 
 Intervalo entre acessos 𝑇 = 1 / 𝑓 
 Buffering é mais vantajoso quando: 
• 𝑓 ∗ 
𝑃𝑟𝑒ç𝑜 𝑑𝑒 𝐻𝐷
𝐴𝑐𝑒𝑠𝑠𝑜𝑠 𝑝𝑜𝑟 𝑠𝑒𝑔𝑢𝑛𝑑𝑜 𝑎𝑜 𝐻𝐷
≥
𝑃𝑟𝑒ç𝑜 𝑝𝑜𝑟 𝑀𝐵 𝑑𝑒 𝑚é𝑚𝑜𝑟𝑖𝑎
𝑃á𝑔𝑖𝑛𝑎𝑠 𝑝𝑜𝑟 𝑀𝐵 𝑑𝑒 𝑚𝑒𝑚ó𝑟𝑖𝑎
 
 Note que podemos ter mais de um página por 
MB de memória. Re-escrevendo a fórmula 
acima temos: 
• 𝑇 ≤
𝑃𝑟𝑒ç𝑜 𝑑𝑒 𝐻𝐷
𝑃𝑟𝑒ç𝑜 𝑝𝑜𝑟 𝑀𝐵 𝑑𝑒 𝑚é𝑚𝑜𝑟𝑖𝑎
∗
𝑃á𝑔𝑖𝑛𝑎𝑠 𝑝𝑜𝑟 𝑀𝐵
𝐴𝑐𝑒𝑠𝑠𝑜𝑠 𝑝𝑜𝑟 𝑠𝑒𝑔𝑢𝑛𝑑𝑜 𝑎𝑜 𝐻𝐷
 
23 fator econômico fator tecnológico 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Hierarquia de Armazenamento 
 Modelo I/O de Computação 
 Regra dos 5 Minutos 
 Características de Discos Magnéticos 
 Acelerando o Acesso ao Disco 
 Lidando com Falhas 
 RAID 
24 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Disco Magnético 
25 
Diagrama 
simplifcado 
Silberschatz, A, et al. 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Disco Magnético (2) 
 Pratos (platters): superfícies planas, circulares, feitas de metal 
rígido ou vidro, cobertas com material magnético sobre o qual 
os bits são armazenados na superfície 
• Pratos de discos modernos possuem diâmetro de 3.5‘‘, 1-5 pratos 
por disco 
 O motor rotaciona os pratos em volta do eixo (splindle) a uma 
velocidade constante 
• Velocidades de discos modernos variam entre 5400-15000 
rotações por minuto (rpm) 
 Os locais onde os bits são armazenados na superfície dos pratos 
são organizados em círculos concêntricos chamados trilhas 
• 50k-100k trilhas por prato 
 
26 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Disco Magnético (3) 
 Trilhas são organizadas em setores separados por espaços 
livres (sem informação armazenada) 
 Espaços livres correspondem a ≈ 10% da trilha 
 512 bytes é o tamanho típico de um setor 
 Trilhas mais internas contém 500-1000 setores, trilhas mais 
externas contém 1000-2000 setores 
 Setores representam a menor unidade de informação para 
operações de leitura e escrita e para a ocorrência de erros 
 Blocos são as unidades lógicas de transferência entre a 
memória principal e o disco 
• Blocos consistem em um ou mais setores 
 
 
27 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Disco Magnético (4) 
 Em cada superfície de cada disco, existe uma cabeça de 
leitura/escrita conectada a um mesmo eixo através de um 
braço 
 O controlador do disco é responsável por movimentar 
conjuntamente as cabeças de leitura/escrita pelas trilhas dos 
pratos, selecionar a superfície e setores da trilha que estão 
sob as cabeças para leitura ou escrita, e movimentar dados 
entre o disco e a memória principal 
 Controladores de disco modernos são subsistemas com 
memória e capacidade de processamento 
 Implementa diversas operações de alto-nível: controle de erros 
via checksums, remapeamento lógico de setores defeituosos 
 Todas as trilhas que encontram-se sobre as cabeças ao 
mesmo tempo formam um cilindro 
 
 28 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Interface Controlador-Memória 
 Discos internos 
• SATA (Serial Advanced Technology Attachment), taxa de transferência 
(revisão 3.0): 600 MB/s 
• SCSI (Small Computer System Interface), taxa de transferência (Ultra-
5): 640 MB/s 
• SAS (Serial Attached SCSI), taxa de transferência (SAS 2.0): 600 MB/s 
• Fiber Channel, taxa de transferência: 531 MB/s 
 Discos externos 
• USB (Universal Serial Bus), taxa de transferência (USB 3.0): 625 MB/s 
• IEEE 1394 Firewire, taxa de transferência: 393.216 MB/s 
 Discos conectados por rede de comunicação de dados 
• SAN (Storage Area Network): permite conectar logicamente diversos 
meios de armazenamento (não apenas discos magnéticos); uma rede 
SAN é vista pelo SO como um único disco 
• NAS (Network Attached Storage): provê abstração de um protocolo de 
sistema de arquivos como NFS ou CIFS 
 
29 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Acesso ao Disco 
 Blocos lógicos são lidos ou escritos quando: 
• As cabeças são posicionadas nos cilindros contendo as 
trilhas ondes os blocos estão localizados 
• Setores que contém os blocos movem-se sob a cabeça 
quando os pratos são rotacionados 
 Latência do disco: tempo entre o momento em 
que um comando para ler um bloco do disco é 
emitido e o momento em que os blocos são 
armazenados na memória principal 
30 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Acesso ao Disco (2) 
 Latência do disco pode ser dividida em vários componentes: 
1. Tempo de processamento: Tempo para que o processador e 
o controlador do disco processem a requisição− Inclui tempo gasto devido a contenção do controlador de disco e do 
barramento de comunicação memória/disco (quando mais de um 
processo está usando o disco) 
− Latência, no geral, negligenciável se comparada com as demais 
2. Tempo de busca (seek time): tempo para posicionar o 
conjunto de cabeças sobre o cilindro 
− Tempo é variável dependendo da posição atual da cabeça e do 
cilindro 
− Melhor caso: a cabeça já se encontra posicionada sobre o cilindro 
correto 
− Pior caso:cabeça e cilindro encontram-se em extremidades opostas 
− Tempo médio de busca: 4-10 ms 
31 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Acesso ao Disco (3) 
3. Latência de rotação: tempo para que a rotação do disco 
posicione o primeiro dos setores contidos nos blocos 
requisitados 
 Discos modernos: 90-250 rotações por segundo 
 Latência média de rotação: metade do tempo para uma 
rotação completa 
4. Tempo de transferência: tempo até que todos os setores 
de um bloco (e espaços vazios) “passem” pelas cabeças do 
disco (valor típico: 50Mb/s) 
 Operação de escrita é bastante similar à operação de 
leitura 
• Certos discos verificam se a escrita foi feita corretamente 
através da realização de outra leitura (tipicamente, para verificar 
o checksum como veremos mais adiante) 
• A cabeça do disco pode estar em uma posição diferente se 
múltiplos processos estão acessando o disco concorrentemente 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Hierarquia de Armazenamento 
 Modelo I/O de Computação 
 Regra dos 5 Minutos 
 Características de Discos Magnéticos 
 Acelerando o Acesso ao Disco 
 Lidando com Falhas 
 RAID 
33 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Acelerando Acesso ao Disco 
 Sequências de requisições de acesso ao disco podem 
ser classificadas como sequencial ou randômico 
 Sequencial: acesso a blocos lógicos sucessivos, e.g., 
scan de uma relação 
 Randômico: acesso aleatório a blocos lógicos não-
relacionados, e.g., requisições de diferentes transações 
 Existem diversas estratégias para melhorar o tempo de 
acesso a blocos do disco para os dois tipos de acesso 
• Organização de dados por cilindros 
• Uso de múltiplos discos 
• Otimização do escalonamento de acessos a disco 
• Prefetching (double buffering) 
34 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Organização de Dados 
por Cilindros 
 O tempo de busca é responsável por uma grande 
parcela do tempo para acessar um bloco 
 Armazenando dados que são frequentemente 
acessados sequencialmente (e.g., uma relação) 
em um conjunto de cilindros adjacentes é 
possível reduzir drasticamente o tempo de busca 
• Tempo de busca total: busca do primeiro cilindro + (N 
– 1) acessos a cilindros adjacentes, onde N é 
quantidade de cilindros a serem acessados 
 Desvantagem: Nenhum ganho é obtido com 
acessos randômicos 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Uso de Múltiplos Discos 
 Usando múltiplos discos com cabeças 
independentes, é possível, aproximadamente, 
reduzir o tempo de acesso original 𝑇 para 𝑇/𝑛, 
onde 𝑛 é o número de discos 
 Técnica popularmente empregada: distribuição 
a nível de blocos (block-level striping) 
• Empregado no esquema RAID nível 0 (mais sobre 
RAID adiante) 
• Outras alternativas: distribuição a nível de bits, 
bytes, setores 
36 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Esquema para 
Distribuição a Nível de Blocos 
 Trata o conjunto (array) de discos como um único disco 
 Atribui números lógicos para cada bloco (a partir de zero) 
 Dado um array de 1, … , 𝑛 discos, associa o bloco de 
número lógico 𝑖 com o disco 𝑖 𝑚𝑜𝑑 𝑛 + 1 e usa o bloco 
físico 𝑖/𝑛 deste disco para armazenar o bloco lógico 𝑖 
37 
1 2 3 4 5 6 7 8 
Bloco lógico 0 
(0 mod 8) + 1 = 1 
Bloco lógico 13 
(13 mod 8) + 1 = 6 
Bloco Físico = 0/8 = 𝟎 Bloco Físico = 13/8 = 1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Distribuição a Nível de Blocos 
 Quando um arquivo armazenado em múltiplos 
blocos é lido, 𝑛 blocos podem ser acessados 
paralelamente de 𝑛 discos e, com isso, 
aumentando a taxa de transferência 
 Quando um único bloco é lido, a taxa de 
transferência é a mesma que a de 1 disco; mesmo 
assim, os 𝑛 − 1 discos restantes estão livres para 
servirem outras requisições e, com isso, pode-se 
obter melhor balanceamento de carga 
38 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Escalonamento 
de Acessos a Disco 
 Considere uma sequência de acessos 
randômico a um mesmo disco 
 Qual a melhor estratégia para o controlador 
ordenar estes acessos? 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Algoritmo do Elevador 
 As cabeças varrem os pratos no sentido dos cilindros 
mais externos para os mais internos e voltam, no 
sentido oposto 
• Movimento similar a um elevador que vai dos andares 
mais baixos para os mais altos e depois volta 
 As cabeças atendem requisições de acessos a cilindros 
enquanto se movem em uma das duas direções 
 A direção do movimento é invertida quando não existir 
mais requisições pendentes para cilindros localizados à 
frente (de acordo com a direção do movimento) da 
atual posição 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Algoritmo do Elevador: Exemplo 
 Por simplicidade, vamos assumir que o disco 
possui apenas 20 cilindros e que o tempo de 
busca em uma unidade de tempo (𝑢𝑡) qualquer é 
equivalente a quantidade de cilindros 
percorridos. Ex.: um movimento do cilindro 0 até 
o cilindro 20 gasta 20 unidades de tempo 
 Além disso, vamos assumir que a latência de 
rotação e o tempo de transferência consomem 
conjuntamente 4 𝑢𝑡‘s 
41 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Algoritmo do Elevador: Exemplo 
 Considere o tempo de chegada das seis 
requisições de acessos a blocos seguintes 
42 
Cinlindro Requisitado Tempo de chegada da requisição 
2 0 
7 0 
13 0 
2 10 
18 20 
8 30 
 Exercício: Calcule o tempo total para processamento destas 
transações usando o algoritmo do elevador e uma estratégia “por 
ordem de chegada”. Considere que a cabeça encontra-se 
posicionada originalmente no cilindro 2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 43 
Algoritmo do Elevador: Exemplo 
Cilindro requisitado Tempo de 
completude 
2 4 
7 13 
13 23 
18 31 
8 45 
2 55 
Cilindro requisitado Tempo de 
completude 
2 4 
7 13 
13 23 
2 38 
18 58 
8 72 
Elevador Ordem de chegada 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prefetching 
 Em certas aplicações, é possível prever a ordem na 
qual os blocos serão requisitados do disco 
 Neste caso, é possível carregar antecipadamente 
blocos em buffers na memória principal, antes que a 
requisição para acessar estes blocos seja feita pela 
aplicação 
 Vantagens: Melhor exploração de padrões de acesso 
sequencial quando o tempo de chegada das 
requisições é imprevisível 
 Desvantagens: Requer buffers extra na memória e 
nenhum ganho é obtido quando o acesso é 
inerentemente randômico 
44 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Hierarquia de Armazenamento 
 Modelo I/O de Computação 
 Regra dos 5 Minutos 
 Características de Discos Magnéticos 
 Acelerando o Acesso ao Disco 
 Lidando com Falhas 
 RAID 
45 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Falhas em Discos 
 Discos podem falhar de diversas maneiras; os 4 tipos de 
falhas abaixo são bastante comuns 
1. Falhas intermitentes: uma tentativa de leitura ou escrita 
não é bem-sucedida na primeira tentativa, mas sim após 
um certo número de tentativas 
2. Corrupção de mídia: bits corrompidos permanentemente 
em uma áreaespecífica do disco, impossiblidade de 
leitura e escrita 
3. Falha de escrita: durante a escrita de um setor, a 
operação não é concluída com sucesso e também não é 
possível restaurar o valor anterior; uma causa comum é a 
queda de energia 
4. Crash do disco: todo o disco é comprometido e seu 
conteúdo torna-se inacessível 
46 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Uso de Informação Redundante 
 Através do armazenamento de informação redundante no 
disco permite verificar se a informação lida do disco está 
correta e se a operação de escrita foi concluída com 
sucesso 
 Cada operação operação retorna, além dos dados do setor 
requerido, um bit de status indicando se os dados do setor 
são válidos ou estão corrompidos 
 Operações de escrita podem ser verificadas realizando-se 
uma operação de leitura sobre o setor escrito e 
comparando os dados lidos com os dados usados na escrita 
 Aumentando a quantidade de informação redundante 
permite melhorar a acuracidade do status de setores 
47 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Checksum 
 Checksum: Bits adicionais armazenados em cada 
setor que são “setados” de acordo com os dados 
armazenados no setor 
 Se após a leitura, os dados de um setor e o 
checksum são incompatíveis, então o setor é 
considerado corrompido 
 Método mais simples de checksum: bits de 
paridade 
• Princípio básico: o número de 1‘s entre uma coleção 
de bits e seu bit de paridade deve ser par 
48 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Bits de Paridade 
 Exemplos: 
• Sequência: 01101000; bit de paridade: 1. A sequência 
contém um número ímpar de 1‘s (3), com o bit de paridade 
passamos a ter 4 1‘s 
• Sequência: 11101110; bit de paridade: 0. A sequência já 
contém um número par de 1‘s (6), portanto o bit de 
paridade é zero 
 Quando um setor é escrito, o controlador pode calcular 
automaticamente o bit de paridade e anexar à 
sequência de bits escrita no setor 
 Durante a leitura, o controlado apenas precisa checar 
se quantidade de bits armazenados no setor é par 
49 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Bits de Paridade 
 Se mais de um bit de um setor é corrompido, 
existe uma probabilidade de 50% de que o 
número de 1‘s resultante será par e, portanto, o 
erro não poderá ser detectado via bit de paridade 
 Como solução, é possível usar vários bits de 
paridade 
• Exemplo: Uso de 8 bits de paridade, 1 bit de paridade 
para o primeiro bit de cada byte, outro bit para o 
segundo bit de de cada byte, e assim por diante 
50 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Bits de Paridade 
 No exemplo anteiror, no caso de um erro 
massivo, existe uma probabilidade de 50% de que 
algum bit de paridade irá detectar o erro; a 
chance de que nenhum bit de paridade irá 
detectar o erro é de 
1
28
=
1
256
 
 No geral, usando n bits de paridade 
independentes, a chance de não detectar algum 
erro é 
1
2𝑛
 
• Com 4 bytes de paridade, temos que apenas um erro 
em 4 bilhões passará desapercebido 
51 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Armazenamento Estável 
 Bits de paridade permitem a detecção de erros, mas 
ajudam a corrigir estes erros 
• Particularmente insuficiente no caso de falhas de escrita, 
isto é, durante a escrita de um setor, a operação não é 
concluída com sucesso e também não é possível restaurar 
o valor anterior 
 Armazenamento estável: consiste em escrever um 
dado 𝑋 em pares de setores, isto é, 𝑋 é duplicado em 
dois setores consecutivos 
 Permite restaurar o valor original de um setor no caso 
de erros 
• Bits de paridade ainda são necessários para a detecção de 
erros 
52 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Hierarquia de Armazenamento 
 Modelo I/O de Computação 
 Regra dos 5 Minutos 
 Características de Discos Magnéticos 
 Acelerando o Acesso ao Disco 
 Lidando com Falhas 
 RAID 
53 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Crashes de Disco 
 A medição da ocorrência de crashes de disco é 
chamada de tempo médio para falhas (mean time to 
failure) 
 Este número é o tempo para que 50% da população de 
discos tenha uma falha catastófrica 
 Para discos modernos, este tempo é estimado em 10 
anos 
• Maior parte dos crashes ocorrem após poucos meses de 
uso 
 Neste contexto, o principal objetivo é fazer com que o 
tempo médio para perda de dados seja bem menor 
que o tempo médio para falhas 
54 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
RAID (Redundant Arrays of 
Independent Discs*) 
 Esquema geral para reduzir o risco de perda de dados 
devido a crashes de disco usando um conjunto 
independente de discos: disco de dados + discos 
redundantes 
• RAID também visa aumentar performance, vide a 
estratégia de distribuição a nível de blocos que é utilizada 
pelo RAID nível 0 
 Existe uma grande variedade de esquemas RAID 
específicos RAID classificados através de diferentes 
níveis RAID: 0, 1, 0+1, 2, 3, 500,... 
 A seguir, iremos discutir RAID níveis 1, 4, 5 
55 
*O acrônimo RAID foi previamente associado com Redundant Arrays of Inexpensive 
Discs; este significado ainda encontrado na literatura 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
RAID Nível 1 
 Esquema consiste em simplesmente espelhar 
disco de dados com um disco redundante 
• Similar ao método de armazenamento estável 
 Aumenta significativamente o tempo médio para 
perda de dados 
 Se um disco falha, apenas é necessário subtituir o 
disco defeituoso por um disco novo e copiar o 
conteúdo do disco redudante correspondente 
para o disco novo 
 Perda de dados somente é possível quando o 
disco redundante falha durante a cópia 
56 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
RAID Nível 1: Exemplo 
 Suponha que o tempo médio de falhas de um disco é 10 
anos e que a probabilidade de crash do disco em um dado 
ano é de 10% 
 Suponha também que o processo de reposição do disco 
defeituoso pelo disco redundante leve 3 horas, ou 1/8 de 
um dia, ou 1/2920 de 1 ano 
 Como a probabilidade de crash do disco em um dado ano é 
10%, então a probabilidade de crash durante a cópia do 
disco redudante é 1/10 * 1/2920 = 1/29200 
 Além disso, 1 único disco falha em média após um período 
de 10 anos; um entre dois disco falha após um período de 5 
anos. 
 Uma em cada 29200 destas falhas resulta em perda de 
dados. Portanto, o tempo médio para perda de dados será 
5 x 29200 = 146000 anos 
 
57 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
RAID Nível 4 
 RAID 1 é uma maneira efetiva para aumentar 
significativamente o tempo médio para perda 
de dados 
 Entretanto, o espelhamento requer um disco 
redudante para cada disco de dados 
 RAID nível 4 requer apenas um disco 
redundante para uma quantidade qualquer de 
discos de dados 
58 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
RAID Nível 4 
 No disco redudante, o bloco 𝑖th consiste em 
bits de paridade para o conjunto de blocos 𝑖th 
de todos os discos de dados 
• O conjunto de bits 𝑗th dos bloco ith de todos os 
discos, de dados e redundante, devem ter um 
número par de 1‘s 
59 
discos de dados disco redundante 
11110000 
i 
…… 
…… 
10101010 
i 
…… 
…… 
00111000 
i 
…… 
…… 
01100010 
i 
…… 
…… 
Todos os discos devem ser idênticos 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
RAID Nível 4 
 O cálculo usado para determinar os bits de paridade é 
soma módulo-2 
 Usando soma módulo-2 é possível calcular não apenas o 
conteúdo do disco redundante, mas também o conteúdo 
de qualquer disco através dos dados dos demais discos 
 Cálculo usado para recuperação de falhas em qq disco 
60Disco 1: ???????? 
Disco 2: 10101010 
Disco 3: 00111000 
Disco R.:01100010 
Crash disco 1 Crash disco 2 Crash disco 3 Crash disco red. 
Disco 1:11110000 
Disco 1: 11110000 
Disco 2: ???????? 
Disco 3: 00111000 
Disco R.:01100010 
Disco 2: 10101010 
Disco 1: 11110000 
Disco 2: 10101010 
Disco 3: ???????? 
Disco R.:01100010 
Disco 3:00111000 
Disco 1: 11110000 
Disco 2: 10101010 
Disco 3: 00111000 
Disco R.:???????? 
Disco R.:01100010 
cálculo módulo-2 cálculo módulo-2 cálculo módulo-2 cálculo módulo-2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operação de Leitura 
 No geral, as operações de leitura são realizadas 
normalmente nos discos de dados; o disco redundante 
não precisa ser acessado 
 Em casos específicos, é possível explorar o disco 
redundante para obter o resultado de dois acessos 
simultâneos sobre o mesmo disco de dados 
 Suponha que o primeiro bloco do disco de dados 1 está 
sendo lido quando chega uma requisição para acessar 
o segundo bloco deste disco 
 Em vez esperar a completude da primeira leitura para 
executar a segundo disco, podemos simplesmente 
calcular o conteúdo do segundo bloco do disco 1 
usando os demais discos de dados e o disco 
redundante 
 61 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operação de Escrita 
 Sempre que um novo bloco é escrito em qualquer 
disco de dados, o bloco correspondente no disco 
redundante também tem que ser atualizado 
 Abordagem naive (n discos de dados): 
1. Lê os blocos correspondentes dos demais 𝑛 −
1 discos de dados 
2. Calcula a soma modulo-2 entre o novo bloco e os n-
1 blocos correspondentes para obter o novo bloco 
de paridade 
3. Escreve o valor do novo bloco no disco de dados e o 
novo bloco de paridade no disco redundante 
• Total: 𝑛 + 1 operações de IO 
62 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operação de Escrita 
 Otimização: Calcula o novo bloco de paridade usando as 
duas versões (a nova e a antiga) do bloco a ser escrito e a 
antiga versão do bloco de paridade do disco redundante 
 Abordagem otimizada: 
1. Leia a antiga versão do bloco de dados que será modificado e 
do bloco correspondente no disco redudante (2 operações de 
IO) 
2. Obtenha o novo bloco do disco redundante calculando a soma 
modulo-2 entre o antigo valor do bloco de dados, o novo valor 
do bloco de dados e a versão antigo do bloco do disco 
redundante 
3. Escreva as novas versões do bloco de dados e do bloco de 
paridade nos discos de dados e redundante, respectivamente 
• Total: 4 de operações de IO independente da quantidade de 
discos de dados 
 
 
 
63 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
64 
Disco 1: 11110000 
Disco 2: 10101010 
Disco 3: 00111000 
Disco R.:01100010 
Disco2: 11001100 
Novo valor 
Obs: A soma módulo-2 
entre o novo e antigo valor 
do bloco indica quais bits 
foram modificados 
Antigo valor dos dados 
Antigo valor de paridade 
Disco 2 (Antigo): 10101010 
Disco 2 (Novo): 11001100 
Disco R (Antigo): 01100010 
cálculo módulo-2 
Disco R (Novo): 00000100 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
RAID Nível 5 
 Em RAID nível 4, toda modificação em blocos dos 
𝑛 discos de dados requer uma modificação no 
disco redundante 
• Como resultado, o número médio de escritas disco 
redundante será aproximadamente 𝑛 vezes o número 
de escritas em um único disco 
• Possível gargalo 
 RAID nível 5 explora o fato de que a operação de 
soma modulo-2 pode ser usada para recuperar 
qualquer disco, de dados ou o disco redundante 
• Cada disco pode desempenhar o papel de disco 
redudante 
65 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
RAID Nível 5 
 Considere 𝑛 + 1 discos numerados de 0 a 𝑛. O 
cilindro 𝑖 de um disco 𝑗 é tratado como 
redundante se 𝑗 = 𝑖 𝑚𝑜𝑑 (𝑛 + 1) 
66 
 {0, 4, 8, …} 
𝑛 = 3 
 {1, 5, 9, …,} {2, 6, 10, …,} {3, 7, 11, …,} 
Disco 0 Disco 1 Disco 2 Disco 3 
cilindros redundantes 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
RAID 6 
 RAID 4 e 5 usam apenas um disco redundante, 
mas garantem proteção contra a falha de apenas 
um disco 
 RAID 6 usa um conjunto extra de informações de 
paridade para garantir proteção contra a falha 
simultânea de dois discos 
 Generalização desta técnica permite tratar a falha 
simultânea de qualquer quantidade de discos, 
sejam discos de dados ou redundantes, desde 
que uma quantidade suficiente de discos 
redundantes seja usada 
67 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Referências Adicionais 
 Jim Gray, Gianfranco R. Putzolu: The 5 Minute 
Rule for Trading Memory for Disk Accesses 
and The 10 Byte Rule for Trading Memory for 
CPU Time. SIGMOD Conference 1987: 395-398 
 Jim Gray, Goetz Graefe: The Five-Minute Rule 
Ten Years Later, and Other Computer Storage 
Rules of Thumb. SIGMOD Record 26(4): 63-68 
(1997) 
68