Negative assertion cache

Cache design decisions

Shards and Zones over which the server has authority are only removed when they expire. All other shards and zones are subject to a least recently used policy.
Expired but not yet reaped shards and zones are also returned such that the caller can decide how he wants to handle them. e.g. when a query has option 5 (expired assertions are acceptable) set.

Negative assertion requirements

cache has a maximum size which is configurable (to avoid memory exhaustion of the server in case of an attack). It is not fix size to reduce the number of comparisons needed for checking that a new shard or zone is consistent with all already cached entries.
In case the cache is full the least recently used shard or zone over which the server has no authority is removed from the cache. In case the authoritative shards and zones fill up the cache an error msg must be logged such that an operator can change the configuration.
it must provide an insertion function which stores a shard or zone together with an expiration time to the cache (expiration time is necessary as we might want to store them for a shorter amount of time as they are valid. It is not possible to change the value directly as it is protected by the signature). The shard or zone must also be added to the consistency cache.
it must provide fast lookup of a set of shards and zones based on a subjectZone (if any context is allowed) or a subjectZone and context. A set of all intervals containing the subjectZone is returned such that the calling function can decide which entry it wants to send back according to a policy.
it must provide a reap function that removes expired entries. This function must also remove the corresponding element in the consistency cache.
it must provide a removal function which removes all assertions of a specific zone in case this zone misbehaved or sent inconsistent messages.
all cache operations must be safe for concurrent access

Negative assertion implementation

lru strategy is implemented as a linked list where pointers to the head and tail of the list are accessible.
on insertion or lookup of an entry it is moved to the head of the list
in case the cache is full the shard or zone at the tail of the list is removed.
to allow fast lookup two hash maps and segment trees are used. Segment trees can efficiently return all intervals stored in the tree which contain a query point. The first hashmap is keyed by a zone. The value is a pointer to the second hashmap which is keyed by the context. The value points to a segment tree data structure. A stored interval in the tree is a lru list node where the interval of the list node is inherited from the contained shard or zone.
a list node contains a set (safe for concurrent accesses) of objects containing a shard or zone with an expiration time. Each object in the set must have the same subjectZone, context and interval.
sections over which this server has authority are not subject to lru removal.