How does parity actually work?


guitarlp

Recommended Posts

I understand RAID1 with mirroring... I understand RAID0 with stripping. I also get how RAID 5, 6, and 10 work.

 

But I'm not fully understanding how the unRAID parity drive works. Any hard drive can be removed from the unRAID server and the files on it viewed in Linux (or windows if the correct driver is installed). This means data isn't being striped across all the hard drives (right?).

 

So... how does 1 parity drive hold all the data of 15 hard drives? Does it compress the data to fit onto the drive (this would explain why writing with Parity enabled is so slow)? How exactly does parity work at backing up every hard drive?

Link to comment

Think "raid 4" without striping.

 

http://en.wikipedia.org/wiki/Standard_RAID_levels#RAID_4

There's a section here in regards to raid5 parity that may also help.

 

and a section here on Parity

http://www.pcguide.com/ref/hdd/perf/raid/concepts/gen_Parity.htm

 

Allot is based on the use of XOR with all of the matching blocks in an array

"the interesting thing about "XOR" is that it is a logical operation that if performed twice in a row, "undoes itself".

 

So if each matching block across multple disks is XOR'ed a parity value is created.

If a drive fails and you XOR each surviving piece of a block, you will be left with the missing block.

This is how you survive a single disk failure. and why you can loose data on a multiple drive failure.

Because unRAID uses single drives as a filesystem without striping, you will only loose the failed drives on a multple drive failure.

Link to comment

Pretty cool actually... thanks for the info :)

 

Is there an actual limit to the size and/or drives that can run off a parity disk? I know unRAID has it's own limit of 15... but there must be a limit at one point where no more drives can be added to parity right?

Link to comment

actually no

 

again, search google and read the math behind it

 

if you have a single bit of data, spanning let say in 3000 disks and there was a way to construct parity info based on those 3000 disks (quickly enough to have a point), then changing a single bit of this "3000 disk bit slice", will change the parity, thus it works

 

the whole point of parity is this though (to be reliable):

 

- parity IS valid at the point in time where the failure happens (so there needs to be a mechanism to revalidate parity with EVERY transaction)

 

- parity only protects a SINGLE failure (because the whole point of parity is to use... erm... parity + ALL the other data of the same "slice" to reconstruct the missing information)

 

I am sure you can find much cleaner explanations in google and wiki

 

 

Link to comment

My simple minded view of parity is that parity is always trying to make sure that the SUM of all the corresponding bits is EVEN (called EVEN parity) or ODD (called ODD parity).  (unRAID uses EVEN parity.) 

 

- If you have 4 drives with bit values 1,1,1,1 the parity will be 0 (1+1+1+1+0=even). 

- If the bit values are 1,0,0,0 the parity will be 1 (1+0+0+0+1=even).

 

The sum of the bits is always even.  With this information, you can reconstruct any ONE missing piece of data (the parity or a data disk), as long as you know the other pieces are correct. 

 

In the two examples above, say the 2nd drive fails. 

 

- 1+x+1+1+0=even, x must equal 1

- 1+x+0+0+1=even, x must equal 0

 

Of course the implementation is with extremely efficient XOR operations, but conceptually this is what is happening.

 

This calculation is done billions or trillions of times (depending on the size of your parity disk), once for each bit position.  (For a 1 TB parity drive, this calculation is done 8 trillion times)

 

So what happens when one disk is bigger than the others?  unRAID will substitute a 0 value for all bits above a disk's capacity, so unRAID can continue to compute parity to the size of the parity drive.

 

The answer to the question "is there a limit" becomes clear.  Theoretically, if you had 10, 100, 1000, or 1,000,000,000 drives you could still compute parity, it would just take longer.  But the chances of simultaneous failure increases, so that as the number of drives increases, the reliability of the array decreases.  unRAID has a somewhat arbitrary limit of 15 drives + parity.  This could (probably) easily be increased if Tom wanted to.  But Linux and the PC hardware have limits as well.  There have been a few threads on this topic, and most believe that somewhere between 20 and 30 is the max number of drives that could (should) be practically connected to a single array.

 

  • Like 1
Link to comment
There have been a few threads on this topic, and most believe that somewhere between 20 and 30 is the max number of drives that could (should) be practically connected to a single array.

 

From what I can gather regarding the Devices.txt file and various text on the net there are conflicting values as to max disks. (or it is old information).

 

From what I gathered by looking in the devices.txt file you can have 16-32 scsi devices.

Major Device Node 8 block  SCSI disk devices (0-15) with up to 15 partitions.

Minor nodes range from 0,16,32,

and Major Device node 65  SCSI disk devices (16-31) with up to 15 partitions.

 

By looking in the /dev directory you can have 20 IDE Devices.

 

