Logical view of a Versioning Map-List

2 views
Skip to first unread message

William la Forge

unread,
Mar 4, 2015, 8:45:57 AM3/4/15
to AgileWikiDevelopers
Let us for the moment ignore such issues as dividing structures into blocks, thread safety, lazy deserialization and immutability. At the same time we are ignoring higher-level Rolonic issues like wholeness/partness and structure/stream. Instead we will look at the logical view of a versioning map list.

An entry in a versioning list map has a key, a value, a creation timestamp and a deletion timestamp, where the deletion timestamp has a default value of MAX_VALUE. There is also an order for entries with the same key. Each value in the map list has a key and a list index, where the index is not altered by deletions of other entries. (The index can only be increased when another entry is inserted earlier in the list for a given key.)

For an implementation, we will use an embellishment of AA trees. Each node in the map tree contains a level, a left map node pointer, a right map node pointer, a key and a list node. List nodes are similar, containing a level, a left list node pointer, a right list node pointer, a size, a creation timestamp, a deletion timestamp and a value. Size is the size of the list sub-tree and is set to the size of the left list node + the size of the right list node + 1.

Creation and deletion timestamps apply only to the value of the list node. Searches for a value are always for a given time and a value is considered present only if it has a creation timestamp less than or equal to the query time and a deletion timestamp greater than the query time.

A versioning map list is important enough that we should probably implement it in Java, even without considering things like durability (dividing into blocksk / lazy deserialization), thread safety and immutability.

William la Forge

unread,
Mar 4, 2015, 8:54:39 AM3/4/15
to AgileWikiDevelopers
Hmm. Dividing a list map into blocks is really a scalability issue rather than being purely a durability issue. This is a fascinating topic in its own right which I want to discuss. Perhaps when I need a break from coding up the "simple" versioning map list. :D
Reply all
Reply to author
Forward
0 new messages