{"id":87758,"date":"2020-07-10T01:41:58","date_gmt":"2020-07-09T23:41:58","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye"},"modified":"2020-07-10T01:41:58","modified_gmt":"2020-07-09T23:41:58","slug":"kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","status":"publish","type":"post","link":"https:\/\/prohoster.info\/pt\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"C\u00f3digos de redund\u00e2ncia: explicando de forma simples como armazenar dados com seguran\u00e7a e de forma econ\u00f4mica","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"C\u00f3digos<\/p>\n

<\/p>\n

Esta \u00e9 a apar\u00eancia da redund\u00e2ncia<\/em><\/p>\n

<\/p>\n

C\u00f3digos de redund\u00e2ncia* s\u00e3o amplamente utilizados em sistemas computacionais para aumentar a confiabilidade do armazenamento de dados. No Yandex, eles s\u00e3o empregados em muitos projetos. Por exemplo, o uso de c\u00f3digos de redund\u00e2ncia em vez de replica\u00e7\u00e3o em nosso armazenamento de objetos interno economiza milh\u00f5es sem comprometer a confiabilidade. No entanto, apesar da ampla dissemina\u00e7\u00e3o, uma descri\u00e7\u00e3o clara de como funcionam os c\u00f3digos de redund\u00e2ncia \u00e9 rara. Aqueles que desejam entender deparam-se com algo como o seguinte (de Wikis<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

Meu nome \u00e9 Vadim, e no Yandex eu trabalho no desenvolvimento do armazenamento de objetos interno MDS. Neste artigo, explicarei de forma simples os fundamentos te\u00f3ricos dos c\u00f3digos de redund\u00e2ncia (c\u00f3digos de Reed-Solomon e LRC). Contarei como isso funciona, sem matem\u00e1tica complexa ou termos raros. No final, apresentarei exemplos de uso dos c\u00f3digos de redund\u00e2ncia no Yandex.<\/p>\n

<\/p>\n

Uma s\u00e9rie de detalhes matem\u00e1ticos n\u00e3o ser\u00e1 abordada com profundidade, mas fornecer\u00e9 links para aqueles que desejam se aprofundar. Tamb\u00e9m observarei que algumas defini\u00e7\u00f5es matem\u00e1ticas podem n\u00e3o ser rigorosas, uma vez que o artigo n\u00e3o \u00e9 destinado a matem\u00e1ticos, mas a engenheiros que desejam entender a ess\u00eancia da quest\u00e3o.<\/p>\n

<\/p>\n

* Na literatura em l\u00edngua inglesa, os c\u00f3digos de redund\u00e2ncia s\u00e3o frequentemente chamados de erasure codes.<\/p>\n

<\/a><\/noindex><\/p>\n

1. A ess\u00eancia dos c\u00f3digos de redund\u00e2ncia<\/h1>\n

<\/p>\n

A ess\u00eancia de todos os c\u00f3digos de redund\u00e2ncia \u00e9 extremamente simples: armazenar (ou transmitir) dados de maneira que n\u00e3o se percam em caso de erros (falhas de discos, erros na transmiss\u00e3o de dados, etc.). <\/p>\n

<\/p>\n

Na maioria* dos c\u00f3digos de redund\u00e2ncia, os dados s\u00e3o divididos em n blocos de dados, para os quais s\u00e3o calculados m blocos de c\u00f3digos de redund\u00e2ncia, totalizando n + m blocos. Os c\u00f3digos de redund\u00e2ncia s\u00e3o constru\u00eddos de forma que seja poss\u00edvel recuperar n blocos de dados utilizando apenas uma parte dos n + m blocos. A seguir, abordaremos apenas c\u00f3digos de redund\u00e2ncia em bloco, ou seja, aqueles em que os dados s\u00e3o divididos em blocos.<\/p>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

Para restaurar todos os n blocos de dados, \u00e9 necess\u00e1rio ter pelo menos n de n + m blocos, pois n\u00e3o se pode obter n blocos tendo apenas n-1 bloco (neste caso, seria necess\u00e1rio obter 1 bloco 'do nada'). \u00c9 suficiente ter n blocos arbitr\u00e1rios de n + m blocos para a restaura\u00e7\u00e3o de todos os dados? Isso depende do tipo de c\u00f3digos de redund\u00e2ncia; por exemplo, os c\u00f3digos de Reed-Solomon permitem restaurar todos os dados com n blocos arbitr\u00e1rios, enquanto os c\u00f3digos de redund\u00e2ncia LRC nem sempre o fazem.<\/p>\n

<\/p>\n

Armazenamento de dados<\/h3>\n

<\/p>\n

Nos sistemas de armazenamento de dados, geralmente, cada um dos blocos de dados e blocos de c\u00f3digos de redund\u00e2ncia \u00e9 gravado em um disco separado. Assim, ao falhar um disco qualquer, os dados originais ainda poder\u00e3o ser recuperados e lidos. Os dados poder\u00e3o ser recuperados mesmo em caso de falha simult\u00e2nea de v\u00e1rios discos.<\/p>\n

<\/p>\n

Transmiss\u00e3o de dados<\/h3>\n

<\/p>\n

Os c\u00f3digos de redund\u00e2ncia podem ser usados para uma transmiss\u00e3o confi\u00e1vel de dados em uma rede n\u00e3o confi\u00e1vel. Os dados transmitidos s\u00e3o divididos em blocos, e para eles s\u00e3o calculados os c\u00f3digos de redund\u00e2ncia. Tanto os blocos de dados quanto os blocos de c\u00f3digos de redund\u00e2ncia s\u00e3o transmitidos pela rede. Em caso de erro em blocos arbitr\u00e1rios (at\u00e9 um certo n\u00famero de blocos), os dados ainda podem ser transmitidos pela rede de forma confi\u00e1vel. Os c\u00f3digos de Reed-Solomon, por exemplo, s\u00e3o utilizados para a transmiss\u00e3o de dados por linhas \u00f3pticas de comunica\u00e7\u00e3o e em comunica\u00e7\u00f5es via sat\u00e9lite.<\/p>\n

<\/p>\n

* Existem tamb\u00e9m c\u00f3digos de redund\u00e2ncia em que os dados n\u00e3o s\u00e3o divididos em blocos, como os c\u00f3digos de Hamming e os c\u00f3digos CRC, amplamente utilizados para transmiss\u00e3o de dados em redes Ethernet. Esses s\u00e3o c\u00f3digos para codifica\u00e7\u00e3o resistente a interfer\u00eancias, destinados \u00e0 detec\u00e7\u00e3o de erros, e n\u00e3o \u00e0 sua corre\u00e7\u00e3o (o c\u00f3digo de Hamming tamb\u00e9m permite corrigir erros parcialmente).<\/p>\n

<\/p>\n

2. C\u00f3digos de Reed-Solomon<\/h1>\n

<\/p>\n

Os c\u00f3digos de Reed-Solomon s\u00e3o um dos c\u00f3digos de redund\u00e2ncia mais amplamente utilizados, inventados na d\u00e9cada de 1960 e que obtiveram aplica\u00e7\u00e3o generalizada em 1980 para a produ\u00e7\u00e3o em s\u00e9rie de CDs.<\/p>\n

<\/p>\n

Duas quest\u00f5es chave para entender os c\u00f3digos de Reed-Solomon s\u00e3o: 1) como criar blocos de c\u00f3digos de redund\u00e2ncia; 2) como recuperar dados usando blocos de c\u00f3digos de redund\u00e2ncia. Vamos encontrar respostas para elas.
\nPara simplificar, consideraremos a seguir que n=6 e m=4. Outros esquemas s\u00e3o considerados por analogia.<\/p>\n

