Merge pull request #582 from matrix-org/erikj/presence

Rewrite presence for performance.

30 files changed, 1450 insertions, 3102 deletions

diff --git a/synapse/api/constants.py b/synapse/api/constants.py
index 84cbe710b3..8cf4d6169c 100644
--- a/synapse/api/constants.py
+++ b/synapse/api/constants.py
@@ -32,7 +32,6 @@ class PresenceState(object):
     OFFLINE = u"offline"
     UNAVAILABLE = u"unavailable"
     ONLINE = u"online"
-    FREE_FOR_CHAT = u"free_for_chat"
 
 
 class JoinRules(object):
diff --git a/synapse/handlers/events.py b/synapse/handlers/events.py
index 4933c31c19..72a31a9755 100644
--- a/synapse/handlers/events.py
+++ b/synapse/handlers/events.py
@@ -19,6 +19,8 @@ from synapse.util.logutils import log_function
 from synapse.types import UserID
 from synapse.events.utils import serialize_event
 from synapse.util.logcontext import preserve_context_over_fn
+from synapse.api.constants import Membership, EventTypes
+from synapse.events import EventBase
 
 from ._base import BaseHandler
 
@@ -126,11 +128,12 @@ class EventStreamHandler(BaseHandler):
         If `only_keys` is not None, events from keys will be sent down.
         """
         auth_user = UserID.from_string(auth_user_id)
+        presence_handler = self.hs.get_handlers().presence_handler
 
-        try:
-            if affect_presence:
-                yield self.started_stream(auth_user)
-
+        context = yield presence_handler.user_syncing(
+            auth_user_id, affect_presence=affect_presence,
+        )
+        with context:
             if timeout:
                 # If they've set a timeout set a minimum limit.
                 timeout = max(timeout, 500)
@@ -145,6 +148,34 @@ class EventStreamHandler(BaseHandler):
                 is_guest=is_guest, explicit_room_id=room_id
             )
 
+            # When the user joins a new room, or another user joins a currently
+            # joined room, we need to send down presence for those users.
+            to_add = []
+            for event in events:
+                if not isinstance(event, EventBase):
+                    continue
+                if event.type == EventTypes.Member:
+                    if event.membership != Membership.JOIN:
+                        continue
+                    # Send down presence.
+                    if event.state_key == auth_user_id:
+                        # Send down presence for everyone in the room.
+                        users = yield self.store.get_users_in_room(event.room_id)
+                        states = yield presence_handler.get_states(
+                            users,
+                            as_event=True,
+                        )
+                        to_add.extend(states)
+                    else:
+
+                        ev = yield presence_handler.get_state(
+                            UserID.from_string(event.state_key),
+                            as_event=True,
+                        )
+                        to_add.append(ev)
+
+            events.extend(to_add)
+
             time_now = self.clock.time_msec()
 
             chunks = [
@@ -159,10 +190,6 @@ class EventStreamHandler(BaseHandler):
 
             defer.returnValue(chunk)
 
-        finally:
-            if affect_presence:
-                self.stopped_stream(auth_user)
-
 
 class EventHandler(BaseHandler):
 
diff --git a/synapse/handlers/message.py b/synapse/handlers/message.py
index 723bc0e34f..afa7c9c36c 100644
--- a/synapse/handlers/message.py
+++ b/synapse/handlers/message.py
@@ -21,7 +21,6 @@ from synapse.streams.config import PaginationConfig
 from synapse.events.utils import serialize_event
 from synapse.events.validator import EventValidator
 from synapse.util import unwrapFirstError
-from synapse.util.logcontext import PreserveLoggingContext
 from synapse.util.caches.snapshot_cache import SnapshotCache
 from synapse.types import UserID, RoomStreamToken, StreamToken
 
@@ -249,8 +248,7 @@ class MessageHandler(BaseHandler):
 
         if event.type == EventTypes.Message:
             presence = self.hs.get_handlers().presence_handler
-            with PreserveLoggingContext():
-                presence.bump_presence_active_time(user)
+            yield presence.bump_presence_active_time(user)
 
     def deduplicate_state_event(self, event, context):
         """
@@ -674,10 +672,6 @@ class MessageHandler(BaseHandler):
             room_id=room_id,
         )
 
-        # TODO(paul): I wish I was called with user objects not user_id
-        #   strings...
-        auth_user = UserID.from_string(user_id)
-
         # TODO: These concurrently
         time_now = self.clock.time_msec()
         state = [
@@ -702,13 +696,11 @@ class MessageHandler(BaseHandler):
         @defer.inlineCallbacks
         def get_presence():
             states = yield presence_handler.get_states(
-                target_users=[UserID.from_string(m.user_id) for m in room_members],
-                auth_user=auth_user,
+                [m.user_id for m in room_members],
                 as_event=True,
-                check_auth=False,
             )
 
-            defer.returnValue(states.values())
+            defer.returnValue(states)
 
         @defer.inlineCallbacks
         def get_receipts():
diff --git a/synapse/handlers/presence.py b/synapse/handlers/presence.py
index b61394f2b5..fb9536cee3 100644
--- a/synapse/handlers/presence.py
+++ b/synapse/handlers/presence.py
@@ -13,13 +13,25 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
-from twisted.internet import defer
+"""This module is responsible for keeping track of presence status of local
+and remote users.
 
-from synapse.api.errors import SynapseError, AuthError
+The methods that define policy are:
+    - PresenceHandler._update_states
+    - PresenceHandler._handle_timeouts
+    - should_notify
+"""
+
+from twisted.internet import defer, reactor
+from contextlib import contextmanager
+
+from synapse.api.errors import SynapseError
 from synapse.api.constants import PresenceState
+from synapse.storage.presence import UserPresenceState
 
-from synapse.util.logcontext import PreserveLoggingContext
+from synapse.util.logcontext import preserve_fn
 from synapse.util.logutils import log_function
+from synapse.util.wheel_timer import WheelTimer
 from synapse.types import UserID
 import synapse.metrics
 
@@ -33,33 +45,24 @@ logger = logging.getLogger(__name__)
 metrics = synapse.metrics.get_metrics_for(__name__)
 
 
-# Don't bother bumping "last active" time if it differs by less than 60 seconds
+# If a user was last active in the last LAST_ACTIVE_GRANULARITY, consider them
+# "currently_active"
 LAST_ACTIVE_GRANULARITY = 60 * 1000
 
-# Keep no more than this number of offline serial revisions
-MAX_OFFLINE_SERIALS = 1000
-
-
-# TODO(paul): Maybe there's one of these I can steal from somewhere
-def partition(l, func):
-    """Partition the list by the result of func applied to each element."""
-    ret = {}
+# How long to wait until a new /events or /sync request before assuming
+# the client has gone.
+SYNC_ONLINE_TIMEOUT = 30 * 1000
 
-    for x in l:
-        key = func(x)
-        if key not in ret:
-            ret[key] = []
-        ret[key].append(x)
+# How long to wait before marking the user as idle. Compared against last active
+IDLE_TIMER = 5 * 60 * 1000
 
-    return ret
+# How often we expect remote servers to resend us presence.
+FEDERATION_TIMEOUT = 30 * 60 * 1000
 
+# How often to resend presence to remote servers
+FEDERATION_PING_INTERVAL = 25 * 60 * 1000
 
-def partitionbool(l, func):
-    def boolfunc(x):
-        return bool(func(x))
-
-    ret = partition(l, boolfunc)
-    return ret.get(True, []), ret.get(False, [])
+assert LAST_ACTIVE_GRANULARITY < IDLE_TIMER
 
 
 def user_presence_changed(distributor, user, statuscache):
@@ -72,45 +75,13 @@ def collect_presencelike_data(distributor, user, content):
 
 class PresenceHandler(BaseHandler):
 
-    STATE_LEVELS = {
-        PresenceState.OFFLINE: 0,
-        PresenceState.UNAVAILABLE: 1,
-        PresenceState.ONLINE: 2,
-        PresenceState.FREE_FOR_CHAT: 3,
-    }
-
     def __init__(self, hs):
         super(PresenceHandler, self).__init__(hs)
-
-        self.homeserver = hs
-
+        self.hs = hs
         self.clock = hs.get_clock()
-
-        distributor = hs.get_distributor()
-        distributor.observe("registered_user", self.registered_user)
-
-        distributor.observe(
-            "started_user_eventstream", self.started_user_eventstream
-        )
-        distributor.observe(
-            "stopped_user_eventstream", self.stopped_user_eventstream
-        )
-
-        distributor.observe("user_joined_room", self.user_joined_room)
-
-        distributor.declare("collect_presencelike_data")
-
-        distributor.declare("changed_presencelike_data")
-        distributor.observe(
-            "changed_presencelike_data", self.changed_presencelike_data
-        )
-
-        # outbound signal from the presence module to advertise when a user's
-        # presence has changed
-        distributor.declare("user_presence_changed")
-
-        self.distributor = distributor
-
+        self.store = hs.get_datastore()
+        self.wheel_timer = WheelTimer()
+        self.notifier = hs.get_notifier()
         self.federation = hs.get_replication_layer()
 
         self.federation.register_edu_handler(
@@ -138,348 +109,523 @@ class PresenceHandler(BaseHandler):
             )
         )
 
-        # IN-MEMORY store, mapping local userparts to sets of local users to
-        # be informed of state changes.
-        self._local_pushmap = {}
-        # map local users to sets of remote /domain names/ who are interested
-        # in them
-        self._remote_sendmap = {}
-        # map remote users to sets of local users who're interested in them
-        self._remote_recvmap = {}
-        # list of (serial, set of(userids)) tuples, ordered by serial, latest
-        # first
-        self._remote_offline_serials = []
-
-        # map any user to a UserPresenceCache
-        self._user_cachemap = {}
-        self._user_cachemap_latest_serial = 0
-
-        # map room_ids to the latest presence serial for a member of that
-        # room
-        self._room_serials = {}
-
-        metrics.register_callback(
-            "userCachemap:size",
-            lambda: len(self._user_cachemap),
-        )
-
-    def _get_or_make_usercache(self, user):
-        """If the cache entry doesn't exist, initialise a new one."""
-        if user not in self._user_cachemap:
-            self._user_cachemap[user] = UserPresenceCache()
-        return self._user_cachemap[user]
-
-    def _get_or_offline_usercache(self, user):
-        """If the cache entry doesn't exist, return an OFFLINE one but do not
-        store it into the cache."""
-        if user in self._user_cachemap:
-            return self._user_cachemap[user]
-        else:
-            return UserPresenceCache()
+        distributor = hs.get_distributor()
+        distributor.observe("user_joined_room", self.user_joined_room)
 
-    def registered_user(self, user):
-        return self.store.create_presence(user.localpart)
+        active_presence = self.store.take_presence_startup_info()
+
+        # A dictionary of the current state of users. This is prefilled with
+        # non-offline presence from the DB. We should fetch from the DB if
+        # we can't find a users presence in here.
+        self.user_to_current_state = {
+            state.user_id: state
+            for state in active_presence
+        }
+
+        now = self.clock.time_msec()
+        for state in active_presence:
+            self.wheel_timer.insert(
+                now=now,
+                obj=state.user_id,
+                then=state.last_active_ts + IDLE_TIMER,
+            )
+            self.wheel_timer.insert(
+                now=now,
+                obj=state.user_id,
+                then=state.last_user_sync_ts + SYNC_ONLINE_TIMEOUT,
+            )
+            if self.hs.is_mine_id(state.user_id):
+                self.wheel_timer.insert(
+                    now=now,
+                    obj=state.user_id,
+                    then=state.last_federation_update_ts + FEDERATION_PING_INTERVAL,
+                )
+            else:
+                self.wheel_timer.insert(
+                    now=now,
+                    obj=state.user_id,
+                    then=state.last_federation_update_ts + FEDERATION_TIMEOUT,
+                )
 
-    @defer.inlineCallbacks
-    def is_presence_visible(self, observer_user, observed_user):
-        assert(self.hs.is_mine(observed_user))
+        # Set of users who have presence in the `user_to_current_state` that
+        # have not yet been persisted
+        self.unpersisted_users_changes = set()
 
-        if observer_user == observed_user:
-            defer.returnValue(True)
+        reactor.addSystemEventTrigger("before", "shutdown", self._on_shutdown)
 
-        if (yield self.store.user_rooms_intersect(
-                [u.to_string() for u in observer_user, observed_user])):
-            defer.returnValue(True)
+        self.serial_to_user = {}
+        self._next_serial = 1
 
-        if (yield self.store.is_presence_visible(
-                observed_localpart=observed_user.localpart,
-                observer_userid=observer_user.to_string())):
-            defer.returnValue(True)
+        # Keeps track of the number of *ongoing* syncs. While this is non zero
+        # a user will never go offline.
+        self.user_to_num_current_syncs = {}
 
-        defer.returnValue(False)
+        # Start a LoopingCall in 30s that fires every 5s.
+        # The initial delay is to allow disconnected clients a chance to
+        # reconnect before we treat them as offline.
+        self.clock.call_later(
+            0 * 1000,
+            self.clock.looping_call,
+            self._handle_timeouts,
+            5000,
+        )
 
     @defer.inlineCallbacks
-    def get_state(self, target_user, auth_user, as_event=False, check_auth=True):
-        """Get the current presence state of the given user.
+    def _on_shutdown(self):
+        """Gets called when shutting down. This lets us persist any updates that
+        we haven't yet persisted, e.g. updates that only changes some internal
+        timers. This allows changes to persist across startup without having to
+        persist every single change.
+
+        If this does not run it simply means that some of the timers will fire
+        earlier than they should when synapse is restarted. This affect of this
+        is some spurious presence changes that will self-correct.
+        """
+        logger.info(
+            "Performing _on_shutdown. Persiting %d unpersisted changes",
+            len(self.user_to_current_state)
+        )
 
-        Args:
-            target_user (UserID): The user whose presence we want
-            auth_user (UserID): The user requesting the presence, used for
-                checking if said user is allowed to see the persence of the
-                `target_user`
-            as_event (bool): Format the return as an event or not?
-            check_auth (bool): Perform the auth checks or not?
+        if self.unpersisted_users_changes:
+            yield self.store.update_presence([
+                self.user_to_current_state[user_id]
+                for user_id in self.unpersisted_users_changes
+            ])
+        logger.info("Finished _on_shutdown")
 
-        Returns:
-            dict: The presence state of the `target_user`, whose format depends
-            on the `as_event` argument.
+    @defer.inlineCallbacks
+    def _update_states(self, new_states):
+        """Updates presence of users. Sets the appropriate timeouts. Pokes
+        the notifier and federation if and only if the changed presence state
+        should be sent to clients/servers.
         """
-        if self.hs.is_mine(target_user):
-            if check_auth:
-                visible = yield self.is_presence_visible(
-                    observer_user=auth_user,
-                    observed_user=target_user
-                )
+        now = self.clock.time_msec()
+
+        # NOTE: We purposefully don't yield between now and when we've
+        # calculated what we want to do with the new states, to avoid races.
+
+        to_notify = {}  # Changes we want to notify everyone about
+        to_federation_ping = {}  # These need sending keep-alives
+        for new_state in new_states:
+            user_id = new_state.user_id
+
+            # Its fine to not hit the database here, as the only thing not in
+            # the current state cache are OFFLINE states, where the only field
+            # of interest is last_active which is safe enough to assume is 0
+            # here.
+            prev_state = self.user_to_current_state.get(
+                user_id, UserPresenceState.default(user_id)
+            )
 
-                if not visible:
-                    raise SynapseError(404, "Presence information not visible")
+            new_state, should_notify, should_ping = handle_update(
+                prev_state, new_state,
+                is_mine=self.hs.is_mine_id(user_id),
+                wheel_timer=self.wheel_timer,
+                now=now
+            )
 
-            if target_user in self._user_cachemap:
-                state = self._user_cachemap[target_user].get_state()
-            else:
-                state = yield self.store.get_presence_state(target_user.localpart)
-                if "mtime" in state:
-                    del state["mtime"]
-                state["presence"] = state.pop("state")
-        else:
-            # TODO(paul): Have remote server send us permissions set
-            state = self._get_or_offline_usercache(target_user).get_state()
+            self.user_to_current_state[user_id] = new_state
+
+            if should_notify:
+                to_notify[user_id] = new_state
+            elif should_ping:
+                to_federation_ping[user_id] = new_state
+
+        # TODO: We should probably ensure there are no races hereafter
 
-        if "last_active" in state:
-            state["last_active_ago"] = int(
-                self.clock.time_msec() - state.pop("last_active")
+        if to_notify:
+            yield self._persist_and_notify(to_notify.values())
+
+        self.unpersisted_users_changes |= set(s.user_id for s in new_states)
+        self.unpersisted_users_changes -= set(to_notify.keys())
+
+        to_federation_ping = {
+            user_id: state for user_id, state in to_federation_ping.items()
+            if user_id not in to_notify
+        }
+        if to_federation_ping:
+            _, _, hosts_to_states = yield self._get_interested_parties(
+                to_federation_ping.values()
             )
 
-        if as_event:
-            content = state
+            self._push_to_remotes(hosts_to_states)
 
-            content["user_id"] = target_user.to_string()
+    def _handle_timeouts(self):
+        """Checks the presence of users that have timed out and updates as
+        appropriate.
+        """
+        now = self.clock.time_msec()
 
-            if "last_active" in content:
-                content["last_active_ago"] = int(
-                    self._clock.time_msec() - content.pop("last_active")
-                )
+        # Fetch the list of users that *may* have timed out. Things may have
+        # changed since the timeout was set, so we won't necessarily have to
+        # take any action.
+        users_to_check = self.wheel_timer.fetch(now)
 
-            defer.returnValue({"type": "m.presence", "content": content})
-        else:
-            defer.returnValue(state)
+        states = [
+            self.user_to_current_state.get(
+                user_id, UserPresenceState.default(user_id)
+            )
+            for user_id in set(users_to_check)
+        ]
+
+        changes = handle_timeouts(
+            states,
+            is_mine_fn=self.hs.is_mine_id,
+            user_to_num_current_syncs=self.user_to_num_current_syncs,
+            now=now,
+        )
+
+        preserve_fn(self._update_states)(changes)
 
     @defer.inlineCallbacks
-    def get_states(self, target_users, auth_user, as_event=False, check_auth=True):
-        """A batched version of the `get_state` method that accepts a list of
-        `target_users`
+    def bump_presence_active_time(self, user):
+        """We've seen the user do something that indicates they're interacting
+        with the app.
+        """
+        user_id = user.to_string()
 
-        Args:
-            target_users (list): The list of UserID's whose presence we want
-            auth_user (UserID): The user requesting the presence, used for
-                checking if said user is allowed to see the persence of the
-                `target_users`
-            as_event (bool): Format the return as an event or not?
-            check_auth (bool): Perform the auth checks or not?
+        prev_state = yield self.current_state_for_user(user_id)
 
-        Returns:
-            dict: A mapping from user -> presence_state
-        """
-        local_users, remote_users = partitionbool(
-            target_users,
-            lambda u: self.hs.is_mine(u)
-        )
+        new_fields = {
+            "last_active_ts": self.clock.time_msec(),
+        }
+        if prev_state.state == PresenceState.UNAVAILABLE:
+            new_fields["state"] = PresenceState.ONLINE
 
-        if check_auth:
-            for user in local_users:
-                visible = yield self.is_presence_visible(
-                    observer_user=auth_user,
-                    observed_user=user
-                )
+        yield self._update_states([prev_state.copy_and_replace(**new_fields)])
 
-                if not visible:
-                    raise SynapseError(404, "Presence information not visible")
+    @defer.inlineCallbacks
+    def user_syncing(self, user_id, affect_presence=True):
+        """Returns a context manager that should surround any stream requests
+        from the user.
 
-        results = {}
-        if local_users:
-            for user in local_users:
-                if user in self._user_cachemap:
-                    results[user] = self._user_cachemap[user].get_state()
+        This allows us to keep track of who is currently streaming and who isn't
+        without having to have timers outside of this module to avoid flickering
+        when users disconnect/reconnect.
 
-            local_to_user = {u.localpart: u for u in local_users}
+        Args:
+            user_id (str)
+            affect_presence (bool): If false this function will be a no-op.
+                Useful for streams that are not associated with an actual
+                client that is being used by a user.
+        """
+        if affect_presence:
+            curr_sync = self.user_to_num_current_syncs.get(user_id, 0)
+            self.user_to_num_current_syncs[user_id] = curr_sync + 1
+
+            prev_state = yield self.current_state_for_user(user_id)
+            if prev_state.state == PresenceState.OFFLINE:
+                # If they're currently offline then bring them online, otherwise
+                # just update the last sync times.
+                yield self._update_states([prev_state.copy_and_replace(
+                    state=PresenceState.ONLINE,
+                    last_active_ts=self.clock.time_msec(),
+                    last_user_sync_ts=self.clock.time_msec(),
+                )])
+            else:
+                yield self._update_states([prev_state.copy_and_replace(
+                    last_user_sync_ts=self.clock.time_msec(),
+                )])
 
-            states = yield self.store.get_presence_states(
-                [u.localpart for u in local_users if u not in results]
-            )
+        @defer.inlineCallbacks
+        def _end():
+            if affect_presence:
+                self.user_to_num_current_syncs[user_id] -= 1
 
-            for local_part, state in states.items():
-                if state is None:
-                    continue
-                res = {"presence": state["state"]}
-                if "status_msg" in state and state["status_msg"]:
-                    res["status_msg"] = state["status_msg"]
-                results[local_to_user[local_part]] = res
-
-        for user in remote_users:
-            # TODO(paul): Have remote server send us permissions set
-            results[user] = self._get_or_offline_usercache(user).get_state()
-
-        for state in results.values():
-            if "last_active" in state:
-                state["last_active_ago"] = int(
-                    self.clock.time_msec() - state.pop("last_active")
-                )
+                prev_state = yield self.current_state_for_user(user_id)
+                yield self._update_states([prev_state.copy_and_replace(
+                    last_user_sync_ts=self.clock.time_msec(),
+                )])
 
-        if as_event:
-            for user, state in results.items():
-                content = state
-                content["user_id"] = user.to_string()
+        @contextmanager
+        def _user_syncing():
+            try:
+                yield
+            finally:
+                preserve_fn(_end)()
 
-                if "last_active" in content:
-                    content["last_active_ago"] = int(
-                        self._clock.time_msec() - content.pop("last_active")
-                    )
+        defer.returnValue(_user_syncing())
 
-                results[user] = {"type": "m.presence", "content": content}
+    @defer.inlineCallbacks
+    def current_state_for_user(self, user_id):
+        """Get the current presence state for a user.
+        """
+        res = yield self.current_state_for_users([user_id])
+        defer.returnValue(res[user_id])
 
-        defer.returnValue(results)
+    @defer.inlineCallbacks
+    def current_state_for_users(self, user_ids):
+        """Get the current presence state for multiple users.
+
+        Returns:
+            dict: `user_id` -> `UserPresenceState`
+        """
+        states = {
+            user_id: self.user_to_current_state.get(user_id, None)
+            for user_id in user_ids
+        }
+
+        missing = [user_id for user_id, state in states.items() if not state]
+        if missing:
+            # There are things not in our in memory cache. Lets pull them out of
+            # the database.
+            res = yield self.store.get_presence_for_users(missing)
+            states.update({state.user_id: state for state in res})
+
+            missing = [user_id for user_id, state in states.items() if not state]
+            if missing:
+                new = {
+                    user_id: UserPresenceState.default(user_id)
+                    for user_id in missing
+                }
+                states.update(new)
+                self.user_to_current_state.update(new)
+
+        defer.returnValue(states)
 
     @defer.inlineCallbacks
-    @log_function
-    def set_state(self, target_user, auth_user, state):
-        # return
-        # TODO (erikj): Turn this back on. Why did we end up sending EDUs
-        # everywhere?
+    def _get_interested_parties(self, states):
+        """Given a list of states return which entities (rooms, users, servers)
+        are interested in the given states.
 
