There are multiple ways of building subscriptions on top of remote scry. The two extremes of the design space are naive polling and statefully acked push notifications, both of which pose their own performance problems. This document will describe a sequence of optimizations building from naive polling to arrive at a happy middle ground that brings both performance issues under control without placing unduly complex requirements on the runtime.
In this system, the subscriber polls at some interval for the next update. For the rest of this document, consider a chat system where the subscriber ~sub polls the publisher ~pub for /~pub/chat/34, the 34th chat message in a channel. ~sub has already received the response for /~pub/chat/33, the previous message. Now ~sub tries to retrieve the next message.
The hard part is that most of the time, when ~sub sends a scry request packet to ~pub asking for the first packet of the /~pub/chat/34 message, that message doesn't exist yet. Let's say the channel typically gets one message every ten minutes. If there are 100 subscribers and they each poll once every 6 seconds, almost all requests going over the network will be trying to download data that doesn't exist yet.
Well, it's still a relatively small number of network packetss, so that might not be a huge problem. But naively, the publisher Vere has to +peek into Arvo again on every packet until a request succeeds and the result can be cached. Vere can't cache the negative response, since Vere doesn't know whether /~pub/chat/34 exists yet. This means we're running Nock just to drop packets, and doing it on repeat for every subscriber for every subscription update -- talk about bad asymptotics.
One could imagine tuning this so that each subscriber only retries a request once a minute, instead of ten times a minute. This would reduce load on the publisher by 10x, but then the subscriber needs to wait on the order of a whole minute before it knows about new data. For a direct message channel or a lively conversation, this is a non-starter.
Let's now examine the antithesis of naive polling: statefully acked push notifications. This is what Urbit does now (1/3/2021). Every time ~pub has a new chat message, it enqueues an outgoing message in Ames for each subscriber. Ames then retries each packet until the subscriber acks it, backing off using a TCP-inspired congestion control algorithm. When ~pub receives an ack from a subscriber, its runtime injects a new Arvo event that causes ~pub to update its state and stop retrying that packet.
This is reliable and doesn't cause latency problems (beyond those implied by Urbit's event log model itself, usually 5-10ms on an SSD), but it requires that ~pub write every ack packet to disk. This is O(n) in the number of subscribers, which also isn't great asymptotics -- especially because those disk writes are per-packet, not just per-message. That's not a big deal for chat messages, which are usually a single packet, but it's significantly worse for most other applications, which tend to broadcast pieces of data larger than a single lines of text.
Intermediate solutions can mitigate these problems, but it's important not to require too much complexity in the runtime or fail to maintain exactly-once delivery.
Instead of always polling every k seconds naively, or doing naive exponential backoff, retrying a scry request for the next item in a subscription could start at an interval governed by the expected rate of new subscription updates, as estimated from recent data. If a chat channel has had a message, say, every minute, for the last, say, three minutes, the retry interval could start at 20 seconds, to maintain a 33% expected hit rate initially, until it starts to back off. To maintain that same percentage of wasted packets for a channel with one message every three seconds, the initial retry interval would be one second, although we might want a cost function on wasted packets that increases as the message rate increases, so maybe it would be better to retry, say, every two seconds, so that only roughly one out of three packets is wasted.
I'm sure there's a better way to schedule retries by assuming subscription updates follow a certain probability distribution, such as a Poisson process, and continually estimating the parameters of the distribution. A Poisson process assumes independent event intervals, though, whereas chat channels and most other social protocols probably exhibit clusters of events that happen more frequently while people are actively communicating. Maybe a geometric Poisson distribution would be a more accurate model than a naive Poisson distribution -- we could look at historical chat data to determine what distribution fits best.
Ideally whatever system we use here will have a small number of tunable parameters to make it easier to measure and keep stable.
To reduce the CPU load caused by packets requesting data that doesn't exist yet, Vere could ask Arvo to notify it once the data comes into existence. Let's say that Vere asks Arvo to notify it about /~pub/chat/34 once it receives two premature requests for it. Vere injects an event into Arvo asking it to emit an effect once /~pub/chat/34 exists.
Until it gets that notification, Vere remembers (in memory, not persistently across restarts) that Arvo has not yet generated data at that path, so it can drop every packet requesting that data without needing to run any Nock.
Once Arvo creates data at this path, it notifies Vere by emitting an effect. Vere then "drops shields" and subsequent requests for this path are no longer automatically dropped by Vere. Arvo could potentially include the scry response data in the effect, which Vere could use to prime its scry cache so that it never has to run Nock again to field this scry request. This would also enable the next optimization, optimistic broadcast. Or Vere could just relay the next request to Arvo as a +peek, as if the shielding had never happened.
This optimization should allow for a shorter scry request max retry interval, since it drastically reduces the load on the publisher for each premature request packet.
Note that it's important for Vere to inject the subscription event immediately after a premature request, to make sure there were no intervening events that could have caused the data to pop into existence before the subscription is initialized. Also note that this mechanism requires the presence of a notifications system inside the Arvo kernel too, which further implies that concrete paths with simple attached listeners are likely to be more performant than repeatedly running a dynamic scry request for each subscription after every app activation.
It would be advantageous for ~pub to push /~pub/chat/34 out assoon as it exists, without waiting for the next poll from each of its subscribers. This can be done by building on top of the previous optimization.
Every time a request arrives for a future scry path, Vere would the ship that requested that path to a set of requester ships for that path, stored in its transient state. Then when Arvo notifies Vere with the scry response, Vere primes its cache with all the packets in the response and broadcasts the first response packet (requests for a new subscription update begin by requesting only the first packet of the response message) to each ship in its set of requester ships.
This is an optimistic broadcast because it isn't acknowledged. Any of the subscriber ships could fail to hear this broadcast packet -- however, the system as a whole remains reliable: any ship that missed the broadcast is still running a polling loop that will eventually fetch the data. We should consider running each broadcast a few times, with, say, one repeat after 33ms and one after 1s, since it's cheap for the publisher and reduces the chance that any given subscriber will miss all three broadcasts and only hear about the data from a poll.
A system with a dynamic poll interval and Vere-to-Arvo subscriptions should be viable and scalable. Neither unacceptably high latency nor onerous publisher disk write load should afflict such a system; reliable delivery is maintained across process restarts; runtime requirements are not onerous, and naively polling runtimes will still work, just less scalably.
Optimistic broadcast is probably not needed to reach a workable system, although it could improve latency considerably and shouldn't be infeasibly complex.
I expect the most difficult part of this to get right will be optimizing the dynamic polling interval, although reaching something stable with acceptable performance should be relatively straightforward even with simplistic modeling.