The md (meta Disk) major nodes(#9) allow for many drives.

by default I think this is configured for 32 in a normal environment and 16 (15+1) in unRAID.

 

 

Snippets from devices.txt

 

3 block   First MFM, RLL and IDE hard disk/CD-ROM interface
          0 = /dev/hda      Master: whole disk (or CD-ROM)
         64 = /dev/hdb      Slave: whole disk (or CD-ROM)

        For partitions, add to the whole disk device number:
          0 = /dev/hd?      Whole disk
          1 = /dev/hd?1     First partition
          2 = /dev/hd?2     Second partition
            ...
         63 = /dev/hd?63    63rd partition

        For Linux/i386, partitions 1-4 are the primary
        partitions, and 5 and above are logical partitions.
        Other versions of Linux use partitioning schemes
        appropriate to their respective architectures.
---
  9 block   Metadisk (RAID) devices
          0 = /dev/md0      First metadisk group
          1 = /dev/md1      Second metadisk group
            ...

        The metadisk driver is used to span a
        filesystem across multiple physical disks.
---
  8 block   SCSI disk devices (0-15)
          0 = /dev/sda      First SCSI disk whole disk
         16 = /dev/sdb      Second SCSI disk whole disk
         32 = /dev/sdc      Third SCSI disk whole disk
            ...
        240 = /dev/sdp      Sixteenth SCSI disk whole disk

        Partitions are handled in the same way as for IDE
        disks (see major number 3) except that the limit on
        partitions is 15.


33  block       Third IDE hard disk/CD-ROM interface
                  0 = /dev/hde          Master: whole disk (or CD-ROM)
                 64 = /dev/hdf          Slave: whole disk (or CD-ROM)

                Partitions are handled the same way as for the first
                interface (see major number 3).

(There are more I left them out)


65   block       SCSI disk devices (16-31)
                  0 = /dev/sdq          16th SCSI disk whole disk
                 16 = /dev/sdr          17th SCSI disk whole disk
                 32 = /dev/sds          18th SCSI disk whole disk
                    ...
                240 = /dev/sdaf         32nd SCSI disk whole disk

                Partitions are handled in the same way as for IDE
                disks (see major number 3) except that the limit on
                partitions is 15.

[/quote]


ls -l on my /dev directory from a 2.4 kernel. 

[quote]
IDE 

rcotrone@gatekeeper: /dev > ls -l hd[a-z] 
brw-rw----    1 root     disk       3,   0 Apr 11  2002 hda
brw-rw----    1 root     disk       3,  64 Apr 11  2002 hdb
brw-------    1 rcotrone disk      22,   0 Apr 11  2002 hdc
brw-rw----    1 root     disk      22,  64 Apr 11  2002 hdd
brw-rw----    1 root     disk      33,   0 Apr 11  2002 hde
brw-rw----    1 root     disk      33,  64 Apr 11  2002 hdf
brw-rw----    1 root     disk      34,   0 Apr 11  2002 hdg
brw-rw----    1 root     disk      34,  64 Apr 11  2002 hdh
brw-rw----    1 root     disk      56,   0 Apr 11  2002 hdi
brw-rw----    1 root     disk      56,  64 Apr 11  2002 hdj
brw-rw----    1 root     disk      57,   0 Apr 11  2002 hdk
brw-rw----    1 root     disk      57,  64 Apr 11  2002 hdl
brw-rw----    1 root     disk      88,   0 Apr 11  2002 hdm
brw-rw----    1 root     disk      88,  64 Apr 11  2002 hdn
brw-rw----    1 root     disk      89,   0 Apr 11  2002 hdo
brw-rw----    1 root     disk      89,  64 Apr 11  2002 hdp
brw-rw----    1 root     disk      90,   0 Apr 11  2002 hdq
brw-rw----    1 root     disk      90,  64 Apr 11  2002 hdr
brw-rw----    1 root     disk      91,   0 Apr 11  2002 hds
brw-rw----    1 root     disk      91,  64 Apr 11  2002 hdt

SCSI

rcotrone@gatekeeper: /dev > ls -l sd[a-z] 
brw-rw----    1 root     disk       8,   0 Apr 11  2002 sda
brw-rw----    1 root     disk       8,  16 Apr 11  2002 sdb
brw-rw----    1 root     disk       8,  32 Apr 11  2002 sdc
brw-rw----    1 root     disk       8,  48 Apr 11  2002 sdd
brw-rw----    1 root     disk       8,  64 Apr 11  2002 sde
brw-rw----    1 root     disk       8,  80 Apr 11  2002 sdf
brw-rw----    1 root     disk       8,  96 Apr 11  2002 sdg
brw-rw----    1 root     disk       8, 112 Apr 11  2002 sdh
brw-rw----    1 root     disk       8, 128 Apr 11  2002 sdi
brw-rw----    1 root     disk       8, 144 Apr 11  2002 sdj
brw-rw----    1 root     disk       8, 160 Apr 11  2002 sdk
brw-rw----    1 root     disk       8, 176 Apr 11  2002 sdl
brw-rw----    1 root     disk       8, 192 Apr 11  2002 sdm
brw-rw----    1 root     disk       8, 208 Apr 11  2002 sdn
brw-rw----    1 root     disk       8, 224 Apr 11  2002 sdo
brw-rw----    1 root     disk       8, 240 Apr 11  2002 sdp
brw-rw----    1 root     disk      65,   0 Apr 11  2002 sdq
brw-rw----    1 root     disk      65,  16 Apr 11  2002 sdr
brw-rw----    1 root     disk      65,  32 Apr 11  2002 sds
brw-rw----    1 root     disk      65,  48 Apr 11  2002 sdt
brw-rw----    1 root     disk      65,  64 Apr 11  2002 sdu
brw-rw----    1 root     disk      65,  80 Apr 11  2002 sdv
brw-rw----    1 root     disk      65,  96 Apr 11  2002 sdw
brw-rw----    1 root     disk      65, 112 Apr 11  2002 sdx
brw-rw----    1 root     disk      65, 128 Apr 11  2002 sdy
brw-rw----    1 root     disk      65, 144 Apr 11  2002 sdz

[/quote]

Link to comment

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.