delta-dictionary/dictionary with revision awareness in python?

Question

I am looking to create a dictionary with 'roll-back' capabilities in python. The dictionary would start with a revision number of 0, and the revision would be bumped up only by explicit method call. I do not need to delete keys, only add and update key,value pairs, and then roll back. I will never need to 'roll forward', that is, when rolling the dictionary back, all the newer revisions can be discarded, and I can start re-reving up again. thus I want behaviour like:

>>> rr = rev_dictionary()
>>> rr.rev
0
>>> rr["a"] = 17
>>> rr[('b',23)] = 'foo'
>>> rr["a"]
17
>>> rr.rev
0
>>> rr.roll_rev()
>>> rr.rev
1
>>> rr["a"]
17
>>> rr["a"] = 0
>>> rr["a"]
0
>>> rr[('b',23)]
'foo'
>>> rr.roll_to(0)
>>> rr.rev
0
>>> rr["a"]
17
>>> rr.roll_to(1)
Exception ... 

Just to be clear, the state associated with a revision is the state of the dictionary just prior to the roll_rev() method call. thus if I can alter the value associated with a key several times 'within' a revision, and only have the last one remembered.

I would like a fairly memory-efficient implementation of this: the memory usage should be proportional to the deltas. Thus simply having a list of copies of the dictionary will not scale for my problem. One should assume the keys are in the tens of thousands, and the revisions are in the hundreds of thousands.

We can assume the values are immutable, but need not be numeric. For the case where the values are e.g. integers, there is a fairly straightforward implementation (have a list of dictionaries of the numerical delta from revision to revision). I am not sure how to turn this into the general form. Maybe bootstrap the integer version and add on an array of values?

all help appreciated.

Answer 1

Have just one dictionary, mapping from the key to a list of (revision_number, actual_value) tuples. Current value is the_dict[akey][-1][1]. Rollback merely involves popping the appropriate entries off the end of each list.

Update: examples of rollback

key1 -> [(10, 'v1-10'), (20, 'v1-20')]

Scenario 1: current revision is 30, rollback to 25: nothing happens

Scenario 2: current 30, back to 15: pop last entry

Scenario 3: current 30, back to 5: pop both entries

Update 2: faster rollback (with trade-offs)

I think your concern about popping every list is better expressed as "needs to examine every list to see if it needs popping". With a fancier data structure (more memory, more time to maintain the fancy bits in add and update operations) you can reduce the time to roll back.

Add an array (indexed by revision number) whose values are lists of the dictionary values that were changed in that revision.

# Original rollback code:
for rlist in the_dict.itervalues():
    if not rlist: continue
    while rlist[-1][0] > target_revno:
        rlist.pop()

# New rollback code
for revno in xrange(current_revno, target_revno, -1):
    for rlist in delta_index[revno]:
        assert rlist[-1][0] == revno
        del rlist[-1] # faster than rlist.pop()    
del delta_index[target_revno+1:]

Update 3: full code for fancier method

import collections

class RevDict(collections.MutableMapping):

    def __init__(self):
        self.current_revno = 0
        self.dict = {}
        self.delta_index = [[]]

    def __setitem__(self, key, value):
        if key in self.dict:
            rlist = self.dict[key]
            last_revno = rlist[-1][0]
            rtup = (self.current_revno, value)
            if last_revno == self.current_revno:
                rlist[-1] = rtup
                # delta_index already has an entry for this rlist
            else:
                rlist.append(rtup)
                self.delta_index[self.current_revno].append(rlist)
        else:
            rlist = [(self.current_revno, value)]
            self.dict[key] = rlist
            self.delta_index[self.current_revno].append(rlist)

    def __getitem__(self, key):
        if not key in self.dict:
            raise KeyError(key)
        return self.dict[key][-1][1]

    def new_revision(self):
        self.current_revno += 1
        self.delta_index.append([])

    def roll_back(self, target_revno):
        assert 0 <= target_revno < self.current_revno
        for revno in xrange(self.current_revno, target_revno, -1):
            for rlist in self.delta_index[revno]:
                assert rlist[-1][0] == revno
                del rlist[-1]
        del self.delta_index[target_revno+1:]
        self.current_revno = target_revno

    def __delitem__(self, key):
        raise TypeError("RevDict doesn't do del")

    def keys(self):
        return self.dict.keys()

    def __contains__(self, key):
        return key in self.dict

    def iteritems(self):
        for key, rlist in self.dict.iteritems():
            yield key, rlist[-1][1]

    def __len__(self):
        return len(self.dict)

    def __iter__(self):
        return self.dict.iterkeys()

Answer 2

The deluxe solution would be to use B+Trees with copy-on-write. I used a variation on B+Trees to implement my blist data type (which can be used to very efficiently create revisions of lists, exactly analogous to your problem).

The general idea is to store the data in a balanced tree. When you create a new revision, you copy only the root node. If you need to modify a node shared with an older revision, you copy the node and modify the copy instead. That way, the old tree is still completely intact, but you only need memory for the changes (technically, O(k * log n) where k is the number of changes and n is the total number of items).

It's non-trivial to implement, though.