QMIN Encoder State Diagrammed

The QMIN encoder tracks stream and dynamic table entry relationships using checkpoints. A checkpoint is a way to address a range of dynamic table entries and streams at the same time. The diagrams below describe a high-level model of the encoder state.

Table of Contents

• First header block is encoded
• Second header block is encoded
• Five header blocks encoded
• Third flush is acked
• Long-Lived Stream 11
• Marked for death
• Dropping DEAD checkpoints
• Another header block encoded
• Flush
• Implementation Notes

First header block is encoded

We will start with the encoder shortly after it began operating. Header block for Stream 5 has been encoded, with the following header fields, in order:

• X-Some-Header: 123
• X-Another-Header: 234
• X-Secret: passw0rd
• X-begin: false

Second header block is encoded

The next diagram shows the encoder state after two more things have occurred, in order:

1. Checkpoint flush has been acknowledged, making entries 62, 63, and 64 available for encoding; and
2. Header block for Stream 7 has been encoded:
   • X-Some-Header: 123 (indexed representation using entry 62)
   • X-Another-Header: 234 (indexed representation using entry 63)
   • X-begin: false (new entry 65)

Five header blocks encoded

In this diagram, we are skipping ahead: five header blocks have been encoded, three flushes have been issued, of which two have been acked. We can see that

• Entries 62, 63, 64, and 65 are available for encoding, while entries 66, 67, and 68 are not.
• The PENDING checkpoint references entries 66 and 67, which should become available for encoding when the flush is acked.

Third flush is ACKed

Since the previous state, two first streams, Stream 5 and Stream 7, have been closed, and the flush has been acknowledged. Note that entries 66 and 67 are now available for encoding.

There are three LIVE checkpoints, each referenced by at least one stream. They cannot be marked DEAD yet.

Long-Lived Stream 11

It turns out that Stream 11 is going to live for a long time. While it is uploading 7 TB of data, Stream 9 and Stream 13 have finished. One of the LIVE checkpoints is no longer referenced by any streams.

Marked for death

The encoder can use a number of strategies to decide when to declare a checkpoint DEAD. Just because a LIVE checkpoint is not referenced by any streams does not mean that it should be declared DEAD: the entries it references may repeat again and so, unless there is memory pressure, the encoder should keep its checkpoints LIVE. Nevertheless, here, for illustration purposes, we declare a LIVE checkpoint DEAD.

Note how entry 65 is no longer available for encoding, as the victim checkpoint was the only one referencing it.

Dropping DEAD checkpoints

Once a DEAD checkpoint is not referenced by any streams, there is no reason to keep it around -- it can be immediately dropped.

Because entry 65 is no longer referenced by any checkpoint, it is evicted and the slot 65 in the dynamic table becomes available for reuse.

Another header block encoded

Stream 15 is created and its header block encoded:

• X-Another-Header: 234 (indexed representation, entry 63)
• Another-Header: Dude! (new entry, use smallest available dynamic entry -- 65)

Flush

Here, Stream 11 has finished and the encoder flushes again.

Implementation Notes

Note that the proof-of-concept QMIN Encoder does not make objects for streams; nor does it maintain links from checkpoints to dynamic table entries or vice versa. Instead, it uses bitmap-based lists of entry and stream IDs per checkpoint object. This approach uses less memory and is simple to implement.