<\/p>\n

Como criar blocos de c\u00f3digos de redund\u00e2ncia<\/h3>\n

<\/p>\n

Cada bloco de c\u00f3digos de redund\u00e2ncia \u00e9 considerado independentemente dos outros. Para o c\u00e1lculo de cada bloco, s\u00e3o utilizados todos os n blocos de dados. No diagrama abaixo, X1-X6 representam os blocos de dados, enquanto P1\u2013P4 s\u00e3o blocos de c\u00f3digos de redund\u00e2ncia.<\/p>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

Todos os blocos de dados devem ter o mesmo tamanho; para o alinhamento, podem ser utilizados bits nulos. Os blocos de c\u00f3digos de redund\u00e2ncia resultantes ter\u00e3o o mesmo tamanho que os blocos de dados. Todos os blocos de dados s\u00e3o divididos em palavras (por exemplo, 16 bits). Suponha que dividimos os blocos de dados em k palavras. Assim, todos os blocos de c\u00f3digos de redund\u00e2ncia tamb\u00e9m ser\u00e3o divididos em k palavras.<\/p>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

Para calcular a i-\u00e9sima palavra de cada bloco de redund\u00e2ncia, utilizaremos as i-\u00e9simas palavras de todos os blocos de dados. Elas ser\u00e3o calculadas pela seguinte f\u00f3rmula:<\/p>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

