{"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\/sv\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"Felkoder: en enkel f\u00f6rklaring om hur man p\u00e5 ett s\u00e4kert och billigt s\u00e4tt lagrar data","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Felkoder:<\/p>\n

<\/p>\n

S\u00e5 h\u00e4r ser \u00f6verskottsdata ut<\/em><\/p>\n

<\/p>\n

\u00d6verskottskoder* anv\u00e4nds i stor utstr\u00e4ckning i datorsystem f\u00f6r att \u00f6ka tillf\u00f6rlitligheten vid datalagring. P\u00e5 Yandex anv\u00e4nds de i m\u00e5nga projekt. Till exempel sparar anv\u00e4ndningen av \u00f6verskottskoder ist\u00e4llet f\u00f6r replikering i v\u00e5rt interna objektlagringssystem miljontals utan att minska tillf\u00f6rlitligheten. Men trots den utbredda anv\u00e4ndningen \u00e4r en begriplig beskrivning av hur \u00f6verskottskoder fungerar mycket s\u00e4llsynt. De som vill f\u00f6rst\u00e5 st\u00f6ter ofta p\u00e5 f\u00f6ljande (fr\u00e5n Wikipedia<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Felkoder:<\/p>\n

<\/p>\n

Jag heter Vadim, och p\u00e5 Yandex arbetar jag med utvecklingen av det interna objektlagringssystemet MDS. I denna artikel ska jag p\u00e5 ett enkelt s\u00e4tt beskriva de teoretiska grunderna f\u00f6r \u00f6verskottskoder (Reed-Solomon-koder och LRC). Jag kommer att f\u00f6rklara hur det fungerar utan komplicerad matematik och s\u00e4llsynta termer. I slutet kommer jag att ge exempel p\u00e5 anv\u00e4ndning av \u00f6verskottskoder i Yandex.<\/p>\n

<\/p>\n

Jag kommer inte att g\u00e5 in p\u00e5 en rad matematiska detaljer, men jag ger l\u00e4nkar f\u00f6r dem som vill f\u00f6rdjupa sig mer. Jag noterar ocks\u00e5 att vissa matematiska definitioner kanske inte \u00e4r strikta, eftersom artikeln \u00e4r avsedd f\u00f6r ingenj\u00f6rer som vill f\u00f6rst\u00e5 k\u00e4rnan i fr\u00e5gan.<\/p>\n

<\/p>\n

* I engelskspr\u00e5kig litteratur kallas \u00f6verskottskoder ofta f\u00f6r erasure codes.<\/p>\n

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

1. K\u00e4rnan i \u00f6verskottskoder<\/h1>\n

<\/p>\n

K\u00e4rnan i alla \u00f6verskottskoder \u00e4r mycket enkel: att lagra (eller \u00f6verf\u00f6ra) data p\u00e5 ett s\u00e4tt som f\u00f6rhindrar dataf\u00f6rlust vid uppkomst av fel (diskfel, data\u00f6verf\u00f6ringsfel osv.). <\/p>\n

<\/p>\n

I de flesta* \u00f6verskottskoder delas data upp i n datablokker, och f\u00f6r dessa ber\u00e4knas m \u00f6verskottskoder, vilket ger totalt n + m block. \u00d6verskottskoderna konstrueras s\u00e5 att man kan \u00e5terst\u00e4lla n datablokker genom att anv\u00e4nda endast en del av de n + m blocken. Nedan kommer vi endast att titta p\u00e5 block\u00f6verskottskoder, det vill s\u00e4ga s\u00e5dana d\u00e4r data delas upp i block.<\/p>\n

<\/p>\n

\"Felkoder:<\/p>\n

<\/p>\n

F\u00f6r att \u00e5terst\u00e4lla alla n datablok m\u00e5ste man ha minst n av n + m block, eftersom man inte kan f\u00e5 n block med endast n-1 block (i s\u00e5 fall skulle man beh\u00f6va ta 1 block \"fr\u00e5n ingenstans\"). \u00c4r n godtyckliga block av n + m block tillr\u00e4ckligt f\u00f6r att \u00e5terst\u00e4lla all data? Det beror p\u00e5 typen av \u00f6verfl\u00f6dskoder, till exempel till\u00e5ter Reid-Solomon-koder att \u00e5terst\u00e4lla all data med hj\u00e4lp av godtyckliga n block, medan LRC-\u00f6verfl\u00f6dskoder inte alltid g\u00f6r det.<\/p>\n

<\/p>\n

Databevarande<\/h3>\n

<\/p>\n

I datalagringssystem lagras vanligtvis varje databasblock och \u00f6verfl\u00f6dsblock p\u00e5 enskilda diskar. Om en godtycklig disk g\u00e5r s\u00f6nder kan de ursprungliga uppgifterna fortfarande \u00e5terst\u00e4llas och l\u00e4sas. Data kan \u00e5terst\u00e4llas \u00e4ven vid samtidig fel p\u00e5 flera diskar.<\/p>\n

<\/p>\n

Datatransmission<\/h3>\n

<\/p>\n

\u00d6verfl\u00f6dskoder kan anv\u00e4ndas f\u00f6r p\u00e5litlig datatransmission i op\u00e5litliga n\u00e4tverk. De \u00f6verf\u00f6rda uppgifterna delas upp i block, och \u00f6verfl\u00f6dskoder ber\u00e4knas f\u00f6r dessa. B\u00e5de datablok och \u00f6verfl\u00f6dsblock \u00f6verf\u00f6rs \u00f6ver n\u00e4tverket. N\u00e4r fel uppst\u00e5r i godtyckliga block (upp till ett visst antal block) kan data fortfarande \u00f6verf\u00f6ras felfritt \u00f6ver n\u00e4tverket. Reid-Solomon-koder, till exempel, anv\u00e4nds f\u00f6r datatransmission \u00f6ver optiska kommunikationslinjer och i satellitkommunikation.<\/p>\n

<\/p>\n

* Det finns \u00e4ven \u00f6verfl\u00f6dskoder d\u00e4r data inte delas upp i block, till exempel Hamming-koder och CRC-koder, som \u00e4r vanligt f\u00f6rekommande f\u00f6r datatransmission i Ethernet-n\u00e4tverk. Dessa \u00e4r koder f\u00f6r felkorrigerande kodning och \u00e4r avsedda f\u00f6r att uppt\u00e4cka fel snarare \u00e4n att korrigera dem (Hamming-koden till\u00e5ter ocks\u00e5 delvis korrigering av fel).<\/p>\n

<\/p>\n

2. Reid-Solomon-koder<\/h1>\n

<\/p>\n

Reid-Solomon-koder \u00e4r en av de mest spridda \u00f6verfl\u00f6dskoderna, uppfunna redan p\u00e5 1960-talet och som f\u00f6rst fick stor anv\u00e4ndning p\u00e5 1980-talet f\u00f6r massproduktion av CD-skivor.<\/p>\n

<\/p>\n

Det finns tv\u00e5 nyckelfr\u00e5gor f\u00f6r att f\u00f6rst\u00e5 Reid-Solomon-koder: 1) hur man skapar \u00f6verfl\u00f6dsblock; 2) hur man \u00e5terst\u00e4ller data med hj\u00e4lp av \u00f6verfl\u00f6dsblock. L\u00e5t oss hitta svar p\u00e5 dem.
\nF\u00f6r enkelhetens skull kommer vi att anta att n=6 och m=4. Andra scheman behandlas p\u00e5 liknande s\u00e4tt.<\/p>\n

<\/p>\n

Hur man skapar \u00f6verfl\u00f6dsblock<\/h3>\n

<\/p>\n

Varje block av felkorrigeringskoder betraktas oberoende av de andra. F\u00f6r att r\u00e4kna varje block anv\u00e4nds samtliga n datablokkar. I diagrammet nedan \u00e4r X1-X6 datablokkar och P1\u2013P4 \u00e4r felkorrigeringsblocks.<\/p>\n

<\/p>\n

\"Felkoder:<\/p>\n

<\/p>\n

Alla datablokkar m\u00e5ste vara samma storlek; f\u00f6r att justera kan nollbitar anv\u00e4ndas. De resulterande felkorrigeringsblocken kommer att ha samma storlek som datablokkarna. Alla datablokkar delas upp i ord (till exempel 16 bitar). Anta att vi delar upp datablokkarna i k ord. D\u00e5 kommer alla felkorrigeringsblocker ocks\u00e5 att delas in i k ord.<\/p>\n

<\/p>\n

\"Felkoder:<\/p>\n

<\/p>\n

F\u00f6r att r\u00e4kna i:e ordet i varje felkorrigeringsblock kommer i:e orden fr\u00e5n alla datablokkar att anv\u00e4ndas. De kommer att ber\u00e4knas enligt f\u00f6ljande formel:<\/p>\n

<\/p>\n

\"Felkoder:<\/p>\n

<\/p>\n

H\u00e4r \u00e4r v\u00e4rdena x = ord fr\u00e5n datablokkar, p = ord fr\u00e5n felkorrigeringsblock, alla alfa, beta, gamma och delta \u00e4r speciellt valda tal, lika f\u00f6r alla i. Det m\u00e5ste genast s\u00e4gas att alla dessa v\u00e4rden inte \u00e4r vanliga tal, utan element i Galoisf\u00e4ltet, operationerna +, -, *, \/ - \u00e4r inte de vi k\u00e4nner till, utan speciella operationer som inf\u00f6rts \u00f6ver elementen i Galoisf\u00e4ltet.<\/p>\n

<\/p>\n

Vad \u00e4r Galoisf\u00e4lt till f\u00f6r<\/h3>\n

<\/p>\n

\"Felkoder:<\/p>\n

<\/p>\n

Det verkar enkelt: vi delar upp data i block, blocken i ord, med hj\u00e4lp av orden fr\u00e5n datablokkarna ber\u00e4knar vi orden fr\u00e5n felkorrigeringsblocken \u2013 vi f\u00e5r felkorrigeringsblock. I stort sett fungerar det s\u00e5, men dj\u00e4vulen ligger i detaljerna:<\/p>\n

<\/p>\n

    \n
  1. Som n\u00e4mnts tidigare \u00e4r ordstorleken fast, i v\u00e5rt exempel 16 bitar. Formlerna ovan f\u00f6r Reed-Solomon-koder \u00e4r s\u00e5dana att n\u00e4r vanliga heltal anv\u00e4nds kan resultatet av ber\u00e4kningen av p vara orepresenterbart med hj\u00e4lp av ett ord av giltig storlek.<\/li>\n
  2. Vid \u00e5terst\u00e4llande av data kommer ovanst\u00e5ende formler att betraktas som ett system av ekvationer som m\u00e5ste l\u00f6sas f\u00f6r att \u00e5terst\u00e4lla data. Under l\u00f6sningen kan det bli n\u00f6dv\u00e4ndigt att utf\u00f6ra division av heltal med varandra, vilket ger ett reellt tal som inte kan representeras exakt i datorns minne.<\/li>\n<\/ol>\n

    <\/p>\n

    Dessa problem g\u00f6r att hela tal inte kan anv\u00e4ndas f\u00f6r Reed-Solomon-koder. L\u00f6sningen p\u00e5 problemet \u00e4r originell och kan beskrivas p\u00e5 f\u00f6ljande s\u00e4tt: l\u00e5t oss t\u00e4nka ut speciella tal som kan representeras med ord av \u00f6nskad l\u00e4ngd (till exempel 16 bitar) och resultatet av alla operationer p\u00e5 dem (addition, subtraktion, multiplikation, division) ocks\u00e5 kommer att representeras i datorns minne med ord av \u00f6nskad l\u00e4ngd.<\/p>\n

    <\/p>\n

    Dessa \"speciella\" tal har l\u00e4nge studerats inom matematik och kallas kroppar. En kropp \u00e4r en m\u00e4ngd element med specifika operationer f\u00f6r addition, subtraktion, multiplikation och division.<\/p>\n

    <\/p>\n

    Galois-kroppar* \u00e4r kroppar d\u00e4r det finns ett entydigt resultat f\u00f6r varje operation (+, -, *, \\\/) f\u00f6r vilka som helst tv\u00e5 element i kroppen. Galois-kroppar kan byggas f\u00f6r tal som \u00e4r en potens av 2: 2, 4, 8, 16 och s\u00e5 vidare (i praktiken \u00e4r vi dock bara intresserade av potenser av 2). Till exempel, f\u00f6r ord av storlek 16 bitar \u00e4r detta en kropp som inneh\u00e5ller 65 536 element, f\u00f6r vilka man kan hitta resultatet av vilken operation (+, -, *, \\\/) som helst f\u00f6r varje par. V\u00e4rdena x, p, alfa, beta, gamma, delta i ovanst\u00e5ende ekvationer kommer att betraktas som element av Galois-kroppen f\u00f6r ber\u00e4kningarna.<\/p>\n

    <\/p>\n

    S\u00e5ledes har vi ett system av ekvationer, med hj\u00e4lp av vilket vi kan bygga redundanta kodblock genom att skriva ett motsvarande datorprogram. Med hj\u00e4lp av detta system av ekvationer kan vi ocks\u00e5 utf\u00f6ra datag \u00e5terst\u00e4llning.<\/p>\n

    <\/p>\n

    * Detta \u00e4r ingen strikt definition, snarare en beskrivning.<\/p>\n

    <\/p>\n

    Hur man \u00e5terst\u00e4ller data<\/h3>\n

    <\/p>\n

    \u00c5terst\u00e4llning \u00e4r n\u00f6dv\u00e4ndig n\u00e4r en del av blocken \u00e4r saknade fr\u00e5n n + m block. Det kan vara antingen datablock eller redundanta kodblock. Fr\u00e5nvaro av datablock och\/eller redundanta kodblock inneb\u00e4r att de motsvarande variablerna x och\/eller p i ovanst\u00e5ende ekvationer \u00e4r ok\u00e4nda.<\/p>\n

    <\/p>\n

    Ekvationerna f\u00f6r Reed-Solomon-koder kan betraktas som ett system av ekvationer, d\u00e4r alla v\u00e4rden alfa, beta, gamma, delta \u00e4r konstanter, alla x och p som motsvarar tillg\u00e4ngliga block \u00e4r k\u00e4nda variabler, medan de \u00f6vriga x och p \u00e4r ok\u00e4nda.<\/p>\n

    <\/p>\n

    Till exempel, l\u00e5t oss anta att datablock 1, 2, 3 och redundanta kodblock 2 \u00e4r otillg\u00e4ngliga, d\u00e5 kommer f\u00f6ljande system av ekvationer att g\u00e4lla f\u00f6r den i:te ordgruppen (ok\u00e4nda markerade i r\u00f6tt):<\/p>\n

    <\/p>\n

    \"Felkoder:<\/p>\n

    <\/p>\n

    Vi har ett system med 4 ekvationer och 4 obekanta, vilket inneb\u00e4r att vi kan l\u00f6sa det och \u00e5terst\u00e4lla data!<\/p>\n

    <\/p>\n

    Fr\u00e5n detta ekvationssystem f\u00f6ljer en rad slutsatser om datarader f\u00f6r Reed-Solomon-koder (n datablokkar, m redundanta kodblock):<\/p>\n

    <\/p>\n