Merge branch 'develop' of github.com:matrix-org/synapse into use-simplejson

10 files changed, 261 insertions, 25 deletions

diff --git a/synapse/config/_base.py b/synapse/config/_base.py
index 9b0f8c3c32..87cdbf1d30 100644
--- a/synapse/config/_base.py
+++ b/synapse/config/_base.py
@@ -28,6 +28,16 @@ class Config(object):
         pass
 
     @staticmethod
+    def parse_size(string):
+        sizes = {"K": 1024, "M": 1024 * 1024}
+        size = 1
+        suffix = string[-1]
+        if suffix in sizes:
+            string = string[:-1]
+            size = sizes[suffix]
+        return int(string) * size
+
+    @staticmethod
     def abspath(file_path):
         return os.path.abspath(file_path) if file_path else file_path
 
diff --git a/synapse/config/database.py b/synapse/config/database.py
index daa161c952..87efe54645 100644
--- a/synapse/config/database.py
+++ b/synapse/config/database.py
@@ -24,6 +24,7 @@ class DatabaseConfig(Config):
             self.database_path = ":memory:"
         else:
             self.database_path = self.abspath(args.database_path)
+        self.event_cache_size = self.parse_size(args.event_cache_size)
 
     @classmethod
     def add_arguments(cls, parser):
@@ -33,6 +34,10 @@ class DatabaseConfig(Config):
             "-d", "--database-path", default="homeserver.db",
             help="The database name."
         )
+        db_group.add_argument(
+            "--event-cache-size", default="100K",
+            help="Number of events to cache in memory."
+        )
 
     @classmethod
     def generate_config(cls, args, config_dir_path):
