“and this is me starting with something that was *useful*”
Back in March, Aljoscha and myself huddled at a hotel bar with adz, glyph, and sam from p2panda. We’d decided we were going to draft and submit a new grant proposal hours before said grant’s deadline. Collaboration between our projects had always seemed like a bit of a utopian idea, but we finally had convergent goals.
“Project title?” said Aljoscha, hovering his mouse over the empty form input.
“Hmmm… put Pillow” said adz. “We can always change it later”.
Pillow is a new collaboration between p2panda and worm-blossom. It’s a way for p2panda apps to quickly store and retrieve data from highly available peers. These highly available peers don’t know anything about p2panda data, but they do have decentralised, capability-powered permissions, can happily evict stale data, and can efficiently sync with each other. That’s because they’re Willow peers!
In this grant we’ll be implementing WTP, meaning that at long last Willow peers will be able to sync over the internet via range-based set reconciliation. We’ll also be developing WTP-powered servers with web interfaces for configuring capabilities, data eviction, and viewing storage usage.
The first users of these Willow ‘support peers’ will be p2panda apps, which will be able to interface with them via Pillow. The idea is that the Willow-powered peers don’t need to do all the stuff a p2panda peer usually does, and will be freed up to act as oblivious (but permissioned) storage.
Not only will we be working with the pandas on this project, but we’ll also be bringing a new member into worm-blossom (more on that later).
In the meantime, I’m getting back on my feet and using those feet to make silly announcement videos.
~sammy
I just came home from a productive walk with some realisations about message encodings for the WTP. These center around statefulness of peers, optimised relative encodings, and request cancellation.
The most basic requests are purely stateless: a peer issues the request, and then simply discards all state that pertains to it. Consequently, the (encoding of the) response must be fully self-contained. First realisation: such responses are indistinguishable from eagerly pushed messages — a peer might as well send such responses without ever having received a corresponding request, and the other peer would be unable to tell. I spent the past two weeks trying to argue against eagerly pushed messages, and now I feel a bit silly.
The other option are stateful requests: a peer issues a request, assigns it a request id, and keeps some state associated with the request. The response contains the request id, and can refer to the state for more efficient encodings. For example, when requesting a Willow entry in a specific namespace, the response encoding can omit that namespace. Second realisation: protocols can easily support both modes of operation. Requests can simply indicate whether responses should be standalone (allowing for stateless requesters) or whether they should be optimised (forcing the requester to keep state).
Moving on to message cancellation: as far I can tell, cancellation (by the requester) serves two important purposes. The obvious one is that it can prevent large responses from being sent only to be discarded upon arrival. The second, less obvious purpose is that cancellation allows the requester to free up any state it had to keep around to be able to decode and process an eventual response. This leads to the rather obvious third realisation: there is no sensible notion of cancellation for stateless requests — if a peer does not even record that it sent a request, it cannot later cancel it. And there is no state for it to free up anyway (though preventing pointless responses would still be desirable, of course).
For stateful requests, there is a more interesting dynamic going on. When using optimised response encodings that rely on state kept by the requester, the requestor cannot immediately clean up its state after sending a cancellation. Concurrently to sending the cancellation, the other peer might have sent a response, after all. And decoding that response requires the old state. Hence, realisation number four: stateful requests imply that cancellations must be confirmed by the other peer before state can be cleared.
This, frankly, is not great. Thankfully, there is a way by which to combine efficient encodings of responses to stateful requests with immediate, non-interactive cancellation: prefixing responses with their length allows the receiver to discard the response from the communication channel and then keep decoding the next messages even after having cleaned up the state that would have been required to properly parse the response. This was realisation number five.
I'm happy with this outcome: letting peers indicate whether their requests are stateful or stateless allows for incremental implementation of a protocol, by starting with the easier-to-implement stateless variants only. And stateful messages with their more efficient responses still do not force requesters to keep around state until their peer cooperates. This is a lot better than what the current Willow Confidential Sync draft offers (mandatory stateful encodings, mandatory cooperative cancellation).
What remains is a final meta realisation: it feels odd that I needed to come up with these approaches myself, after years of being active in the space. We really need better teaching material. I know I'm slightly peculiar in my emphasis on (bounded) state management in communication protocols, and I know that using state for optimising message encodings is a topic that will be skipped by anyone who wants to simply use a serialisation library and not think about encodings at all. But still, everything I've been writing about today is fundamental to how communication works. Guess I need to add yet another article-to-write to my todo list =S
~Aljoscha
It is now a few hours after writing my first editorial, and the consequences of these realisations for the WTP are starting to sink in. The initial WTP draft had both RequestGet messages for requesting individual entries (and the corresponding ResponseGet messages) and RequestPut messages for eagerly pushing an entry to the other peer. Here is the key insight: ResponseGet and RequestPut carry the same information. The only difference is that RequestPut uses an absolute encoding, whereas ResponseGet uses an encoding relative to the corresponding RequestGet message. In a design where the same messages can be encoded either absolutely or relatively, these two message types can merge into a single type.
And this can be an overarching design theme for the WTP. Instead of thinking of messages in terms of requests and responses, as many messages as possible should admit both absolute and relative encodings. Specifically this means:
- Asking for an entry (and/or its payload): absolute only.
- Sending an entry: absolute, or relative to anything that asks for one or more entries.
- Sending a (part of a) payload: absolute, or relative to a message asking for a payload.
- Asking for all entries in an area or range (and optionally supplying metadata — fingerprint, entry count, and/or total payload lengths — about one's own entries in that area or range): absolute, or relative to a message asking for a super-area or super-range.
- Cancelling a “request”: relative to anything asking for one or more entries.
I want to note that where I write “absolute” encoding, that is only meant in the sense that the encoding is not relative to a dynamically indicated message. To make the encodings as efficient as possible, the spec might still use relative encodings even for standalone messages. To give an example: peers could be mandated to remember the last entry they sent. Each send-entry message could then be encoded relative to the previously-sent entry, allowing, for example, to indicate with a single bit that the current entry has the same namespace id as the previous one. The crucial point is that such encodings require only a constant amount of space, irrespective of the behaviour at runtime, whereas encodings relative to any previous message would require tracking state proportional to the number of previous messages. Another application of this technique will allow transmitting payload slices while keeping the corresponding entry and/or slice start purely implicit.
Aside from a certain elegance, breaking up the request-response dichotomy has a tangible benefit: this design allows peers to express and run both symmetric and asymmetric range-based set reconciliation. The old design was restricted to client-driven asymmetric reconciliation only, exactly because requests for ranges could not be sent in response to other such requests.
THIS IS SHAPING UP NICELY, I AM QUITE EXCITED!
~Aljoscha
We have been teasing the 