Directory-based coherence

Directory-based coherence is a mechanism to handle Cache coherence problem in Distributed shared memory (DSM) a.k.a. Non-Uniform Memory Access (NUMA). Another popular way is to use a special type of computer bus between all the nodes as a "shared bus" (a.k.a. System bus). Directory-based coherence uses a special directory to serve instead of the shared bus in the bus-based coherence protocols. Both of these designs use the corresponding medium (i.e. directory or bus) as tool to facilitate the communication between different nodes, and to guarantee that the coherence protocol is working properly along all the communicating nodes. In directory based cache coherence, this is done by using this directory to keep track of the status of all cache blocks, the status of each block includes in which cache coherence "state" that block is, and which nodes are sharing that block at that time, which can be used to eliminate the need to broadcast all the signals to all nodes, and only send it to the nodes that are interested in this single block.
Following are a few advantages and disadvantages of the directory based cache coherence protocol:
According to the above discussion, it is clear that using bus based systems seems more attractive for relatively small systems. However, directory based systems become crucial when the system scale up and the number of nodes grows. So there is a kind of trade-off between the simplicity and the scalability when comparing between Bus-based and Directory-based cache coherence designs.
History.
The idea of Directory-based cache coherence systems began long ago. The idea of DASH (Directory Architecture for SHared-memory) was first proposed by C.K. Tang in the mid 1970s. However, applying it to cache coherence was proposed a few years later, specifically in 1978, when researchers at Stanford university proposed the first version of this coherence systems called Stanford DASH, in a paper that described the system with the difficulties and improvements associated with such designs. Beside this approach, several attempts were done to provide a scalable systems. For instance, BBN Butterfly which was introduced in 1985, and IBM PR3 which was introduced in 1987, are some examples of scalable multiprocessor systems. However, both of these systems have a drawback; For example, BBN Butterfly does not have caches. Similarly, IBM PR3 does not provide hardware cache coherence, which limits the performance of both of these designs, especially when employing high performance processors.
The limitations of other competitors made it easier for DASH based systems to get chosen when designing cache coherence systems and other systems needing scalability in cache-based nodes. In 1985, James Archibald and Jean-Loup Baer from the University of Washington published a paper that proposes a more economical, expandable, and modular variation of the "global directory" approach in the term of hardware use in the design.
In 1992, Daniel Lenoski from Stanford university published a paper proposing advances in cache coherence protocols for directory-based systems. In a 1996 paper, he introduced the design of the SGI Origin 2000, a family of server computers employing directory based cache coherence. The subsequent Origin 3000 was introduced in July 2000.
Protocols.
Unlike snoopy coherence protocols, in a directory based coherence approach, the information about which caches have a copy of a block is maintained in a structure called "Directory". In a directory based scheme, participating caches do not broadcast requests to all other sharing caches of the block in order to locate cached copies, instead it queries the directory to retrieve the information about which block have cached copies and sends only to those particular processors and hence traffic saving compared to a snoopy protocol is large. In well optimized applications, most data sharing is only for data that is read only, and there is little sharing for data that is frequently read and written. A directory approach can result in a substantial traffic saving compared to broadcast/snoopy approach in such applications.
As shown in the data flow diagram, the actors involved in a distributed shared memory system implementing directory based coherence protocol are:
Requestor and Owner nodes maintain their state transition similar to a snoopy coherence protocols like MESI protocol. However, unlike a bus based implementation where nodes communicate using a common bus, directory based implementation uses message passing model to exchange information required for maintaining cache coherence.
Directory node acts as a serializing point and all communications are directed through this node to maintain correctness.
Directory Node.
A directory node keeps track of the overall state of a cache block in the entire cache system for all processors. It can be in three states :
Explanation of the Directory state transition Finite State Machine (refer image 1) is captured below in the table:
In addition to cache state, a directory must track which processors have data when in the shared state. This is required for sending invalidation and intervention requests to the individual processor caches which have the cache block in shared state. Few of the popular implementation approaches are: 
Please note that the protocol described above is the basic implementation and race conditions can occur due to the fact that directory can be out of sync with the caches and also messages between processors can be overlapping. More complex implementations are available like Scalable Coherent Interface which have multiple states.
DASH cache coherence protocol is another protocol that uses directory-based coherence scheme. DASH protocol uses a clustered approach, where processors inside a cluster are kept coherent using bus based snooping scheme, while the clusters are connected in a directory approach. Even though various protocols use different implementations for tracking cache blocks, however the concept of directory remains same.