Fragment Reconstruction: A New Cache Coherence Scheme for Split Caching Storage Systems (Looking at the Doughnut and not the Hole)

Fragment reconstruction is cache coherence protocol for transactional storage systems based on global caching in a network of workstations. It supports fine-grained sharing and works in the presence of object-based concurrency  control algorithm. When transactions commit new versions of objects, stale cached copies of these objects get invalidated. Therefore, pages in a clients cache may become fragments, i.e. contain “holes” corresponding to invalid objects. when such a page is used in the global cache, the coherence protocol fills in the holes using modifications stored in a recoverable cache at the server.

Fragment reconstruction is the first coherence protocol that supports fine-grained sharing and global caching in transactional storage systems. Because it is integrated with the recoverable modification cache, it works correctly even in the presence of client failures, and can take advantage of lazy update propagation and update absorption, which is beneficial when pages are updated repeatedly. This paper describes the fragment reconstruction protocol and presents its correctness invariant which insures that only correctly reconstructed fragments are propagated to database.