diff --git a/synapse/python_dependencies.py b/synapse/python_dependencies.py
index e2a9d1f6a7..c7a685e71e 100644
--- a/synapse/python_dependencies.py
+++ b/synapse/python_dependencies.py
@@ -4,7 +4,7 @@ from distutils.version import LooseVersion
 logger = logging.getLogger(__name__)
 
 REQUIREMENTS = {
-    "syutil==0.0.2": ["syutil"],
+    "syutil>=0.0.2": ["syutil"],
     "matrix_angular_sdk>=0.6.1": ["syweb>=0.6.1"],
     "Twisted==14.0.2": ["twisted==14.0.2"],
     "service_identity>=1.0.0": ["service_identity>=1.0.0"],
diff --git a/synapse/storage/__init__.py b/synapse/storage/__init__.py
index a0284d54b9..02b1f06854 100644
--- a/synapse/storage/__init__.py
+++ b/synapse/storage/__init__.py
@@ -163,6 +163,9 @@ class DataStore(RoomMemberStore, RoomStore,
                            stream_ordering=None, is_new_state=True,
                            current_state=None):
 
+        # Remove the any existing cache entries for the event_id
+        self._get_event_cache.pop(event.event_id)
+
         # We purposefully do this first since if we include a `current_state`
         # key, we *want* to update the `current_state_events` table
         if current_state:
@@ -426,6 +429,8 @@ class DataStore(RoomMemberStore, RoomStore,
         )
 
     def _store_redaction(self, txn, event):
+        # invalidate the cache for the redacted event
+        self._get_event_cache.pop(event.redacts)
         txn.execute(
             "INSERT OR IGNORE INTO redactions "
             "(event_id, redacts) VALUES (?,?)",
diff --git a/synapse/storage/_base.py b/synapse/storage/_base.py
index b74e74ac91..be9934c66f 100644
--- a/synapse/storage/_base.py
+++ b/synapse/storage/_base.py
@@ -19,6 +19,7 @@ from synapse.events import FrozenEvent
 from synapse.events.utils import prune_event
 from synapse.util.logutils import log_function
 from synapse.util.logcontext import PreserveLoggingContext, LoggingContext
+from synapse.util.lrucache import LruCache
 
 from twisted.internet import defer
 
@@ -128,6 +129,8 @@ class SQLBaseStore(object):
         self._txn_perf_counters = PerformanceCounters()
         self._get_event_counters = PerformanceCounters()
 
+        self._get_event_cache = LruCache(hs.config.event_cache_size)
+
     def start_profiling(self):
         self._previous_loop_ts = self._clock.time_msec()
 
@@ -579,6 +582,19 @@ class SQLBaseStore(object):
 
     def _get_event_txn(self, txn, event_id, check_redacted=True,
                        get_prev_content=False, allow_rejected=False):
+
+        start_time = time.time() * 1000
+        update_counter = self._get_event_counters.update
+
+        try:
+            cache = self._get_event_cache.setdefault(event_id, {})
+            # Separate cache entries for each way to invoke _get_event_txn
+            return cache[(check_redacted, get_prev_content, allow_rejected)]
+        except KeyError:
+            pass
+        finally:
+            start_time = update_counter("event_cache", start_time)
+
         sql = (
             "SELECT e.internal_metadata, e.json, r.event_id, rej.reason "
             "FROM event_json as e "
@@ -588,8 +604,6 @@ class SQLBaseStore(object):
             "LIMIT 1 "
         )
 
-        start_time = time.time() * 1000
-
         txn.execute(sql, (event_id,))
 
         res = txn.fetchone()
@@ -599,14 +613,16 @@ class SQLBaseStore(object):
 
         internal_metadata, js, redacted, rejected_reason = res
 
-        self._get_event_counters.update("select_event", start_time)
+        start_time = update_counter("select_event", start_time)
 
         if allow_rejected or not rejected_reason:
-            return self._get_event_from_row_txn(
+            result = self._get_event_from_row_txn(
                 txn, internal_metadata, js, redacted,
                 check_redacted=check_redacted,
                 get_prev_content=get_prev_content,
             )
+            cache[(check_redacted, get_prev_content, allow_rejected)] = result
+            return result
         else:
             return None
 
diff --git a/synapse/storage/roommember.py b/synapse/storage/roommember.py
index c69dd995ce..779f9ce544 100644
--- a/synapse/storage/roommember.py
+++ b/synapse/storage/roommember.py
@@ -35,6 +35,11 @@ RoomsForUser = namedtuple(
 
 class RoomMemberStore(SQLBaseStore):
 
+    def __init__(self, *args, **kw):
+        super(RoomMemberStore, self).__init__(*args, **kw)
+
+        self._user_rooms_cache = {}
+
     def _store_room_member_txn(self, txn, event):
         """Store a room member in the database.
         """
@@ -98,6 +103,8 @@ class RoomMemberStore(SQLBaseStore):
 
                 txn.execute(sql, (event.room_id, domain))
 
+        self.invalidate_rooms_for_user(target_user_id)
+
     @defer.inlineCallbacks
     def get_room_member(self, user_id, room_id):
         """Retrieve the current state of a room member.
@@ -240,28 +247,53 @@ class RoomMemberStore(SQLBaseStore):
         results = self._parse_events_txn(txn, rows)
         return results
 
+    # TODO(paul): Create a nice @cached decorator to do this
+    #    @cached
+    #    def get_foo(...)
+    #        ...
+    #    invalidate_foo = get_foo.invalidator
+
+    @defer.inlineCallbacks
+    def get_rooms_for_user(self, user_id):
+        # TODO(paul): put some performance counters in here so we can easily
+        #   track what impact this cache is having
+        if user_id in self._user_rooms_cache:
+            defer.returnValue(self._user_rooms_cache[user_id])
+
+        rooms = yield self.get_rooms_for_user_where_membership_is(
+            user_id, membership_list=[Membership.JOIN],
+        )
+
+        # TODO(paul): Consider applying a maximum size; just evict things at
+        #   random, or consider LRU?
+
+        self._user_rooms_cache[user_id] = rooms
+        defer.returnValue(rooms)
+
+    def invalidate_rooms_for_user(self, user_id):
+        if user_id in self._user_rooms_cache:
+            del self._user_rooms_cache[user_id]
+
+    @defer.inlineCallbacks
     def user_rooms_intersect(self, user_id_list):
         """ Checks whether all the users whose IDs are given in a list share a
         room.
+
+        This is a "hot path" function that's called a lot, e.g. by presence for
+        generating the event stream. As such, it is implemented locally by
+        wrapping logic around heavily-cached database queries.
         """
-        def interaction(txn):
-            user_list_clause = " OR ".join(["m.user_id = ?"] * len(user_id_list))
-            sql = (
-                "SELECT m.room_id FROM room_memberships as m "
-                "INNER JOIN current_state_events as c "
-                "ON m.event_id = c.event_id "
-                "WHERE m.membership = 'join' "
-                "AND (%(clause)s) "
-                # TODO(paul): We've got duplicate rows in the database somewhere
-                #   so we have to DISTINCT m.user_id here
-                "GROUP BY m.room_id HAVING COUNT(DISTINCT m.user_id) = ?"
-            ) % {"clause": user_list_clause}
-
-            args = list(user_id_list)
-            args.append(len(user_id_list))
+        if len(user_id_list) < 2:
+            defer.returnValue(True)
 
-            txn.execute(sql, args)
+        deferreds = [self.get_rooms_for_user(u) for u in user_id_list]
+
+        results = yield defer.DeferredList(deferreds)
+
+        # A list of sets of strings giving room IDs for each user
+        room_id_lists = [set([r.room_id for r in result[1]]) for result in results]
 
-            return len(txn.fetchall()) > 0
+        # There isn't a setintersection(*list_of_sets)
+        ret = len(room_id_lists.pop(0).intersection(*room_id_lists)) > 0
 
-        return self.runInteraction("user_rooms_intersect", interaction)
+        defer.returnValue(ret)
diff --git a/synapse/util/lrucache.py b/synapse/util/lrucache.py
new file mode 100644
index 0000000000..a45c673d32
--- /dev/null
+++ b/synapse/util/lrucache.py
@@ -0,0 +1,110 @@
+# -*- coding: utf-8 -*-
+# Copyright 2015 OpenMarket Ltd
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+
+class LruCache(object):
+    """Least-recently-used cache."""
+    # TODO(mjark) Add hit/miss counters
+    # TODO(mjark) Add mutex for linked list for thread safety.
+    def __init__(self, max_size):
+        cache = {}
+        list_root = []
+        list_root[:] = [list_root, list_root, None, None]
+
+        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
+
+        def add_node(key, value):
+            prev_node = list_root
+            next_node = prev_node[NEXT]
+            node = [prev_node, next_node, key, value]
+            prev_node[NEXT] = node
+            next_node[PREV] = node
+            cache[key] = node
+
+        def move_node_to_front(node):
+            prev_node = node[PREV]
+            next_node = node[NEXT]
+            prev_node[NEXT] = next_node
+            next_node[PREV] = prev_node
+            prev_node = list_root
+            next_node = prev_node[NEXT]
+            node[PREV] = prev_node
+            node[NEXT] = next_node
+            prev_node[NEXT] = node
+            next_node[PREV] = node
+
+        def delete_node(node):
+            prev_node = node[PREV]
+            next_node = node[NEXT]
+            prev_node[NEXT] = next_node
+            next_node[PREV] = prev_node
+            cache.pop(node[KEY], None)
+
+        def cache_get(key, default=None):
+            node = cache.get(key, None)
+            if node is not None:
+                move_node_to_front(node)
+                return node[VALUE]
+            else:
+                return default
+
+        def cache_set(key, value):
+            node = cache.get(key, None)
+            if node is not None:
+                move_node_to_front(node)
+                node[VALUE] = value
+            else:
+                add_node(key, value)
+                if len(cache) > max_size:
+                    delete_node(list_root[PREV])
+
+        def cache_set_default(key, value):
+            node = cache.get(key, None)
+            if node is not None:
+                return node[VALUE]
+            else:
+                add_node(key, value)
+                if len(cache) > max_size:
+                    delete_node(list_root[PREV])
+                return value
+
+        def cache_pop(key, default=None):
+            node = cache.get(key, None)
+            if node:
+                delete_node(node)
+                return node[VALUE]
+            else:
+                return default
+
+        self.sentinel = object()
+        self.get = cache_get
+        self.set = cache_set
+        self.setdefault = cache_set_default
+        self.pop = cache_pop
+
+    def __getitem__(self, key):
+        result = self.get(key, self.sentinel)
+        if result is self.sentinel:
+            raise KeyError()
+        else:
+            return result
+
+    def __setitem__(self, key, value):
+        self.set(key, value)
+
+    def __delitem__(self, key, value):
+        result = self.pop(key, self.sentinel)
+        if result is self.sentinel:
+            raise KeyError()
diff --git a/tests/storage/test_base.py b/tests/storage/test_base.py
index a0a24ce096..55fbffa7a2 100644
--- a/tests/storage/test_base.py
+++ b/tests/storage/test_base.py
@@ -38,8 +38,9 @@ class SQLBaseStoreTestCase(unittest.TestCase):
             return defer.succeed(func(self.mock_txn, *args, **kwargs))
         self.db_pool.runInteraction = runInteraction
 
-        hs = HomeServer("test",
-                db_pool=self.db_pool)
+        config = Mock()
+        config.event_cache_size = 1
+        hs = HomeServer("test", db_pool=self.db_pool, config=config)
 
         self.datastore = SQLBaseStore(hs)
 
diff --git a/tests/util/test_lrucache.py b/tests/util/test_lrucache.py
new file mode 100644
index 0000000000..ab934bf928
--- /dev/null
+++ b/tests/util/test_lrucache.py
@@ -0,0 +1,56 @@
+# -*- coding: utf-8 -*-
+# Copyright 2015 OpenMarket Ltd
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+
+from .. import unittest
+
+from synapse.util.lrucache import LruCache
+
+class LruCacheTestCase(unittest.TestCase):
+
+    def test_get_set(self):
+        cache = LruCache(1)
+        cache["key"] = "value"
+        self.assertEquals(cache.get("key"), "value")
+        self.assertEquals(cache["key"], "value")
+
+    def test_eviction(self):
+        cache = LruCache(2)
+        cache[1] = 1
+        cache[2] = 2
+
+        self.assertEquals(cache.get(1), 1)
+        self.assertEquals(cache.get(2), 2)
+
+        cache[3] = 3
+
+        self.assertEquals(cache.get(1), None)
+        self.assertEquals(cache.get(2), 2)
+        self.assertEquals(cache.get(3), 3)
+
+    def test_setdefault(self):
+        cache = LruCache(1)
+        self.assertEquals(cache.setdefault("key", 1), 1)
+        self.assertEquals(cache.get("key"), 1)
+        self.assertEquals(cache.setdefault("key", 2), 1)
+        self.assertEquals(cache.get("key"), 1)
+
+    def test_pop(self):
+        cache = LruCache(1)
+        cache["key"] = 1
+        self.assertEquals(cache.pop("key"), 1)
+        self.assertEquals(cache.pop("key"), None)
+
+
diff --git a/tests/utils.py b/tests/utils.py
index 25c33492a5..39895c739f 100644
--- a/tests/utils.py
+++ b/tests/utils.py
@@ -41,6 +41,7 @@ def setup_test_homeserver(name="test", datastore=None, config=None, **kargs):
     if config is None:
         config = Mock()
         config.signing_key = [MockKey()]
+        config.event_cache_size = 1
 
     if datastore is None:
         db_pool = SQLiteMemoryDbPool()