Papers
f4: Facebook's Warm BLOB Storage System
Subramanian Muralidhar, Wyatt Lloyd, Sabyasachi Roy, Cory Hill, Ernest Lin, Weiwen Liu, Satadru Pan, Shiva Shankar, Viswanath Sivakumar, Linpeng Tang, Sanjeev Kumar · 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI) 2014, 2014
O problema: dados que esfriam continuam pagando o preço de dados quentes
O Facebook guarda fotos, vídeos e outros BLOBs (objetos binários grandes, escritos uma vez e quase nunca alterados). O sistema anterior para isso, o Haystack, foi pensado para servir conteúdo recente e muito acessado. Ele mantém três réplicas (duas em racks diferentes do datacenter principal e uma terceira em outro datacenter), com RAID-6 em cada máquina. O custo efetivo é um fator de replicação de 3,6 (três cópias vezes 1,2 do RAID-6). Os autores estudaram os padrões de acesso e concluíram que o uso depende fortemente da idade: BLOBs novos são lidos com muito mais frequência, e a taxa de requisições cai bastante conforme o conteúdo envelhece. A taxa de deleção também cai com a idade. O resultado é que a maior parte dos objetos armazenados é morna (warm): nas medianas por janela de calendário, mais de 80% dos objetos eram mornos em todos os seis tipos analisados na janela mais antiga e mais de 89% na mais recente, ou seja, a fração morna cresce. Esses dados têm poucas leituras por terabyte, mas continuam ocupando o número alto de réplicas pensado para a carga quente. Isso desperdiça disco: o gargalo de um dado morno não é throughput, é capacidade. O paper propõe separar os dois regimes. O Haystack continua servindo o conteúdo quente, e um sistema novo, o f4, assume os BLOBs mornos com custo de armazenamento menor, aceitando throughput inferior por terabyte. A análise indica um mês como limite seguro entre quente e morno para a maioria dos tipos e três meses para Photos; Profile Photos não migra para o f4. Na produção da época, por simplicidade, usava-se um corte de cerca de três meses para todos os tipos.
A ideia central: trocar réplicas completas por codificação de apagamento
A ideia do f4 é substituir cópias inteiras por erasure coding, mantendo tolerância a falhas. Dentro de uma célula (o bloco de construção do f4, em um único datacenter), os dados são divididos em stripes com 10 blocos de dados e 4 blocos de paridade, usando Reed-Solomon (10,4). Qualquer 4 blocos de um stripe podem ser perdidos e ainda assim o conteúdo é reconstruído. O custo é de 1,4 vez o tamanho dos dados, bem abaixo dos 3,6 do Haystack. Os blocos usados na codificação têm cerca de 1 GB. As células da época (2014) usavam 14 racks de 15 máquinas, cada uma com 30 discos de 4 TB, e os blocos de um stripe ficam espalhados por racks diferentes, de modo que falhas de disco, de máquina e de rack dentro do datacenter sejam toleradas. Esse desenho fica simples porque o f4 só guarda volumes travados, que aceitam apenas leitura e deleção: não há appends nem sobrescritas, então o desenho dispensa journal e compaction, já que a deleção é feita pela chave. Cada BLOB tem sua própria chave de criptografia, e a deleção lógica consiste em destruir essa chave, em vez de reescrever o stripe. O ganho vem de explorar três propriedades da carga ao mesmo tempo: dados somente leitura, pouca leitura e preferência por capacidade.
Arquitetura da célula: nós de armazenamento e nós sem disco
Cada célula do f4 separa armazenamento de computação. Os nós de armazenamento guardam os blocos em disco e atendem leituras. Entre os componentes da célula (nós de armazenamento, name, backoff, rebuilder e coordinator), três ficam em máquinas sem armazenamento próprio e com CPU abundante; o name node, em primário-backup, guarda o mapeamento entre blocos e nós. Os backoff nodes entram quando o bloco de dados que contém o BLOB pedido está indisponível: eles reconstroem sob demanda o BLOB pedido, lendo trechos dos outros blocos do stripe, em vez de refazer o bloco inteiro. Os rebuilder nodes detectam falhas por sondagem e reconstroem blocos inteiros em segundo plano, com taxa limitada para não prejudicar as requisições dos usuários. Os coordinator nodes agendam as reconstruções e executam um balanceador de posicionamento, que corrige casos em que blocos do mesmo stripe acabam no mesmo domínio de falha, como o mesmo rack. Essa divisão mantém o caminho normal de leitura simples, e o custo extra de decodificação só aparece na falha. A reconstrução é um processo pesado, que impõe carga significativa de I/O e de rede aos nós de armazenamento; por isso as reconstruções são limitadas e agendadas com cuidado. O paper reporta que as leituras do f4 têm latência um pouco maior que as do Haystack (nas leituras dentro da mesma região, a mediana é de 17 ms contra 14 ms), o que os autores consideram suficiente para uma boa experiência do usuário.
Tolerância a falhas de datacenter: do fator 2,8 ao 2,1 com XOR
O Reed-Solomon (10,4) protege contra falhas dentro de um datacenter, mas não contra a perda do datacenter inteiro. A primeira solução do f4 foi guardar uma segunda cópia completa da célula em outra região geográfica, o que dobra o custo: 1,4 vezes 2 resulta em um fator efetivo de 2,8. O passo seguinte foi usar XOR entre regiões. Cada volume, stripe e bloco é emparelhado com um parceiro (buddy) em outra região, e o XOR dos dois é gravado em uma terceira região. Se qualquer uma das três regiões for perdida, o conteúdo pode ser recuperado a partir das outras duas: um bloco perdido é obtido combinando seu parceiro com o XOR. Para cada par de volumes há três células codificadas (os dois volumes e o XOR deles), ou seja, 3 células para 2 volumes lógicos, o que dá 1,5 vezes entre as regiões. Combinado com 1,4, o cálculo é (1,4·2 + 1,4)/2 = 2,1. O abstract do paper resume o resultado dizendo que o f4 reduz o fator de 3,6 para 2,8 ou 2,1, conforme o esquema, tolerando falhas de disco, máquina, rack e datacenter. O trade-off está no custo de leitura sob falha: se o datacenter que guarda o BLOB falha, a leitura combina o bloco XOR com o buddy de outra região, com throughput menor para os BLOBs daquele datacenter.
Resultados, limites e lições de projeto
O paper reporta que o f4 armazenava mais de 65 PB de BLOBs lógicos e economizava mais de 53 PB com a implantação parcial do esquema 2,1 (mais de 39 PB a 2,8; mais de 87 PB projetados com 2,1 completo). Os autores relatam também um episódio de falhas: um lote ruim de discos, combinado com temperaturas altas em uma região, elevou a taxa anual de falhas de cerca de 1% para mais de 60% por algumas semanas, sem perda de dados, porque os blocos buddy e XOR estavam em outras células, não afetadas. Na seção de lições, o paper destaca três. Primeira, a simplicidade favorece a estabilidade operacional: uma versão inicial usava um arquivo de journal de deleções como o do Haystack, que destoava do resto do desenho somente leitura, e removê-lo ajudou. Segunda, vale medir o software de base para o seu caso de uso, no caso o caminho de leitura do sistema de arquivos distribuído. Terceira, a heterogeneidade de hardware reduz a chance de falhas correlacionadas, como a do episódio acima; os autores planejam usá-la. Além disso, o f4 complementa o Haystack, tratando só o que esfriou, e hardware e software foram co-projetados, de modo que o software garante que o pico semanal de carga em cada disco fique abaixo do IOPS máximo que ele entrega. O erasure coding troca menor custo de armazenamento por tempos maiores de reconstrução e recuperação sob falha e menor throughput máximo de leitura. O leitor pode tratar o f4 como um estudo de caso de separar camadas por padrão de acesso.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.