Werking pariteit

[Spixo]

Ik heb het een en ander opgezocht over de werking van pariteit, ik zal eerst eens hetgene wat ik wil weten vereenvoudigen tot 3 hardeschijven (1,2 en schijf 3 is de pariteits disk).

Ik hanteer de volgende (wiskundige) regels:

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

Dat geeft het volgende:

code:

D1    D2    P1
--------------
1     1     0
1     0     1
0     1     1
0     0     0

Hierbij staan D1, D2 en P1 respectievelijk voor 'disk 1', 'disk 2' en 'pariteits disk 1'.

Mocht nu disk een wegvallen is de data van disk 1 terug te krijgen door D2 en P1 te XOR'en. Dus:

1 XOR 0 = 1 (dus D1)

Tot zover loopt het allemaal goed, nu wil ik het geheel uitbreiden naar een systeem van 3 disks (D1, D2 en D3) en 1 gezamenlijke pariteitsdisk (D1). Waarbij in dit systeem maximaal 1 disk uit kan vallen (RAID 5). Hoe werkt het dan met XOR parity?

[Flotter]

Simple, zorg dat er altijd een even aantal 1-en (of 0-en) is

code:

D1  D2  D3  P
--------------
0   0   0   0
0   0   1   1
0   1   0   1
0   1   1   0
1   0   0   1
1   0   1   0
1   1   0   0
1   1   1   1

oftewel (D1 XOR D2) XOR D3

[edit]
Bij het uitvallen van 1 disk (bijvoorbeeld D1) doe je gewoon (P XOR D2) XOR D3

[ Voor 15% gewijzigd door Flotter op 14-09-2004 17:07 ]

[Homerius]

Ik interpreteer de pariteit altijd als een bitje die aangeeft of het aantal "1"-en even of oneven is. Met behulp van dit bitje kun je dus, als er een bitje verloren is gegaan, altijd reproduceren of dat een 1 of een 0 geweest is.

Voorbeeldje, analoog aan jouw voorbeeld:

0 XOR 0 XOR 0 = 0
0 XOR 0 XOR 1 = 1
etc.

Als ik het uitschrijf naar 3 disks, dan krijg ik het volgende tabelletje:

code:

D1    D2    D3    P
---------------------
0     0     0     0
0     0     1     1
0     1     0     1
0     1     1     0
0     0     0     0
0     0     1     1
0     1     0     1
0     1     1     0

Als bijvoorbeeld disk 1 verloren gaat, disk 2 en 3 bevatten een 1, en de pariteit is 0, dan krijgen we:
1 XOR 1 XOR 0 = 0 (dus D1 = 0)

Eigenlijk werkt het dus precies analoog aan raid met 2 disks en 1 pariteit-disk. Het aantal schijven kun je in principe oneindig uitbreiden, alleen mag er maar 1 tegelijkertijd crashen.

_{Overigens is het werken met 1 pariteits-disk volgens mij raid 3 of raid 4. Met raid 5 is er geen sprake van een specifieke pariteits-disk, maar wordt de pariteit (om performance-redenen) verdeeld over de verschillende schijven}

[Spixo]

Bedankt, met deze informatie kan ik weer even wat verder stoeien

MmmBeer schreef op 14 september 2004 @ 17:06:
_{Overigens is het werken met 1 pariteits-disk volgens mij raid 3 of raid 4. Met raid 5 is er geen sprake van een specifieke pariteits-disk, maar wordt de pariteit (om performance-redenen) verdeeld over de verschillende schijven}

Inderdaad je hebt helemaal gelijk, RAID 5 verdeeld de parity blokken

[Spixo]

Heb er vandaag nog eens naar gekeken, wat nu als 2 hardeschijven uitvallen?

Stel:

We hebben D1 t/m D8, hier staat de data op. En we hebben P1 en P2, dit zijn 2 parity schijven.

P1 doet de parity van D1 t/m D4, P2 doet D5 t/m D8. Dus als D2 en D6 uitvalt is er geen probleem.

Wat nu echter als D7 en D8 uitvalt? Dan heb ik niets aan P1

[Homerius]

Ricardo87 schreef op 15 september 2004 @ 16:27:
Heb er vandaag nog eens naar gekeken, wat nu als 2 hardeschijven uitvallen?

Stel:

We hebben D1 t/m D8, hier staat de data op. En we hebben P1 en P2, dit zijn 2 parity schijven.

P1 doet de parity van D1 t/m D4, P2 doet D5 t/m D8. Dus als D2 en D6 uitvalt is er geen probleem.

