Next: Parity Caching
To reduce the main memory waste caused by mirroring,
we can use parity-based redundancy schemes much
like the ones used in RAIDS . 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
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:
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 ().
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.
Fri Mar 24 14:41:51 EET 1995