Aqui os valores x representam as palavras dos blocos de dados, p as palavras dos blocos de c\u00f3digos de redund\u00e2ncia, e todos os alfa, beta, gama e delta s\u00e3o n\u00fameros especialmente escolhidos, iguais para todos os i. \u00c9 importante notar que todos esses valores n\u00e3o s\u00e3o n\u00fameros comuns, mas elementos de um campo de Galois; as opera\u00e7\u00f5es +, -, *, \/ n\u00e3o s\u00e3o as opera\u00e7\u00f5es habituais que conhecemos, mas opera\u00e7\u00f5es especiais introduzidas sobre os elementos do campo de Galois.<\/p>\n

<\/p>\n

Por que s\u00e3o necess\u00e1rios os campos de Galois<\/h3>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

A princ\u00edpio, parece simples: dividimos os dados em blocos, os blocos em palavras, e com as palavras dos blocos de dados calculamos as palavras dos blocos de c\u00f3digos de redund\u00e2ncia, obtendo assim os blocos de c\u00f3digos de redund\u00e2ncia. De forma geral, \u00e9 assim que funciona, mas o diabo est\u00e1 nos detalhes:<\/p>\n

<\/p>\n

    \n
  1. Como mencionado acima, o tamanho da palavra \u00e9 fixo, em nosso exemplo 16 bits. As f\u00f3rmulas acima para os c\u00f3digos de Reed-Solomon s\u00e3o tais que, ao utilizar inteiros comuns, o resultado do c\u00e1lculo de p pode n\u00e3o ser represent\u00e1vel com uma palavra do tamanho permitido.<\/li>\n
  2. Ao restaurar os dados, as f\u00f3rmulas acima ser\u00e3o consideradas como um sistema de equa\u00e7\u00f5es a ser resolvido para restaurar os dados. Durante o processo de resolu\u00e7\u00e3o, pode haver a necessidade de dividir n\u00fameros inteiros entre si, resultando em um n\u00famero real que n\u00e3o pode ser representado com precis\u00e3o na mem\u00f3ria do computador.<\/li>\n<\/ol>\n

    <\/p>\n

    Esses problemas impedem o uso de n\u00fameros inteiros para os c\u00f3digos de Reed-Solomon. A solu\u00e7\u00e3o para o problema \u00e9 original e pode ser descrita da seguinte forma: vamos criar n\u00fameros especiais que podem ser representados por palavras de um determinado tamanho (por exemplo, 16 bits), e o resultado de todas as opera\u00e7\u00f5es realizadas sobre esses n\u00fameros (adi\u00e7\u00e3o, subtra\u00e7\u00e3o, multiplica\u00e7\u00e3o, divis\u00e3o) tamb\u00e9m ser\u00e1 representado na mem\u00f3ria do computador usando palavras desse tamanho.<\/p>\n

    <\/p>\n

    Esses n\u00fameros \u201cespeciais\u201d s\u00e3o estudados h\u00e1 muito tempo pela matem\u00e1tica e s\u00e3o chamados de campos. Um campo \u00e9 um conjunto de elementos com opera\u00e7\u00f5es de adi\u00e7\u00e3o, subtra\u00e7\u00e3o, multiplica\u00e7\u00e3o e divis\u00e3o definidas para eles.<\/p>\n

    <\/p>\n

    Os campos de Galois* s\u00e3o campos para os quais existe e \u00e9 \u00fanico o resultado de cada opera\u00e7\u00e3o (+, -, *, \/) para quaisquer dois elementos do campo. Os campos de Galois podem ser constru\u00eddos para n\u00fameros que s\u00e3o pot\u00eancias de 2: 2, 4, 8, 16, etc. (na verdade, pot\u00eancias de qualquer n\u00famero primo p, mas na pr\u00e1tica, estamos interessados apenas nas pot\u00eancias de 2). Por exemplo, para palavras de tamanho 16 bits, esse campo cont\u00e9m 65.536 elementos, para cada par dos quais \u00e9 poss\u00edvel encontrar o resultado de qualquer opera\u00e7\u00e3o (+, -, *, \/). Os valores x, p, alfa, beta, gama, delta nas equa\u00e7\u00f5es acima para c\u00e1lculos ser\u00e3o considerados elementos do campo de Galois.<\/p>\n

    <\/p>\n

    Assim, temos um sistema de equa\u00e7\u00f5es que pode ser usado para construir blocos de c\u00f3digos de redund\u00e2ncia, escrevendo um programa de computador correspondente. Com esse mesmo sistema de equa\u00e7\u00f5es, \u00e9 poss\u00edvel realizar a recupera\u00e7\u00e3o de dados.<\/p>\n

    <\/p>\n

    * Esta n\u00e3o \u00e9 uma defini\u00e7\u00e3o estrita, mas sim uma descri\u00e7\u00e3o.<\/p>\n

    <\/p>\n

    Como recuperar dados<\/h3>\n

    <\/p>\n

    A recupera\u00e7\u00e3o \u00e9 necess\u00e1ria quando, de n + m blocos, alguns blocos est\u00e3o ausentes. Isso pode incluir tanto blocos de dados quanto blocos de c\u00f3digos de redund\u00e2ncia. A aus\u00eancia de blocos de dados e\/ou blocos de c\u00f3digos de redund\u00e2ncia significa que nas equa\u00e7\u00f5es acima as vari\u00e1veis correspondentes x e\/ou p s\u00e3o desconhecidas.<\/p>\n

    <\/p>\n

    As equa\u00e7\u00f5es para os c\u00f3digos de Reed-Solomon podem ser vistas como um sistema de equa\u00e7\u00f5es em que todos os valores alfa, beta, gama, delta s\u00e3o constantes, todos os x e p correspondentes aos blocos dispon\u00edveis s\u00e3o vari\u00e1veis conhecidas, e os demais x e p s\u00e3o desconhecidos.<\/p>\n

    <\/p>\n

    Por exemplo, suponha que os blocos de dados 1, 2, 3 e o bloco de c\u00f3digos de redund\u00e2ncia 2 estejam indispon\u00edveis, ent\u00e3o para o i-\u00e9simo grupo de palavras teremos o seguinte sistema de equa\u00e7\u00f5es (as inc\u00f3gnitas est\u00e3o marcadas em vermelho):<\/p>\n

    <\/p>\n

    \"C\u00f3digos<\/p>\n

    <\/p>\n

    Temos um sistema de 4 equa\u00e7\u00f5es com 4 inc\u00f3gnitas, portanto podemos resolv\u00ea-lo e recuperar os dados!<\/p>\n

    <\/p>\n

    Dessa sistema de equa\u00e7\u00f5es decorrem v\u00e1rias conclus\u00f5es sobre a recupera\u00e7\u00e3o de dados para c\u00f3digos de Reed-Solomon (n blocos de dados, m blocos de c\u00f3digo de redund\u00e2ncia):<\/p>\n

    <\/p>\n