Wat nu echter als D7 en D8 uitvalt? Dan heb ik niets aan P1

Tjah, op zo'n manier heb je inderdaad een probleem Wil je 2 (of meer) uitvallende schijven kunnen herstellen met 2 pariteits-schijven, dan moet je een iets andere methode gebruiken. Ik zal later misschien nog een voorbeeldje geven, tenzij iemand me voor is

Voorbeeld :
Met twee pariteits-schijven heb je twee bits beschikbaar om informatie in op te slaan. Hiermee kun je bijvoorbeeld coderen dat het totale aantal 1-tjes op de andere schijven, modulo 4 coderen:

code:

                               codering
Aantal 1-bits    modulo 4     P1      P2
0, 4, 8, ....        0        0        0
1, 5, 9, ....        1        0        1
2, 6, 10, ....       2        1        0
3, 7, 11, ....       3        1        1

Stel, we hebben 15 schijven met 2 pariteit-schijven.

Als dan 1 schijf uitvalt, tellen we het aantal 1-tjes op de resterende schijven (bijvoorbeeld 11), en vervolgens we kijken naar de pariteits-bits (bijvoorbeeld [1,1]).
Uit de pariteit blijkt dat het totaal aantal 1-tjes 3, 7, 11 of 15 (etc.) 1-tjes moet zijn geweest. Op de uitgevallen schijf moet dus een 0 hebben gestaan!

Als er 2 schijven uitvallen, tellen we weer het aantal 1-tjes (bijvoorbeeld 7). Uit de pariteit blijkt dat het er 1, 5, 9 of 13 zijn geweest. Er missen er dus 2. Op beide uitgevallen schijven moeten dus een 1 hebben gestaan.

Het probleem is nu alleen dat er, als er zowel een 1 als een 0 gestaan moet hebben op de uitgevallen schijven, ik niet weet op welke de 0 moet, en op welke de 1 En daar gaan we dus de mist in.... je zult dus iets slimmers moeten verzinnen

En nu weet ik ook waarom ik er zo 123 niet helemaal uitkom... kijk voor de grap eens naar dit documentje

edit:
Niet-werkend voorbeeld toegevoegd

[ Voor 55% gewijzigd door Homerius op 15-09-2004 17:24 . Reden: linkje naar Raid-6 document toegevoegd ]

[Spixo]

MmmBeer schreef op 15 september 2004 @ 16:37:
[...]


Tjah, op zo'n manier heb je inderdaad een probleem Wil je 2 (of meer) uitvallende schijven kunnen herstellen met 2 pariteits-schijven, dan moet je een iets andere methode gebruiken. Ik zal later misschien nog een voorbeeldje geven, tenzij iemand me voor is

Heel graag dan kan ik weer verder me ideeen uitwerken

[Xandrios]

Ricardo87 schreef op 15 september 2004 @ 16:27:
Heb er vandaag nog eens naar gekeken, wat nu als 2 hardeschijven uitvallen?

Stel:

We hebben D1 t/m D8, hier staat de data op. En we hebben P1 en P2, dit zijn 2 parity schijven.

P1 doet de parity van D1 t/m D4, P2 doet D5 t/m D8. Dus als D2 en D6 uitvalt is er geen probleem.

Wat nu echter als D7 en D8 uitvalt? Dan heb ik niets aan P1

Je kunt de P schijven ook weer een extra schijf toekennen, voor Pariteit

Dan heb je dus:

code:

D1  ---|
D2      |
D3      |  P1  --- |
D4  ---|           |
                   |
D5  ---|           |  
D6      |          |
D7      |  P2  --- |
D8  ---|           |
                   | -----P5
D9  ---|           |
D10     |          |
D11     |  P3  --- |
D12 ---|           |
                   |
D13 ---|           |  
D14     |          |
D15    |  P4  ---
D16 ---|

In feite zet je de pariteits schijven weer in 'n array met wederom extra pariteit


_{Ik weet niet of bovenstaande daadwerkelijk bestaat, er zijn vast handigere manieren te bedenken om zulk een aantal schijven te beveiligen}

[ Voor 5% gewijzigd door Xandrios op 15-09-2004 16:51 ]

[Spixo]

Xandrios schreef op 15 september 2004 @ 16:47:
[...]


Je kunt de P schijven ook weer een extra schijf toekennen, voor Pariteit

Dan heb je dus:

code:

D1  ---|
D2      |
D3      |  P1  --- |
D4  ---|           |
                   |
