An algorithm for stabilising multiple stores

The algorithm for stabilising multiple stores, which we present in this paper, was developed in the process of designing the global stability and resilience mechanism for Grasshopper, an operating system explicitly designed for experimentation in persistence. Grasshopper's persistent store is divided into multiple logical partitions (local stores) with arbitrary data interdependencies. A global asynchronous checkpoint mechanism is used to ensure the resilience of the store as a whole. In order to eliminate the known deficiencies of such an approach our algorithm takes advantage of the hardware techniques originally developed for fault tolerant systems, ie. mirrored disks and an uninterruptible power source (UPS). We show that these two techniques complement each other resulting in a simple and efficient algorithm where the main cost is the cost of additional hardware. Although developed in the context of the Grasshopper system, the algorithm can be applied to multiple persistent stores in general.