5.2 Consistency

For sake of customizability and extensibility, the hit-server provides a consistency mechanism from which per-object consistency protocols can be implemented by miss-servers. So policies can be fully customized.

Unlike a hardware bus, a LAN does not enable snooping-based solutions for coherency. Instead, we enable the use of miss-servers as arbiters that can coordinate conflicting accesses to objects that are shared by multiple hit-servers.

The hit-server provides a single basic consistency mechanism: per-object consistency-action matrices. Two status bits are managed per object: accessed is set for any operation, dirty is set when a put operation occurs. The hit-server never resets these bits. The miss-server, however, can arbitrarily change them. Combination of the four states with the two possible operations (get/put) leads to a 2 x 4 consistency-action matrix. Miss-servers specify a consistency action for each of the 8 fields for each object (in an object descriptor's consistency-matrix attribute). Four different consistency actions are available:

Ignore. The get/put operation takes place without involving the miss-server.

Notify. The object's miss-server is notified about the get/put operation. This notification is non-blocking. The miss-server will be informed concurrently to serving the client's request.

Call. The object's miss-server is called before the get/put request is served. The request blocks until the miss-server grants or denies it. In its reply, the miss-server can define new settings for the object's accessed/dirty bits and the consistency-action matrix. Before replying to a call, the miss-server can itself read the object back or update its value. Call-associated actions are completely controlled by the corresponding miss-server, and have a higher latency than ignore-associated and notify-associated actions.

Propagate. Any put operation is directly propagated to the corresponding miss-server (put-through). The data received from the client is sent to the miss-server and concurrently used for updating the object in the hit-server. Receive and propagate activities are pipelined; however, the client is not acknowledged until the miss-server commits or aborts the operation. Prior to handling a client's get request, the hit-server itself ``gets'' the newest version of the object from the corresponding miss-server (get-through). (Get requests include no data transfer if the requestor already holds the current object version.) To minimize the latency, receiving the new object data from the miss-server and propagating it to the client overlap in time.

The consistency-action matrix is a generic mechanism that can be used to implement a variety of different cache-consistency protocols and also cache-replacement protocols.

For a simple write-through policy, (i,i,i,i/p,p,p,p)⁴ could be used: get operations on this object do not involve the miss-server whereas any put operation is directly propagated. For implementing write-back together with LRU replacement, the miss-server can use (n,i,n,i/n,n,n,i) . Then the miss-server is notified (a) when the object is accessed the first time (read or write) and (b) when the object becomes dirty (first write). Subsequent accesses do not involve miss-server notification. For LRU bookeeping, the miss-server will periodically reset all objects to unaccessed that have been accessed in the meantime. New accesses are then signaled (once per period) to the miss server. Inactive objects do not incur bookeeping overhead since there is no need for the miss-server to scan them periodically.

For consistency in a multi-hit-server system with write-shared objects, a MESI-like policy can be used:

(i,i,i,i/i,i,i,i) for M or E objects,

(i,i,i,i/c,c,c,c) for S objects,

(c,c,c,c/c,c,c,c) for I objects.

Modified (M) and exclusive (E) objects reside only in one hit-server. Clean objects are called E, dirty ones are called M. Accessing an M or E object does not involve miss-server activity. Shared (S) objects can reside in multiple hit-servers: gets happen without involving the miss-server whereas puts invoke a call consistency action. As a result of the call, the miss-server can invalidate the replicas of the according object in all other hit servers by changing their respective consistency-action matrices or even by removing them completely. For classical MESI, the miss-server will afterwards change the original object's consistency-action matrix to the M state and permit the put operation. Invalid (I) objects call the miss-server for any access so that this one could update the object replica and permit the access or simply delay it by delaying its reply.

⁴ We denote a consistency-action matrix by (get-clean-unacc, get-clean-acc, get-dirty-unacc, get-dirty-acc / put-clean-unacc, put-clean-acc, put-dirty-unacc, put-dirty-acc), where the first four entries specify the actions for get operations, the second row for put operations. Consistency actions are qualified by their first letter, i, n, c, and p.