-        if not self.hs.is_mine(target_user):
-            raise SynapseError(400, "User is not hosted on this Home Server")
+        Returns:
+            3-tuple: `(room_ids_to_states, users_to_states, hosts_to_states)`,
+            with each item being a dict of `entity_name` -> `[UserPresenceState]`
+        """
+        room_ids_to_states = {}
+        users_to_states = {}
+        for state in states:
+            events = yield self.store.get_rooms_for_user(state.user_id)
+            for e in events:
+                room_ids_to_states.setdefault(e.room_id, []).append(state)
 
-        if target_user != auth_user:
-            raise AuthError(400, "Cannot set another user's presence")
+            plist = yield self.store.get_presence_list_observers_accepted(state.user_id)
+            for u in plist:
+                users_to_states.setdefault(u, []).append(state)
 
-        if "status_msg" not in state:
-            state["status_msg"] = None
+            # Always notify self
+            users_to_states.setdefault(state.user_id, []).append(state)
 
-        for k in state.keys():
-            if k not in ("presence", "status_msg"):
-                raise SynapseError(
-                    400, "Unexpected presence state key '%s'" % (k,)
-                )
+        hosts_to_states = {}
+        for room_id, states in room_ids_to_states.items():
+            hosts = yield self.store.get_joined_hosts_for_room(room_id)
+            for host in hosts:
+                hosts_to_states.setdefault(host, []).extend(states)
 
-        if state["presence"] not in self.STATE_LEVELS:
-            raise SynapseError(400, "'%s' is not a valid presence state" % (
-                state["presence"],
-            ))
+        for user_id, states in users_to_states.items():
+            host = UserID.from_string(user_id).domain
+            hosts_to_states.setdefault(host, []).extend(states)
 
-        logger.debug("Updating presence state of %s to %s",
-                     target_user.localpart, state["presence"])
+        # TODO: de-dup hosts_to_states, as a single host might have multiple
+        # of same presence
 
-        state_to_store = dict(state)
-        state_to_store["state"] = state_to_store.pop("presence")
+        defer.returnValue((room_ids_to_states, users_to_states, hosts_to_states))
+
+    @defer.inlineCallbacks
+    def _persist_and_notify(self, states):
+        """Persist states in the database, poke the notifier and send to
+        interested remote servers
+        """
+        stream_id, max_token = yield self.store.update_presence(states)
 
-        statuscache = self._get_or_offline_usercache(target_user)
-        was_level = self.STATE_LEVELS[statuscache.get_state()["presence"]]
-        now_level = self.STATE_LEVELS[state["presence"]]
+        parties = yield self._get_interested_parties(states)
+        room_ids_to_states, users_to_states, hosts_to_states = parties
 
-        yield self.store.set_presence_state(
-            target_user.localpart, state_to_store
+        self.notifier.on_new_event(
+            "presence_key", stream_id, rooms=room_ids_to_states.keys(),
+            users=[UserID.from_string(u) for u in users_to_states.keys()]
         )
-        yield collect_presencelike_data(self.distributor, target_user, state)
 
-        if now_level > was_level:
-            state["last_active"] = self.clock.time_msec()
+        self._push_to_remotes(hosts_to_states)
 
-        now_online = state["presence"] != PresenceState.OFFLINE
-        was_polling = target_user in self._user_cachemap
+    def _push_to_remotes(self, hosts_to_states):
+        """Sends state updates to remote servers.
 
-        if now_online and not was_polling:
-            yield self.start_polling_presence(target_user, state=state)
-        elif not now_online and was_polling:
-            yield self.stop_polling_presence(target_user)
+        Args:
+            hosts_to_states (dict): Mapping `server_name` -> `[UserPresenceState]`
+        """
+        now = self.clock.time_msec()
+        for host, states in hosts_to_states.items():
+            self.federation.send_edu(
+                destination=host,
+                edu_type="m.presence",
+                content={
+                    "push": [
+                        _format_user_presence_state(state, now)
+                        for state in states
+                    ]
+                }
+            )
 
-        # TODO(paul): perform a presence push as part of start/stop poll so
-        #   we don't have to do this all the time
-        yield self.changed_presencelike_data(target_user, state)
+    @defer.inlineCallbacks
+    def incoming_presence(self, origin, content):
+        """Called when we receive a `m.presence` EDU from a remote server.
+        """
+        now = self.clock.time_msec()
+        updates = []
+        for push in content.get("push", []):
+            # A "push" contains a list of presence that we are probably interested
+            # in.
+            # TODO: Actually check if we're interested, rather than blindly
+            # accepting presence updates.
+            user_id = push.get("user_id", None)
+            if not user_id:
+                logger.info(
+                    "Got presence update from %r with no 'user_id': %r",
+                    origin, push,
+                )
+                continue
 
-    def bump_presence_active_time(self, user, now=None):
-        if now is None:
-            now = self.clock.time_msec()
+            presence_state = push.get("presence", None)
+            if not presence_state:
+                logger.info(
+                    "Got presence update from %r with no 'presence_state': %r",
+                    origin, push,
+                )
+                continue
 
-        prev_state = self._get_or_make_usercache(user)
-        if now - prev_state.state.get("last_active", 0) < LAST_ACTIVE_GRANULARITY:
-            return
+            new_fields = {
+                "state": presence_state,
+                "last_federation_update_ts": now,
+            }
 
-        with PreserveLoggingContext():
-            self.changed_presencelike_data(user, {"last_active": now})
+            last_active_ago = push.get("last_active_ago", None)
+            if last_active_ago is not None:
+                new_fields["last_active_ts"] = now - last_active_ago
 
-    def get_joined_rooms_for_user(self, user):
-        """Get the list of rooms a user is joined to.
+            new_fields["status_msg"] = push.get("status_msg", None)
 
-        Args:
-            user(UserID): The user.
-        Returns:
-            A Deferred of a list of room id strings.
-        """
-        rm_handler = self.homeserver.get_handlers().room_member_handler
-        return rm_handler.get_joined_rooms_for_user(user)
+            prev_state = yield self.current_state_for_user(user_id)
+            updates.append(prev_state.copy_and_replace(**new_fields))
 
-    def get_joined_users_for_room_id(self, room_id):
-        rm_handler = self.homeserver.get_handlers().room_member_handler
-        return rm_handler.get_room_members(room_id)
+        if updates:
+            yield self._update_states(updates)
 
     @defer.inlineCallbacks
-    def changed_presencelike_data(self, user, state):
-        """Updates the presence state of a local user.
+    def get_state(self, target_user, as_event=False):
+        results = yield self.get_states(
+            [target_user.to_string()],
+            as_event=as_event,
+        )
+
+        defer.returnValue(results[0])
+
+    @defer.inlineCallbacks
+    def get_states(self, target_user_ids, as_event=False):
+        """Get the presence state for users.
 
         Args:
-            user(UserID): The user being updated.
-            state(dict): The new presence state for the user.
+            target_user_ids (list)
+            as_event (bool): Whether to format it as a client event or not.
+
         Returns:
-            A Deferred
+            list
         """
-        self._user_cachemap_latest_serial += 1
-        statuscache = yield self.update_presence_cache(user, state)
-        yield self.push_presence(user, statuscache=statuscache)
 
-    @log_function
-    def started_user_eventstream(self, user):
-        # TODO(paul): Use "last online" state
-        return self.set_state(user, user, {"presence": PresenceState.ONLINE})
+        updates = yield self.current_state_for_users(target_user_ids)
+        updates = updates.values()
 
-    @log_function
-    def stopped_user_eventstream(self, user):
-        # TODO(paul): Save current state as "last online" state
-        return self.set_state(user, user, {"presence": PresenceState.OFFLINE})
+        for user_id in set(target_user_ids) - set(u.user_id for u in updates):
+            updates.append(UserPresenceState.default(user_id))
+
+        now = self.clock.time_msec()
+        if as_event:
+            defer.returnValue([
+                {
+                    "type": "m.presence",
+                    "content": _format_user_presence_state(state, now),
+                }
+                for state in updates
+            ])
+        else:
+            defer.returnValue([
+                _format_user_presence_state(state, now) for state in updates
+            ])
 
     @defer.inlineCallbacks
-    def user_joined_room(self, user, room_id):
-        """Called via the distributor whenever a user joins a room.
-        Notifies the new member of the presence of the current members.
-        Notifies the current members of the room of the new member's presence.
+    def set_state(self, target_user, state):
+        """Set the presence state of the user.
+        """
+        status_msg = state.get("status_msg", None)
+        presence = state["presence"]
 
-        Args:
-            user(UserID): The user who joined the room.
-            room_id(str): The room id the user joined.
+        valid_presence = (
+            PresenceState.ONLINE, PresenceState.UNAVAILABLE, PresenceState.OFFLINE
+        )
+        if presence not in valid_presence:
+            raise SynapseError(400, "Invalid presence state")
+
+        user_id = target_user.to_string()
+
+        prev_state = yield self.current_state_for_user(user_id)
+
+        new_fields = {
+            "state": presence,
+            "status_msg": status_msg if presence != PresenceState.OFFLINE else None
+        }
+
+        if presence == PresenceState.ONLINE:
+            new_fields["last_active_ts"] = self.clock.time_msec()
+
+        yield self._update_states([prev_state.copy_and_replace(**new_fields)])
+
+    @defer.inlineCallbacks
+    def user_joined_room(self, user, room_id):
+        """Called (via the distributor) when a user joins a room. This funciton
+        sends presence updates to servers, either:
+            1. the joining user is a local user and we send their presence to
+               all servers in the room.
+            2. the joining user is a remote user and so we send presence for all
+               local users in the room.
         """
+        # We only need to send presence to servers that don't have it yet. We
+        # don't need to send to local clients here, as that is done as part
+        # of the event stream/sync.
+        # TODO: Only send to servers not already in the room.
         if self.hs.is_mine(user):
-            # No actual update but we need to bump the serial anyway for the
-            # event source
-            self._user_cachemap_latest_serial += 1
-            statuscache = yield self.update_presence_cache(
-                user, room_ids=[room_id]
-            )
-            self.push_update_to_local_and_remote(
-                observed_user=user,
-                room_ids=[room_id],
-                statuscache=statuscache,
-            )
+            state = yield self.current_state_for_user(user.to_string())
 
-        # We also want to tell them about current presence of people.
-        curr_users = yield self.get_joined_users_for_room_id(room_id)
+            hosts = yield self.store.get_joined_hosts_for_room(room_id)
+            self._push_to_remotes({host: (state,) for host in hosts})
+        else:
+            user_ids = yield self.store.get_users_in_room(room_id)
+            user_ids = filter(self.hs.is_mine_id, user_ids)
 
-        for local_user in [c for c in curr_users if self.hs.is_mine(c)]:
-            statuscache = yield self.update_presence_cache(
-                local_user, room_ids=[room_id], add_to_cache=False
-            )
+            states = yield self.current_state_for_users(user_ids)
 
-            with PreserveLoggingContext():
-                self.push_update_to_local_and_remote(
-                    observed_user=local_user,
-                    users_to_push=[user],
-                    statuscache=statuscache,
-                )
+            self._push_to_remotes({user.domain: states.values()})
 
     @defer.inlineCallbacks
-    def send_presence_invite(self, observer_user, observed_user):
-        """Request the presence of a local or remote user for a local user"""
+    def get_presence_list(self, observer_user, accepted=None):
+        """Returns the presence for all users in their presence list.
+        """
         if not self.hs.is_mine(observer_user):
             raise SynapseError(400, "User is not hosted on this Home Server")
 
+        presence_list = yield self.store.get_presence_list(
+            observer_user.localpart, accepted=accepted
+        )
+
+        results = yield self.get_states(
+            target_user_ids=[row["observed_user_id"] for row in presence_list],
+            as_event=False,
+        )
+
+        is_accepted = {
+            row["observed_user_id"]: row["accepted"] for row in presence_list
+        }
+
+        for result in results:
+            result.update({
+                "accepted": is_accepted,
+            })
+
+        defer.returnValue(results)
+
+    @defer.inlineCallbacks
+    def send_presence_invite(self, observer_user, observed_user):
+        """Sends a presence invite.
+        """
         yield self.store.add_presence_list_pending(
             observer_user.localpart, observed_user.to_string()
         )
@@ -497,59 +643,40 @@ class PresenceHandler(BaseHandler):
             )
 
     @defer.inlineCallbacks
-    def _should_accept_invite(self, observed_user, observer_user):
-        if not self.hs.is_mine(observed_user):
-            defer.returnValue(False)
-
-        row = yield self.store.has_presence_state(observed_user.localpart)
-        if not row:
-            defer.returnValue(False)
-
-        # TODO(paul): Eventually we'll ask the user's permission for this
-        # before accepting. For now just accept any invite request
-        defer.returnValue(True)
-
-    @defer.inlineCallbacks
     def invite_presence(self, observed_user, observer_user):
-        """Handles a m.presence_invite EDU. A remote or local user has
-        requested presence updates for a local user. If the invite is accepted
-        then allow the local or remote user to see the presence of the local
-        user.
-
-        Args:
-            observed_user(UserID): The local user whose presence is requested.
-            observer_user(UserID): The remote or local user requesting presence.
+        """Handles new presence invites.
         """
-        accept = yield self._should_accept_invite(observed_user, observer_user)
-
-        if accept:
-            yield self.store.allow_presence_visible(
-                observed_user.localpart, observer_user.to_string()
-            )
+        if not self.hs.is_mine(observed_user):
+            raise SynapseError(400, "User is not hosted on this Home Server")
 
+        # TODO: Don't auto accept
         if self.hs.is_mine(observer_user):
-            if accept:
-                yield self.accept_presence(observed_user, observer_user)
-            else:
-                yield self.deny_presence(observed_user, observer_user)
+            yield self.accept_presence(observed_user, observer_user)
         else:
