diff options
Diffstat (limited to 'synapse/util/caches')
| -rw-r--r-- | synapse/util/caches/descriptors.py | 11 | ||||
| -rw-r--r-- | synapse/util/caches/dictionary_cache.py | 10 | ||||
| -rw-r--r-- | synapse/util/caches/lrucache.py | 43 | ||||
| -rw-r--r-- | synapse/util/caches/treecache.py | 52 |
4 files changed, 102 insertions, 14 deletions
diff --git a/synapse/util/caches/descriptors.py b/synapse/util/caches/descriptors.py index 0033051849..af7bf15500 100644 --- a/synapse/util/caches/descriptors.py +++ b/synapse/util/caches/descriptors.py @@ -38,7 +38,7 @@ class Cache(object): def __init__(self, name, max_entries=1000, keylen=1, lru=True): if lru: - self.cache = LruCache(max_size=max_entries) + self.cache = LruCache(max_size=max_entries, keylen=keylen) self.max_entries = None else: self.cache = OrderedDict() @@ -99,6 +99,15 @@ class Cache(object): self.sequence += 1 self.cache.pop(key, None) + def invalidate_many(self, key): + self.check_thread() + if not isinstance(key, tuple): + raise TypeError( + "The cache key must be a tuple not %r" % (type(key),) + ) + self.sequence += 1 + self.cache.del_multi(key) + def invalidate_all(self): self.check_thread() self.sequence += 1 diff --git a/synapse/util/caches/dictionary_cache.py b/synapse/util/caches/dictionary_cache.py index f92d80542b..b7964467eb 100644 --- a/synapse/util/caches/dictionary_cache.py +++ b/synapse/util/caches/dictionary_cache.py @@ -32,7 +32,7 @@ class DictionaryCache(object): """ def __init__(self, name, max_entries=1000): - self.cache = LruCache(max_size=max_entries) + self.cache = LruCache(max_size=max_entries, keylen=1) self.name = name self.sequence = 0 @@ -56,7 +56,7 @@ class DictionaryCache(object): ) def get(self, key, dict_keys=None): - entry = self.cache.get(key, self.sentinel) + entry = self.cache.get((key,), self.sentinel) if entry is not self.sentinel: cache_counter.inc_hits(self.name) @@ -78,7 +78,7 @@ class DictionaryCache(object): # Increment the sequence number so that any SELECT statements that # raced with the INSERT don't update the cache (SYN-369) self.sequence += 1 - self.cache.pop(key, None) + self.cache.pop((key,), None) def invalidate_all(self): self.check_thread() @@ -96,8 +96,8 @@ class DictionaryCache(object): self._update_or_insert(key, value) def _update_or_insert(self, key, value): - entry = self.cache.setdefault(key, DictionaryEntry(False, {})) + entry = self.cache.setdefault((key,), DictionaryEntry(False, {})) entry.value.update(value) def _insert(self, key, value): - self.cache[key] = DictionaryEntry(True, value) + self.cache[(key,)] = DictionaryEntry(True, value) diff --git a/synapse/util/caches/lrucache.py b/synapse/util/caches/lrucache.py index 0122b0bb3f..0feceb298a 100644 --- a/synapse/util/caches/lrucache.py +++ b/synapse/util/caches/lrucache.py @@ -17,11 +17,23 @@ from functools import wraps import threading +from synapse.util.caches.treecache import TreeCache + + +def enumerate_leaves(node, depth): + if depth == 0: + yield node + else: + for n in node.values(): + for m in enumerate_leaves(n, depth - 1): + yield m + class LruCache(object): """Least-recently-used cache.""" - def __init__(self, max_size): - cache = {} + def __init__(self, max_size, keylen): + cache = TreeCache() + self.size = 0 list_root = [] list_root[:] = [list_root, list_root, None, None] @@ -44,6 +56,7 @@ class LruCache(object): prev_node[NEXT] = node next_node[PREV] = node cache[key] = node + self.size += 1 def move_node_to_front(node): prev_node = node[PREV] @@ -62,7 +75,7 @@ class LruCache(object): next_node = node[NEXT] prev_node[NEXT] = next_node next_node[PREV] = prev_node - cache.pop(node[KEY], None) + self.size -= 1 @synchronized def cache_get(key, default=None): @@ -81,8 +94,10 @@ class LruCache(object): node[VALUE] = value else: add_node(key, value) - if len(cache) > max_size: - delete_node(list_root[PREV]) + if self.size > max_size: + todelete = list_root[PREV] + delete_node(todelete) + cache.pop(todelete[KEY], None) @synchronized def cache_set_default(key, value): @@ -91,8 +106,10 @@ class LruCache(object): return node[VALUE] else: add_node(key, value) - if len(cache) > max_size: - delete_node(list_root[PREV]) + if self.size > max_size: + todelete = list_root[PREV] + delete_node(todelete) + cache.pop(todelete[KEY], None) return value @synchronized @@ -100,11 +117,20 @@ class LruCache(object): node = cache.get(key, None) if node: delete_node(node) + cache.pop(node[KEY], None) return node[VALUE] else: return default @synchronized + def cache_del_multi(key): + popped = cache.pop(key) + if popped is None: + return + for leaf in enumerate_leaves(popped, keylen - len(key)): + delete_node(leaf) + + @synchronized def cache_clear(): list_root[NEXT] = list_root list_root[PREV] = list_root @@ -112,7 +138,7 @@ class LruCache(object): @synchronized def cache_len(): - return len(cache) + return self.size @synchronized def cache_contains(key): @@ -123,6 +149,7 @@ class LruCache(object): self.set = cache_set self.setdefault = cache_set_default self.pop = cache_pop + self.del_multi = cache_del_multi self.len = cache_len self.contains = cache_contains self.clear = cache_clear diff --git a/synapse/util/caches/treecache.py b/synapse/util/caches/treecache.py new file mode 100644 index 0000000000..1e5f87e6ad --- /dev/null +++ b/synapse/util/caches/treecache.py @@ -0,0 +1,52 @@ +SENTINEL = object() + + +class TreeCache(object): + def __init__(self): + self.root = {} + + def __setitem__(self, key, value): + return self.set(key, value) + + def set(self, key, value): + node = self.root + for k in key[:-1]: + node = node.setdefault(k, {}) + node[key[-1]] = value + + def get(self, key, default=None): + node = self.root + for k in key[:-1]: + node = node.get(k, None) + if node is None: + return default + return node.get(key[-1], default) + + def clear(self): + self.root = {} + + def pop(self, key, default=None): + nodes = [] + + node = self.root + for k in key[:-1]: + node = node.get(k, None) + nodes.append(node) # don't add the root node + if node is None: + return default + popped = node.pop(key[-1], SENTINEL) + if popped is SENTINEL: + return default + + node_and_keys = zip(nodes, key) + node_and_keys.reverse() + node_and_keys.append((self.root, None)) + + for i in range(len(node_and_keys) - 1): + n,k = node_and_keys[i] + + if n: + break + node_and_keys[i+1][0].pop(k) + + return popped \ No newline at end of file |