Så här ser redundans ut
Redundanskoder* används ofta i datorsystem för att öka tillförlitligheten för datalagring. I Yandex används de i många projekt. Att till exempel använda redundanskoder istället för replikering i vår interna objektlagring sparar miljoner utan att offra tillförlitligheten. Men trots deras utbredda användning är tydliga beskrivningar av hur redundanskoder fungerar mycket sällsynta. De som vill förstå ställs inför ungefär följande (från ):
Jag heter Vadim, på Yandex utvecklar jag MDS för intern objektlagring. I den här artikeln kommer jag i enkla ord att beskriva de teoretiska grunderna för redundanskoder (Reed-Solomon och LRC-koder). Jag ska berätta hur det fungerar, utan komplex matematik och sällsynta termer. I slutet kommer jag att ge exempel på hur du använder redundanskoder i Yandex.
Jag kommer inte att överväga ett antal matematiska detaljer i detalj, men jag kommer att ge länkar för dem som vill dyka djupare. Jag kommer också att notera att vissa matematiska definitioner kanske inte är strikta, eftersom artikeln inte är avsedd för matematiker, utan för ingenjörer som vill förstå kärnan i frågan.
* I engelskspråkig litteratur kallas redundanskoder ofta för raderingskoder.
1. Kärnan i redundanskoder
Kärnan i alla redundanskoder är extremt enkel: lagra (eller överför) data så att de inte går förlorade när fel uppstår (diskfel, dataöverföringsfel, etc.).
I de flesta* redundanskoder är data uppdelad i n datablock, för vilka m block av redundanskoder räknas, vilket resulterar i totalt n + m block. Redundanskoder är konstruerade på ett sådant sätt att n datablock kan återställas med användning av endast en del av n + m block. Därefter kommer vi endast att överväga blockredundanskoder, det vill säga de där data är uppdelade i block.
För att återställa alla n datablock måste du ha minst n av n + m block, eftersom du inte kan få n block genom att bara ha n-1 block (i det här fallet måste du ta 1 block "ur tunna" luft"). Är n slumpmässiga block av n + m block tillräckligt för att återställa all data? Detta beror på typen av redundanskoder, till exempel låter Reed-Solomon-koder dig återställa all data med hjälp av godtyckliga n block, men LRC-redundanskoder gör det inte alltid.
Datalagring
I datalagringssystem skrivs som regel vart och ett av datablocken och redundanskodblocken till en separat disk. Sedan, om en godtycklig disk misslyckas, kan originaldata fortfarande återställas och läsas. Data kan återställas även om flera diskar misslyckas samtidigt.
Dataöverföring
Redundanskoder kan användas för att tillförlitligt överföra data över ett opålitligt nätverk. De överförda data är uppdelade i block och redundanskoder beräknas för dem. Både datablock och redundanskodblock sänds över nätverket. Om fel uppstår i godtyckliga block (upp till ett visst antal block) kan data fortfarande sändas över nätverket utan fel. Reed-Solomon-koder, till exempel, används för att överföra data över optiska kommunikationslinjer och i satellitkommunikation.
* Det finns även redundanskoder där data inte är uppdelade i block, som Hamming-koder och CRC-koder, som används mycket för dataöverföring i Ethernet-nätverk. Detta är koder för felkorrigerande kodning, de är designade för att upptäcka fel och inte för att korrigera dem (Hamming-koden tillåter också partiell korrigering av fel).
2. Reed-Solomon-koder
Reed-Solomon-koder är en av de mest använda redundanskoderna, uppfanns redan på 1960-talet och användes först på 1980-talet för massproduktion av cd-skivor.
Det finns två nyckelfrågor för att förstå Reed-Solomon-koder: 1) hur man skapar block av redundanskoder; 2) hur man återställer data med hjälp av redundanskodblock. Låt oss hitta svar på dem.
För enkelhetens skull kommer vi vidare att anta att n=6 och m=4. Andra system betraktas analogt.
Hur man skapar redundanskodblock
Varje block av redundanskoder räknas oberoende av de andra. Alla n datablock används för att räkna varje block. I diagrammet nedan är X1-X6 datablock, P1-P4 är redundanskodblock.
Alla datablock måste ha samma storlek och noll bitar kan användas för justering. De resulterande redundanskodblocken kommer att ha samma storlek som datablocken. Alla datablock är uppdelade i ord (till exempel 16 bitar). Låt oss säga att vi delar upp datablocken i k ord. Då kommer även alla block av redundanskoder att delas upp i k ord.
För att räkna det i:te ordet i varje redundansblock kommer de i:te orden i alla datablock att användas. De kommer att beräknas enligt följande formel:
Här är värdena x orden för datablock, p är orden för redundanskodblock, alla alfa, beta, gamma och delta är speciellt utvalda tal som är lika för alla i. Det måste sägas omedelbart att alla dessa värden inte är vanliga siffror, utan element i Galois-fältet; operationerna +, -, *, / är inte operationer som är bekanta för oss alla, utan speciella operationer som introduceras på element i Galois fält.
Varför behövs Galois-fält?
Det verkar som att allt är enkelt: vi delar upp data i block, blocken i ord, med hjälp av orden i datablocken räknar vi orden i redundanskodblocken - vi får redundanskodblock. I allmänhet är det så här det fungerar, men djävulen sitter i detaljerna:
- Som nämnts ovan är ordstorleken fast, i vårt exempel 16 bitar. Formlerna ovan för Reed-Solomon-koder är sådana att när man använder vanliga heltal, kanske resultatet av beräkningen av p inte kan representeras med ett ord av giltig storlek.
- Vid återställning av data kommer formlerna ovan att betraktas som ett system av ekvationer som måste lösas för att återställa data. Under lösningsprocessen kan det vara nödvändigt att dela heltal med varandra, vilket resulterar i ett reellt tal som inte kan representeras korrekt i datorns minne.
Dessa problem förhindrar användningen av heltal för Reed-Solomon-koder. Lösningen på problemet är original, det kan beskrivas på följande sätt: låt oss komma på speciella siffror som kan representeras med hjälp av ord med önskad längd (till exempel 16 bitar), och resultatet av att utföra alla operationer som (tillägg) , subtraktion, multiplikation, division) kommer också att presenteras i datorns minne med hjälp av ord med önskad längd.
Sådana "speciella" tal har studerats av matematik under lång tid, de kallas fält. Ett fält är en uppsättning element med operationer av addition, subtraktion, multiplikation och division definierade för dem.
Galois*-fält är fält för vilka det finns ett unikt resultat av varje operation (+, -, *, /) för alla två element i fältet. Galoisfält kan konstrueras för tal som är potenser av 2: 2, 4, 8, 16, etc. (egentligen potenser av vilket primtal p som helst, men i praktiken är vi bara intresserade av potenserna 2). Till exempel, för 16-bitars ord, är detta ett fält som innehåller 65 536 element, för varje par av vilka du kan hitta resultatet av vilken operation som helst (+, -, *, /). Värdena på x, p, alfa, beta, gamma, delta från ekvationerna ovan kommer att betraktas som element i Galois-fältet för beräkningar.
Vi har alltså ett ekvationssystem med vilket vi kan konstruera block av redundanskoder genom att skriva ett lämpligt datorprogram. Med samma ekvationssystem kan du utföra dataåterställning.
* Detta är inte en strikt definition, utan snarare en beskrivning.
Hur man återställer data
Återställning behövs när några av n + m blocken saknas. Dessa kan vara både datablock och redundanskodblock. Frånvaron av datablock och/eller redundanskodblock kommer att innebära att motsvarande x- och/eller p-variabler är okända i ekvationerna ovan.
Ekvationerna för Reed-Solomon-koder kan ses som ett ekvationssystem där alla alfa-, beta-, gamma-, deltavärden är konstanter, alla x och p som motsvarar de tillgängliga blocken är kända variabler, och de återstående x och p är okända.
Låt till exempel datablock 1, 2, 3 och redundanskodblock 2 vara otillgängliga, då för den i:te gruppen av ord kommer det att finnas följande ekvationssystem (okända är markerade med rött):
Vi har ett system med 4 ekvationer med 4 okända, vilket betyder att vi kan lösa det och återställa data!
Från detta ekvationssystem följer ett antal slutsatser om dataåterställning för Reed-Solomon-koder (n datablock, m redundanskodblock):
- Data kan återställas om några m block eller färre går förlorade. Om m+1 eller fler block går förlorade kan data inte återställas: det är omöjligt att lösa ett system av mekvationer med m + 1 okända.
- För att återställa ens ett datablock måste du använda vilket n av de återstående blocken, och du kan använda vilken som helst av redundanskoderna.
Vad mer behöver du veta
I beskrivningen ovan undviker jag ett antal viktiga frågor som kräver en djupare dykning i matematik att överväga. I synnerhet säger jag ingenting om följande:
- Ekvationssystemet för Reed-Solomon-koder måste ha en (unik) lösning för alla kombinationer av okända (högst m okända). Baserat på detta krav väljs värdena för alfa, beta, gamma och delta.
- Ett ekvationssystem måste kunna konstrueras automatiskt (beroende på vilka block som är otillgängliga) och lösas.
- Vi behöver bygga ett Galois-fält: för en given ordstorlek, kunna hitta resultatet av valfri operation (+, -, *, /) för två valfria element.
I slutet av artikeln finns referenser till litteratur om dessa viktiga frågor.
Val av n och m
Hur väljer man n och m i praktiken? I praktiken, i datalagringssystem, används redundanskoder för att spara utrymme, så m väljs alltid mindre än n. Deras specifika värden beror på ett antal faktorer, inklusive:
- Tillförlitlighet för datalagring. Ju större m, desto större antal diskfel som kan överlevas, det vill säga desto högre tillförlitlighet.
- Redundant lagring. Ju högre m/n-förhållande desto högre blir lagringsredundansen och desto dyrare blir systemet.
- Begär handläggningstid. Ju större summan n + m, desto längre blir svarstiden på förfrågningar. Eftersom läsning av data (under återställning) kräver läsning av n block lagrade på n olika diskar, kommer lästiden att bestämmas av den långsammaste disken.
Dessutom innebär lagring av data i flera DC:er ytterligare begränsningar för valet av n och m: om 1 DC är avstängd måste data fortfarande vara tillgänglig för läsning. Till exempel, vid lagring av data i 3 DC:er måste följande villkor uppfyllas: m >= n/2, annars kan det uppstå en situation där data inte är tillgänglig för läsning när 1 DC är avstängd.
3. LRC - Lokala återuppbyggnadskoder
För att återställa data med Reed-Solomon-koder måste du använda n godtyckliga datablock. Detta är en mycket betydande nackdel för distribuerade datalagringssystem, eftersom för att återställa data på en trasig disk måste du läsa data från de flesta andra, vilket skapar en stor extra belastning på diskarna och nätverket.
De vanligaste felen är otillgängligheten av ett datablock på grund av ett fel eller överbelastning av en disk. Är det möjligt att på något sätt minska överbelastningen för dataåterställning i detta (vanligaste) fall? Det visar sig att du kan: det finns LRC-redundanskoder specifikt för detta ändamål.
LRC (Local Reconstruction Codes) är redundanskoder som uppfunnits av Microsoft för användning i Windows Azure Storage. Idén med LRC är så enkel som möjligt: dela upp alla datablock i två (eller flera) grupper och läs en del av redundanskodblocken för varje grupp separat. Sedan kommer vissa redundanskodblock att räknas med alla datablock (i LRC kallas de globala redundanskoder), och några - med en av två grupper av datablock (de kallas lokala redundanskoder).
LRC betecknas med tre siffror: nrl, där n är antalet datablock, r är antalet globala redundanskodblock, l är antalet lokala redundanskodblock. För att läsa data när ett datablock inte är tillgängligt behöver du endast läsa n/l block - detta är l gånger mindre än i Reed-Solomon-koder.
Tänk till exempel på LRC 6-2-2-schemat. X1–X6 — 6 datablock, P1, P2 — 2 globala redundansblock, P3, P4 — 2 lokala redundansblock.
Redundanskodblocken P1, P2 räknas med användning av alla datablock. Redundanskodblock P3 - använder datablock X1-X3, redundanskodblock P4 - använder datablock X4-X6.
Resten görs i LRC i analogi med Reed-Solomon-koder. Ekvationerna för att räkna orden i redundanskodblock kommer att vara:
För att välja talen alfa, beta, gamma, delta måste ett antal villkor uppfyllas för att garantera möjligheten till dataåterställning (det vill säga att lösa ekvationssystemet). Du kan läsa mer om dem i .
Också i praktiken används XOR-operationen för att beräkna lokala redundanskoder P3, P4.
Ett antal slutsatser följer av ekvationssystemet för LRC:
- För att återställa ett 1 datablock räcker det att läsa n/l block (n/2 i vårt exempel).
- Om r + l-block inte är tillgängliga och alla block ingår i en grupp, kan data inte återställas. Detta är lätt att förklara med ett exempel. Låt block X1–X3 och P3 vara otillgängliga: dessa är r + l block från samma grupp, 4 i vårt fall. Sedan har vi ett system med 3 ekvationer med 4 okända som inte går att lösa.
- I alla andra fall av otillgänglighet av r+l-block (när minst ett block är tillgängligt från varje grupp), kan data i LRC återställas.
Således överträffar LRC Reed-Solomon-koder när det gäller att återställa data efter enstaka fel. I Reed-Solomon-koder, för att återställa ens ett datablock, måste du använda n block, och i LRC, för att återställa ett datablock, räcker det att använda n/l block (n/2 i vårt exempel). Å andra sidan är LRC sämre än Reed-Solomon-koder när det gäller det maximala antalet tillåtna fel. I exemplen ovan kan Reed-Solomon-koder återställa data för alla fyra fel, och för LRC finns det två kombinationer av fyra fel när data inte kan återställas.
Vad som är viktigare beror på den specifika situationen, men ofta uppväger besparingarna i överbelastning som LRC ger den något mindre tillförlitliga lagringen.
4. Andra redundanskoder
Förutom Reed-Solomon och LRC-koder finns det många andra redundanskoder. Olika redundanskoder använder olika matematik. Här är några andra redundanskoder:
- Redundanskod med XOR-operatorn. XOR-operationen utförs på n datablock, och 1 block med redundanskoder erhålls, det vill säga ett n+1-schema (n datablock, 1 redundanskod). Använd i , där datablock och redundanskoder skrivs cykliskt till alla diskar i arrayen.
- Jämn-udda algoritm baserad på XOR-operationen. Låter dig bygga 2 block med redundanskoder, det vill säga n+2-schemat.
- STAR-algoritm baserad på XOR-operationen. Låter dig bygga 3 block med redundanskoder, det vill säga n+3-schemat.
- Pyramidkoder är andra redundanskoder från Microsoft.
5. Använd i Yandex
Ett antal Yandex infrastrukturprojekt använder redundanskoder för tillförlitlig datalagring. Här är några exempel:
- MDS intern objektlagring, som jag skrev om i början av artikeln.
- — MapReduce-systemet för Yandex.
- (Yandex DataBase) - newSQL distribuerad databas.
MDS använder LRC redundanskoder, 8-2-2-schema. Data med redundanskoder skrivs till 12 olika diskar på olika servrar i 3 olika DC:er: 4 servrar i varje DC. Läs mer om detta i .
YT använder både Reed-Solomon-koder (schema 6-3), som var de första att implementera, och LRC-redundanskoder (schema 12-2-2), där LRC är den föredragna lagringsmetoden.
YDB använder jämna-udda-baserade redundanskoder (Figur 4-2). Om redundanskoder i YDB redan .
Användningen av olika redundanskodscheman beror på olika krav på system. Till exempel, i MDS, placeras data som lagras med LRC i 3 DC på en gång. Det är viktigt för oss att data förblir tillgänglig för avläsning om 1 av några DC-enheter misslyckas, därför måste blocken fördelas över DCs så att om någon DC är otillgänglig, är antalet otillgängliga block inte mer än tillåtet. I 8-2-2-schemat kan du placera 4 block i varje DC, sedan när någon DC är avstängd kommer 4 block att vara otillgängliga och data kan läsas. Oavsett vilket schema vi väljer när vi placerar det i 3 DC, bör det i alla fall finnas (r + l) / n >= 0,5, det vill säga lagringsredundansen kommer att vara minst 50%.
I YT är situationen annorlunda: varje YT-kluster är helt beläget i 1 DC (olika kluster i olika DC), så det finns ingen sådan begränsning. 12-2-2-schemat ger 33 % redundans, det vill säga att lagra data är billigare, och det kan också överleva upp till 4 samtidiga diskavbrott, precis som MDS-schemat.
Det finns många fler funktioner för användningen av redundanskoder i datalagrings- och bearbetningssystem: nyanser av dataåterställning, återställningens inverkan på frågekörningstiden, funktioner för datainspelning, etc. Jag kommer att prata separat om dessa och andra funktioner av användningen av redundanskoder i praktiken, om ämnet kommer att vara intressant.
6. Länkar
- En serie artiklar om Reed-Solomon-koder och Galois-fält:
De tar en djupare titt på matematik på ett tillgängligt språk. - Artikel från Microsoft om LRC:
Avsnitt 2 förklarar kort teorin och diskuterar sedan erfarenheter av LRC i praktiken. - Jämnt-udda schema:
- STAR-schema:
- Pyramidkoder:
- Redundanskoder i MDS:
- Redundanskoder i YT:
- Redundanskoder i YDB:
Källa: will.com