next up previous
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:

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