25 Eviction of DGS nodes

LRU eviction

To the extent that a single eviction queue holds a very large number of DGS nodes, it can be seen as providing a somewhat "global" LRU eviction system for its DGS nodes.

A node has a bit flag DF_IN_EVICTION_QUEUE for whether it has already been inserted into the eviction queue. This allows it to be inserted automatically by the read barrier.

DGS nodes don't self-destruct

Nodes in the eviction queue can be clean or soft-dirty or hard-dirty, and they may or may not have any in-nodes or out-nodes. DGS nodes never "self destruct" (such as because they are hard-dirty and have no out-nodes). Rather, nodes must be evicted by the eviction system according to the LRU policy. This is simpler than trying to make nodes automatically self destruct when they are no longer used in the dependency graph.

In fact automatic self destruction is inefficient:

  • The cxPersistStore Resident Object Table (ROT) uses a map from OID to independent DGS node to support async binding of OIDs. Consider that an independent node removes itself from the map when it has no out-nodes. That will tend to happen very often because any dependent that becomes hard-dirty immediately detaches all its inputs. That would be bad for the ROT because an async bind would often start and then be cancelled a moment later just because the dependent that had prompted the async bind became hard-dirty (perhaps because some other input changed).
  • In a similar manner the fields of models are also associated with indep nodes in a map (currently called DGActiveIndepNodeMap), and with automatic self destruction there will be continual inserts/erases in the map, making it quite inefficient (mutations - i.e. insert/erase is relatively slow in a map because of all the re-balancing etc).

Avoiding self-destruction means $cache functions can always return a reference to a value cached in a map without fear of it being removed by the read barrier

Eviction of a DGS node

When the evictor wants to evict a node it calls the virtual method EnsureNoInnodesOrOutnodes() on the node. This invalidates the out-nodes (making them hard-dirty) so they detach. If it's a dependent node then it marks the node as hard-dirty to make it detach from its in-nodes. 


    virtual void EnsureNoInnodesOrOutnodes() const = 0;

This is well suited to $cache functions where the nodes are in maps. The associated map element is deleted when the node is evicted by the eviction system.