算法练习：有版本号的key-value store

feellikelearning June 25, 2021 0 Comments

要求

写一个kv store，需要实现按版本查找的method，简单的每次take新snapshot，就把map复制一次，放到list里面，这样按版本找可以实现O(1)。如果想省空间可以次snapshot只存diff。查的时候要把每个snapshot都查一次，就变成O(num_snapshots)。

Python 实现

class kvstore:
    def __init__(self):
        self.store = {}
        self.snapshots = []
        self.changed_keys = set()

    def set(self, k, v):
        self.store[k] = v
        self.changed_keys.add(k)

    def get(self, k):
        return self.store.get(k, None) 

    def snapshot(self):
        d = {}
        for k in self.changed_keys:
            d[k] = self.store[k]
        self.snapshots.append(d)
        self.changed_keys = set()
        return len(self.snapshots) - 1

    def get_from_snap(self, snap_version, key):
        for version in range(snap_version, -1, -1):
            if key in self.snapshots[version]:
                return self.snapshots[version][key]
        return None

store = kvstore()
store.set("k1",  "v1")
store.set("k2", "v2")

assert store.get("k1") == "v1"

last_snapshot = store.snapshot()
assert last_snapshot == 0
assert store.get("k1") == "v1"
assert store.get_from_snap(last_snapshot, "k1") == "v1"
assert store.get_from_snap(last_snapshot, "k2") == "v2"
assert store.get_from_snap(last_snapshot, "k3") == None

last_snapshot = store.snapshot()
assert last_snapshot == 1
assert store.get("k1") == "v1"
assert store.get_from_snap(last_snapshot, "k1") == "v1"
assert store.get_from_snap(last_snapshot, "k2") == "v2"
assert store.get_from_snap(last_snapshot, "k3") == None

store.set("k3", "v3")
store.set("k2", "k2-1")
last_snapshot = store.snapshot()
assert last_snapshot == 2
assert store.get("k1") == "v1"
assert store.get_from_snap(last_snapshot, "k1") == "v1"
assert store.get_from_snap(last_snapshot, "k2") == "k2-1"
assert store.get_from_snap(last_snapshot, "k3") == "v3"