Re: APack async header compression

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

I had discussion on Slack and was requested to do a writeup on git. While
doing so I realised that though bitmaps do work, they might not be the best
way to go for this use case because timestamps can cover the same problem
with less accuracy, and accuracy isn’t exactly needed when you cache data
and don’t know when they might be needed next. Timestamps are often used in
distributed garbage collection algorithms.

So this resulted in APACK for timestamps. It turns out to be not very
different from the ideas in QMIN, but it is also not exactly the same, but
we are still trying to figure this out.

A very rough first write up is placed on

https://github.com/dvidelabs/apack

while

qmin is found at

https://github.com/litespeedtech/qmin/blob/master/id-qmin.txt

Kind Regards,
Mikkel Fahnøe Jørgensen


On 9 December 2017 at 10.34.57, Mikkel Fahnøe Jørgensen ([e-mail])
wrote:

I forgot to mention that a receiver must defer decoding of dynamic name
references until the EOX message has been received on the control channel,
otherwise it might read stale data. It must also perform the dynamic name
decoding before the next commit bitmap is send on the return control
channel. This still leads to some degree of HOL, but only on low data
volumes, and, the control stream could be given high priority.

Note that even if there are no dynamic updates in an exchange, or if the
sender chooses to send updated names as explicit names on the exchange
specific stream as well, the dynamic table may still depend on earlier
updates, so it is still not safe to decode until EOX has been seen. Some
mitigations could be taken to reduce this dependency, but it does not
appear to be worth the complexity, and possibly additional bandwidth
requirements.

The following is not exactly correct:

 "When this happens we xor the allocation bitmap into the free bitmap”

what we actually do is to clear the bits in the free bitmap which are set
in the allocation bitmap, which is then replaced with a new free bitmap
snapshot.

Kind Regards,
Mikkel Fahnøe Jørgensen


On 9 December 2017 at 00.54.11, Mikkel Fahnøe Jørgensen ([e-mail])
wrote:


Minor correction: The receiver can include all entries with refcount zero
because it only tracks what may be evicted, not what is evicted. Eviction
happens when the sender does on actual allocation from the allocation map.
What is correct though, is that we only need to scan for zero entries when
we have are running short of things to allocate.

Old text:
Refcount zero entries are only evicted when space is needed, otherwise
we loose the history needed for efficient compression.

Kind Regards,
Mikkel Fahnøe Jørgensen


On 9 December 2017 at 00.15.01, Mikkel Fahnøe Jørgensen ([e-mail])
wrote:

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.