APack async header compression

[Mikkel Fahnøe Jørgensen <[e-mail]>]

OK, it turns out this async compression problem is very similar to certain
async problems I have been working with related to distributed garbage
collection, so I wrote up an algorithm based on exchanging bitmaps. At
first it may sound a bit complex and it does require a good bitmap
implementation, but it doesn’t have very much overhead nor any difficult
heuristics. The main cost is a bitmap of dictionary size per active request
aside from the dictionary itself so this is 100 bytes if there are 800
entries in the dynamic table. It also requires a reference count per entry
on the sender side but this count only need to go up to the number of
concurrent requests, so typically one byte. Beware of dragons, I just made
it up, but I do have somewhat similar stuff that is actually working.

The main idea is to have a free bitmap lazily synchronised between sender
and receiver and prevent freeing up entries still in use. There is a level
of HOL but it only delays eviction of old entries. There is only one shared
dictionary.


# APack

An async header compression scheme.

## Problem

We need to send an ordered list name/value pairs a strings from a sender
to a receiver, typically, but not necessarily a HTTP header list. We
call this an exhange, although it is essentially one-directional but we
expect the name/value list to be used for constructing a subsequent
response that we need not be concerned with here.

We want to reduce the size of the exchange without significant
complexity and time/space resource consumption and we must protect the
receiver from abuse.

Also we want to avoid optionally compression on some name/value pairs
because that could compromise secrecy, for example a password field.

In addition we want to have multiple exchanges and allow later exchanges
to benefit from earlier exchanges to increase the compression ratio when
reasonable.

Multiple exchanges can happen overlapped in time. Each exchange happens
over an ordered stream but seperate exhanges happen on separate
uni-directional streams without any implied ordering across streams. We
can have bi-directional streams too, but prefer not when not needed.

The sender and the receiver has shared state across the exhanges and all
exhanges, while active, has access to one or more shared bi-direcitonal
control streams over which global synchronization can be achieved.
However, if we only relied on shared streams we would have head of line
blocking (HOL) unnecessarily introducing dependencies across exhanges.


## Solution

The values are always sent explicitly as a string while the names are
sent via a compression scheme that can improve across exchanges. The
values may be compressed in a simplistic manner, but it carries no
state. Runlength encoding and static huffman encoding is possible, but
we just assume value is sent as is, because it does not affect any other
part of the operation. We call this local string compression.

Hence we focus on names. Names are either sent a strings in the same
form as values. We call this explicit names. Explicit names may be
subject to local string compression. Otherwise names are sent
by reference into a dictionary that is known to both sender and
receiver. We call this implicit names. We have to forms of implicit
names: dynamic and static. Static names are a list of names known in
advance out of band each assigned a unique index. Dynamic names a
references into a dynamic dictionary that is updated by the sender and
read by the receiver. When a dictionary is updated, the name is sent as
an explicit string subject to local string compression.

Our primary concern is now how to update the dicationary such that
subsequent implicit dynamic name references will see the correct
dictionary value.

An exchange is roughly communicated as a list of commands where a
command eithers sends a dynamic dictionary update, or name/value pair
where the name is either explicit, implicit dynamic, or implicit static.
When all name value pairs are sent, a final command indicates
completion.

If we only had one exchange at a time this would be all we needed
because a dictionary could just be updated before using the value.
To conserve space, some dictionary entries must be evicted. This can be
explicit, or implied by a dictionary update because it is known to
overtake an existing location.

Abuse can be avoided by requiring that the sender reuses locations
instead of indefinintely adding new entries and a limit on the number of
entries can be negotiated in advance or out of band.

The above is roughly the HPACK compression scheme without the gritty
practical details.

However, we need to handle multiple exchanges concurrently.

The following will deal with an async solution.


## Asynchronous Problems

We are not concerned with static names or and explicit names because
these are transmitted trivially on single exchange stream.

This leaves us with dynamic dictionary updates and references.

We could send all updates on a shared control stream and all references
on specific exhange stream. The only problem is that the reference might
not have arrived yet, or it might have been replaced or evicted before
the reference arrives.

We could solve this problem by splitting the dictionary into multiple
read only groups, sometimes called an epoch or a checkpoint such that a
reference is known to belong one such. The trick is then to ensure the
group survives long enough via coordination between sender and receiver.
This is not necessarily a bad idea, but since it has been explored, we
take a different approach.


## Asynchronous Solution

When a dictionary entry is updated, this always happens on the control
channel from sender to receiver. When a reference is sent on an exchange
stream the sender increments a reference count locally on the dictionary
entry but does not transmit it. When an exhange completes, this fact is
sent on the control channel along with the exchange id and then
decrements local reference counts on all entries sent through the
exchange. The end of exchange message is called EOX.

When the receiver sees an EOX message on the control channel it first
checks a dead EOX map. If found, the dead entry is removed and no
further action is taken. Otherwise receiver places the EOX message on a
EOX queue that can also be accessed by EOX id. A scan will normally
suffice due to the access pattern.  The EOX queue entry has an empty
eviction bitmap which will be discussed later.

The receiver does not implicitly evict any dictionary entries and the
sender does not evict any entries that do not have refcount zero.
Refcount zero entries are only evicted when space is needed, otherwise
we loose the history needed for efficient compression.

If we assume the dictionary is table with 1000 entries, we can have a
bitmap with 1000 entries. The sender periodically sends eviction bitmaps
that may be runlength compressed.

The receiver processes eviction bitmaps by finding the most recent EOX
entry and merges the new eviction bitmap into it. If the queue is empty
then all entries in the bitmap are evicted immediately. When the
receiver evicts an entry it marks this in a commit bitmap that is
initially empty. The receiver periodically sends the commit bitmap back
to the sender while merging it into a free bitmap and clears the commit
bitmap. The free bitmap is initially completely set but will have been
partially cleared once there are commit bits.

When the sender receives a commit bitmap it merges it into its freemap
that also originally was complete set, but is no more.

When the reciever completes an exchange on the dedicated exchange
channel it looks up the exchange ID in the EOX index. If it finds any it
removes the EOX entry and merges its eviction bitmap with the next older
entry. If there is no older entry the bitmap is merged with the commit
bitmap. If there is no matching EOX entry in the EOX queue, an entry is
made in a dead EOX map.

We can now see how we can allocate new dictionary entries:

The receiver has free bitmap that is initially complete set. A working
copy of the bitmap is saved. This is called the allocation map. It is
not strictly needed, but helpful because it doesn't change when the
commit bitmaps messages are used to update the free bitmap.

The sender maintains a current position in the allocation bitmap which
is originally at the first non-empty bit. (We assume there is one for
now).  The next allocation happens at the current index and the current
index is advanced. The name is send on the control channel along with
the index. We can avoid sending the index with a bit more coodination
but for simplicity lets assume we send the index along.  Eventually we
reach the end of the allocation bitmap. When this happens we xor the
allocation bitmap into the free bitmap to clear the consumed positions
then make a new snapshot of the free bitmap and start over. If we still
do not have a free loation, then we have no free location and we proceed
with sending explicit names on each exhchange separately.

We can avoid sending the index with each name update if we carefully
coordinate when the allocation bitmap is snapshot. But it might not be
worth the complexity.

By snapshotting the free bitmap into the allocation bitmap we ensure
that that we evict older entries first but when we send the index with
each name update we could also choose any arbitrary set bit in the free
bitmap directly and clear that bit.