Next: Parity Caching
Up: Reliability
Previous: Mirroring
To reduce the main memory waste caused by mirroring,
we can use parity-based redundancy schemes much
like the ones used in RAIDS [13]. Suppose, for example,
that we have S servers, each having P pages. Page
is the 
page that resides on server i.
Assume, that we have P parity pages, where parity page j is formed
by taking the XOR of all the 
pages in all servers.
We say that all these 
pages belong to the same
parity group.
If a server crashes, all its pages can be restored
by XORing all pages within each parity group.
When the client swaps out a page
it has to update the parity to reflect the
change. This update is done in two steps:
-
The client sends the swapped out page to the server, which
computes the XOR of the old and the new page.
-
The server sends the just computed XOR to the parity server,
which XORs it with the old parity, forming the new parity.
Unfortunately, this method involves two page transfers:
one from client to server, and one from server to parity.
Moreover, the client should not discard the page
just swapped out, because the server may crash
before the new parity is computed, thus, making it impossible
to restore the swapped out page.
This parity method increases the amount of
remote main memory only by a factor of (
).
Evangelos Markatos
Fri Mar 24 14:41:51 EET 1995