1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
#
# This file is licensed under the Affero General Public License (AGPL) version 3.
#
# Copyright (C) 2023 New Vector, Ltd
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU Affero General Public License as
# published by the Free Software Foundation, either version 3 of the
# License, or (at your option) any later version.
#
# See the GNU Affero General Public License for more details:
# <https://www.gnu.org/licenses/agpl-3.0.html>.
#
# Originally licensed under the Apache License, Version 2.0:
# <http://www.apache.org/licenses/LICENSE-2.0>.
#
# [This file includes modifications made by New Vector Limited]
#
#
import logging
import time
from typing import Any, Callable, Dict, Generic, Tuple, TypeVar, Union
import attr
from sortedcontainers import SortedList
from synapse.util.caches import register_cache
logger = logging.getLogger(__name__)
SENTINEL: Any = object()
T = TypeVar("T")
KT = TypeVar("KT")
VT = TypeVar("VT")
class TTLCache(Generic[KT, VT]):
"""A key/value cache implementation where each entry has its own TTL"""
def __init__(self, cache_name: str, timer: Callable[[], float] = time.time):
# map from key to _CacheEntry
self._data: Dict[KT, _CacheEntry[KT, VT]] = {}
# the _CacheEntries, sorted by expiry time
self._expiry_list: SortedList[_CacheEntry[KT, VT]] = SortedList()
self._timer = timer
self._metrics = register_cache("ttl", cache_name, self, resizable=False)
def set(self, key: KT, value: VT, ttl: float) -> None:
"""Add/update an entry in the cache
Args:
key: key for this entry
value: value for this entry
ttl: TTL for this entry, in seconds
"""
expiry = self._timer() + ttl
self.expire()
e = self._data.pop(key, SENTINEL)
if e is not SENTINEL:
assert isinstance(e, _CacheEntry)
self._expiry_list.remove(e)
entry = _CacheEntry(expiry_time=expiry, ttl=ttl, key=key, value=value)
self._data[key] = entry
self._expiry_list.add(entry)
def get(self, key: KT, default: T = SENTINEL) -> Union[VT, T]:
"""Get a value from the cache
Args:
key: key to look up
default: default value to return, if key is not found. If not set, and the
key is not found, a KeyError will be raised
Returns:
value from the cache, or the default
"""
self.expire()
e = self._data.get(key, SENTINEL)
if e is SENTINEL:
self._metrics.inc_misses()
if default is SENTINEL:
raise KeyError(key)
return default
assert isinstance(e, _CacheEntry)
self._metrics.inc_hits()
return e.value
def get_with_expiry(self, key: KT) -> Tuple[VT, float, float]:
"""Get a value, and its expiry time, from the cache
Args:
key: key to look up
Returns:
A tuple of the value from the cache, the expiry time and the TTL
Raises:
KeyError if the entry is not found
"""
self.expire()
try:
e = self._data[key]
except KeyError:
self._metrics.inc_misses()
raise
self._metrics.inc_hits()
return e.value, e.expiry_time, e.ttl
def pop(self, key: KT, default: T = SENTINEL) -> Union[VT, T]:
"""Remove a value from the cache
If key is in the cache, remove it and return its value, else return default.
If default is not given and key is not in the cache, a KeyError is raised.
Args:
key: key to look up
default: default value to return, if key is not found. If not set, and the
key is not found, a KeyError will be raised
Returns:
value from the cache, or the default
"""
self.expire()
e = self._data.pop(key, SENTINEL)
if e is SENTINEL:
self._metrics.inc_misses()
if default is SENTINEL:
raise KeyError(key)
return default
assert isinstance(e, _CacheEntry)
self._expiry_list.remove(e)
self._metrics.inc_hits()
return e.value
def __getitem__(self, key: KT) -> VT:
return self.get(key)
def __delitem__(self, key: KT) -> None:
self.pop(key)
def __contains__(self, key: KT) -> bool:
return key in self._data
def __len__(self) -> int:
self.expire()
return len(self._data)
def expire(self) -> None:
"""Run the expiry on the cache. Any entries whose expiry times are due will
be removed
"""
now = self._timer()
while self._expiry_list:
first_entry = self._expiry_list[0]
if first_entry.expiry_time - now > 0.0:
break
del self._data[first_entry.key]
del self._expiry_list[0]
@attr.s(frozen=True, slots=True, auto_attribs=True)
class _CacheEntry(Generic[KT, VT]):
"""TTLCache entry"""
# expiry_time is the first attribute, so that entries are sorted by expiry.
expiry_time: float
ttl: float
key: KT
value: VT
|