-            edu_type = "m.presence_accept" if accept else "m.presence_deny"
-
-            yield self.federation.send_edu(
+            self.federation.send_edu(
                 destination=observer_user.domain,
-                edu_type=edu_type,
+                edu_type="m.presence_accept",
                 content={
                     "observed_user": observed_user.to_string(),
                     "observer_user": observer_user.to_string(),
                 }
             )
 
+            state_dict = yield self.get_state(observed_user, as_event=False)
+
+            self.federation.send_edu(
+                destination=observer_user.domain,
+                edu_type="m.presence",
+                content={
+                    "push": [state_dict]
+                }
+            )
+
     @defer.inlineCallbacks
     def accept_presence(self, observed_user, observer_user):
         """Handles a m.presence_accept EDU. Mark a presence invite from a
         local or remote user as accepted in a local user's presence list.
         Starts polling for presence updates from the local or remote user.
-
         Args:
             observed_user(UserID): The user to update in the presence list.
             observer_user(UserID): The owner of the presence list to update.
@@ -558,15 +685,10 @@ class PresenceHandler(BaseHandler):
             observer_user.localpart, observed_user.to_string()
         )
 
-        yield self.start_polling_presence(
-            observer_user, target_user=observed_user
-        )
-
     @defer.inlineCallbacks
     def deny_presence(self, observed_user, observer_user):
         """Handle a m.presence_deny EDU. Removes a local or remote user from a
         local user's presence list.
-
         Args:
             observed_user(UserID): The local or remote user to remove from the
                 list.
@@ -584,7 +706,6 @@ class PresenceHandler(BaseHandler):
     def drop(self, observed_user, observer_user):
         """Remove a local or remote user from a local user's presence list and
         unsubscribe the local user from updates that user.
-
         Args:
             observed_user(UserId): The local or remote user to remove from the
                 list.
@@ -599,710 +720,301 @@ class PresenceHandler(BaseHandler):
             observer_user.localpart, observed_user.to_string()
         )
 
-        self.stop_polling_presence(
-            observer_user, target_user=observed_user
-        )
+        # TODO: Inform the remote that we've dropped the presence list.
 
     @defer.inlineCallbacks
-    def get_presence_list(self, observer_user, accepted=None):
-        """Get the presence list for a local user. The retured list includes
-        the current presence state for each user listed.
-
-        Args:
-            observer_user(UserID): The local user whose presence list to fetch.
-            accepted(bool or None): If not none then only include users who
-                have or have not accepted the presence invite request.
-        Returns:
-            A Deferred list of presence state events.
+    def is_visible(self, observed_user, observer_user):
+        """Returns whether a user can see another user's presence.
         """
-        if not self.hs.is_mine(observer_user):
-            raise SynapseError(400, "User is not hosted on this Home Server")
+        observer_rooms = yield self.store.get_rooms_for_user(observer_user.to_string())
+        observed_rooms = yield self.store.get_rooms_for_user(observed_user.to_string())
 
-        presence_list = yield self.store.get_presence_list(
-            observer_user.localpart, accepted=accepted
-        )
+        observer_room_ids = set(r.room_id for r in observer_rooms)
+        observed_room_ids = set(r.room_id for r in observed_rooms)
 
-        results = []
-        for row in presence_list:
-            observed_user = UserID.from_string(row["observed_user_id"])
-            result = {
-                "observed_user": observed_user, "accepted": row["accepted"]
-            }
-            result.update(
-                self._get_or_offline_usercache(observed_user).get_state()
-            )
-            if "last_active" in result:
-                result["last_active_ago"] = int(
-                    self.clock.time_msec() - result.pop("last_active")
-                )
-            results.append(result)
-
-        defer.returnValue(results)
-
-    @defer.inlineCallbacks
-    @log_function
-    def start_polling_presence(self, user, target_user=None, state=None):
-        """Subscribe a local user to presence updates from a local or remote
-        user. If no target_user is supplied then subscribe to all users stored
-        in the presence list for the local user.
-
-        Additonally this pushes the current presence state of this user to all
-        target_users. That state can be provided directly or will be read from
-        the stored state for the local user.
-
-        Also this attempts to notify the local user of the current state of
-        any local target users.
-
-        Args:
-            user(UserID): The local user that whishes for presence updates.
-            target_user(UserID): The local or remote user whose updates are
-                wanted.
-            state(dict): Optional presence state for the local user.
-        """
-        logger.debug("Start polling for presence from %s", user)
-
-        if target_user:
-            target_users = set([target_user])
-            room_ids = []
-        else:
-            presence = yield self.store.get_presence_list(
-                user.localpart, accepted=True
-            )
-            target_users = set([
-                UserID.from_string(x["observed_user_id"]) for x in presence
-            ])
-
-            # Also include people in all my rooms
-
-            room_ids = yield self.get_joined_rooms_for_user(user)
+        if observer_room_ids & observed_room_ids:
+            defer.returnValue(True)
 
-        if state is None:
-            state = yield self.store.get_presence_state(user.localpart)
-        else:
-            # statuscache = self._get_or_make_usercache(user)
-            # self._user_cachemap_latest_serial += 1
-            # statuscache.update(state, self._user_cachemap_latest_serial)
-            pass
-
-        yield self.push_update_to_local_and_remote(
-            observed_user=user,
-            users_to_push=target_users,
-            room_ids=room_ids,
-            statuscache=self._get_or_make_usercache(user),
+        accepted_observers = yield self.store.get_presence_list_observers_accepted(
+            observed_user.to_string()
         )
 
-        for target_user in target_users:
-            if self.hs.is_mine(target_user):
-                self._start_polling_local(user, target_user)
-
-                # We want to tell the person that just came online
-                # presence state of people they are interested in?
-                self.push_update_to_clients(
-                    users_to_push=[user],
-                )
-
-        deferreds = []
-        remote_users = [u for u in target_users if not self.hs.is_mine(u)]
-        remoteusers_by_domain = partition(remote_users, lambda u: u.domain)
-        # Only poll for people in our get_presence_list
-        for domain in remoteusers_by_domain:
-            remoteusers = remoteusers_by_domain[domain]
+        defer.returnValue(observer_user.to_string() in accepted_observers)
 
-            deferreds.append(self._start_polling_remote(
-                user, domain, remoteusers
-            ))
 
-        yield defer.DeferredList(deferreds, consumeErrors=True)
+def should_notify(old_state, new_state):
+    """Decides if a presence state change should be sent to interested parties.
+    """
+    if old_state.status_msg != new_state.status_msg:
+        return True
 
-    def _start_polling_local(self, user, target_user):
-        """Subscribe a local user to presence updates for a local user
+    if old_state.state == PresenceState.ONLINE:
+        if new_state.state != PresenceState.ONLINE:
+            # Always notify for online -> anything
+            return True
 
-        Args:
-            user(UserId): The local user that wishes for updates.
-            target_user(UserId): The local users whose updates are wanted.
-        """
-        target_localpart = target_user.localpart
+        if new_state.currently_active != old_state.currently_active:
+            return True
 
-        if target_localpart not in self._local_pushmap:
-            self._local_pushmap[target_localpart] = set()
+    if new_state.last_active_ts - old_state.last_active_ts > LAST_ACTIVE_GRANULARITY:
+        # Always notify for a transition where last active gets bumped.
+        return True
 
-        self._local_pushmap[target_localpart].add(user)
+    if old_state.state != new_state.state:
+        return True
 
-    def _start_polling_remote(self, user, domain, remoteusers):
-        """Subscribe a local user to presence updates for remote users on a
-        given remote domain.
+    return False
 
-        Args:
-            user(UserID): The local user that wishes for updates.
-            domain(str): The remote server the local user wants updates from.
-            remoteusers(UserID): The remote users that local user wants to be
-                told about.
-        Returns:
-            A Deferred.
-        """
-        to_poll = set()
 
-        for u in remoteusers:
-            if u not in self._remote_recvmap:
-                self._remote_recvmap[u] = set()
-                to_poll.add(u)
+def _format_user_presence_state(state, now):
+    """Convert UserPresenceState to a format that can be sent down to clients
+    and to other servers.
+    """
+    content = {
+        "presence": state.state,
+        "user_id": state.user_id,
+    }
+    if state.last_active_ts:
+        content["last_active_ago"] = now - state.last_active_ts
+    if state.status_msg and state.state != PresenceState.OFFLINE:
+        content["status_msg"] = state.status_msg
+    if state.state == PresenceState.ONLINE:
+        content["currently_active"] = state.currently_active
 
-            self._remote_recvmap[u].add(user)
+    return content
 
-        if not to_poll:
-            return defer.succeed(None)
 
-        return self.federation.send_edu(
-            destination=domain,
-            edu_type="m.presence",
-            content={"poll": [u.to_string() for u in to_poll]}
-        )
+class PresenceEventSource(object):
+    def __init__(self, hs):
+        self.hs = hs
+        self.clock = hs.get_clock()
+        self.store = hs.get_datastore()
 
+    @defer.inlineCallbacks
     @log_function
-    def stop_polling_presence(self, user, target_user=None):
-        """Unsubscribe a local user from presence updates from a local or
-        remote user. If no target user is supplied then unsubscribe the user
-        from all presence updates that the user had subscribed to.
+    def get_new_events(self, user, from_key, room_ids=None, include_offline=True,
+                       **kwargs):
+        # The process for getting presence events are:
+        #  1. Get the rooms the user is in.
+        #  2. Get the list of user in the rooms.
+        #  3. Get the list of users that are in the user's presence list.
+        #  4. If there is a from_key set, cross reference the list of users
+        #     with the `presence_stream_cache` to see which ones we actually
+        #     need to check.
+        #  5. Load current state for the users.
+        #
+        # We don't try and limit the presence updates by the current token, as
+        # sending down the rare duplicate is not a concern.
+
+        user_id = user.to_string()
+        if from_key is not None:
+            from_key = int(from_key)
+        room_ids = room_ids or []
 
-        Args:
-            user(UserID): The local user that no longer wishes for updates.
-            target_user(UserID or None): The user whose updates are no longer
-                wanted.
-        Returns:
-            A Deferred.
-        """
-        logger.debug("Stop polling for presence from %s", user)
+        presence = self.hs.get_handlers().presence_handler
 
-        if not target_user or self.hs.is_mine(target_user):
-            self._stop_polling_local(user, target_user=target_user)
+        if not room_ids:
+            rooms = yield self.store.get_rooms_for_user(user_id)
+            room_ids = set(e.room_id for e in rooms)
 
-        deferreds = []
+        user_ids_to_check = set()
+        for room_id in room_ids:
+            users = yield self.store.get_users_in_room(room_id)
+            user_ids_to_check.update(users)
 
-        if target_user:
-            if target_user not in self._remote_recvmap:
-                return
-            target_users = set([target_user])
-        else:
-            target_users = self._remote_recvmap.keys()
+        plist = yield self.store.get_presence_list_accepted(user.localpart)
+        user_ids_to_check.update([row["observed_user_id"] for row in plist])
 
-        remoteusers = [u for u in target_users
-                       if user in self._remote_recvmap[u]]
-        remoteusers_by_domain = partition(remoteusers, lambda u: u.domain)
+        # Always include yourself. Only really matters for when the user is
+        # not in any rooms, but still.
+        user_ids_to_check.add(user_id)
 
-        for domain in remoteusers_by_domain:
-            remoteusers = remoteusers_by_domain[domain]
+        max_token = self.store.get_current_presence_token()
 
-            deferreds.append(
-                self._stop_polling_remote(user, domain, remoteusers)
+        if from_key:
+            user_ids_changed = self.store.presence_stream_cache.get_entities_changed(
+                user_ids_to_check, from_key,
             )
+        else:
+            user_ids_changed = user_ids_to_check
 
-        return defer.DeferredList(deferreds, consumeErrors=True)
-
-    def _stop_polling_local(self, user, target_user):
-        """Unsubscribe a local user from presence updates from a local user on
-        this server.
-
-        Args:
-            user(UserID): The local user that no longer wishes for updates.
-            target_user(UserID): The user whose updates are no longer wanted.
-        """
-        for localpart in self._local_pushmap.keys():
-            if target_user and localpart != target_user.localpart:
-                continue
-
-            if user in self._local_pushmap[localpart]:
-                self._local_pushmap[localpart].remove(user)
-
-            if not self._local_pushmap[localpart]:
-                del self._local_pushmap[localpart]
-
-    @log_function
-    def _stop_polling_remote(self, user, domain, remoteusers):
-        """Unsubscribe a local user from presence updates from remote users on
-        a given domain.
-
-        Args:
-            user(UserID): The local user that no longer wishes for updates.
-            domain(str): The remote server to unsubscribe from.
-            remoteusers([UserID]): The users on that remote server that the
-                local user no longer wishes to be updated about.
-        Returns:
-            A Deferred.
-        """
-        to_unpoll = set()
-
-        for u in remoteusers:
-            self._remote_recvmap[u].remove(user)
-
-            if not self._remote_recvmap[u]:
-                del self._remote_recvmap[u]
-                to_unpoll.add(u)
-
-        if not to_unpoll:
-            return defer.succeed(None)
-
-        return self.federation.send_edu(
-            destination=domain,
-            edu_type="m.presence",
-            content={"unpoll": [u.to_string() for u in to_unpoll]}
-        )
+        updates = yield presence.current_state_for_users(user_ids_changed)
 
-    @defer.inlineCallbacks
-    @log_function
-    def push_presence(self, user, statuscache):
-        """
-        Notify local and remote users of a change in presence of a local user.
-        Pushes the update to local clients and remote domains that are directly
-        subscribed to the presence of the local user.
-        Also pushes that update to any local user or remote domain that shares
-        a room with the local user.
+        now = self.clock.time_msec()
 
-        Args:
-            user(UserID): The local user whose presence was updated.
-            statuscache(UserPresenceCache): Cache of the user's presence state
-        Returns:
-            A Deferred.
-        """
-        assert(self.hs.is_mine(user))
-
-        logger.debug("Pushing presence update from %s", user)
+        defer.returnValue(([
+            {
+                "type": "m.presence",
+                "content": _format_user_presence_state(s, now),
+            }
+            for s in updates.values()
+            if include_offline or s.state != PresenceState.OFFLINE
+        ], max_token))
 
-        localusers = set(self._local_pushmap.get(user.localpart, set()))
-        remotedomains = set(self._remote_sendmap.get(user.localpart, set()))
+    def get_current_key(self):
+        return self.store.get_current_presence_token()
 
-        # Reflect users' status changes back to themselves, so UIs look nice
-        # and also user is informed of server-forced pushes
-        localusers.add(user)
+    def get_pagination_rows(self, user, pagination_config, key):
+        return self.get_new_events(user, from_key=None, include_offline=False)
 
-        room_ids = yield self.get_joined_rooms_for_user(user)
 
-        if not localusers and not room_ids:
-            defer.returnValue(None)
+def handle_timeouts(user_states, is_mine_fn, user_to_num_current_syncs, now):
+    """Checks the presence of users that have timed out and updates as
+    appropriate.
 
-        yield self.push_update_to_local_and_remote(
-            observed_user=user,
-            users_to_push=localusers,
-            remote_domains=remotedomains,
-            room_ids=room_ids,
-            statuscache=statuscache,
-        )
-        yield user_presence_changed(self.distributor, user, statuscache)
+    Args:
+        user_states(list): List of UserPresenceState's to check.
+        is_mine_fn (fn): Function that returns if a user_id is ours
+        user_to_num_current_syncs (dict): Mapping of user_id to number of currently
+            active syncs.
+        now (int): Current time in ms.
 
-    @defer.inlineCallbacks
-    def incoming_presence(self, origin, content):
-        """Handle an incoming m.presence EDU.
-        For each presence update in the "push" list update our local cache and
-        notify the appropriate local clients. Only clients that share a room
-        or are directly subscribed to the presence for a user should be
-        notified of the update.
-        For each subscription request in the "poll" list start pushing presence
-        updates to the remote server.
-        For unsubscribe request in the "unpoll" list stop pushing presence
-        updates to the remote server.
+    Returns:
+        List of UserPresenceState updates
+    """
+    changes = {}  # Actual changes we need to notify people about
 
-        Args:
-            orgin(str): The source of this m.presence EDU.
-            content(dict): The content of this m.presence EDU.
-        Returns:
-            A Deferred.
-        """
-        deferreds = []
+    for state in user_states:
+        is_mine = is_mine_fn(state.user_id)
 
-        for push in content.get("push", []):
-            user = UserID.from_string(push["user_id"])
+        new_state = handle_timeout(state, is_mine, user_to_num_current_syncs, now)
+        if new_state:
+            changes[state.user_id] = new_state
 
-            logger.debug("Incoming presence update from %s", user)
+    return changes.values()
 
-            observers = set(self._remote_recvmap.get(user, set()))
-            if observers:
-                logger.debug(
-                    " | %d interested local observers %r", len(observers), observers
-                )
 
-            room_ids = yield self.get_joined_rooms_for_user(user)
-            if room_ids:
-                logger.debug(" | %d interested room IDs %r", len(room_ids), room_ids)
+def handle_timeout(state, is_mine, user_to_num_current_syncs, now):
+    """Checks the presence of the user to see if any of the timers have elapsed
 
-            state = dict(push)
-            del state["user_id"]
+    Args:
+        state (UserPresenceState)
+        is_mine (bool): Whether the user is ours
+        user_to_num_current_syncs (dict): Mapping of user_id to number of currently
+            active syncs.
+        now (int): Current time in ms.
 
-            if "presence" not in state:
-                logger.warning(
-                    "Received a presence 'push' EDU from %s without a"
-                    " 'presence' key", origin
+    Returns:
+        A UserPresenceState update or None if no update.
+    """
+    if state.state == PresenceState.OFFLINE:
+        # No timeouts are associated with offline states.
+        return None
+
+    changed = False
+    user_id = state.user_id
+
+    if is_mine:
+        if state.state == PresenceState.ONLINE:
+            if now - state.last_active_ts > IDLE_TIMER:
+                # Currently online, but last activity ages ago so auto
+                # idle
+                state = state.copy_and_replace(
+                    state=PresenceState.UNAVAILABLE,
                 )
-                continue
-
-            if "last_active_ago" in state:
-                state["last_active"] = int(
-                    self.clock.time_msec() - state.pop("last_active_ago")
+                changed = True
+            elif now - state.last_active_ts > LAST_ACTIVE_GRANULARITY:
+                # So that we send down a notification that we've
+                # stopped updating.
+                changed = True
+
+        if now - state.last_federation_update_ts > FEDERATION_PING_INTERVAL:
+            # Need to send ping to other servers to ensure they don't
+            # timeout and set us to offline
+            changed = True
+
+        # If there are have been no sync for a while (and none ongoing),
+        # set presence to offline
+        if not user_to_num_current_syncs.get(user_id, 0):
+            if now - state.last_user_sync_ts > SYNC_ONLINE_TIMEOUT:
+                state = state.copy_and_replace(
+                    state=PresenceState.OFFLINE,
+                    status_msg=None,
                 )
-
-            self._user_cachemap_latest_serial += 1
-            yield self.update_presence_cache(user, state, room_ids=room_ids)
-
-            if not observers and not room_ids:
-                logger.debug(" | no interested observers or room IDs")
-                continue
-
-            self.push_update_to_clients(
-                users_to_push=observers, room_ids=room_ids
+                changed = True
+    else:
+        # We expect to be poked occaisonally by the other side.
+        # This is to protect against forgetful/buggy servers, so that
+        # no one gets stuck online forever.
+        if now - state.last_federation_update_ts > FEDERATION_TIMEOUT:
+            # The other side seems to have disappeared.
+            state = state.copy_and_replace(
+                state=PresenceState.OFFLINE,
+                status_msg=None,
             )
+            changed = True
 
-            user_id = user.to_string()
-
-            if state["presence"] == PresenceState.OFFLINE:
-                self._remote_offline_serials.insert(
-                    0,
-                    (self._user_cachemap_latest_serial, set([user_id]))
-                )
-                while len(self._remote_offline_serials) > MAX_OFFLINE_SERIALS:
-                    self._remote_offline_serials.pop()  # remove the oldest
-                if user in self._user_cachemap:
-                    del self._user_cachemap[user]
-            else:
-                # Remove the user from remote_offline_serials now that they're
-                # no longer offline
-                for idx, elem in enumerate(self._remote_offline_serials):
-                    (_, user_ids) = elem
-                    user_ids.discard(user_id)
-                    if not user_ids:
-                        self._remote_offline_serials.pop(idx)
-
-        for poll in content.get("poll", []):
-            user = UserID.from_string(poll)
-
-            if not self.hs.is_mine(user):
-                continue
-
-            # TODO(paul) permissions checks
-
-            if user not in self._remote_sendmap:
-                self._remote_sendmap[user] = set()
-
-            self._remote_sendmap[user].add(origin)
-
-            deferreds.append(self._push_presence_remote(user, origin))
-
-        for unpoll in content.get("unpoll", []):
-            user = UserID.from_string(unpoll)
-
-            if not self.hs.is_mine(user):
-                continue
-
-            if user in self._remote_sendmap:
-                self._remote_sendmap[user].remove(origin)
-
-                if not self._remote_sendmap[user]:
-                    del self._remote_sendmap[user]
-
-        yield defer.DeferredList(deferreds, consumeErrors=True)
-
-    @defer.inlineCallbacks
-    def update_presence_cache(self, user, state={}, room_ids=None,
-                              add_to_cache=True):
-        """Update the presence cache for a user with a new state and bump the
-        serial to the latest value.
-
-        Args:
-            user(UserID): The user being updated
-            state(dict): The presence state being updated
-            room_ids(None or list of str): A list of room_ids to update. If
-                room_ids is None then fetch the list of room_ids the user is
-                joined to.
-            add_to_cache: Whether to add an entry to the presence cache if the
-                user isn't already in the cache.
-        Returns:
-            A Deferred UserPresenceCache for the user being updated.
-        """
-        if room_ids is None:
-            room_ids = yield self.get_joined_rooms_for_user(user)
-
-        for room_id in room_ids:
-            self._room_serials[room_id] = self._user_cachemap_latest_serial
-        if add_to_cache:
-            statuscache = self._get_or_make_usercache(user)
-        else:
-            statuscache = self._get_or_offline_usercache(user)
-        statuscache.update(state, serial=self._user_cachemap_latest_serial)
-        defer.returnValue(statuscache)
-
-    @defer.inlineCallbacks
-    def push_update_to_local_and_remote(self, observed_user, statuscache,
-                                        users_to_push=[], room_ids=[],
-                                        remote_domains=[]):
-        """Notify local clients and remote servers of a change in the presence
-        of a user.
-
-        Args:
-            observed_user(UserID): The user to push the presence state for.
-            statuscache(UserPresenceCache): The cache for the presence state to
-                push.
-            users_to_push([UserID]): A list of local and remote users to
-                notify.
-            room_ids([str]): Notify the local and remote occupants of these
-                rooms.
-            remote_domains([str]): A list of remote servers to notify in
-                addition to those implied by the users_to_push and the
-                room_ids.
-        Returns:
-            A Deferred.
-        """
-
-        localusers, remoteusers = partitionbool(
-            users_to_push,
-            lambda u: self.hs.is_mine(u)
-        )
+    return state if changed else None
 
-        localusers = set(localusers)
 
-        self.push_update_to_clients(
-            users_to_push=localusers, room_ids=room_ids
-        )
+def handle_update(prev_state, new_state, is_mine, wheel_timer, now):
+    """Given a presence update:
+        1. Add any appropriate timers.
+        2. Check if we should notify anyone.
 
-        remote_domains = set(remote_domains)
-        remote_domains |= set([r.domain for r in remoteusers])
-        for room_id in room_ids:
-            remote_domains.update(
-                (yield self.store.get_joined_hosts_for_room(room_id))
-            )
+    Args:
+        prev_state (UserPresenceState)
+        new_state (UserPresenceState)
+        is_mine (bool): Whether the user is ours
+        wheel_timer (WheelTimer)
+        now (int): Time now in ms
 
-        remote_domains.discard(self.hs.hostname)
-
-        deferreds = []
-        for domain in remote_domains:
-            logger.debug(" | push to remote domain %s", domain)
-            deferreds.append(
-                self._push_presence_remote(
-                    observed_user, domain, state=statuscache.get_state()
-                )
+    Returns:
+        3-tuple: `(new_state, persist_and_notify, federation_ping)` where:
+            - new_state: is the state to actually persist
+            - persist_and_notify (bool): whether to persist and notify people
+            - federation_ping (bool): whether we should send a ping over federation
+    """
+    user_id = new_state.user_id
+
+    persist_and_notify = False
+    federation_ping = False
+
+    # If the users are ours then we want to set up a bunch of timers
+    # to time things out.
+    if is_mine:
+        if new_state.state == PresenceState.ONLINE:
+            # Idle timer
+            wheel_timer.insert(
+                now=now,
+                obj=user_id,
+                then=new_state.last_active_ts + IDLE_TIMER
             )
 
-        yield defer.DeferredList(deferreds, consumeErrors=True)
-
-        defer.returnValue((localusers, remote_domains))
-
-    def push_update_to_clients(self, users_to_push=[], room_ids=[]):
-        """Notify clients of a new presence event.
-
-        Args:
-            users_to_push([UserID]): List of users to notify.
-            room_ids([str]): List of room_ids to notify.
-        """
-        with PreserveLoggingContext():
-            self.notifier.on_new_event(
-                "presence_key",
-                self._user_cachemap_latest_serial,
-                users_to_push,
-                room_ids,
+        if new_state.state != PresenceState.OFFLINE:
+            # User has stopped syncing
+            wheel_timer.insert(
+                now=now,
+                obj=user_id,
+                then=new_state.last_user_sync_ts + SYNC_ONLINE_TIMEOUT
             )
 
-    @defer.inlineCallbacks
-    def _push_presence_remote(self, user, destination, state=None):
-        """Push a user's presence to a remote server. If a presence state event
-        that event is sent. Otherwise a new state event is constructed from the
-        stored presence state.
-        The last_active is replaced with last_active_ago in case the wallclock
-        time on the remote server is different to the time on this server.
-        Sends an EDU to the remote server with the current presence state.
-
-        Args:
-            user(UserID): The user to push the presence state for.
-            destination(str): The remote server to send state to.
-            state(dict): The state to push, or None to use the current stored
-                state.
-        Returns:
-            A Deferred.
-        """
-        if state is None:
-            state = yield self.store.get_presence_state(user.localpart)
-            del state["mtime"]
-            state["presence"] = state.pop("state")
-
-            if user in self._user_cachemap:
-                state["last_active"] = (
-                    self._user_cachemap[user].get_state()["last_active"]
+            last_federate = new_state.last_federation_update_ts
+            if now - last_federate > FEDERATION_PING_INTERVAL:
+                # Been a while since we've poked remote servers
+                new_state = new_state.copy_and_replace(
+                    last_federation_update_ts=now,
                 )
+                federation_ping = True
 
-            yield collect_presencelike_data(self.distributor, user, state)
-
-        if "last_active" in state:
-            state = dict(state)
-            state["last_active_ago"] = int(
-                self.clock.time_msec() - state.pop("last_active")
-            )
-
-        user_state = {"user_id": user.to_string(), }
-        user_state.update(state)
-
-        yield self.federation.send_edu(
-            destination=destination,
-            edu_type="m.presence",
-            content={"push": [user_state, ], }
+    else:
+        wheel_timer.insert(
+            now=now,
+            obj=user_id,
+            then=new_state.last_federation_update_ts + FEDERATION_TIMEOUT
         )
 
-
-class PresenceEventSource(object):
-    def __init__(self, hs):
-        self.hs = hs
-        self.clock = hs.get_clock()
-
-    @defer.inlineCallbacks
-    @log_function
-    def get_new_events(self, user, from_key, room_ids=None, **kwargs):
-        from_key = int(from_key)
-        room_ids = room_ids or []
-
-        presence = self.hs.get_handlers().presence_handler
-        cachemap = presence._user_cachemap
-
-        max_serial = presence._user_cachemap_latest_serial
-
-        clock = self.clock
-        latest_serial = 0
-
-        user_ids_to_check = {user}
-        presence_list = yield presence.store.get_presence_list(
-            user.localpart, accepted=True
+    if new_state.state == PresenceState.ONLINE:
+        active = now - new_state.last_active_ts < LAST_ACTIVE_GRANULARITY
+        new_state = new_state.copy_and_replace(
+            currently_active=active,
         )
-        if presence_list is not None:
-            user_ids_to_check |= set(
-                UserID.from_string(p["observed_user_id"]) for p in presence_list
-            )
-        for room_id in set(room_ids) & set(presence._room_serials):
-            if presence._room_serials[room_id] > from_key:
-                joined = yield presence.get_joined_users_for_room_id(room_id)
-                user_ids_to_check |= set(joined)
 
-        updates = []
-        for observed_user in user_ids_to_check & set(cachemap):
-            cached = cachemap[observed_user]
-
-            if cached.serial <= from_key or cached.serial > max_serial:
-                continue
-
-            latest_serial = max(cached.serial, latest_serial)
-            updates.append(cached.make_event(user=observed_user, clock=clock))
-
-        # TODO(paul): limit
-
-        for serial, user_ids in presence._remote_offline_serials:
-            if serial <= from_key:
-                break
-
-            if serial > max_serial:
-                continue
-
-            latest_serial = max(latest_serial, serial)
-            for u in user_ids:
-                updates.append({
-                    "type": "m.presence",
-                    "content": {"user_id": u, "presence": PresenceState.OFFLINE},
-                })
-        # TODO(paul): For the v2 API we want to tell the client their from_key
-        #   is too old if we fell off the end of the _remote_offline_serials
-        #   list, and get them to invalidate+resync. In v1 we have no such
-        #   concept so this is a best-effort result.
-
-        if updates:
-            defer.returnValue((updates, latest_serial))
-        else:
-            defer.returnValue(([], presence._user_cachemap_latest_serial))
-
-    def get_current_key(self):
-        presence = self.hs.get_handlers().presence_handler
-        return presence._user_cachemap_latest_serial
-
-    @defer.inlineCallbacks
-    def get_pagination_rows(self, user, pagination_config, key):
-        # TODO (erikj): Does this make sense? Ordering?
-
-        from_key = int(pagination_config.from_key)
-
-        if pagination_config.to_key:
-            to_key = int(pagination_config.to_key)
-        else:
-            to_key = -1
-
-        presence = self.hs.get_handlers().presence_handler
-        cachemap = presence._user_cachemap
-
-        user_ids_to_check = {user}
-        presence_list = yield presence.store.get_presence_list(
-            user.localpart, accepted=True
-        )
-        if presence_list is not None:
-            user_ids_to_check |= set(
-                UserID.from_string(p["observed_user_id"]) for p in presence_list
-            )
-        room_ids = yield presence.get_joined_rooms_for_user(user)
-        for room_id in set(room_ids) & set(presence._room_serials):
-            if presence._room_serials[room_id] >= from_key:
-                joined = yield presence.get_joined_users_for_room_id(room_id)
-                user_ids_to_check |= set(joined)
-
-        updates = []
-        for observed_user in user_ids_to_check & set(cachemap):
-            if not (to_key < cachemap[observed_user].serial <= from_key):
-                continue
-
-            updates.append((observed_user, cachemap[observed_user]))
-
-        # TODO(paul): limit
-
-        if updates:
-            clock = self.clock
-
-            earliest_serial = max([x[1].serial for x in updates])
-            data = [x[1].make_event(user=x[0], clock=clock) for x in updates]
-
-            defer.returnValue((data, earliest_serial))
-        else:
-            defer.returnValue(([], 0))
-
-
-class UserPresenceCache(object):
-    """Store an observed user's state and status message.
-
-    Includes the update timestamp.
-    """
-    def __init__(self):
-        self.state = {"presence": PresenceState.OFFLINE}
-        self.serial = None
-
-    def __repr__(self):
-        return "UserPresenceCache(state=%r, serial=%r)" % (
-            self.state, self.serial
+    # Check whether the change was something worth notifying about
+    if should_notify(prev_state, new_state):
+        new_state = new_state.copy_and_replace(
+            last_federation_update_ts=now,
         )
+        persist_and_notify = True
 
-    def update(self, state, serial):
-        assert("mtime_age" not in state)
-
-        self.state.update(state)
-        # Delete keys that are now 'None'
-        for k in self.state.keys():
-            if self.state[k] is None:
-                del self.state[k]
-
-        self.serial = serial
-
-        if "status_msg" in state:
-            self.status_msg = state["status_msg"]
-        else:
-            self.status_msg = None
-
-    def get_state(self):
-        # clone it so caller can't break our cache
-        state = dict(self.state)
-        return state
-
-    def make_event(self, user, clock):
-        content = self.get_state()
-        content["user_id"] = user.to_string()
-
-        if "last_active" in content:
-            content["last_active_ago"] = int(
-                clock.time_msec() - content.pop("last_active")
-            )
-
-        return {"type": "m.presence", "content": content}
+    return new_state, persist_and_notify, federation_ping
diff --git a/synapse/handlers/profile.py b/synapse/handlers/profile.py
index f3e73d926e..c9ad5944e6 100644
--- a/synapse/handlers/profile.py
+++ b/synapse/handlers/profile.py
@@ -48,6 +48,9 @@ class ProfileHandler(BaseHandler):
         distributor = hs.get_distributor()
         self.distributor = distributor
 
+        distributor.declare("collect_presencelike_data")
+        distributor.declare("changed_presencelike_data")
+
         distributor.observe("registered_user", self.registered_user)
 
         distributor.observe(
diff --git a/synapse/handlers/sync.py b/synapse/handlers/sync.py
index b2b9b928c9..efeec72fd8 100644
--- a/synapse/handlers/sync.py
+++ b/synapse/handlers/sync.py
@@ -582,6 +582,28 @@ class SyncHandler(BaseHandler):
             if room_sync:
                 joined.append(room_sync)
 
+        # For each newly joined room, we want to send down presence of
+        # existing users.
+        presence_handler = self.hs.get_handlers().presence_handler
+        extra_presence_users = set()
+        for room_id in newly_joined_rooms:
+            users = yield self.store.get_users_in_room(event.room_id)
+            extra_presence_users.update(users)
+
+        # For each new member, send down presence.
+        for joined_sync in joined:
+            it = itertools.chain(joined_sync.timeline.events, joined_sync.state.values())
+            for event in it:
+                if event.type == EventTypes.Member:
+                    if event.membership == Membership.JOIN:
+                        extra_presence_users.add(event.state_key)
+
+        states = yield presence_handler.get_states(
+            [u for u in extra_presence_users if u != user_id],
+            as_event=True,
+        )
+        presence.extend(states)
+
         account_data_for_user = sync_config.filter_collection.filter_account_data(
             self.account_data_for_user(account_data)
         )
diff --git a/synapse/rest/client/v1/presence.py b/synapse/rest/client/v1/presence.py
index a6f8754e32..bbfa1d6ac4 100644
--- a/synapse/rest/client/v1/presence.py
+++ b/synapse/rest/client/v1/presence.py
@@ -17,7 +17,7 @@
 """
 from twisted.internet import defer
 
-from synapse.api.errors import SynapseError
+from synapse.api.errors import SynapseError, AuthError
 from synapse.types import UserID
 from .base import ClientV1RestServlet, client_path_patterns
 
@@ -35,8 +35,15 @@ class PresenceStatusRestServlet(ClientV1RestServlet):
         requester = yield self.auth.get_user_by_req(request)
         user = UserID.from_string(user_id)
 
-        state = yield self.handlers.presence_handler.get_state(
-            target_user=user, auth_user=requester.user)
+        if requester.user != user:
+            allowed = yield self.handlers.presence_handler.is_visible(
+                observed_user=user, observer_user=requester.user,
+            )
+
+            if not allowed:
+                raise AuthError(403, "You are not allowed to see their presence.")
+
+        state = yield self.handlers.presence_handler.get_state(target_user=user)
 
         defer.returnValue((200, state))
 
@@ -45,6 +52,9 @@ class PresenceStatusRestServlet(ClientV1RestServlet):
         requester = yield self.auth.get_user_by_req(request)
         user = UserID.from_string(user_id)
 
+        if requester.user != user:
+            raise AuthError(403, "Can only set your own presence state")
+
         state = {}
         try:
             content = json.loads(request.content.read())
@@ -63,8 +73,7 @@ class PresenceStatusRestServlet(ClientV1RestServlet):
         except:
             raise SynapseError(400, "Unable to parse state")
 
-        yield self.handlers.presence_handler.set_state(
-            target_user=user, auth_user=requester.user, state=state)
+        yield self.handlers.presence_handler.set_state(user, state)
 
         defer.returnValue((200, {}))
 
@@ -87,11 +96,8 @@ class PresenceListRestServlet(ClientV1RestServlet):
             raise SynapseError(400, "Cannot get another user's presence list")
 
         presence = yield self.handlers.presence_handler.get_presence_list(
-            observer_user=user, accepted=True)
-
-        for p in presence:
-            observed_user = p.pop("observed_user")
-            p["user_id"] = observed_user.to_string()
+            observer_user=user, accepted=True
+        )
 
         defer.returnValue((200, presence))
 
diff --git a/synapse/rest/client/v1/room.py b/synapse/rest/client/v1/room.py
index cf7fcb04ff..e6f5c5614a 100644
--- a/synapse/rest/client/v1/room.py
+++ b/synapse/rest/client/v1/room.py
@@ -298,18 +298,6 @@ class RoomMemberListRestServlet(ClientV1RestServlet):
             if event["type"] != EventTypes.Member:
                 continue
             chunk.append(event)
-            # FIXME: should probably be state_key here, not user_id
-            target_user = UserID.from_string(event["user_id"])
-            # Presence is an optional cache; don't fail if we can't fetch it
-            try:
-                presence_handler = self.handlers.presence_handler
-                presence_state = yield presence_handler.get_state(
-                    target_user=target_user,
-                    auth_user=requester.user,
-                )
-                event["content"].update(presence_state)
-            except:
-                pass
 
         defer.returnValue((200, {
             "chunk": chunk
@@ -535,6 +523,10 @@ class RoomTypingRestServlet(ClientV1RestServlet):
         "/rooms/(?P<room_id>[^/]*)/typing/(?P<user_id>[^/]*)$"
     )
 
+    def __init__(self, hs):
+        super(RoomTypingRestServlet, self).__init__(hs)
+        self.presence_handler = hs.get_handlers().presence_handler
+
     @defer.inlineCallbacks
     def on_PUT(self, request, room_id, user_id):
         requester = yield self.auth.get_user_by_req(request)
@@ -546,6 +538,8 @@ class RoomTypingRestServlet(ClientV1RestServlet):
 
         typing_handler = self.handlers.typing_notification_handler
 
+        yield self.presence_handler.bump_presence_active_time(requester.user)
+
         if content["typing"]:
             yield typing_handler.started_typing(
                 target_user=target_user,
diff --git a/synapse/rest/client/v2_alpha/receipts.py b/synapse/rest/client/v2_alpha/receipts.py
index eb4b369a3d..b831d8c95e 100644
--- a/synapse/rest/client/v2_alpha/receipts.py
+++ b/synapse/rest/client/v2_alpha/receipts.py
@@ -37,6 +37,7 @@ class ReceiptRestServlet(RestServlet):
         self.hs = hs
         self.auth = hs.get_auth()
         self.receipts_handler = hs.get_handlers().receipts_handler
+        self.presence_handler = hs.get_handlers().presence_handler
 
     @defer.inlineCallbacks
     def on_POST(self, request, room_id, receipt_type, event_id):
@@ -45,6 +46,8 @@ class ReceiptRestServlet(RestServlet):
         if receipt_type != "m.read":
             raise SynapseError(400, "Receipt type must be 'm.read'")
 
+        yield self.presence_handler.bump_presence_active_time(requester.user)
+
         yield self.receipts_handler.received_client_receipt(
             room_id,
             receipt_type,
diff --git a/synapse/rest/client/v2_alpha/sync.py b/synapse/rest/client/v2_alpha/sync.py
index accbc6cfac..de4a020ad4 100644
--- a/synapse/rest/client/v2_alpha/sync.py
+++ b/synapse/rest/client/v2_alpha/sync.py
@@ -25,6 +25,7 @@ from synapse.events.utils import (
 )
 from synapse.api.filtering import FilterCollection, DEFAULT_FILTER_COLLECTION
 from synapse.api.errors import SynapseError
+from synapse.api.constants import PresenceState
 from ._base import client_v2_patterns
 
 import copy
@@ -82,6 +83,7 @@ class SyncRestServlet(RestServlet):
         self.sync_handler = hs.get_handlers().sync_handler
         self.clock = hs.get_clock()
         self.filtering = hs.get_filtering()
+        self.presence_handler = hs.get_handlers().presence_handler
 
     @defer.inlineCallbacks
     def on_GET(self, request):
@@ -139,17 +141,19 @@ class SyncRestServlet(RestServlet):
         else:
             since_token = None
 
-        if set_presence == "online":
-            yield self.event_stream_handler.started_stream(user)
+        affect_presence = set_presence != PresenceState.OFFLINE
 
-        try:
+        if affect_presence:
+            yield self.presence_handler.set_state(user, {"presence": set_presence})
+
+        context = yield self.presence_handler.user_syncing(
+            user.to_string(), affect_presence=affect_presence,
+        )
+        with context:
             sync_result = yield self.sync_handler.wait_for_sync_for_user(
                 sync_config, since_token=since_token, timeout=timeout,
                 full_state=full_state
             )
-        finally:
-            if set_presence == "online":
-                self.event_stream_handler.stopped_stream(user)
 
         time_now = self.clock.time_msec()
 
diff --git a/synapse/storage/__init__.py b/synapse/storage/__init__.py
index 5a9e7720d9..9be1d12fac 100644
--- a/synapse/storage/__init__.py
+++ b/synapse/storage/__init__.py
@@ -20,7 +20,7 @@ from .appservice import (
 from ._base import Cache
 from .directory import DirectoryStore
 from .events import EventsStore
-from .presence import PresenceStore
+from .presence import PresenceStore, UserPresenceState
 from .profile import ProfileStore
 from .registration import RegistrationStore
 from .room import RoomStore
@@ -47,6 +47,7 @@ from .account_data import AccountDataStore
 
 from util.id_generators import IdGenerator, StreamIdGenerator
 
+from synapse.api.constants import PresenceState
 from synapse.util.caches.stream_change_cache import StreamChangeCache
 
 
@@ -110,6 +111,9 @@ class DataStore(RoomMemberStore, RoomStore,
         self._account_data_id_gen = StreamIdGenerator(
             db_conn, "account_data_max_stream_id", "stream_id"
         )
+        self._presence_id_gen = StreamIdGenerator(
+            db_conn, "presence_stream", "stream_id"
+        )
 
         self._transaction_id_gen = IdGenerator("sent_transactions", "id", self)
         self._state_groups_id_gen = IdGenerator("state_groups", "id", self)
@@ -119,7 +123,7 @@ class DataStore(RoomMemberStore, RoomStore,
         self._push_rule_id_gen = IdGenerator("push_rules", "id", self)
         self._push_rules_enable_id_gen = IdGenerator("push_rules_enable", "id", self)
 
-        events_max = self._stream_id_gen.get_max_token(None)
+        events_max = self._stream_id_gen.get_max_token()
         event_cache_prefill, min_event_val = self._get_cache_dict(
             db_conn, "events",
             entity_column="room_id",
@@ -135,13 +139,31 @@ class DataStore(RoomMemberStore, RoomStore,
             "MembershipStreamChangeCache", events_max,
         )
 
-        account_max = self._account_data_id_gen.get_max_token(None)
+        account_max = self._account_data_id_gen.get_max_token()
         self._account_data_stream_cache = StreamChangeCache(
             "AccountDataAndTagsChangeCache", account_max,
         )
 
+        self.__presence_on_startup = self._get_active_presence(db_conn)
+
+        presence_cache_prefill, min_presence_val = self._get_cache_dict(
+            db_conn, "presence_stream",
+            entity_column="user_id",
+            stream_column="stream_id",
+            max_value=self._presence_id_gen.get_max_token(),
+        )
+        self.presence_stream_cache = StreamChangeCache(
+            "PresenceStreamChangeCache", min_presence_val,
+            prefilled_cache=presence_cache_prefill
+        )
+
         super(DataStore, self).__init__(hs)
 
+    def take_presence_startup_info(self):
+        active_on_startup = self.__presence_on_startup
+        self.__presence_on_startup = None
+        return active_on_startup
+
     def _get_cache_dict(self, db_conn, table, entity_column, stream_column, max_value):
         # Fetch a mapping of room_id -> max stream position for "recent" rooms.
         # It doesn't really matter how many we get, the StreamChangeCache will
@@ -161,6 +183,7 @@ class DataStore(RoomMemberStore, RoomStore,
         txn = db_conn.cursor()
         txn.execute(sql, (int(max_value),))
         rows = txn.fetchall()
+        txn.close()
 
         cache = {
             row[0]: int(row[1])
@@ -174,6 +197,28 @@ class DataStore(RoomMemberStore, RoomStore,
 
         return cache, min_val
 
+    def _get_active_presence(self, db_conn):
+        """Fetch non-offline presence from the database so that we can register
+        the appropriate time outs.
+        """
+
+        sql = (
+            "SELECT user_id, state, last_active_ts, last_federation_update_ts,"
+            " last_user_sync_ts, status_msg, currently_active FROM presence_stream"
+            " WHERE state != ?"
+        )
+        sql = self.database_engine.convert_param_style(sql)
+
+        txn = db_conn.cursor()
+        txn.execute(sql, (PresenceState.OFFLINE,))
+        rows = self.cursor_to_dict(txn)
+        txn.close()
+
+        for row in rows:
+            row["currently_active"] = bool(row["currently_active"])
+
+        return [UserPresenceState(**row) for row in rows]
+
     @defer.inlineCallbacks
     def insert_client_ip(self, user, access_token, ip, user_agent):
         now = int(self._clock.time_msec())
diff --git a/synapse/storage/account_data.py b/synapse/storage/account_data.py
index b8387fc500..91cbf399b6 100644
--- a/synapse/storage/account_data.py
+++ b/synapse/storage/account_data.py
@@ -168,7 +168,7 @@ class AccountDataStore(SQLBaseStore):
                 "add_room_account_data", add_account_data_txn, next_id
             )
 
-        result = yield self._account_data_id_gen.get_max_token(self)
+        result = yield self._account_data_id_gen.get_max_token()
         defer.returnValue(result)
 
     @defer.inlineCallbacks
@@ -207,7 +207,7 @@ class AccountDataStore(SQLBaseStore):
                 "add_user_account_data", add_account_data_txn, next_id
             )
 
-        result = yield self._account_data_id_gen.get_max_token(self)
+        result = yield self._account_data_id_gen.get_max_token()
         defer.returnValue(result)
 
     def _update_max_stream_id(self, txn, next_id):
diff --git a/synapse/storage/events.py b/synapse/storage/events.py
index 3a5c6ee4b1..1dd3236829 100644
--- a/synapse/storage/events.py
+++ b/synapse/storage/events.py
@@ -131,7 +131,7 @@ class EventsStore(SQLBaseStore):
         except _RollbackButIsFineException:
             pass
 
-        max_persisted_id = yield self._stream_id_gen.get_max_token(self)
+        max_persisted_id = yield self._stream_id_gen.get_max_token()
         defer.returnValue((stream_ordering, max_persisted_id))
 
     @defer.inlineCallbacks
diff --git a/synapse/storage/prepare_database.py b/synapse/storage/prepare_database.py
index 850736c85e..0fd5d497ab 100644
--- a/synapse/storage/prepare_database.py
+++ b/synapse/storage/prepare_database.py
@@ -25,7 +25,7 @@ logger = logging.getLogger(__name__)
 
 # Remember to update this number every time a change is made to database
 # schema files, so the users will be informed on server restarts.
-SCHEMA_VERSION = 29
+SCHEMA_VERSION = 30
 
 dir_path = os.path.abspath(os.path.dirname(__file__))
 
diff --git a/synapse/storage/presence.py b/synapse/storage/presence.py
index ef525f34c5..70ece56548 100644
--- a/synapse/storage/presence.py
+++ b/synapse/storage/presence.py
@@ -14,73 +14,129 @@
 # limitations under the License.
 
 from ._base import SQLBaseStore
-from synapse.util.caches.descriptors import cached, cachedList
+from synapse.api.constants import PresenceState
+from synapse.util.caches.descriptors import cached, cachedInlineCallbacks
 
+from collections import namedtuple
 from twisted.internet import defer
 
 
-class PresenceStore(SQLBaseStore):
-    def create_presence(self, user_localpart):
-        res = self._simple_insert(
-            table="presence",
-            values={"user_id": user_localpart},
-            desc="create_presence",
+class UserPresenceState(namedtuple("UserPresenceState",
+                        ("user_id", "state", "last_active_ts",
+                            "last_federation_update_ts", "last_user_sync_ts",
+                            "status_msg", "currently_active"))):
+    """Represents the current presence state of the user.
+
+    user_id (str)
+    last_active (int): Time in msec that the user last interacted with server.
+    last_federation_update (int): Time in msec since either a) we sent a presence
+        update to other servers or b) we received a presence update, depending
+        on if is a local user or not.
+    last_user_sync (int): Time in msec that the user last *completed* a sync
+        (or event stream).
+    status_msg (str): User set status message.
+    """
+
+    def copy_and_replace(self, **kwargs):
+        return self._replace(**kwargs)
+
+    @classmethod
+    def default(cls, user_id):
+        """Returns a default presence state.
+        """
+        return cls(
+            user_id=user_id,
+            state=PresenceState.OFFLINE,
+            last_active_ts=0,
+            last_federation_update_ts=0,
+            last_user_sync_ts=0,
+            status_msg=None,
+            currently_active=False,
         )
 
-        self.get_presence_state.invalidate((user_localpart,))
-        return res
 
-    def has_presence_state(self, user_localpart):
-        return self._simple_select_one(
-            table="presence",
-            keyvalues={"user_id": user_localpart},
-            retcols=["user_id"],
-            allow_none=True,
-            desc="has_presence_state",
+class PresenceStore(SQLBaseStore):
+    @defer.inlineCallbacks
+    def update_presence(self, presence_states):
+        stream_id_manager = yield self._presence_id_gen.get_next(self)
+        with stream_id_manager as stream_id:
+            yield self.runInteraction(
+                "update_presence",
+                self._update_presence_txn, stream_id, presence_states,
+            )
+
+        defer.returnValue((stream_id, self._presence_id_gen.get_max_token()))
+
+    def _update_presence_txn(self, txn, stream_id, presence_states):
+        for state in presence_states:
+            txn.call_after(
+                self.presence_stream_cache.entity_has_changed,
+                state.user_id, stream_id,
+            )
+
+        # Actually insert new rows
+        self._simple_insert_many_txn(
+            txn,
+            table="presence_stream",
+            values=[
+                {
+                    "stream_id": stream_id,
+                    "user_id": state.user_id,
+                    "state": state.state,
+                    "last_active_ts": state.last_active_ts,
+                    "last_federation_update_ts": state.last_federation_update_ts,
+                    "last_user_sync_ts": state.last_user_sync_ts,
+                    "status_msg": state.status_msg,
+                    "currently_active": state.currently_active,
+                }
+                for state in presence_states
+            ],
         )
 
-    @cached(max_entries=2000)
-    def get_presence_state(self, user_localpart):
-        return self._simple_select_one(
-            table="presence",
-            keyvalues={"user_id": user_localpart},
-            retcols=["state", "status_msg", "mtime"],
-            desc="get_presence_state",
+        # Delete old rows to stop database from getting really big
+        sql = (
+            "DELETE FROM presence_stream WHERE"
+            " stream_id < ?"
+            " AND user_id IN (%s)"
         )
 
-    @cachedList(get_presence_state.cache, list_name="user_localparts",
-                inlineCallbacks=True)
-    def get_presence_states(self, user_localparts):
+        batches = (
+            presence_states[i:i + 50]
+            for i in xrange(0, len(presence_states), 50)
+        )
+        for states in batches:
+            args = [stream_id]
+            args.extend(s.user_id for s in states)
+            txn.execute(
+                sql % (",".join("?" for _ in states),),
+                args
+            )
+
+    @defer.inlineCallbacks
+    def get_presence_for_users(self, user_ids):
         rows = yield self._simple_select_many_batch(
-            table="presence",
+            table="presence_stream",
             column="user_id",
-            iterable=user_localparts,
-            retcols=("user_id", "state", "status_msg", "mtime",),
-            desc="get_presence_states",
+            iterable=user_ids,
+            keyvalues={},
+            retcols=(
+                "user_id",
+                "state",
+                "last_active_ts",
+                "last_federation_update_ts",
+                "last_user_sync_ts",
+                "status_msg",
+                "currently_active",
+            ),
         )
 
-        defer.returnValue({
-            row["user_id"]: {
-                "state": row["state"],
-                "status_msg": row["status_msg"],
-                "mtime": row["mtime"],
-            }
-            for row in rows
-        })
+        for row in rows:
+            row["currently_active"] = bool(row["currently_active"])
 
-    @defer.inlineCallbacks
-    def set_presence_state(self, user_localpart, new_state):
-        res = yield self._simple_update_one(
-            table="presence",
-            keyvalues={"user_id": user_localpart},
-            updatevalues={"state": new_state["state"],
-                          "status_msg": new_state["status_msg"],
-                          "mtime": self._clock.time_msec()},
-            desc="set_presence_state",
-        )
+        defer.returnValue([UserPresenceState(**row) for row in rows])
 
-        self.get_presence_state.invalidate((user_localpart,))
-        defer.returnValue(res)
+    def get_current_presence_token(self):
+        return self._presence_id_gen.get_max_token()
 
     def allow_presence_visible(self, observed_localpart, observer_userid):
         return self._simple_insert(
@@ -128,6 +184,7 @@ class PresenceStore(SQLBaseStore):
             desc="set_presence_list_accepted",
         )
         self.get_presence_list_accepted.invalidate((observer_localpart,))
+        self.get_presence_list_observers_accepted.invalidate((observed_userid,))
         defer.returnValue(result)
 
     def get_presence_list(self, observer_localpart, accepted=None):
@@ -154,6 +211,19 @@ class PresenceStore(SQLBaseStore):
             desc="get_presence_list_accepted",
         )
 
+    @cachedInlineCallbacks()
+    def get_presence_list_observers_accepted(self, observed_userid):
+        user_localparts = yield self._simple_select_onecol(
+            table="presence_list",
+            keyvalues={"observed_user_id": observed_userid, "accepted": True},
+            retcol="user_id",
+            desc="get_presence_list_accepted",
+        )
+
+        defer.returnValue([
+            "@%s:%s" % (u, self.hs.hostname,) for u in user_localparts
+        ])
+
     @defer.inlineCallbacks
     def del_presence_list(self, observer_localpart, observed_userid):
         yield self._simple_delete_one(
@@ -163,3 +233,4 @@ class PresenceStore(SQLBaseStore):
             desc="del_presence_list",
         )
         self.get_presence_list_accepted.invalidate((observer_localpart,))
+        self.get_presence_list_observers_accepted.invalidate((observed_userid,))
diff --git a/synapse/storage/receipts.py b/synapse/storage/receipts.py
index 4202a6b3dc..a7343c97f7 100644
--- a/synapse/storage/receipts.py
+++ b/synapse/storage/receipts.py
@@ -31,7 +31,7 @@ class ReceiptsStore(SQLBaseStore):
         super(ReceiptsStore, self).__init__(hs)
 
         self._receipts_stream_cache = StreamChangeCache(
-            "ReceiptsRoomChangeCache", self._receipts_id_gen.get_max_token(None)
+            "ReceiptsRoomChangeCache", self._receipts_id_gen.get_max_token()
         )
 
     @cached(num_args=2)
@@ -222,7 +222,7 @@ class ReceiptsStore(SQLBaseStore):
         defer.returnValue(results)
 
     def get_max_receipt_stream_id(self):
-        return self._receipts_id_gen.get_max_token(self)
+        return self._receipts_id_gen.get_max_token()
 
     def insert_linearized_receipt_txn(self, txn, room_id, receipt_type,
                                       user_id, event_id, data, stream_id):
@@ -347,7 +347,7 @@ class ReceiptsStore(SQLBaseStore):
             room_id, receipt_type, user_id, event_ids, data
         )
 
-        max_persisted_id = yield self._stream_id_gen.get_max_token(self)
+        max_persisted_id = yield self._stream_id_gen.get_max_token()
 
         defer.returnValue((stream_id, max_persisted_id))
 
diff --git a/synapse/storage/schema/delta/30/presence_stream.sql b/synapse/storage/schema/delta/30/presence_stream.sql
new file mode 100644
index 0000000000..606bbb037d
--- /dev/null
+++ b/synapse/storage/schema/delta/30/presence_stream.sql
@@ -0,0 +1,30 @@
+/* Copyright 2016 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.
+ */
+
+
+ CREATE TABLE presence_stream(
+     stream_id BIGINT,
+     user_id TEXT,
+     state TEXT,
+     last_active_ts BIGINT,
+     last_federation_update_ts BIGINT,
+     last_user_sync_ts BIGINT,
+     status_msg TEXT,
+     currently_active BOOLEAN
+ );
+
+ CREATE INDEX presence_stream_id ON presence_stream(stream_id, user_id);
+ CREATE INDEX presence_stream_user_id ON presence_stream(user_id);
+ CREATE INDEX presence_stream_state ON presence_stream(state);
diff --git a/synapse/storage/stream.py b/synapse/storage/stream.py
index c236dafafb..8908d5b5da 100644
--- a/synapse/storage/stream.py
+++ b/synapse/storage/stream.py
@@ -531,7 +531,7 @@ class StreamStore(SQLBaseStore):
 
     @defer.inlineCallbacks
     def get_room_events_max_id(self, direction='f'):
-        token = yield self._stream_id_gen.get_max_token(self)
+        token = yield self._stream_id_gen.get_max_token()
         if direction != 'b':
             defer.returnValue("s%d" % (token,))
         else:
diff --git a/synapse/storage/tags.py b/synapse/storage/tags.py
index e1a9c0c261..9551aa9739 100644
--- a/synapse/storage/tags.py
+++ b/synapse/storage/tags.py
@@ -30,7 +30,7 @@ class TagsStore(SQLBaseStore):
         Returns:
             A deferred int.
         """
-        return self._account_data_id_gen.get_max_token(self)
+        return self._account_data_id_gen.get_max_token()
 
     @cached()
     def get_tags_for_user(self, user_id):
@@ -147,7 +147,7 @@ class TagsStore(SQLBaseStore):
 
         self.get_tags_for_user.invalidate((user_id,))
 
-        result = yield self._account_data_id_gen.get_max_token(self)
+        result = yield self._account_data_id_gen.get_max_token()
         defer.returnValue(result)
 
     @defer.inlineCallbacks
@@ -169,7 +169,7 @@ class TagsStore(SQLBaseStore):
 
         self.get_tags_for_user.invalidate((user_id,))
 
-        result = yield self._account_data_id_gen.get_max_token(self)
+        result = yield self._account_data_id_gen.get_max_token()
         defer.returnValue(result)
 
     def _update_revision_txn(self, txn, user_id, room_id, next_id):
diff --git a/synapse/storage/util/id_generators.py b/synapse/storage/util/id_generators.py
index 5c522f4ab9..ef5e4a4668 100644
--- a/synapse/storage/util/id_generators.py
+++ b/synapse/storage/util/id_generators.py
@@ -130,7 +130,7 @@ class StreamIdGenerator(object):
 
         return manager()
 
-    def get_max_token(self, store):
+    def get_max_token(self):
         """Returns the maximum stream id such that all stream ids less than or
         equal to it have been successfully persisted.
         """
diff --git a/synapse/util/__init__.py b/synapse/util/__init__.py
index 133671e238..3b9da5b34a 100644
--- a/synapse/util/__init__.py
+++ b/synapse/util/__init__.py
@@ -42,7 +42,7 @@ class Clock(object):
 
     def time_msec(self):
         """Returns the current system time in miliseconds since epoch."""
-        return self.time() * 1000
+        return int(self.time() * 1000)
 
     def looping_call(self, f, msec):
         l = task.LoopingCall(f)
diff --git a/synapse/util/wheel_timer.py b/synapse/util/wheel_timer.py
new file mode 100644
index 0000000000..2c9f957616
--- /dev/null
+++ b/synapse/util/wheel_timer.py
@@ -0,0 +1,91 @@
+# -*- coding: utf-8 -*-
+# Copyright 2016 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 _Entry(object):
+    __slots__ = ["end_key", "queue"]
+
+    def __init__(self, end_key):
+        self.end_key = end_key
+        self.queue = []
+
+
+class WheelTimer(object):
+    """Stores arbitrary objects that will be returned after their timers have
+    expired.
+    """
+
+    def __init__(self, bucket_size=5000):
+        """
+        Args:
+            bucket_size (int): Size of buckets in ms. Corresponds roughly to the
+                accuracy of the timer.
+        """
+        self.bucket_size = bucket_size
+        self.entries = []
+        self.current_tick = 0
+
+    def insert(self, now, obj, then):
+        """Inserts object into timer.
+
+        Args:
+            now (int): Current time in msec
+            obj (object): Object to be inserted
+            then (int): When to return the object strictly after.
+        """
+        then_key = int(then / self.bucket_size) + 1
+
+        if self.entries:
+            min_key = self.entries[0].end_key
+            max_key = self.entries[-1].end_key
+
+            if then_key <= max_key:
+                # The max here is to protect against inserts for times in the past
+                self.entries[max(min_key, then_key) - min_key].queue.append(obj)
+                return
+
+        next_key = int(now / self.bucket_size) + 1
+        if self.entries:
+            last_key = self.entries[-1].end_key
+        else:
+            last_key = next_key
+
+        # Handle the case when `then` is in the past and `entries` is empty.
+        then_key = max(last_key, then_key)
+
+        # Add empty entries between the end of the current list and when we want
+        # to insert. This ensures there are no gaps.
+        self.entries.extend(
+            _Entry(key) for key in xrange(last_key, then_key + 1)
+        )
+
+        self.entries[-1].queue.append(obj)
+
+    def fetch(self, now):
+        """Fetch any objects that have timed out
+
+        Args:
+            now (ms): Current time in msec
+
+        Returns:
+            list: List of objects that have timed out
+        """
+        now_key = int(now / self.bucket_size)
+
+        ret = []
+        while self.entries and self.entries[0].end_key <= now_key:
+            ret.extend(self.entries.pop(0).queue)
+
+        return ret
diff --git a/tests/handlers/test_presence.py b/tests/handlers/test_presence.py
index 447a22b5fc..197298db15 100644
--- a/tests/handlers/test_presence.py
+++ b/tests/handlers/test_presence.py
@@ -1,5 +1,5 @@
 # -*- coding: utf-8 -*-
-# Copyright 2014-2016 OpenMarket Ltd
+# Copyright 2016 OpenMarket Ltd
 #
 # Licensed under the Apache License, Version 2.0 (the "License");
 # you may not use this file except in compliance with the License.
@@ -15,1326 +15,359 @@
 
 
 from tests import unittest
-from twisted.internet import defer, reactor
 
-from mock import Mock, call, ANY, NonCallableMock
-import json
-
-from tests.utils import (
-    MockHttpResource, MockClock, DeferredMockCallable, setup_test_homeserver
-)
+from mock import Mock, call
 
 from synapse.api.constants import PresenceState
-from synapse.api.errors import SynapseError
-from synapse.handlers.presence import PresenceHandler, UserPresenceCache
-from synapse.streams.config import SourcePaginationConfig
-from synapse.types import UserID
-
-OFFLINE = PresenceState.OFFLINE
-UNAVAILABLE = PresenceState.UNAVAILABLE
-ONLINE = PresenceState.ONLINE
-
-
-def _expect_edu(destination, edu_type, content, origin="test"):
-    return {
-        "origin": origin,
-        "origin_server_ts": 1000000,
-        "pdus": [],
-        "edus": [
-            {
-                "edu_type": edu_type,
-                "content": content,
-            }
-        ],
-        "pdu_failures": [],
-    }
-
-def _make_edu_json(origin, edu_type, content):
-    return json.dumps(_expect_edu("test", edu_type, content, origin=origin))
-
-
-class JustPresenceHandlers(object):
-    def __init__(self, hs):
-        self.presence_handler = PresenceHandler(hs)
-
-
-class PresenceTestCase(unittest.TestCase):
-    @defer.inlineCallbacks
-    def setUp(self):
-        self.clock = MockClock()
-
-        self.mock_federation_resource = MockHttpResource()
-
-        self.mock_http_client = Mock(spec=[])
-        self.mock_http_client.put_json = DeferredMockCallable()
-
-        hs_kwargs = {}
-        if hasattr(self, "make_datastore_mock"):
-            hs_kwargs["datastore"] = self.make_datastore_mock()
-
-        hs = yield setup_test_homeserver(
-            clock=self.clock,
-            handlers=None,
-            resource_for_federation=self.mock_federation_resource,
-            http_client=self.mock_http_client,
-            keyring=Mock(),
-            **hs_kwargs
-        )
-        hs.handlers = JustPresenceHandlers(hs)
-
-        self.datastore = hs.get_datastore()
-
-        self.setUp_roommemberhandler_mocks(hs.handlers)
-
-        self.handler = hs.get_handlers().presence_handler
-        self.event_source = hs.get_event_sources().sources["presence"]
-
-        self.distributor = hs.get_distributor()
-        self.distributor.declare("user_joined_room")
-
-        yield self.setUp_users(hs)
-
-    def setUp_roommemberhandler_mocks(self, handlers):
-        self.room_id = "a-room"
-        self.room_members = []
-
-        room_member_handler = handlers.room_member_handler = Mock(spec=[
-            "get_joined_rooms_for_user",
-            "get_room_members",
-            "fetch_room_distributions_into",
-        ])
-        self.room_member_handler = room_member_handler
-
-        def get_rooms_for_user(user):
-            if user in self.room_members:
-                return defer.succeed([self.room_id])
-            else:
-                return defer.succeed([])
-        room_member_handler.get_joined_rooms_for_user = get_rooms_for_user
-
-        def get_room_members(room_id):
-            if room_id == self.room_id:
-                return defer.succeed(self.room_members)
-            else:
-                return defer.succeed([])
-        room_member_handler.get_room_members = get_room_members
-
-        @defer.inlineCallbacks
-        def fetch_room_distributions_into(room_id, localusers=None,
-                remotedomains=None, ignore_user=None):
-
-            members = yield get_room_members(room_id)
-            for member in members:
-                if ignore_user is not None and member == ignore_user:
-                    continue
-
-                if member.is_mine:
-                    if localusers is not None:
-                        localusers.add(member)
-                else:
-                    if remotedomains is not None:
-                        remotedomains.add(member.domain)
-        room_member_handler.fetch_room_distributions_into = (
-                fetch_room_distributions_into)
-
-        self.setUp_datastore_room_mocks(self.datastore)
-
-    def setUp_datastore_room_mocks(self, datastore):
-        def get_room_hosts(room_id):
-            if room_id == self.room_id:
-                hosts = set([u.domain for u in self.room_members])
-                return defer.succeed(hosts)
-            else:
-                return defer.succeed([])
-        datastore.get_joined_hosts_for_room = get_room_hosts
-
-        def user_rooms_intersect(userlist):
-            room_member_ids = map(lambda u: u.to_string(), self.room_members)
-
-            shared = all(map(lambda i: i in room_member_ids, userlist))
-            return defer.succeed(shared)
-        datastore.user_rooms_intersect = user_rooms_intersect
-
-    @defer.inlineCallbacks
-    def setUp_users(self, hs):
-        # Some local users to test with
-        self.u_apple = UserID.from_string("@apple:test")
-        self.u_banana = UserID.from_string("@banana:test")
-        self.u_clementine = UserID.from_string("@clementine:test")
-
-        for u in self.u_apple, self.u_banana, self.u_clementine:
-            yield self.datastore.create_presence(u.localpart)
-
-        yield self.datastore.set_presence_state(
-            self.u_apple.localpart, {"state": ONLINE, "status_msg": "Online"}
-        )
-
-        # ID of a local user that does not exist
-        self.u_durian = UserID.from_string("@durian:test")
-
-        # A remote user
-        self.u_cabbage = UserID.from_string("@cabbage:elsewhere")
-
-
-class MockedDatastorePresenceTestCase(PresenceTestCase):
-    def make_datastore_mock(self):
-        datastore = Mock(spec=[
-            # Bits that Federation needs
-            "prep_send_transaction",
-            "delivered_txn",
-            "get_received_txn_response",
-            "set_received_txn_response",
-            "get_destination_retry_timings",
-        ])
-
-        self.setUp_datastore_federation_mocks(datastore)
-        self.setUp_datastore_presence_mocks(datastore)
-
-        return datastore
-
-    def setUp_datastore_federation_mocks(self, datastore):
-        retry_timings_res = {
-            "destination": "",
-            "retry_last_ts": 0,
-            "retry_interval": 0,
-        }
-        datastore.get_destination_retry_timings.return_value = (
-            defer.succeed(retry_timings_res)
-        )
-
-        def get_received_txn_response(*args):
-            return defer.succeed(None)
-        datastore.get_received_txn_response = get_received_txn_response
-
-    def setUp_datastore_presence_mocks(self, datastore):
-        self.current_user_state = {
-            "apple": OFFLINE,
-            "banana": OFFLINE,
-            "clementine": OFFLINE,
-            "fig": OFFLINE,
-        }
-
-        def get_presence_state(user_localpart):
-            return defer.succeed(
-                    {"state": self.current_user_state[user_localpart],
-                     "status_msg": None,
-                     "mtime": 123456000}
-            )
-        datastore.get_presence_state = get_presence_state
-
-        def set_presence_state(user_localpart, new_state):
-            was = self.current_user_state[user_localpart]
-            self.current_user_state[user_localpart] = new_state["state"]
-            return defer.succeed({"state": was})
-        datastore.set_presence_state = set_presence_state
-
-        def get_presence_list(user_localpart, accepted):
-            if not user_localpart in self.PRESENCE_LIST:
-                return defer.succeed([])
-            return defer.succeed([
-                {"observed_user_id": u, "accepted": accepted} for u in
-                self.PRESENCE_LIST[user_localpart]])
-        datastore.get_presence_list = get_presence_list
-
-        def is_presence_visible(observed_localpart, observer_userid):
-            return True
-        datastore.is_presence_visible = is_presence_visible
-
-    @defer.inlineCallbacks
-    def setUp_users(self, hs):
-        # Some local users to test with
-        self.u_apple = UserID.from_string("@apple:test")
-        self.u_banana = UserID.from_string("@banana:test")
-        self.u_clementine = UserID.from_string("@clementine:test")
-        self.u_durian = UserID.from_string("@durian:test")
-        self.u_elderberry = UserID.from_string("@elderberry:test")
-        self.u_fig = UserID.from_string("@fig:test")
-
-        # Remote user
-        self.u_onion = UserID.from_string("@onion:farm")
-        self.u_potato = UserID.from_string("@potato:remote")
-
-        yield
-
-
-class PresenceStateTestCase(PresenceTestCase):
-    """ Tests presence management. """
-    @defer.inlineCallbacks
-    def setUp(self):
-        yield super(PresenceStateTestCase, self).setUp()
-
-        self.mock_start = Mock()
-        self.mock_stop = Mock()
-
-        self.handler.start_polling_presence = self.mock_start
-        self.handler.stop_polling_presence = self.mock_stop
-
-    @defer.inlineCallbacks
-    def test_get_my_state(self):
-        state = yield self.handler.get_state(
-            target_user=self.u_apple, auth_user=self.u_apple
-        )
-
-        self.assertEquals(
-            {"presence": ONLINE, "status_msg": "Online"},
-            state
-        )
-
-    @defer.inlineCallbacks
-    def test_get_allowed_state(self):
-        yield self.datastore.allow_presence_visible(
-            observed_localpart=self.u_apple.localpart,
-            observer_userid=self.u_banana.to_string(),
-        )
-
-        state = yield self.handler.get_state(
-            target_user=self.u_apple, auth_user=self.u_banana
-        )
+from synapse.handlers.presence import (
+    handle_update, handle_timeout,
+    IDLE_TIMER, SYNC_ONLINE_TIMEOUT, LAST_ACTIVE_GRANULARITY, FEDERATION_TIMEOUT,
+    FEDERATION_PING_INTERVAL,
+)
+from synapse.storage.presence import UserPresenceState
 
-        self.assertEquals(
-            {"presence": ONLINE, "status_msg": "Online"},
-            state
-        )
 
-    @defer.inlineCallbacks
-    def test_get_same_room_state(self):
-        self.room_members = [self.u_apple, self.u_clementine]
+class PresenceUpdateTestCase(unittest.TestCase):
+    def test_offline_to_online(self):
+        wheel_timer = Mock()
+        user_id = "@foo:bar"
+        now = 5000000
 
-        state = yield self.handler.get_state(
-            target_user=self.u_apple, auth_user=self.u_clementine
+        prev_state = UserPresenceState.default(user_id)
+        new_state = prev_state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now,
         )
 
-        self.assertEquals(
-            {"presence": ONLINE, "status_msg": "Online"},
-            state
+        state, persist_and_notify, federation_ping = handle_update(
+            prev_state, new_state, is_mine=True, wheel_timer=wheel_timer, now=now
         )
 
-    @defer.inlineCallbacks
-    def test_get_disallowed_state(self):
-        self.room_members = []
+        self.assertTrue(persist_and_notify)
+        self.assertTrue(state.currently_active)
+        self.assertEquals(new_state.state, state.state)
+        self.assertEquals(new_state.status_msg, state.status_msg)
+        self.assertEquals(state.last_federation_update_ts, now)
 
-        yield self.assertFailure(
-            self.handler.get_state(
-                target_user=self.u_apple, auth_user=self.u_clementine
+        self.assertEquals(wheel_timer.insert.call_count, 2)
+        wheel_timer.insert.assert_has_calls([
+            call(
+                now=now,
+                obj=user_id,
+                then=new_state.last_active_ts + IDLE_TIMER
             ),
-            SynapseError
-        )
-
-    @defer.inlineCallbacks
-    def test_set_my_state(self):
-        yield self.handler.set_state(
-                target_user=self.u_apple, auth_user=self.u_apple,
-                state={"presence": UNAVAILABLE, "status_msg": "Away"})
-
-        self.assertEquals(
-            {"state": UNAVAILABLE,
-             "status_msg": "Away",
-             "mtime": 1000000},
-            (yield self.datastore.get_presence_state(self.u_apple.localpart))
-        )
-
-        self.mock_start.assert_called_with(self.u_apple,
-                state={
-                    "presence": UNAVAILABLE,
-                    "status_msg": "Away",
-                    "last_active": 1000000, # MockClock
-                })
-
-        yield self.handler.set_state(
-                target_user=self.u_apple, auth_user=self.u_apple,
-                state={"presence": OFFLINE})
-
-        self.mock_stop.assert_called_with(self.u_apple)
-
-
-class PresenceInvitesTestCase(PresenceTestCase):
-    """ Tests presence management. """
-    @defer.inlineCallbacks
-    def setUp(self):
-        yield super(PresenceInvitesTestCase, self).setUp()
-
-        self.mock_start = Mock()
-        self.mock_stop = Mock()
-
-        self.handler.start_polling_presence = self.mock_start
-        self.handler.stop_polling_presence = self.mock_stop
-
-    @defer.inlineCallbacks
-    def test_invite_local(self):
-        # TODO(paul): This test will likely break if/when real auth permissions
-        # are added; for now the HS will always accept any invite
-
-        yield self.handler.send_presence_invite(
-                observer_user=self.u_apple, observed_user=self.u_banana)
-
-        self.assertEquals(
-            [{"observed_user_id": "@banana:test", "accepted": 1}],
-            (yield self.datastore.get_presence_list(self.u_apple.localpart))
-        )
-        self.assertTrue(
-            (yield self.datastore.is_presence_visible(
-                observed_localpart=self.u_banana.localpart,
-                observer_userid=self.u_apple.to_string(),
-            ))
-        )
-
-        self.mock_start.assert_called_with(
-                self.u_apple, target_user=self.u_banana)
-
-    @defer.inlineCallbacks
-    def test_invite_local_nonexistant(self):
-        yield self.handler.send_presence_invite(
-                observer_user=self.u_apple, observed_user=self.u_durian)
-
-        self.assertEquals(
-            [],
-            (yield self.datastore.get_presence_list(self.u_apple.localpart))
-        )
-
-    @defer.inlineCallbacks
-    def test_invite_remote(self):
-        # Use a different destination, otherwise retry logic might fail the
-        # request
-        u_rocket = UserID.from_string("@rocket:there")
-
-        put_json = self.mock_http_client.put_json
-        put_json.expect_call_and_return(
-            call("there",
-                path="/_matrix/federation/v1/send/1000000/",
-                data=_expect_edu("there", "m.presence_invite",
-                    content={
-                        "observer_user": "@apple:test",
-                        "observed_user": "@rocket:there",
-                    }
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
-            ),
-            defer.succeed((200, "OK"))
-        )
+            call(
+                now=now,
+                obj=user_id,
+                then=new_state.last_user_sync_ts + SYNC_ONLINE_TIMEOUT
+            )
+        ], any_order=True)
 
-        yield self.handler.send_presence_invite(
-                observer_user=self.u_apple, observed_user=u_rocket)
+    def test_online_to_online(self):
+        wheel_timer = Mock()
+        user_id = "@foo:bar"
+        now = 5000000
 
-        self.assertEquals(
-            [{"observed_user_id": "@rocket:there", "accepted": 0}],
-            (yield self.datastore.get_presence_list(self.u_apple.localpart))
+        prev_state = UserPresenceState.default(user_id)
+        prev_state = prev_state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now,
+            currently_active=True,
         )
 
-        yield put_json.await_calls()
-
-    @defer.inlineCallbacks
-    def test_accept_remote(self):
-        # TODO(paul): This test will likely break if/when real auth permissions
-        # are added; for now the HS will always accept any invite
-
-        # Use a different destination, otherwise retry logic might fail the
-        # request
-        u_rocket = UserID.from_string("@rocket:moon")
-
-        put_json = self.mock_http_client.put_json
-        put_json.expect_call_and_return(
-            call("moon",
-                path="/_matrix/federation/v1/send/1000000/",
-                data=_expect_edu("moon", "m.presence_accept",
-                    content={
-                        "observer_user": "@rocket:moon",
-                        "observed_user": "@apple:test",
-                    }
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
-            ),
-            defer.succeed((200, "OK"))
+        new_state = prev_state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now,
         )
 
-        yield self.mock_federation_resource.trigger("PUT",
-            "/_matrix/federation/v1/send/1000000/",
-            _make_edu_json("elsewhere", "m.presence_invite",
-                content={
-                    "observer_user": "@rocket:moon",
-                    "observed_user": "@apple:test",
-                }
-            )
+        state, persist_and_notify, federation_ping = handle_update(
+            prev_state, new_state, is_mine=True, wheel_timer=wheel_timer, now=now
         )
 
-        self.assertTrue(
-            (yield self.datastore.is_presence_visible(
-                observed_localpart=self.u_apple.localpart,
-                observer_userid=u_rocket.to_string(),
-            ))
-        )
+        self.assertFalse(persist_and_notify)
+        self.assertTrue(federation_ping)
+        self.assertTrue(state.currently_active)
+        self.assertEquals(new_state.state, state.state)
+        self.assertEquals(new_state.status_msg, state.status_msg)
+        self.assertEquals(state.last_federation_update_ts, now)
 
-        yield put_json.await_calls()
-
-    @defer.inlineCallbacks
-    def test_invited_remote_nonexistant(self):
-        # Use a different destination, otherwise retry logic might fail the
-        # request
-        u_rocket = UserID.from_string("@rocket:sun")
-
-        put_json = self.mock_http_client.put_json
-        put_json.expect_call_and_return(
-            call("sun",
-                path="/_matrix/federation/v1/send/1000000/",
-                data=_expect_edu("sun", "m.presence_deny",
-                    content={
-                        "observer_user": "@rocket:sun",
-                        "observed_user": "@durian:test",
-                    }
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
+        self.assertEquals(wheel_timer.insert.call_count, 2)
+        wheel_timer.insert.assert_has_calls([
+            call(
+                now=now,
+                obj=user_id,
+                then=new_state.last_active_ts + IDLE_TIMER
             ),
-            defer.succeed((200, "OK"))
-        )
-
-        yield self.mock_federation_resource.trigger("PUT",
-            "/_matrix/federation/v1/send/1000000/",
-            _make_edu_json("sun", "m.presence_invite",
-                content={
-                    "observer_user": "@rocket:sun",
-                    "observed_user": "@durian:test",
-                }
+            call(
+                now=now,
+                obj=user_id,
+                then=new_state.last_user_sync_ts + SYNC_ONLINE_TIMEOUT
             )
-        )
+        ], any_order=True)
 
-        yield put_json.await_calls()
+    def test_online_to_online_last_active(self):
+        wheel_timer = Mock()
+        user_id = "@foo:bar"
+        now = 5000000
 
-    @defer.inlineCallbacks
-    def test_accepted_remote(self):
-        yield self.datastore.add_presence_list_pending(
-            observer_localpart=self.u_apple.localpart,
-            observed_userid=self.u_cabbage.to_string(),
+        prev_state = UserPresenceState.default(user_id)
+        prev_state = prev_state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now - LAST_ACTIVE_GRANULARITY - 1,
+            currently_active=True,
         )
 
-        yield self.mock_federation_resource.trigger("PUT",
-            "/_matrix/federation/v1/send/1000000/",
-            _make_edu_json("elsewhere", "m.presence_accept",
-                content={
-                    "observer_user": "@apple:test",
-                    "observed_user": "@cabbage:elsewhere",
-                }
-            )
+        new_state = prev_state.copy_and_replace(
+            state=PresenceState.ONLINE,
         )
 
-        self.assertEquals(
-            [{"observed_user_id": "@cabbage:elsewhere", "accepted": 1}],
-            (yield self.datastore.get_presence_list(self.u_apple.localpart))
+        state, persist_and_notify, federation_ping = handle_update(
+            prev_state, new_state, is_mine=True, wheel_timer=wheel_timer, now=now
         )
 
-        self.mock_start.assert_called_with(
-                self.u_apple, target_user=self.u_cabbage)
-
-    @defer.inlineCallbacks
-    def test_denied_remote(self):
-        yield self.datastore.add_presence_list_pending(
-            observer_localpart=self.u_apple.localpart,
-            observed_userid="@eggplant:elsewhere",
-        )
+        self.assertTrue(persist_and_notify)
+        self.assertFalse(state.currently_active)
+        self.assertEquals(new_state.state, state.state)
+        self.assertEquals(new_state.status_msg, state.status_msg)
+        self.assertEquals(state.last_federation_update_ts, now)
 
-        yield self.mock_federation_resource.trigger("PUT",
-            "/_matrix/federation/v1/send/1000000/",
-            _make_edu_json("elsewhere", "m.presence_deny",
-                content={
-                    "observer_user": "@apple:test",
-                    "observed_user": "@eggplant:elsewhere",
-                }
+        self.assertEquals(wheel_timer.insert.call_count, 2)
+        wheel_timer.insert.assert_has_calls([
+            call(
+                now=now,
+                obj=user_id,
+                then=new_state.last_active_ts + IDLE_TIMER
+            ),
+            call(
+                now=now,
+                obj=user_id,
+                then=new_state.last_user_sync_ts + SYNC_ONLINE_TIMEOUT
             )
-        )
-
-        self.assertEquals(
-            [],
-            (yield self.datastore.get_presence_list(self.u_apple.localpart))
-        )
-
-    @defer.inlineCallbacks
-    def test_drop_local(self):
-        yield self.datastore.add_presence_list_pending(
-            observer_localpart=self.u_apple.localpart,
-            observed_userid=self.u_banana.to_string(),
-        )
-        yield self.datastore.set_presence_list_accepted(
-            observer_localpart=self.u_apple.localpart,
-            observed_userid=self.u_banana.to_string(),
-        )
-
-        yield self.handler.drop(
-            observer_user=self.u_apple,
-            observed_user=self.u_banana,
-        )
-
-        self.assertEquals(
-            [],
-            (yield self.datastore.get_presence_list(self.u_apple.localpart))
-        )
-
-        self.mock_stop.assert_called_with(
-                self.u_apple, target_user=self.u_banana)
-
-    @defer.inlineCallbacks
-    def test_drop_remote(self):
-        yield self.datastore.add_presence_list_pending(
-            observer_localpart=self.u_apple.localpart,
-            observed_userid=self.u_cabbage.to_string(),
-        )
-        yield self.datastore.set_presence_list_accepted(
-            observer_localpart=self.u_apple.localpart,
-            observed_userid=self.u_cabbage.to_string(),
-        )
-
-        yield self.handler.drop(
-            observer_user=self.u_apple,
-            observed_user=self.u_cabbage,
-        )
-
-        self.assertEquals(
-            [],
-            (yield self.datastore.get_presence_list(self.u_apple.localpart))
-        )
-
-    @defer.inlineCallbacks
-    def test_get_presence_list(self):
-        yield self.datastore.add_presence_list_pending(
-            observer_localpart=self.u_apple.localpart,
-            observed_userid=self.u_banana.to_string(),
-        )
-        yield self.datastore.set_presence_list_accepted(
-            observer_localpart=self.u_apple.localpart,
-            observed_userid=self.u_banana.to_string(),
-        )
-
-        presence = yield self.handler.get_presence_list(
-                observer_user=self.u_apple)
-
-        self.assertEquals([
-            {"observed_user": self.u_banana,
-             "presence": OFFLINE,
-             "accepted": 1},
-        ], presence)
-
-
-class PresencePushTestCase(MockedDatastorePresenceTestCase):
-    """ Tests steady-state presence status updates.
-
-    They assert that presence state update messages are pushed around the place
-    when users change state, presuming that the watches are all established.
-
-    These tests are MASSIVELY fragile currently as they poke internals of the
-    presence handler; namely the _local_pushmap and _remote_recvmap.
-    BE WARNED...
-    """
-    PRESENCE_LIST = {
-            'apple': [ "@banana:test", "@clementine:test" ],
-            'banana': [ "@apple:test" ],
-    }
-
-    @defer.inlineCallbacks
-    def test_push_local(self):
-        self.room_members = [self.u_apple, self.u_elderberry]
-
-        self.datastore.set_presence_state.return_value = defer.succeed(
-            {"state": ONLINE}
-        )
-
-        # TODO(paul): Gut-wrenching
-        self.handler._user_cachemap[self.u_apple] = UserPresenceCache()
-        self.handler._user_cachemap[self.u_apple].update(
-            {"presence": OFFLINE}, serial=0
-        )
-        apple_set = self.handler._local_pushmap.setdefault("apple", set())
-        apple_set.add(self.u_banana)
-        apple_set.add(self.u_clementine)
-
-        self.assertEquals(self.event_source.get_current_key(), 0)
-
-        yield self.handler.set_state(self.u_apple, self.u_apple,
-            {"presence": ONLINE}
-        )
-
-        # Apple sees self-reflection even without room_id
-        (events, _) = yield self.event_source.get_new_events(
-            user=self.u_apple,
-            from_key=0,
-        )
-
-        self.assertEquals(self.event_source.get_current_key(), 1)
-        self.assertEquals(events,
-            [
-                {"type": "m.presence",
-                 "content": {
-                    "user_id": "@apple:test",
-                    "presence": ONLINE,
-                    "last_active_ago": 0,
-                }},
-            ],
-            msg="Presence event should be visible to self-reflection"
-        )
-
-        # Apple sees self-reflection
-        (events, _) = yield self.event_source.get_new_events(
-            user=self.u_apple,
-            from_key=0,
-            room_ids=[self.room_id],
-        )
-
-        self.assertEquals(self.event_source.get_current_key(), 1)
-        self.assertEquals(events,
-            [
-                {"type": "m.presence",
-                 "content": {
-                    "user_id": "@apple:test",
-                    "presence": ONLINE,
-                    "last_active_ago": 0,
-                }},
-            ],
-            msg="Presence event should be visible to self-reflection"
-        )
-
-        config = SourcePaginationConfig(from_key=1, to_key=0)
-        (chunk, _) = yield self.event_source.get_pagination_rows(
-            self.u_apple, config, None
-        )
-        self.assertEquals(chunk,
-            [
-                {"type": "m.presence",
-                 "content": {
-                     "user_id": "@apple:test",
-                     "presence": ONLINE,
-                     "last_active_ago": 0,
-                }},
-            ]
-        )
-
-        # Banana sees it because of presence subscription
-        (events, _) = yield self.event_source.get_new_events(
-            user=self.u_banana,
-            from_key=0,
-            room_ids=[self.room_id],
-        )
-
-        self.assertEquals(self.event_source.get_current_key(), 1)
-        self.assertEquals(events,
-            [
-                {"type": "m.presence",
-                 "content": {
-                    "user_id": "@apple:test",
-                    "presence": ONLINE,
-                    "last_active_ago": 0,
-                }},
-            ],
-            msg="Presence event should be visible to explicit subscribers"
-        )
-
-        # Elderberry sees it because of same room
-        (events, _) = yield self.event_source.get_new_events(
-            user=self.u_elderberry,
-            from_key=0,
-            room_ids=[self.room_id],
-        )
-
-        self.assertEquals(self.event_source.get_current_key(), 1)
-        self.assertEquals(events,
-            [
-                {"type": "m.presence",
-                 "content": {
-                    "user_id": "@apple:test",
-                    "presence": ONLINE,
-                    "last_active_ago": 0,
-                }},
-            ],
-            msg="Presence event should be visible to other room members"
-        )
-
-        # Durian is not in the room, should not see this event
-        (events, _) = yield self.event_source.get_new_events(
-            user=self.u_durian,
-            from_key=0,
-            room_ids=[],
-        )
+        ], any_order=True)
 
-        self.assertEquals(self.event_source.get_current_key(), 1)
-        self.assertEquals(events, [],
-            msg="Presence event should not be visible to others"
-        )
+    def test_remote_ping_timer(self):
+        wheel_timer = Mock()
+        user_id = "@foo:bar"
+        now = 5000000
 
-        presence = yield self.handler.get_presence_list(
-                observer_user=self.u_apple, accepted=True)
-
-        self.assertEquals(
-            [
-                {"observed_user": self.u_banana,
-                 "presence": OFFLINE,
-                 "accepted": True},
-                {"observed_user": self.u_clementine,
-                 "presence": OFFLINE,
-                 "accepted": True},
-            ],
-            presence
+        prev_state = UserPresenceState.default(user_id)
+        prev_state = prev_state.copy_and_replace(
+            state=PresenceState.ONLINE,
         )
 
-        # TODO(paul): Gut-wrenching
-        banana_set = self.handler._local_pushmap.setdefault("banana", set())
-        banana_set.add(self.u_apple)
-
-        yield self.handler.set_state(self.u_banana, self.u_banana,
-            {"presence": ONLINE}
+        new_state = prev_state.copy_and_replace(
+            state=PresenceState.ONLINE,
         )
 
-        self.clock.advance_time(2)
-
-        presence = yield self.handler.get_presence_list(
-                observer_user=self.u_apple, accepted=True)
-
-        self.assertEquals([
-                {"observed_user": self.u_banana,
-                 "presence": ONLINE,
-                 "last_active_ago": 2000,
-                 "accepted": True},
-                {"observed_user": self.u_clementine,
-                 "presence": OFFLINE,
-                 "accepted": True},
-        ], presence)
-
-        (events, _) = yield self.event_source.get_new_events(
-            user=self.u_apple,
-            from_key=1,
+        state, persist_and_notify, federation_ping = handle_update(
+            prev_state, new_state, is_mine=False, wheel_timer=wheel_timer, now=now
         )
 
-        self.assertEquals(self.event_source.get_current_key(), 2)
-        self.assertEquals(events,
-            [
-                {"type": "m.presence",
-                 "content": {
-                     "user_id": "@banana:test",
-                     "presence": ONLINE,
-                     "last_active_ago": 2000
-                }},
-            ]
-        )
+        self.assertFalse(persist_and_notify)
+        self.assertFalse(federation_ping)
+        self.assertFalse(state.currently_active)
+        self.assertEquals(new_state.state, state.state)
+        self.assertEquals(new_state.status_msg, state.status_msg)
 
-    @defer.inlineCallbacks
-    def test_push_remote(self):
-        put_json = self.mock_http_client.put_json
-        put_json.expect_call_and_return(
-            call("farm",
-                path=ANY,  # Can't guarantee which txn ID will be which
-                data=_expect_edu("farm", "m.presence",
-                    content={
-                        "push": [
-                            {"user_id": "@apple:test",
-                             "presence": u"online",
-                             "last_active_ago": 0},
-                        ],
-                    }
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
-            ),
-            defer.succeed((200, "OK"))
-        )
-        put_json.expect_call_and_return(
-            call("remote",
-                path=ANY,  # Can't guarantee which txn ID will be which
-                data=_expect_edu("remote", "m.presence",
-                    content={
-                        "push": [
-                            {"user_id": "@apple:test",
-                             "presence": u"online",
-                             "last_active_ago": 0},
-                        ],
-                    }
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
+        self.assertEquals(wheel_timer.insert.call_count, 1)
+        wheel_timer.insert.assert_has_calls([
+            call(
+                now=now,
+                obj=user_id,
+                then=new_state.last_federation_update_ts + FEDERATION_TIMEOUT
             ),
-            defer.succeed((200, "OK"))
-        )
+        ], any_order=True)
 
-        self.room_members = [self.u_apple, self.u_onion]
+    def test_online_to_offline(self):
+        wheel_timer = Mock()
+        user_id = "@foo:bar"
+        now = 5000000
 
-        self.datastore.set_presence_state.return_value = defer.succeed(
-            {"state": ONLINE}
+        prev_state = UserPresenceState.default(user_id)
+        prev_state = prev_state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now,
+            currently_active=True,
         )
 
-        # TODO(paul): Gut-wrenching
-        self.handler._user_cachemap[self.u_apple] = UserPresenceCache()
-        self.handler._user_cachemap[self.u_apple].update(
-            {"presence": OFFLINE}, serial=0
+        new_state = prev_state.copy_and_replace(
+            state=PresenceState.OFFLINE,
         )
-        apple_set = self.handler._remote_sendmap.setdefault("apple", set())
-        apple_set.add(self.u_potato.domain)
 
-        yield self.handler.set_state(self.u_apple, self.u_apple,
-            {"presence": ONLINE}
+        state, persist_and_notify, federation_ping = handle_update(
+            prev_state, new_state, is_mine=True, wheel_timer=wheel_timer, now=now
         )
 
-        yield put_json.await_calls()
-
-    @defer.inlineCallbacks
-    def test_recv_remote(self):
-        self.room_members = [self.u_apple, self.u_banana, self.u_potato]
+        self.assertTrue(persist_and_notify)
+        self.assertEquals(new_state.state, state.state)
+        self.assertEquals(state.last_federation_update_ts, now)
 
-        self.assertEquals(self.event_source.get_current_key(), 0)
+        self.assertEquals(wheel_timer.insert.call_count, 0)
 
-        yield self.mock_federation_resource.trigger("PUT",
-            "/_matrix/federation/v1/send/1000000/",
-            _make_edu_json("elsewhere", "m.presence",
-                content={
-                    "push": [
-                        {"user_id": "@potato:remote",
-                         "presence": "online",
-                         "last_active_ago": 1000},
-                    ],
-                }
-            )
-        )
+    def test_online_to_idle(self):
+        wheel_timer = Mock()
+        user_id = "@foo:bar"
+        now = 5000000
 
-        (events, _) = yield self.event_source.get_new_events(
-            user=self.u_apple,
-            from_key=0,
-            room_ids=[self.room_id],
+        prev_state = UserPresenceState.default(user_id)
+        prev_state = prev_state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now,
+            currently_active=True,
         )
 
-        self.assertEquals(self.event_source.get_current_key(), 1)
-        self.assertEquals(events,
-            [
-                {"type": "m.presence",
-                 "content": {
-                     "user_id": "@potato:remote",
-                     "presence": ONLINE,
-                     "last_active_ago": 1000,
-                }}
-            ]
+        new_state = prev_state.copy_and_replace(
+            state=PresenceState.UNAVAILABLE,
         )
 
-        self.clock.advance_time(2)
-
-        state = yield self.handler.get_state(self.u_potato, self.u_apple)
-
-        self.assertEquals(
-            {"presence": ONLINE, "last_active_ago": 3000},
-            state
+        state, persist_and_notify, federation_ping = handle_update(
+            prev_state, new_state, is_mine=True, wheel_timer=wheel_timer, now=now
         )
 
-    @defer.inlineCallbacks
-    def test_recv_remote_offline(self):
-        """ Various tests relating to SYN-261 """
-
-        self.room_members = [self.u_apple, self.u_banana, self.u_potato]
-
-        self.assertEquals(self.event_source.get_current_key(), 0)
+        self.assertTrue(persist_and_notify)
+        self.assertEquals(new_state.state, state.state)
+        self.assertEquals(state.last_federation_update_ts, now)
+        self.assertEquals(new_state.state, state.state)
+        self.assertEquals(new_state.status_msg, state.status_msg)
 
-        yield self.mock_federation_resource.trigger("PUT",
-            "/_matrix/federation/v1/send/1000000/",
-            _make_edu_json("elsewhere", "m.presence",
-                content={
-                    "push": [
-                        {"user_id": "@potato:remote",
-                         "presence": "offline"},
-                    ],
-                }
+        self.assertEquals(wheel_timer.insert.call_count, 1)
+        wheel_timer.insert.assert_has_calls([
+            call(
+                now=now,
+                obj=user_id,
+                then=new_state.last_user_sync_ts + SYNC_ONLINE_TIMEOUT
             )
-        )
-
-        self.assertEquals(self.event_source.get_current_key(), 1)
-
-        (events, _) = yield self.event_source.get_new_events(
-            user=self.u_apple,
-            from_key=0,
-            room_ids=[self.room_id,]
-        )
-        self.assertEquals(events,
-            [
-                {"type": "m.presence",
-                 "content": {
-                     "user_id": "@potato:remote",
-                     "presence": OFFLINE,
-                }}
-            ]
-        )
-
-        yield self.mock_federation_resource.trigger("PUT",
-            "/_matrix/federation/v1/send/1000001/",
-            _make_edu_json("elsewhere", "m.presence",
-                content={
-                    "push": [
-                        {"user_id": "@potato:remote",
-                         "presence": "online"},
-                    ],
-                }
-            )
-        )
-
-        self.assertEquals(self.event_source.get_current_key(), 2)
-
-        (events, _) = yield self.event_source.get_new_events(
-            user=self.u_apple,
-            from_key=0,
-            room_ids=[self.room_id,]
-        )
-        self.assertEquals(events,
-            [
-                {"type": "m.presence",
-                 "content": {
-                     "user_id": "@potato:remote",
-                     "presence": ONLINE,
-                }}
-            ]
-        )
-
-    @defer.inlineCallbacks
-    def test_join_room_local(self):
-        self.room_members = [self.u_apple, self.u_banana]
-
-        self.assertEquals(self.event_source.get_current_key(), 0)
-
-        # TODO(paul): Gut-wrenching
-        self.handler._user_cachemap[self.u_clementine] = UserPresenceCache()
-        self.handler._user_cachemap[self.u_clementine].update(
-            {
-                "presence": PresenceState.ONLINE,
-                "last_active": self.clock.time_msec(),
-            }, self.u_clementine
-        )
-
-        yield self.distributor.fire("user_joined_room", self.u_clementine,
-            self.room_id
-        )
+        ], any_order=True)
 
-        self.room_members.append(self.u_clementine)
 
-        (events, _) = yield self.event_source.get_new_events(
-            user=self.u_apple,
-            from_key=0,
-        )
+class PresenceTimeoutTestCase(unittest.TestCase):
+    def test_idle_timer(self):
+        user_id = "@foo:bar"
+        now = 5000000
 
-        self.assertEquals(self.event_source.get_current_key(), 1)
-        self.assertEquals(events,
-            [
-                {"type": "m.presence",
-                 "content": {
-                     "user_id": "@clementine:test",
-                     "presence": ONLINE,
-                     "last_active_ago": 0,
-                }}
-            ]
+        state = UserPresenceState.default(user_id)
+        state = state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now - IDLE_TIMER - 1,
+            last_user_sync_ts=now,
         )
 
-    @defer.inlineCallbacks
-    def test_join_room_remote(self):
-        ## Sending local user state to a newly-joined remote user
-        put_json = self.mock_http_client.put_json
-        put_json.expect_call_and_return(
-            call("remote",
-                path=ANY,  # Can't guarantee which txn ID will be which
-                data=_expect_edu("remote", "m.presence",
-                    content={
-                        "push": [
-                            {"user_id": "@apple:test",
-                             "presence": "online"},
-                        ],
-                    }
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
-            ),
-            defer.succeed((200, "OK"))
-        )
-        put_json.expect_call_and_return(
-            call("remote",
-                path=ANY,  # Can't guarantee which txn ID will be which
-                data=_expect_edu("remote", "m.presence",
-                    content={
-                        "push": [
-                            {"user_id": "@banana:test",
-                             "presence": "offline"},
-                        ],
-                    }
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
-            ),
-            defer.succeed((200, "OK"))
+        new_state = handle_timeout(
+            state, is_mine=True, user_to_num_current_syncs={}, now=now
         )
 
-        # TODO(paul): Gut-wrenching
-        self.handler._user_cachemap[self.u_apple] = UserPresenceCache()
-        self.handler._user_cachemap[self.u_apple].update(
-                {"presence": PresenceState.ONLINE}, self.u_apple)
-        self.room_members = [self.u_apple, self.u_banana]
+        self.assertIsNotNone(new_state)
+        self.assertEquals(new_state.state, PresenceState.UNAVAILABLE)
 
-        yield self.distributor.fire("user_joined_room", self.u_potato,
-            self.room_id
-        )
+    def test_sync_timeout(self):
+        user_id = "@foo:bar"
+        now = 5000000
 
-        yield put_json.await_calls()
-
-        ## Sending newly-joined local user state to remote users
-
-        put_json.expect_call_and_return(
-            call("remote",
-                path="/_matrix/federation/v1/send/1000002/",
-                data=_expect_edu("remote", "m.presence",
-                    content={
-                        "push": [
-                            {"user_id": "@clementine:test",
-                             "presence": "online"},
-                        ],
-                    }
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
-            ),
-            defer.succeed((200, "OK"))
+        state = UserPresenceState.default(user_id)
+        state = state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now,
+            last_user_sync_ts=now - SYNC_ONLINE_TIMEOUT - 1,
         )
 
-        self.handler._user_cachemap[self.u_clementine] = UserPresenceCache()
-        self.handler._user_cachemap[self.u_clementine].update(
-                {"presence": ONLINE}, self.u_clementine)
-        self.room_members.append(self.u_potato)
-
-        yield self.distributor.fire("user_joined_room", self.u_clementine,
-            self.room_id
+        new_state = handle_timeout(
+            state, is_mine=True, user_to_num_current_syncs={}, now=now
         )
 
-        put_json.await_calls()
-
-
-class PresencePollingTestCase(MockedDatastorePresenceTestCase):
-    """ Tests presence status polling. """
-
-    # For this test, we have three local users; apple is watching and is
-    # watched by the other two, but the others don't watch each other.
-    # Additionally clementine is watching a remote user.
-    PRESENCE_LIST = {
-            'apple': [ "@banana:test", "@clementine:test" ],
-            'banana': [ "@apple:test" ],
-            'clementine': [ "@apple:test", "@potato:remote" ],
-            'fig': [ "@potato:remote" ],
-    }
-
-    @defer.inlineCallbacks
-    def setUp(self):
-        yield super(PresencePollingTestCase, self).setUp()
-
-        self.mock_update_client = Mock()
-
-        def update(*args,**kwargs):
-            return defer.succeed(None)
-        self.mock_update_client.side_effect = update
-
-        self.handler.push_update_to_clients = self.mock_update_client
-
-    @defer.inlineCallbacks
-    def test_push_local(self):
-        # apple goes online
-        yield self.handler.set_state(
-            target_user=self.u_apple, auth_user=self.u_apple,
-            state={"presence": ONLINE}
-        )
-
-        # apple should see both banana and clementine currently offline
-        self.mock_update_client.assert_has_calls([
-            call(users_to_push=[self.u_apple]),
-            call(users_to_push=[self.u_apple]),
-        ], any_order=True)
-
-        # Gut-wrenching tests
-        self.assertTrue("banana" in self.handler._local_pushmap)
-        self.assertTrue(self.u_apple in self.handler._local_pushmap["banana"])
-        self.assertTrue("clementine" in self.handler._local_pushmap)
-        self.assertTrue(self.u_apple in self.handler._local_pushmap["clementine"])
+        self.assertIsNotNone(new_state)
+        self.assertEquals(new_state.state, PresenceState.OFFLINE)
 
-        self.mock_update_client.reset_mock()
+    def test_sync_online(self):
+        user_id = "@foo:bar"
+        now = 5000000
 
-        # banana goes online
-        yield self.handler.set_state(
-            target_user=self.u_banana, auth_user=self.u_banana,
-            state={"presence": ONLINE}
+        state = UserPresenceState.default(user_id)
+        state = state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now - SYNC_ONLINE_TIMEOUT - 1,
+            last_user_sync_ts=now - SYNC_ONLINE_TIMEOUT - 1,
         )
 
-        # apple and banana should now both see each other online
-        self.mock_update_client.assert_has_calls([
-            call(users_to_push=set([self.u_apple]), room_ids=[]),
-            call(users_to_push=[self.u_banana]),
-        ], any_order=True)
-
-        self.assertTrue("apple" in self.handler._local_pushmap)
-        self.assertTrue(self.u_banana in self.handler._local_pushmap["apple"])
-
-        self.mock_update_client.reset_mock()
-
-        # apple goes offline
-        yield self.handler.set_state(
-            target_user=self.u_apple, auth_user=self.u_apple,
-            state={"presence": OFFLINE}
+        new_state = handle_timeout(
+            state, is_mine=True, user_to_num_current_syncs={
+                user_id: 1,
+            }, now=now
         )
 
-        # banana should now be told apple is offline
-        self.mock_update_client.assert_has_calls([
-            call(users_to_push=set([self.u_banana, self.u_apple]), room_ids=[]),
-        ], any_order=True)
+        self.assertIsNotNone(new_state)
+        self.assertEquals(new_state.state, PresenceState.ONLINE)
 
-        self.assertFalse("banana" in self.handler._local_pushmap)
-        self.assertFalse("clementine" in self.handler._local_pushmap)
-
-    @defer.inlineCallbacks
-    def test_remote_poll_send(self):
-        put_json = self.mock_http_client.put_json
-        put_json.expect_call_and_return(
-            call("remote",
-                path=ANY,
-                data=_expect_edu("remote", "m.presence",
-                    content={
-                        "poll": [ "@potato:remote" ],
-                    },
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
-            ),
-            defer.succeed((200, "OK"))
-        )
+    def test_federation_ping(self):
+        user_id = "@foo:bar"
+        now = 5000000
 
-        put_json.expect_call_and_return(
-            call("remote",
-                path=ANY,
-                data=_expect_edu("remote", "m.presence",
-                    content={
-                        "push": [ {
-                            "user_id": "@clementine:test",
-                            "presence": OFFLINE,
-                        }],
-                    },
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
-            ),
-            defer.succeed((200, "OK"))
+        state = UserPresenceState.default(user_id)
+        state = state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now,
+            last_user_sync_ts=now,
+            last_federation_update_ts=now - FEDERATION_PING_INTERVAL - 1,
         )
 
-        # clementine goes online
-        yield self.handler.set_state(
-            target_user=self.u_clementine, auth_user=self.u_clementine,
-            state={"presence": ONLINE}
+        new_state = handle_timeout(
+            state, is_mine=True, user_to_num_current_syncs={}, now=now
         )
 
-        yield put_json.await_calls()
+        self.assertIsNotNone(new_state)
+        self.assertEquals(new_state, new_state)
 
-        # Gut-wrenching tests
-        self.assertTrue(self.u_potato in self.handler._remote_recvmap,
-            msg="expected potato to be in _remote_recvmap"
-        )
-        self.assertTrue(self.u_clementine in
-                self.handler._remote_recvmap[self.u_potato])
-
-
-        put_json.expect_call_and_return(
-            call("remote",
-                path=ANY,
-                data=_expect_edu("remote", "m.presence",
-                    content={
-                        "push": [ {
-                            "user_id": "@fig:test",
-                            "presence": OFFLINE,
-                        }],
-                    },
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
-            ),
-            defer.succeed((200, "OK"))
-        )
+    def test_no_timeout(self):
+        user_id = "@foo:bar"
+        now = 5000000
 
-        # fig goes online; shouldn't send a second poll
-        yield self.handler.set_state(
-            target_user=self.u_fig, auth_user=self.u_fig,
-            state={"presence": ONLINE}
+        state = UserPresenceState.default(user_id)
+        state = state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now,
+            last_user_sync_ts=now,
+            last_federation_update_ts=now,
         )
 
-        # reactor.iterate(delay=0)
-
-        yield put_json.await_calls()
-
-        # fig goes offline
-        yield self.handler.set_state(
-            target_user=self.u_fig, auth_user=self.u_fig,
-            state={"presence": OFFLINE}
+        new_state = handle_timeout(
+            state, is_mine=True, user_to_num_current_syncs={}, now=now
         )
 
-        reactor.iterate(delay=0)
+        self.assertIsNone(new_state)
 
-        put_json.assert_had_no_calls()
+    def test_federation_timeout(self):
+        user_id = "@foo:bar"
+        now = 5000000
 
-        put_json.expect_call_and_return(
-            call("remote",
-                path=ANY,
-                data=_expect_edu("remote", "m.presence",
-                    content={
-                        "unpoll": [ "@potato:remote" ],
-                    },
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
-            ),
-            defer.succeed((200, "OK"))
+        state = UserPresenceState.default(user_id)
+        state = state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now,
+            last_user_sync_ts=now,
+            last_federation_update_ts=now - FEDERATION_TIMEOUT - 1,
         )
 
-        # clementine goes offline
-        yield self.handler.set_state(
-            target_user=self.u_clementine, auth_user=self.u_clementine,
-            state={"presence": OFFLINE}
+        new_state = handle_timeout(
+            state, is_mine=False, user_to_num_current_syncs={}, now=now
         )
 
-        yield put_json.await_calls()
+        self.assertIsNotNone(new_state)
+        self.assertEquals(new_state.state, PresenceState.OFFLINE)
 
-        self.assertFalse(self.u_potato in self.handler._remote_recvmap,
-            msg="expected potato not to be in _remote_recvmap"
-        )
+    def test_last_active(self):
+        user_id = "@foo:bar"
+        now = 5000000
 
-    @defer.inlineCallbacks
-    def test_remote_poll_receive(self):
-        put_json = self.mock_http_client.put_json
-        put_json.expect_call_and_return(
-            call("remote",
-                path="/_matrix/federation/v1/send/1000000/",
-                data=_expect_edu("remote", "m.presence",
-                    content={
-                        "push": [
-                            {"user_id": "@banana:test",
-                             "presence": "offline",
-                             "status_msg": None},
-                        ],
-                    },
-                ),
-                json_data_callback=ANY,
-                long_retries=True,
-            ),
-            defer.succeed((200, "OK"))
+        state = UserPresenceState.default(user_id)
+        state = state.copy_and_replace(
+            state=PresenceState.ONLINE,
+            last_active_ts=now - LAST_ACTIVE_GRANULARITY - 1,
+            last_user_sync_ts=now,
+            last_federation_update_ts=now,
         )
 
-        yield self.mock_federation_resource.trigger("PUT",
-            "/_matrix/federation/v1/send/1000000/",
-            _make_edu_json("remote", "m.presence",
-                content={
-                    "poll": [ "@banana:test" ],
-                },
-            )
-        )
-
-        yield put_json.await_calls()
-
-        # Gut-wrenching tests
-        self.assertTrue(self.u_banana in self.handler._remote_sendmap)
-
-        yield self.mock_federation_resource.trigger("PUT",
-            "/_matrix/federation/v1/send/1000001/",
-            _make_edu_json("remote", "m.presence",
-                content={
-                    "unpoll": [ "@banana:test" ],
-                }
-            )
+        new_state = handle_timeout(
+            state, is_mine=True, user_to_num_current_syncs={}, now=now
         )
 
-        # Gut-wrenching tests
-        self.assertFalse(self.u_banana in self.handler._remote_sendmap)
+        self.assertIsNotNone(new_state)
+        self.assertEquals(state, new_state)
diff --git a/tests/handlers/test_presencelike.py b/tests/handlers/test_presencelike.py
deleted file mode 100644
index 76f6ba5e7b..0000000000
--- a/tests/handlers/test_presencelike.py
+++ /dev/null
@@ -1,311 +0,0 @@
-# -*- coding: utf-8 -*-
-# Copyright 2014-2016 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.
-
-"""This file contains tests of the "presence-like" data that is shared between
-presence and profiles; namely, the displayname and avatar_url."""
-
-from tests import unittest
-from twisted.internet import defer
-
-from mock import Mock, call, ANY, NonCallableMock
-
-from ..utils import MockClock, setup_test_homeserver
-
-from synapse.api.constants import PresenceState
-from synapse.handlers.presence import PresenceHandler
-from synapse.handlers.profile import ProfileHandler
-from synapse.types import UserID
-
-
-OFFLINE = PresenceState.OFFLINE
-UNAVAILABLE = PresenceState.UNAVAILABLE
-ONLINE = PresenceState.ONLINE
-
-
-class MockReplication(object):
-    def __init__(self):
-        self.edu_handlers = {}
-
-    def register_edu_handler(self, edu_type, handler):
-        self.edu_handlers[edu_type] = handler
-
-    def register_query_handler(self, query_type, handler):
-        pass
-
-    def received_edu(self, origin, edu_type, content):
-        self.edu_handlers[edu_type](origin, content)
-
-
-class PresenceAndProfileHandlers(object):
-    def __init__(self, hs):
-        self.presence_handler = PresenceHandler(hs)
-        self.profile_handler = ProfileHandler(hs)
-
-
-class PresenceProfilelikeDataTestCase(unittest.TestCase):
-
-    @defer.inlineCallbacks
-    def setUp(self):
-        hs = yield setup_test_homeserver(
-            clock=MockClock(),
-            datastore=Mock(spec=[
-                "set_presence_state",
-                "is_presence_visible",
-                "set_profile_displayname",
-                "get_rooms_for_user",
-            ]),
-            handlers=None,
-            resource_for_federation=Mock(),
-            http_client=None,
-            replication_layer=MockReplication(),
-            ratelimiter=NonCallableMock(spec_set=[
-                "send_message",
-            ]),
-        )
-        self.ratelimiter = hs.get_ratelimiter()
-        self.ratelimiter.send_message.return_value = (True, 0)
-        hs.handlers = PresenceAndProfileHandlers(hs)
-
-        self.datastore = hs.get_datastore()
-
-        self.replication = hs.get_replication_layer()
-        self.replication.send_edu = Mock()
-
-        def send_edu(*args, **kwargs):
-            # print "send_edu: %s, %s" % (args, kwargs)
-            return defer.succeed((200, "OK"))
-        self.replication.send_edu.side_effect = send_edu
-
-        def get_profile_displayname(user_localpart):
-            return defer.succeed("Frank")
-        self.datastore.get_profile_displayname = get_profile_displayname
-
-        def is_presence_visible(*args, **kwargs):
-            return defer.succeed(False)
-        self.datastore.is_presence_visible = is_presence_visible
-
-        def get_profile_avatar_url(user_localpart):
-            return defer.succeed("http://foo")
-        self.datastore.get_profile_avatar_url = get_profile_avatar_url
-
-        self.presence_list = [
-            {"observed_user_id": "@banana:test", "accepted": True},
-            {"observed_user_id": "@clementine:test", "accepted": True},
-        ]
-        def get_presence_list(user_localpart, accepted=None):
-            return defer.succeed(self.presence_list)
-        self.datastore.get_presence_list = get_presence_list
-
-        def user_rooms_intersect(userlist):
-            return defer.succeed(False)
-        self.datastore.user_rooms_intersect = user_rooms_intersect
-
-        self.handlers = hs.get_handlers()
-
-        self.mock_update_client = Mock()
-        def update(*args, **kwargs):
-            # print "mock_update_client: %s, %s" %(args, kwargs)
-            return defer.succeed(None)
-        self.mock_update_client.side_effect = update
-
-        self.handlers.presence_handler.push_update_to_clients = (
-                self.mock_update_client)
-
-        hs.handlers.room_member_handler = Mock(spec=[
-            "get_joined_rooms_for_user",
-        ])
-        hs.handlers.room_member_handler.get_joined_rooms_for_user = (
-                lambda u: defer.succeed([]))
-
-        # Some local users to test with
-        self.u_apple = UserID.from_string("@apple:test")
-        self.u_banana = UserID.from_string("@banana:test")
-        self.u_clementine = UserID.from_string("@clementine:test")
-
-        # Remote user
-        self.u_potato = UserID.from_string("@potato:remote")
-
-        self.mock_get_joined = (
-            self.datastore.get_rooms_for_user
-        )
-
-    @defer.inlineCallbacks
-    def test_set_my_state(self):
-        self.presence_list = [
-            {"observed_user_id": "@banana:test", "accepted": True},
-            {"observed_user_id": "@clementine:test", "accepted": True},
-        ]
-
-        mocked_set = self.datastore.set_presence_state
-        mocked_set.return_value = defer.succeed({"state": OFFLINE})
-
-        yield self.handlers.presence_handler.set_state(
-                target_user=self.u_apple, auth_user=self.u_apple,
-                state={"presence": UNAVAILABLE, "status_msg": "Away"})
-
-        mocked_set.assert_called_with("apple",
-            {"state": UNAVAILABLE, "status_msg": "Away"}
-        )
-
-    @defer.inlineCallbacks
-    def test_push_local(self):
-        def get_joined(*args):
-            return defer.succeed([])
-
-        self.mock_get_joined.side_effect = get_joined
-
-        self.presence_list = [
-            {"observed_user_id": "@banana:test", "accepted": True},
-            {"observed_user_id": "@clementine:test", "accepted": True},
-        ]
-
-        self.datastore.set_presence_state.return_value = defer.succeed(
-            {"state": ONLINE}
-        )
-
-        # TODO(paul): Gut-wrenching
-        from synapse.handlers.presence import UserPresenceCache
-        self.handlers.presence_handler._user_cachemap[self.u_apple] = (
-            UserPresenceCache()
-        )
-        self.handlers.presence_handler._user_cachemap[self.u_apple].update(
-            {"presence": OFFLINE}, serial=0
-        )
-        apple_set = self.handlers.presence_handler._local_pushmap.setdefault(
-                "apple", set())
-        apple_set.add(self.u_banana)
-        apple_set.add(self.u_clementine)
-
-        yield self.handlers.presence_handler.set_state(self.u_apple,
-            self.u_apple, {"presence": ONLINE}
-        )
-        yield self.handlers.presence_handler.set_state(self.u_banana,
-            self.u_banana, {"presence": ONLINE}
-        )
-
-        presence = yield self.handlers.presence_handler.get_presence_list(
-                observer_user=self.u_apple, accepted=True)
-
-        self.assertEquals([
-            {"observed_user": self.u_banana,
-                "presence": ONLINE,
-                "last_active_ago": 0,
-                "displayname": "Frank",
-                "avatar_url": "http://foo",
-                "accepted": True},
-            {"observed_user": self.u_clementine,
-                "presence": OFFLINE,
-                "accepted": True}
-        ], presence)
-
-        self.mock_update_client.assert_has_calls([
-            call(
-                users_to_push={self.u_apple, self.u_banana, self.u_clementine},
-                room_ids=[]
-            ),
-        ], any_order=True)
-
-        self.mock_update_client.reset_mock()
-
-        self.datastore.set_profile_displayname.return_value = defer.succeed(
-                None)
-
-        yield self.handlers.profile_handler.set_displayname(self.u_apple,
-                self.u_apple, "I am an Apple")
-
-        self.mock_update_client.assert_has_calls([
-            call(
-                users_to_push={self.u_apple, self.u_banana, self.u_clementine},
-                room_ids=[],
-            ),
-        ], any_order=True)
-
-    @defer.inlineCallbacks
-    def test_push_remote(self):
-        self.presence_list = [
-            {"observed_user_id": "@potato:remote", "accepted": True},
-        ]
-
-        self.datastore.set_presence_state.return_value = defer.succeed(
-            {"state": ONLINE}
-        )
-
-        # TODO(paul): Gut-wrenching
-        from synapse.handlers.presence import UserPresenceCache
-        self.handlers.presence_handler._user_cachemap[self.u_apple] = (
-            UserPresenceCache()
-        )
-        self.handlers.presence_handler._user_cachemap[self.u_apple].update(
-            {"presence": OFFLINE}, serial=0
-        )
-        apple_set = self.handlers.presence_handler._remote_sendmap.setdefault(
-                "apple", set())
-        apple_set.add(self.u_potato.domain)
-
-        yield self.handlers.presence_handler.set_state(self.u_apple,
-            self.u_apple, {"presence": ONLINE}
-        )
-
-        self.replication.send_edu.assert_called_with(
-                destination="remote",
-                edu_type="m.presence",
-                content={
-                    "push": [
-                        {"user_id": "@apple:test",
-                         "presence": "online",
-                         "last_active_ago": 0,
-                         "displayname": "Frank",
-                         "avatar_url": "http://foo"},
-                    ],
-                },
-        )
-
-    @defer.inlineCallbacks
-    def test_recv_remote(self):
-        self.presence_list = [
-            {"observed_user_id": "@banana:test"},
-            {"observed_user_id": "@clementine:test"},
-        ]
-
-        # TODO(paul): Gut-wrenching
-        potato_set = self.handlers.presence_handler._remote_recvmap.setdefault(
-            self.u_potato, set()
-        )
-        potato_set.add(self.u_apple)
-
-        yield self.replication.received_edu(
-            "remote", "m.presence", {
-                "push": [
-                    {"user_id": "@potato:remote",
-                     "presence": "online",
-                     "displayname": "Frank",
-                     "avatar_url": "http://foo"},
-                ],
-            }
-        )
-
-        self.mock_update_client.assert_called_with(
-            users_to_push=set([self.u_apple]),
-            room_ids=[],
-        )
-
-        state = yield self.handlers.presence_handler.get_state(self.u_potato,
-                self.u_apple)
-
-        self.assertEquals(
-                {"presence": ONLINE,
-                 "displayname": "Frank",
-                 "avatar_url": "http://foo"},
-            state)
diff --git a/tests/handlers/test_profile.py b/tests/handlers/test_profile.py
index 237fc8223c..95c87f0ebd 100644
--- a/tests/handlers/test_profile.py
+++ b/tests/handlers/test_profile.py
@@ -70,9 +70,6 @@ class ProfileTestCase(unittest.TestCase):
 
         self.handler = hs.get_handlers().profile_handler
 
-        # TODO(paul): Icky signal declarings.. booo
-        hs.get_distributor().declare("changed_presencelike_data")
-
     @defer.inlineCallbacks
     def test_get_my_name(self):
         yield self.store.set_profile_displayname(
diff --git a/tests/rest/client/v1/test_presence.py b/tests/rest/client/v1/test_presence.py
deleted file mode 100644
index 8d7cfd79ab..0000000000
--- a/tests/rest/client/v1/test_presence.py
+++ /dev/null
@@ -1,412 +0,0 @@
-# -*- coding: utf-8 -*-
-# Copyright 2014-2016 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.
-
-"""Tests REST events for /presence paths."""
-from tests import unittest
-from twisted.internet import defer
-
-from mock import Mock
-
-from ....utils import MockHttpResource, setup_test_homeserver
-
-from synapse.api.constants import PresenceState
-from synapse.handlers.presence import PresenceHandler
-from synapse.rest.client.v1 import presence
-from synapse.rest.client.v1 import events
-from synapse.types import Requester, UserID
-from synapse.util.async import run_on_reactor
-
-from collections import namedtuple
-
-
-OFFLINE = PresenceState.OFFLINE
-UNAVAILABLE = PresenceState.UNAVAILABLE
-ONLINE = PresenceState.ONLINE
-
-
-myid = "@apple:test"
-PATH_PREFIX = "/_matrix/client/api/v1"
-
-
-class NullSource(object):
-    """This event source never yields any events and its token remains at
-    zero. It may be useful for unit-testing."""
-    def __init__(self, hs):
-        pass
-
-    def get_new_events(
-            self,
-            user,
-            from_key,
-            room_ids=None,
-            limit=None,
-            is_guest=None
-    ):
-        return defer.succeed(([], from_key))
-
-    def get_current_key(self, direction='f'):
-        return defer.succeed(0)
-
-    def get_pagination_rows(self, user, pagination_config, key):
-        return defer.succeed(([], pagination_config.from_key))
-
-
-class JustPresenceHandlers(object):
-    def __init__(self, hs):
-        self.presence_handler = PresenceHandler(hs)
-
-
-class PresenceStateTestCase(unittest.TestCase):
-
-    @defer.inlineCallbacks
-    def setUp(self):
-        self.mock_resource = MockHttpResource(prefix=PATH_PREFIX)
-        hs = yield setup_test_homeserver(
-            datastore=Mock(spec=[
-                "get_presence_state",
-                "set_presence_state",
-                "insert_client_ip",
-            ]),
-            http_client=None,
-            resource_for_client=self.mock_resource,
-            resource_for_federation=self.mock_resource,
-        )
-        hs.handlers = JustPresenceHandlers(hs)
-
-        self.datastore = hs.get_datastore()
-        self.datastore.get_app_service_by_token = Mock(return_value=None)
-
-        def get_presence_list(*a, **kw):
-            return defer.succeed([])
-        self.datastore.get_presence_list = get_presence_list
-
-        def _get_user_by_access_token(token=None, allow_guest=False):
-            return {
-                "user": UserID.from_string(myid),
-                "token_id": 1,
-                "is_guest": False,
-            }
-
-        hs.get_v1auth()._get_user_by_access_token = _get_user_by_access_token
-
-        room_member_handler = hs.handlers.room_member_handler = Mock(
-            spec=[
-                "get_joined_rooms_for_user",
-            ]
-        )
-
-        def get_rooms_for_user(user):
-            return defer.succeed([])
-        room_member_handler.get_joined_rooms_for_user = get_rooms_for_user
-
-        presence.register_servlets(hs, self.mock_resource)
-
-        self.u_apple = UserID.from_string(myid)
-
-    @defer.inlineCallbacks
-    def test_get_my_status(self):
-        mocked_get = self.datastore.get_presence_state
-        mocked_get.return_value = defer.succeed(
-            {"state": ONLINE, "status_msg": "Available"}
-        )
-
-        (code, response) = yield self.mock_resource.trigger("GET",
-                "/presence/%s/status" % (myid), None)
-
-        self.assertEquals(200, code)
-        self.assertEquals(
-            {"presence": ONLINE, "status_msg": "Available"},
-            response
-        )
-        mocked_get.assert_called_with("apple")
-
-    @defer.inlineCallbacks
-    def test_set_my_status(self):
-        mocked_set = self.datastore.set_presence_state
-        mocked_set.return_value = defer.succeed({"state": OFFLINE})
-
-        (code, response) = yield self.mock_resource.trigger("PUT",
-                "/presence/%s/status" % (myid),
-                '{"presence": "unavailable", "status_msg": "Away"}')
-
-        self.assertEquals(200, code)
-        mocked_set.assert_called_with("apple",
-            {"state": UNAVAILABLE, "status_msg": "Away"}
-        )
-
-
-class PresenceListTestCase(unittest.TestCase):
-
-    @defer.inlineCallbacks
-    def setUp(self):
-        self.mock_resource = MockHttpResource(prefix=PATH_PREFIX)
-
-        hs = yield setup_test_homeserver(
-            datastore=Mock(spec=[
-                "has_presence_state",
-                "get_presence_state",
-                "allow_presence_visible",
-                "is_presence_visible",
-                "add_presence_list_pending",
-                "set_presence_list_accepted",
-                "del_presence_list",
-                "get_presence_list",
-                "insert_client_ip",
-            ]),
-            http_client=None,
-            resource_for_client=self.mock_resource,
-            resource_for_federation=self.mock_resource,
-        )
-        hs.handlers = JustPresenceHandlers(hs)
-
-        self.datastore = hs.get_datastore()
-        self.datastore.get_app_service_by_token = Mock(return_value=None)
-
-        def has_presence_state(user_localpart):
-            return defer.succeed(
-                user_localpart in ("apple", "banana",)
-            )
-        self.datastore.has_presence_state = has_presence_state
-
-        def _get_user_by_access_token(token=None, allow_guest=False):
-            return {
-                "user": UserID.from_string(myid),
-                "token_id": 1,
-                "is_guest": False,
-            }
-
-        hs.handlers.room_member_handler = Mock(
-            spec=[
-                "get_joined_rooms_for_user",
-            ]
-        )
-
-        hs.get_v1auth()._get_user_by_access_token = _get_user_by_access_token
-
-        presence.register_servlets(hs, self.mock_resource)
-
-        self.u_apple = UserID.from_string("@apple:test")
-        self.u_banana = UserID.from_string("@banana:test")
-
-    @defer.inlineCallbacks
-    def test_get_my_list(self):
-        self.datastore.get_presence_list.return_value = defer.succeed(
-            [{"observed_user_id": "@banana:test", "accepted": True}],
-        )
-
-        (code, response) = yield self.mock_resource.trigger("GET",
-                "/presence/list/%s" % (myid), None)
-
-        self.assertEquals(200, code)
-        self.assertEquals([
-            {"user_id": "@banana:test", "presence": OFFLINE, "accepted": True},
-        ], response)
-
-        self.datastore.get_presence_list.assert_called_with(
-            "apple", accepted=True
-        )
-
-    @defer.inlineCallbacks
-    def test_invite(self):
-        self.datastore.add_presence_list_pending.return_value = (
-            defer.succeed(())
-        )
-        self.datastore.is_presence_visible.return_value = defer.succeed(
-            True
-        )
-
-        (code, response) = yield self.mock_resource.trigger("POST",
-            "/presence/list/%s" % (myid),
-            """{"invite": ["@banana:test"]}"""
-        )
-
-        self.assertEquals(200, code)
-
-        self.datastore.add_presence_list_pending.assert_called_with(
-            "apple", "@banana:test"
-        )
-        self.datastore.set_presence_list_accepted.assert_called_with(
-            "apple", "@banana:test"
-        )
-
-    @defer.inlineCallbacks
-    def test_drop(self):
-        self.datastore.del_presence_list.return_value = (
-            defer.succeed(())
-        )
-
-        (code, response) = yield self.mock_resource.trigger("POST",
-            "/presence/list/%s" % (myid),
-            """{"drop": ["@banana:test"]}"""
-        )
-
-        self.assertEquals(200, code)
-
-        self.datastore.del_presence_list.assert_called_with(
-            "apple", "@banana:test"
-        )
-
-
-class PresenceEventStreamTestCase(unittest.TestCase):
-    @defer.inlineCallbacks
-    def setUp(self):
-        self.mock_resource = MockHttpResource(prefix=PATH_PREFIX)
-
-        # HIDEOUS HACKERY
-        # TODO(paul): This should be injected in via the HomeServer DI system
-        from synapse.streams.events import (
-            PresenceEventSource, EventSources
-        )
-
-        old_SOURCE_TYPES = EventSources.SOURCE_TYPES
-        def tearDown():
-            EventSources.SOURCE_TYPES = old_SOURCE_TYPES
-        self.tearDown = tearDown
-
-        EventSources.SOURCE_TYPES = {
-            k: NullSource for k in old_SOURCE_TYPES.keys()
-        }
-        EventSources.SOURCE_TYPES["presence"] = PresenceEventSource
-
-        clock = Mock(spec=[
-            "call_later",
-            "cancel_call_later",
-            "time_msec",
-            "looping_call",
-        ])
-
-        clock.time_msec.return_value = 1000000
-
-        hs = yield setup_test_homeserver(
-            http_client=None,
-            resource_for_client=self.mock_resource,
-            resource_for_federation=self.mock_resource,
-            datastore=Mock(spec=[
-                "set_presence_state",
-                "get_presence_list",
-                "get_rooms_for_user",
-            ]),
-            clock=clock,
-        )
-
-        def _get_user_by_req(req=None, allow_guest=False):
-            return Requester(UserID.from_string(myid), "", False)
-
-        hs.get_v1auth().get_user_by_req = _get_user_by_req
-
-        presence.register_servlets(hs, self.mock_resource)
-        events.register_servlets(hs, self.mock_resource)
-
-        hs.handlers.room_member_handler = Mock(spec=[])
-
-        self.room_members = []
-
-        def get_rooms_for_user(user):
-            if user in self.room_members:
-                return ["a-room"]
-            else:
-                return []
-        hs.handlers.room_member_handler.get_joined_rooms_for_user = get_rooms_for_user
-        hs.handlers.room_member_handler.get_room_members = (
-            lambda r: self.room_members if r == "a-room" else []
-        )
-        hs.handlers.room_member_handler._filter_events_for_client = (
-            lambda user_id, events, **kwargs: events
-        )
-
-        self.mock_datastore = hs.get_datastore()
-        self.mock_datastore.get_app_service_by_token = Mock(return_value=None)
-        self.mock_datastore.get_app_service_by_user_id = Mock(
-            return_value=defer.succeed(None)
-        )
-        self.mock_datastore.get_rooms_for_user = (
-            lambda u: [
-                namedtuple("Room", "room_id")(r)
-                for r in get_rooms_for_user(UserID.from_string(u))
-            ]
-        )
-
-        def get_profile_displayname(user_id):
-            return defer.succeed("Frank")
-        self.mock_datastore.get_profile_displayname = get_profile_displayname
-
-        def get_profile_avatar_url(user_id):
-            return defer.succeed(None)
-        self.mock_datastore.get_profile_avatar_url = get_profile_avatar_url
-
-        def user_rooms_intersect(user_list):
-            room_member_ids = map(lambda u: u.to_string(), self.room_members)
-
-            shared = all(map(lambda i: i in room_member_ids, user_list))
-            return defer.succeed(shared)
-        self.mock_datastore.user_rooms_intersect = user_rooms_intersect
-
-        def get_joined_hosts_for_room(room_id):
-            return []
-        self.mock_datastore.get_joined_hosts_for_room = get_joined_hosts_for_room
-
-        self.presence = hs.get_handlers().presence_handler
-
-        self.u_apple = UserID.from_string("@apple:test")
-        self.u_banana = UserID.from_string("@banana:test")
-
-    @defer.inlineCallbacks
-    def test_shortpoll(self):
-        self.room_members = [self.u_apple, self.u_banana]
-
-        self.mock_datastore.set_presence_state.return_value = defer.succeed(
-            {"state": ONLINE}
-        )
-        self.mock_datastore.get_presence_list.return_value = defer.succeed(
-            []
-        )
-
-        (code, response) = yield self.mock_resource.trigger("GET",
-                "/events?timeout=0", None)
-
-        self.assertEquals(200, code)
-
-        # We've forced there to be only one data stream so the tokens will
-        # all be ours
-
-        # I'll already get my own presence state change
-        self.assertEquals({"start": "0_1_0_0_0", "end": "0_1_0_0_0", "chunk": []},
-            response
-        )
-
-        self.mock_datastore.set_presence_state.return_value = defer.succeed(
-            {"state": ONLINE}
-        )
-        self.mock_datastore.get_presence_list.return_value = defer.succeed([])
-
-        yield self.presence.set_state(self.u_banana, self.u_banana,
-            state={"presence": ONLINE}
-        )
-
-        yield run_on_reactor()
-
-        (code, response) = yield self.mock_resource.trigger("GET",
-                "/events?from=s0_1_0&timeout=0", None)
-
-        self.assertEquals(200, code)
-        self.assertEquals({"start": "s0_1_0_0_0", "end": "s0_2_0_0_0", "chunk": [
-            {"type": "m.presence",
-             "content": {
-                 "user_id": "@banana:test",
-                 "presence": ONLINE,
-                 "displayname": "Frank",
-                 "last_active_ago": 0,
-            }},
-        ]}, response)
diff --git a/tests/rest/client/v1/test_rooms.py b/tests/rest/client/v1/test_rooms.py
index ad5dd3bd6e..a90b9dc3d8 100644
--- a/tests/rest/client/v1/test_rooms.py
+++ b/tests/rest/client/v1/test_rooms.py
@@ -953,12 +953,6 @@ class RoomInitialSyncTestCase(RestTestCase):
 
         synapse.rest.client.v1.room.register_servlets(hs, self.mock_resource)
 
-        # Since I'm getting my own presence I need to exist as far as presence
-        # is concerned.
-        hs.get_handlers().presence_handler.registered_user(
-            UserID.from_string(self.user_id)
-        )
-
         # create the room
         self.room_id = yield self.create_room_as(self.user_id)
 
diff --git a/tests/storage/test_presence.py b/tests/storage/test_presence.py
index 333f1e10f1..ec78f007ca 100644
--- a/tests/storage/test_presence.py
+++ b/tests/storage/test_presence.py
@@ -35,32 +35,6 @@ class PresenceStoreTestCase(unittest.TestCase):
         self.u_banana = UserID.from_string("@banana:test")
 
     @defer.inlineCallbacks
-    def test_state(self):
-        yield self.store.create_presence(
-            self.u_apple.localpart
-        )
-
-        state = yield self.store.get_presence_state(
-            self.u_apple.localpart
-        )
-
-        self.assertEquals(
-            {"state": None, "status_msg": None, "mtime": None}, state
-        )
-
-        yield self.store.set_presence_state(
-            self.u_apple.localpart, {"state": "online", "status_msg": "Here"}
-        )
-
-        state = yield self.store.get_presence_state(
-            self.u_apple.localpart
-        )
-
-        self.assertEquals(
-            {"state": "online", "status_msg": "Here", "mtime": 1000000}, state
-        )
-
-    @defer.inlineCallbacks
     def test_visibility(self):
         self.assertFalse((yield self.store.is_presence_visible(
             observed_localpart=self.u_apple.localpart,
diff --git a/tests/util/test_wheel_timer.py b/tests/util/test_wheel_timer.py
new file mode 100644
index 0000000000..c44567e52e
--- /dev/null
+++ b/tests/util/test_wheel_timer.py
@@ -0,0 +1,74 @@
+# -*- coding: utf-8 -*-
+# Copyright 2016 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.wheel_timer import WheelTimer
+
+
+class WheelTimerTestCase(unittest.TestCase):
+    def test_single_insert_fetch(self):
+        wheel = WheelTimer(bucket_size=5)
+
+        obj = object()
+        wheel.insert(100, obj, 150)
+
+        self.assertListEqual(wheel.fetch(101), [])
+        self.assertListEqual(wheel.fetch(110), [])
+        self.assertListEqual(wheel.fetch(120), [])
+        self.assertListEqual(wheel.fetch(130), [])
+        self.assertListEqual(wheel.fetch(149), [])
+        self.assertListEqual(wheel.fetch(156), [obj])
+        self.assertListEqual(wheel.fetch(170), [])
+
+    def test_mutli_insert(self):
+        wheel = WheelTimer(bucket_size=5)
+
+        obj1 = object()
+        obj2 = object()
+        obj3 = object()
+        wheel.insert(100, obj1, 150)
+        wheel.insert(105, obj2, 130)
+        wheel.insert(106, obj3, 160)
+
+        self.assertListEqual(wheel.fetch(110), [])
+        self.assertListEqual(wheel.fetch(135), [obj2])
+        self.assertListEqual(wheel.fetch(149), [])
+        self.assertListEqual(wheel.fetch(158), [obj1])
+        self.assertListEqual(wheel.fetch(160), [])
+        self.assertListEqual(wheel.fetch(200), [obj3])
+        self.assertListEqual(wheel.fetch(210), [])
+
+    def test_insert_past(self):
+        wheel = WheelTimer(bucket_size=5)
+
+        obj = object()
+        wheel.insert(100, obj, 50)
+        self.assertListEqual(wheel.fetch(120), [obj])
+
+    def test_insert_past_mutli(self):
+        wheel = WheelTimer(bucket_size=5)
+
+        obj1 = object()
+        obj2 = object()
+        obj3 = object()
+        wheel.insert(100, obj1, 150)
+        wheel.insert(100, obj2, 140)
+        wheel.insert(100, obj3, 50)
+        self.assertListEqual(wheel.fetch(110), [obj3])
+        self.assertListEqual(wheel.fetch(120), [])
+        self.assertListEqual(wheel.fetch(147), [obj2])
+        self.assertListEqual(wheel.fetch(200), [obj1])
+        self.assertListEqual(wheel.fetch(240), [])
diff --git a/tests/utils.py b/tests/utils.py
index 3b1eb50d8d..f71125042b 100644
--- a/tests/utils.py
+++ b/tests/utils.py
@@ -224,12 +224,12 @@ class MockClock(object):
     def time_msec(self):
         return self.time() * 1000
 
-    def call_later(self, delay, callback):
+    def call_later(self, delay, callback, *args, **kwargs):
         current_context = LoggingContext.current_context()
 
         def wrapped_callback():
             LoggingContext.thread_local.current_context = current_context
-            callback()
+            callback(*args, **kwargs)
 
         t = [self.now + delay, wrapped_callback, False]
         self.timers.append(t)