We describe algorithms to scalably support durable subscriptions in a publish-subscribe system. Durable subscriptions are guaranteed exactly-once message delivery, despite periods of disconnection from the system. Our algorithms persistently log each message only once in the system, and can support administratively speci.ed ?early-release? policies that reclaim persistent storage in the presence of misbehaving durable subscribers. To ef.ciently recover messages missed by a disconnected durable subscriber, without re.ltering messages published while the subscriber was disconnected, we persistently log .ltering information in a manner optimized for the read/write pattern of durable subscriptions. Consolidation of data-structures across all subscribers that are done with catching up (after a disconnection), helps the system support a larger number of subscribers.

We experimentally demonstrate the low-latency and scalability properties of our implementation, both in the presence and absence of failures.