D5  ---|           |  
D6      |          |
D7      |  P2  --- |
D8  ---|           |
                   | -----P5
D9  ---|           |
D10     |          |
D11     |  P3  --- |
D12 ---|           |
                   |
D13 ---|           |  
D14     |          |
D15    |  P4  ---
D16 ---|

In feite zet je de pariteits schijven weer in 'n array met wederom extra pariteit


_{Ik weet niet of bovenstaande daadwerkelijk bestaat, er zijn vast handigere manieren te bedenken om zulk een aantal schijven te beveiligen}

Ik zie het nut van P5 niet omdat ik de pariteit van de D's al weet

[Homerius]

Xandrios schreef op 15 september 2004 @ 16:47:
[...]


Je kunt de P schijven ook weer een extra schijf toekennen, voor Pariteit

Dan heb je dus:

code:

D1  ---|
D2      |
D3      |  P1  --- |
D4  ---|           |
... <snip>

In feite zet je de pariteits schijven weer in 'n array met wederom extra pariteit

Als in dit geval D1 en D2 uitvallen, heb ik toch nog steeds een probleem? Ik heb voor deze 4 schijven nl. maar 1 pariteit-bit beschikbaar... Of kijk ik ergens overheen?

[Xandrios]

ok, ok, ik geef me over

* Xandrios slaps himself

[Spixo]

MmmBeer schreef op 15 september 2004 @ 16:37:
[...]


Tjah, op zo'n manier heb je inderdaad een probleem Wil je 2 (of meer) uitvallende schijven kunnen herstellen met 2 pariteits-schijven, dan moet je een iets andere methode gebruiken. Ik zal later misschien nog een voorbeeldje geven, tenzij iemand me voor is

Voorbeeld :
Met twee pariteits-schijven heb je twee bits beschikbaar om informatie in op te slaan. Hiermee kun je bijvoorbeeld coderen dat het totale aantal 1-tjes op de andere schijven, modulo 4 coderen:

code:

                               codering
Aantal 1-bits    modulo 4     P1      P2
0, 4, 8, ....        0        0        0
1, 5, 9, ....        1        0        1
2, 6, 10, ....       2        1        0
3, 7, 11, ....       3        1        1

Stel, we hebben 15 schijven met 2 pariteit-schijven.

Als dan 1 schijf uitvalt, tellen we het aantal 1-tjes op de resterende schijven (bijvoorbeeld 11), en vervolgens we kijken naar de pariteits-bits (bijvoorbeeld [1,1]).
Uit de pariteit blijkt dat het totaal aantal 1-tjes 3, 7, 11 of 15 (etc.) 1-tjes moet zijn geweest. Op de uitgevallen schijf moet dus een 0 hebben gestaan!

Als er 2 schijven uitvallen, tellen we weer het aantal 1-tjes (bijvoorbeeld 7). Uit de pariteit blijkt dat het er 1, 5, 9 of 13 zijn geweest. Er missen er dus 2. Op beide uitgevallen schijven moeten dus een 1 hebben gestaan.

Het probleem is nu alleen dat er, als er zowel een 1 als een 0 gestaan moet hebben op de uitgevallen schijven, ik niet weet op welke de 0 moet, en op welke de 1 En daar gaan we dus de mist in.... je zult dus iets slimmers moeten verzinnen

En nu weet ik ook waarom ik er zo 123 niet helemaal uitkom... kijk voor de grap eens naar dit documentje

edit:
Niet-werkend voorbeeld toegevoegd

Ik snap helaas niet echt wat je probeer te zeggen

Wel ben ik erachter, mijn methode, 8 datavolumes en 2 parity geeft 16/28 kans op herstel. 12/28 kans op verlies maar bij verlies is de kans nog 1/2 op dat je 1 0 of 0 1 goed gokt

Niemand anders een methode?

[Spixo]

Na een tijd zoeken ben ik erachter gekomen dat RAID 6 ongeveer het principe hanteerd waar ik naartoe probeer te werken. Hieronder even een overzicht:



Ik snap echter niet goed hoe deze pariteit werkt, over wat wordt de pariteit berekend? Kan iemand dit verhelderen?

offtopic:
sorry voor mijn layout verprutsing

[ Voor 9% gewijzigd door Spixo op 15-09-2004 21:10 ]

[Homerius]

Ricardo87 schreef op 15 september 2004 @ 19:44:
[...]

Ik snap helaas niet echt wat je probeer te zeggen

Wel ben ik erachter, mijn methode, 8 datavolumes en 2 parity geeft 16/28 kans op herstel. 12/28 kans op verlies maar bij verlies is de kans nog 1/2 op dat je 1 0 of 0 1 goed gokt

