deleting old mailbox messages: adding DELETE, maybe sequence numbers

The Problem

Currently, all messages sent to a mailbox are retained until the mailbox is finally CLOSEd by both parties. For old-style (pre-dilation) file-transfer, this isn't a big deal, because the mailboxes don't live longer than the (single) file transfer, and the total number of messages is pretty small. A typical file sender will emit PAKE, VERSION, a phase=0 message with a transit key, and phase=1 message with an offer key. The rest of the data goes over the Transit connection. Each of these four messages are pretty small, just a few hundred bytes.

When Dilation is released, especially once we get a GUI app working and persistent Seeds, we'll have arbitrarily long-lived mailboxes. The messages will remain small, but each time one side loses or changes its network presence (and a new direct connection needs to be established), we'll have a new round of four DILATE-nn messages being sent back and forth: type=reconnect from the leader, type=reconnecting from the follower, then a pair of type=connection-hints in each direction.

Under the current scheme, these messages will accumulate for a long time, until the apps on both ends have shut down and stop maintaining the shared mailbox, allowing it to be pruned. But neither app needs these messages to stick around: once they've received and durably processed the message, the server should be allowed to delete it.

I'm thinking about two variants of this approach, with different constraints and efficiencies. Both introduce a MESSAGE-ACK client-to-server command. The second also introduces sequence numbers and requires both clients to be new enough to participate.

MESSAGE-ACK only

The first plan is to introduce a new client->server command tenatively named MESSAGE-ACK. Each time a message is received and processed (durably!) by a client, it can send this command to inform the server that it does not require the message to be retained any longer. The command record will have the following properties:

• type: MESSAGE-ACK
• their-phase: the phase= of the message that can be deleted
• their-side: the side of the message that can be deleted (always the peer's side)

The server reacts to a MESSAGE-ACK by deleting the matching row from the messages table. Note that this must be constrained within the one mailbox to which the client connection is bound: guessing somebody else's side= must not be sufficient to delete their messages.

In this scheme, the server does not remember the deletion, so if the client-server connection is lost before the MESSAGE-ACK arrives, the message might be retained, and will be re-delivered to any client that subsequently reconnects. Clients must tolerate this duplication (but of course they must already tolerate it without this change). Also in this scheme, the other client does not need to do anything special to enable its peer to delete messages. It is entirely possible for one client to know about MESSAGE-ACK and the other not, resulting in half the messages being deleted and the other half being retained. However I expect to have this new feature in place before we fully enable Dilation, so such split-version interactions wouldn't be using Dilation anyways, making the space consumption a non-issue.

sequence number plus MESSAGE-ACK

I've occasionally lamented making the mailbox protocol so open-ended. The server is currently not obligated to provide ordering or non-duplication guarantees, pushing this reponsibility onto the client. And the phase= markers, which are completely open-ended (and opaque to the server) do not provide complete ordering information. My intention was to simplify the server, and help clients be more tolerant of network ups and downs, especially for waterken-style durable clients who save their state changes to a persistent database before releasing their output messages. And I hadn't entirely ruled out having three or more participants in a mailbox, for some sort of as-yet-undesigned group session establishment scheme.

From a client's point of view, scoped to within a given mailbox, the universe consists of a set of messages that have been emitted by one or more sides (one of which is probably your own), which occasionally grows. When the growth is a message from their peer, they might need to react to it.

But this makes analysis and discussion of the protocol a bit more difficult. If it were a durable message pipe, in which there was some point within the client that received exactly one notification per peer message (regardless of network reconnections), some of the state machines could be simplified. In addition, we'd have an easier time specifying an efficient server-message-deletion protocol.

To accomplish this, or perhaps to merely nudge the protocol in this direction for future improvements, we could introduce a sequence number to each message. The server would be aware of sequence numbers, making them part of both the client->server protocol and the client->client protocol.

We would update the server's messages table to include a seqnum field, which would be NULL for messages from older clients that do not provide sequence numbers. The client->server ADD message would change from { phase, body } to { seqnum, phase, body }, with .seqnum being an integer >= 0 and less than the javascript-imposed JSON integer size limit of about 2^52. The server would store the seqnum in each messages row, and deliver it in each outbound MESSAGE notification (which become { side, seqnum, phase, body, id }).

The MESSAGE-ACK command then cites { type, side, seqnum } instead of a phase=. The server remembers the { side, seqnum } with the highest seqnum in a new mailbox_message_acks table (CREATE TABLE mailbox_message_acks (mailbox_id, side, seqnum)), and is allowed to immediately delete any message (including newly-arrived ones) whose side matches and seqnum is equal or lower. Note that messages whose seqnums are NULL are protected from deletion: the phase= string does not provide enough information to safely identify which messages are "old" without introducing additional coupling between the client-to-server and client-to-client protocols (e.g. introducing DILATE-nn would require server changes to realize that DILATE-12 is newer than DILATE-8, etc). The mailbox_message_acks rows are deleted at the same time the mailbox is deleted.

This enables clienst to efficiently delete multiple messages at once (the client could Nagle the MESSAGE-ACK commands, waiting until it has seen a batch and sending a single deletion request at the end), although our pipelining opportunities are pretty shallow so I don't expect this to be a big win.

This would also enable the client to implement a re-ordering filter in front of the inbound messages, iff their peer is new enough to include seqnums, and if they have some way to know what message to expect next. The client would probably remember a last-processed-seqnum in their durable storage. If a message arrives that is equal or lower than that number, it ignores the message and sends a MESSAGE-ACK. If the message is max+1, it processes the message, updates its recorded max, and sends a MESSAGE-ACK. If the message is max+2 or higher, it queues the message until it sees the expected max+1.

It might be helpful if the server provided a hint about the maximum seqnum present for the peer's side=. We don't currently have a direct response to the OPEN message, but if we did ("OPENED"?) it could include a dictionary of { side: max_seqnum } data.

Rejected Approaches

My original thought was to define a set of linear orderings for the various phases, have the server be aware of them, and have a MESSAGE-ACK for e.g. DILATE-12 allow the server to also delete DILATE-1 through DILATE-11 for that side. In particular, the post-quantum PAKE work will require new PAKE phases (at least PAKE-1, maybe PAKE-2 as well), which are subject to the same when-to-delete considerations as application-level messages. This would require at least three orderings: PAKE (-1, -2, .., ending with VERSION), DILATE (-1, -2, ongoing), and the numeric application-level phases. On the plus side, this would work even with older clients who don't supply sequence numbers. On the minus side, it would entangle the server with the client-to-client protocol. To be fair, this wouldn't be hard to manage, since in general it's easy to upgrade the server to e.g. a version that knows about DILATE-nn before any clients start using Dilation, but as a general principle that's not an entanglement I want.

No implementation files or tests are named. Start by resolving whether the MESSAGE-ACK-only or sequence-number design is wanted, then trace the messages table, ADD and MESSAGE handling, and mailbox lifecycle. Done requires an agreed protocol and compatibility behavior for MESSAGE-ACK, sequence numbers, and mailbox_message_acks.