Niemand anders een methode?

Mijn voorbeeld werkt ook niet kwam ik halverwege achter, vandaar dat ik geen zin meer had om 'm verder toe te lichten

En op mijn beurt snap ik niet helemaal hoe je aan die 16/28 en die 12/28 komt. Volgens mij heb je met je methode dataverlies als er 2 disks uit 1 groep uitvallen. Kans daarop is volgens mij 3/7.

edit:
(en dat is natuurlijk hetzelfde als 12/28 )

Ricardo87 schreef op 15 september 2004 @ 21:09:
Na een tijd zoeken ben ik erachter gekomen dat RAID 6 ongeveer het principe hanteerd waar ik naartoe probeer te werken. Hieronder even een overzicht:

Ik snap echter niet goed hoe deze pariteit werkt, over wat wordt de pariteit berekend? Kan iemand dit verhelderen?

De werking van Raid-6 wordt "uitgelegd" in het linkje dat ik in mijn eerdere post gaf.

[ Voor 4% gewijzigd door Homerius op 15-09-2004 21:47 . Reden: Breuken zijn moeilijk! ]

[Luxx]

Wat ik zelf bedacht had is het volgende...

4 dataschijven in 4 blokken per schij verdelen Vervolgens maak je een pariteits bit op iedere kolom, en een op iedere rij.
originele schijf	blok1	blok2	blok3	blok4	pariteit 2
schijf1	1a	2a	3a	4a	pa
schijf2	1b	2b	3b	4b	pb
schijf3	1c	2c	3c	4c	pc
schijf4	1d	2d	3d	4d	pd
pariteit 1	p1	p2	p3	p4

Je hebt nu in het totaal 16 blokken data, en 8 blokken pariteit. Iedere (blok)pariteit bit(s) geeft aan of er een even, of oneven aantal bits in de betreffende rij/kolom zitten.

Vervolgens moet je de 24 blokken op 6 schijven wegschrijven, zodat je bij verlies van 2 willekeurige schijven altijd voldoende overhoudt om ALLES te kunnen terugzetten. Wat ik daarvoor had uitgedacht is het volgende:

wegschijven op 6 schijven
schijf1	1a	2b	3c	4d
schijf2	1b	2c	3d	p4
schijf3	1c	2d	p3	4a
schijf4	1d	p2	3a	4b
schijf5	p1	2a	3b	4c
schijf6	pa	pb	pc	pd

Als je van deze 6 schijven 2 willekeurige weghaalt, kan je altijd alle data nog recoveren. (kijk zelf maar na) Okay, de controller moet een beetje handig zijn in het bedneken van de volgorde van het recoveren, want die is wel belangrijk, maar het kan dus wel.

dit kan dus bij ieder aantal schijven, als je maar de data in net zo veel blokken verdeelt als je dataschijven hebt in het kwadraat. Wel is het met meer schijven nog ingewikkelder. Maar het princiepe is het zelfde. Hoe je dit in or/xor vertaalt, zoek je zelf maar uit hoor.

[ Voor 3% gewijzigd door Luxx op 15-09-2004 21:59 ]

[Spixo]

Luxx schreef op 15 september 2004 @ 21:54:
Wat ik zelf bedacht had is het volgende...
...
Je hebt nu in het totaal 16 blokken data, en 8 blokken pariteit. Iedere (blok)pariteit bit(s) geeft aan of er een even, of oneven aantal bits in de betreffende rij/kolom zitten.

Vervolgens moet je de 24 blokken op 6 schijven wegschrijven, zodat je bij verlies van 2 willekeurige schijven altijd voldoende overhoudt om ALLES te kunnen terugzetten. Wat ik daarvoor had uitgedacht is het volgende:

...

Als je van deze 6 schijven 2 willekeurige weghaalt, kan je altijd alle data nog recoveren. (kijk zelf maar na) Okay, de controller moet een beetje handig zijn in het bedneken van de volgorde van het recoveren, want die is wel belangrijk, maar het kan dus wel.

dit kan dus bij ieder aantal schijven, als je maar de data in net zo veel blokken verdeelt als je dataschijven hebt in het kwadraat. Wel is het met meer schijven nog ingewikkelder. Maar het princiepe is het zelfde. Hoe je dit in or/xor vertaalt, zoek je zelf maar uit hoor.

Bedankt voor de vele moeite zeg, het is een hele hap maar hier kan ik zeker mee verder werken