Part 3 of 14
Reliability and fragmentation
A network drops packets, reorders them, and refuses to carry a message larger than a few kilobytes. A reader that asked for reliable delivery expects none of that to show. Closing the gap means the writer keeps every sample until it knows the sample landed, the reader keeps track of what it is missing, and large samples are cut up and reassembled.
The constraint running through all of it is memory. Every structure here has a size fixed by configuration, because the alternative is letting a slow reader or a hostile sender decide how much memory the process uses.
Acknowledgement
Releasing a sample from writer history
a reader reports how far it has got
Once per report. Readers report on their own schedule and when asked, so this is far less often than once per sample.
A writer that may need to resend a sample has to still have it. So each sample is kept after it is sent, and released only once it is certain nobody will ask for it again.
Readers report progress as a sequence number: everything up to n has arrived. The writer keeps one such number per reader. Since any reader may still ask for anything past its own number, the sample that can be released is decided by the reader that is furthest behind, not by the most recent report.
Acknowledge(w, reader, n)
w the writer and its history · reader the one reporting · n the highest sequence number it says it has
- w.acked[reader] = max(w.acked[reader], n) // reports may arrive out of order
- m = ∞
- for each r in w.readers
- m = min(m, w.acked[r])
- while w.history is not empty and w.history.first.seq ≤ m
- Remove-First(w.history)
A report that arrives out of order
Line 1 takes the maximum rather than assigning. Acknowledgements are carried in messages that can be delayed and reordered, so an older report can arrive after a newer one, and assigning it would move a reader backwards and resurrect samples that were already released.
Cost
One record per matched reader, so finding the minimum is O(R). Computing which samples a reader is asking for is O(K) in the number requested. Both the history and the number of readers are bounded by configuration.
Receipt
Tracking what has been received
a sample arrives, or the writer declares a range irrelevant
Once per received sample and once per declaration.
The reader's side of the same problem. It has to remember which samples arrived so it does not ask for them again, and it has to remember which ones the writer has said will never come — a sample can be filtered out at the writer, or dropped from the writer's history before the reader ever asked. Those are announced as a range the reader should stop waiting for.
Storing that range one sequence number at a time is where this goes wrong. A writer can declare that everything from 5 to four billion is irrelevant, and a reader that records four billion entries has been made to allocate by a single small message.
So the two are stored differently. What arrived is a window of the most recent positions, the same fixed 256 as the report bitmap. What was declared irrelevant is kept as a small set of ranges — each one two numbers, however many sequences lie between them.
Apply-Irrelevant(a, ranges)
a the association — its receipt window, its retained ranges, and the first sequence not yet accounted for · ranges the spans the writer declared irrelevant
- candidate = a.ranges // a copy; the live set is not touched yet
- for each range v in ranges
- if not Fits(candidate, v) // capacity, or the numbers overflow
- return rejected // the association is exactly as it was
- Insert(candidate, v)
- a.ranges = candidate
- Advance-Frontier(a) // absorbs any range now behind the frontier
- return applied
Line 1 is the discipline from Part 1 again, applied to a set rather than a table. A declaration carrying five ranges where only three will fit must leave none of them applied, because a reader holding half of one is a reader that will wait forever for the sequences in the other half.
Line 7 is what keeps the retained set small in practice. Once the frontier has moved past a range, the frontier itself records that those sequences are accounted for, and the range can be dropped. Ranges accumulate only ahead of the frontier.
Building the request
Asking for what is missing is then a walk from the frontier, skipping both what arrived and what was declared irrelevant.
Next-Request(a, last)
a the association · last the highest sequence the writer says it has sent
- base = a.frontier
- bitmap = empty; w = 0
- while w < 256 and base + w ≤ last
- s = base + w
- if s not in a.received and s not in a.ranges
- Select(bitmap, w)
- w = w + 1
- if bitmap is empty
- return none // nothing to ask for
- return request(base, w, bitmap)
Line 5 tests both sets. Leaving out the second test produces a reader that asks, repeatedly and forever, for samples the writer has already said it will never send — and the writer answers each request by saying so again.
Cost
Finding whether a sequence falls in a retained range is O(log G) for G ranges; testing the receipt window is O(1). Removing a range shifts the inline values, O(G). Building a request is O(W + G) over the 256-position window. None of it depends on how many sequence numbers a declared range spans, which is the whole point.
Reporting
Encoding a set of missing numbers
a control message carrying a set of sequence or fragment numbers is built or parsed
Once per such control message.
A reader missing samples 4, 7, and 8 has to say so. Sending a list would mean a variable-length message and somewhere to build the list. Instead the gaps are sent as a bitmap: a starting sequence number, a count of how many positions follow, and the bits themselves. At most 256 positions fit in one of these, held in eight 32-bit words.
The bit ordering
The protocol numbers position 0 as the most significant bit of the first word, which is the reverse of how a number's bits are usually indexed. Position 31 is the least significant bit of word 0, and position 32 goes back to the most significant bit of word 1.
Bitmap-Build(B, W)
B the number of positions the message declares · W the words carrying them
- if B > 256
- return error
- N = ⌈B / 32⌉
- if length(W) ≠ N
- return error // the declared count must match the words present
- for i = 0 to 7
- words[i] = 0
- for i = 0 to N − 1
- words[i] = W[i]
- if B mod 32 ≠ 0
- clear positions B through 32N − 1 in words[N − 1]
- return words
Bitmap-Contains(bm, p)
bm a built bitmap · p a position counted forward from the bitmap's base sequence number
- if p ≥ bm.count
- return false
- i = ⌊p / 32⌋
- m = 1 << (31 − (p mod 32))
- return (bm.words[i] and m) ≠ 0
Worked example
A reader has samples 100 and 103 but is missing 101, 102, and 104. It reports base 101 with 4 positions and one word.
| Position | Sequence | Bit | Mask |
|---|---|---|---|
| 0 | 101 | set | 0x80000000 |
| 1 | 102 | set | 0x40000000 |
| 2 | 103 | clear | 0x20000000 |
| 3 | 104 | set | 0x10000000 |
The word sent is 0xD0000000. Reading it as an ordinary
number and testing bit 0 would examine the value 0 at the
far end of the word, which is position 31 — sequence 132, outside
the four positions declared. That is the mistake the ordering invites:
it does not crash, it reports the wrong sequence numbers as missing.
The four bits past position 3 are cleared when the bitmap is built. Without that, whatever was left in those bits would be reported as missing sequence numbers the reader never asked about.
Bits outside the declared range
Lines 6 to 11 of the first procedure exist so that two bitmaps holding the same positions are the same bytes. Words past the declared count are zeroed, and the bits past the end of the final word are cleared. Without that, leftover bits outside the declared range would compare unequal, and would report positions that were never selected.
Cost
Eight words, 32 bytes, allocated nowhere — the value is fixed-size, so it lives wherever the control message is being built. Selecting or testing one position is O(1); walking the selected positions is O(B) for at most 256 of them.
Encoding
Encoding a control message
any reliability control record is built or read
Continuously while a reliable association is active — more often under loss.
The reports above travel as small records: the writer announcing what it holds, the reader asking for what it lacks, the writer declaring a range irrelevant, and the two fragment-level equivalents. Making progress under loss means sending them frequently, and frequently is the operative word.
Building each one into a freshly allocated buffer makes allocation part of protocol progress. That is the wrong dependency: the situation where these are sent most is the situation where the system is already under stress.
Every one of them is small and bounded. The largest is 88 bytes. So they are written into storage the caller already has, and the encoder returns how much it used.
Encode-Control(c, out)
c the control value · out caller-owned bytes to write into
- n = Encoded-Size(c) // fixed per kind, plus its bitmap words
- if n > |out|
- return error // every byte of out keeps the value it had
- Write-Header(out, c.kind, c.flags, n − 4)
- Write-Fields(out, c)
- return n
The size on line 1 is known before anything is written, which is what makes line 3 a clean refusal rather than a partial write. Two of the five records are a fixed size; the other three vary only with how many bitmap words they carry, which is between zero and eight.
Worked example
| Record | Size | Varies with |
|---|---|---|
| Writer announcement | 32 bytes | nothing |
| Fragment announcement | 28 bytes | nothing |
| Reader request | up to 88 | 0–8 bitmap words |
| Irrelevance declaration | up to 88 | 0–8 bitmap words |
| Fragment request | up to 88 | 0–8 bitmap words |
88 bytes is the number that makes the design work. It is small enough to sit in a buffer the caller already owns, so a reliable association under heavy loss generates no allocation at all while it recovers.
Cost
O(S) in the record's own size, which is O(1) given the 88-byte ceiling. Constant stack storage, no heap allocation, no system call. Placing the record into the outgoing message costs one further copy of the same size into a buffer that is itself reused.
Encoding
Framing a data message
a sample is put on the wire or taken off it
Once per sample, or once per piece of a split sample.
A sample travels in one of two record kinds: a whole one, or a piece of a split one. Both begin with flags, then fixed fields, then optionally a list of extra metadata about this particular sample, then the bytes.
The two kinds use the same flag positions to mean different things, and that is the trap worth stating before anything else.
Worked example
The same bit, read under the two record kinds:
| Bit | In a whole sample | In a piece |
|---|---|---|
0x04 | the payload is present | the payload is a serialized key |
0x08 | the payload is a serialized key | the payload has been transformed |
0x10 | the payload has been transformed | — |
A decoder that treats 0x04 as meaning the same thing in
both turns every ordinary fragment into a serialized key. Nothing
fails: the bytes are the right length, the record parses, and the
reader quietly builds instances out of application data.
Decode-Data(b, kind)
b the borrowed input bytes · kind whole sample or piece — which decides how the flags are read
- h = Read-Header(b)
- if kind == whole
- is-key = h.flags and 0x08
- transformed = h.flags and 0x10
- else
- is-key = h.flags and 0x04 // a different bit for the same question
- transformed = h.flags and 0x08
- if h.flags and inline-metadata-present
- meta = Read-Parameter-List(b) // ends where the list says it ends
- payload = Borrow(b, rest of the declared body)
- if transformed
- return protected(payload, meta) // must not reach ordinary history
- return view(payload, meta, is-key)
Line 9 reads the metadata list to its declared end rather than assuming where it stops. Guessing has a specific failure: the leftover metadata bytes become the first bytes of the payload, and the application receives a sample whose leading fields are protocol internals.
Line 12 keeps a transformed payload out of the ordinary path. Those bytes are still encrypted; handing them to reliability and history would store and deliver ciphertext as though it were the sample.
The payload on line 10 is borrowed, not copied. Byte order applies to the scalars but not to the identifiers or the payload, which are sequences of bytes and are the same either way.
Cost
Encoding is O(B + P) for B payload bytes and P metadata parameters, with one payload copy unless the sample was built in its final position. Decoding is O(P) — the payload is borrowed, so its size does not enter. Neither allocates.
Encoding
Trailing padding on a payload
a serialized payload finishes decoding
Once per sample.
A serialized payload may end with up to three bytes of padding, and the count is announced in the low two bits of the four-byte header that precedes it. This exists because a producer may need to round the payload up to a boundary.
It leaves the reader with a decision about bytes it did not expect. Both obvious answers are wrong. Refusing any trailing bytes rejects payloads from conforming implementations that padded. Accepting whatever is there means a sample with an extra kilobyte on the end decodes happily, and a length mismatch that should have been caught is not.
The announced count is neither ignored nor treated as a maximum. It is exact, and the bytes it covers must be zero.
Finish-Payload(r, announced)
r the reader, positioned at the end of the decoded value · announced the padding count from the header, 0 to 3
- if Remaining(r) ≠ announced
- return error // not "at least"; exactly
- for i = 1 to announced
- if Read-8(r) ≠ 0
- return error
- return ok
Line 1 compares rather than checks a bound, which is what turns the padding count into a checksum on the whole decode. If the value consumed fewer bytes than it should have, the leftover count no longer matches what the header announced, and the sample is rejected here even though every individual field decoded without complaint.
Cost
At most three byte comparisons. The check is free and catches a class of length disagreement that field-by-field decoding cannot see.
Fragmentation
Reassembling a split sample
a piece of a split sample arrives
Once per piece. For a large sample this is the innermost loop of receiving.
A sample too large for one message is sent as numbered pieces. The reader has to collect them, and it may be collecting pieces of several samples from several writers at the same time, interleaved.
The straightforward approach — keep each piece, then join them when the last one lands — copies every byte twice and makes the amount of memory held depend on what arrives. Instead each partly assembled sample gets one buffer the size of the finished sample, and each piece is copied straight to its final position. Alongside it sits a bitmap of which pieces have landed, and a count of how many.
When the count reaches the number of pieces expected, the sample is done. There is nothing to join: the bytes have been in the right place all along. The buffer is handed to the reader's history by transferring ownership of it, so completing a sample copies nothing.
Admit-Fragments(A, key, geometry, meta, pieces)
A the fixed set of assemblies in progress · key the writer and sequence number · geometry the sample size and piece size · meta the sample's metadata · pieces the pieces this message carries
- a = Find-Slot(A, key) // key is the writer and the sequence number
- if a == nil
- a = First-Free-Slot(A)
- if a == nil
- return resource-limit // no other assembly is disturbed
- if geometry.size > max-bytes or geometry.count > max-pieces
- return resource-limit
- if a is new
- a.buffer = Reserve-Buffer(geometry.size)
- Clear(a.received)
- a.count = 0
- c = Merge-Metadata(a.meta, meta) // into a candidate, not into a
- if c == conflict
- return malformed // a is exactly as it was
- for each piece f in pieces
- if a.received[f.number] == 0
- Copy(f.bytes, a.buffer at f.offset)
- a.received[f.number] = 1
- a.count = a.count + 1
- a.meta = c // committed only after every rejection path is past
- if a.count == geometry.count
- Remove-Slot(A, key)
- return complete, Transfer-Ownership(a.buffer)
- return incomplete
Worked example
A 5,000-byte sample sent in 1,400-byte pieces needs ⌈5000 / 1400⌉ = 4 pieces. The buffer reserved is 5,000 bytes, once.
| Piece | Written at offset | Bytes |
|---|---|---|
| 1 | 0 | 1,400 |
| 2 | 1,400 | 1,400 |
| 3 | 2,800 | 1,400 |
| 4 | 4,200 | 800 |
Suppose they arrive 3, 1, 3, 4, 2. The first 3 is written at offset 2,800 and sets its bit. The second 3 finds that bit already set and is skipped — no copy, and the count stays at 3. When 2 arrives the count reaches 4, which equals the piece count, and the buffer is already the complete sample. Nothing is joined and nothing is copied a second time.
The last piece is 800 bytes, not 1,400. A reader that assumed every piece was the full size would compute its offset as 4,200 and its length as 1,400, writing 600 bytes past the end of the buffer — which is why the geometry is validated before any copy.
A piece that arrives twice
Line 16 is what makes a duplicate harmless. A piece whose bit is already set is skipped entirely — not re-copied — so a sender that repeats itself cannot overwrite bytes that were already accepted and cannot inflate the count past the number of pieces.
Two pieces that disagree about the sample
Line 12 merges the sample's metadata into a candidate rather than into the assembly. Two pieces of the same sample must agree about things like the source timestamp; if they disagree, the assembly must be left exactly as it was rather than half-updated. Doing the merge into a candidate and committing at line 20 is what gives that for free.
Cost
The number of assemblies in progress is fixed at startup, so finding the slot is O(A) over a small A, and the buffers are reserved once rather than per sample. One arriving message costs O(X) for the bytes it actually contributes plus one bit operation per piece it carries. Completion is O(1): a hand-off, not a copy.
Ownership
Owning the reassembled bytes
an assembly needs a buffer, and when the last holder of a finished one lets go
Once per split sample, plus one reference operation per holder.
Reassembly writes each piece straight to its final position, which means it needs a buffer the size of the finished sample before the first piece lands. When the sample completes, those bytes are handed on — and may outlive the reassembler by a long way. They can sit in a group waiting to be released, in the reader's history, or be lent directly to the application.
So the question is when the buffer may be used again. Reusing it while any of those still points at it hands the next sample's bytes to something that thinks it is reading the previous one.
The buffers are reserved once, at startup, as one mapping holding a fixed number of them. The arena keeps one reference to each. A buffer is free exactly when that reference is the only one left — the reference count is the free list.
Acquire-Buffer(arena, B)
arena the fixed set of buffers and the arena's own reference to each · B the bytes needed
- if B == 0 or B > arena.max
- return error
- for i = 1 to arena.count
- if Owners(arena.buffer[i]) == 1 // only the arena still holds it
- return Reserve(arena.buffer[i], B)
- return unavailable // every buffer still has a reader
A reservation range-checks every write against the length it asked for, so a piece whose declared position would land outside the buffer is refused rather than writing past it. Completing the sample turns the reservation into shared ownership of the same buffer — no copy, and the bytes never move.
Everything downstream that keeps the sample takes its own reference. Line 4 then becomes the whole release mechanism: when the last of them drops, the count returns to one and the buffer is acquirable again. There is no separate free list to keep consistent with who is actually reading.
Why the mapping is not touched at startup
Reserving the whole arena means asking for a large region — the buffer count times the largest sample allowed. The pages behind it are not written when the reader is created, so the cost of creating a reader does not scale with the size of the samples it is prepared to receive. A page is committed when a sample first uses it.
Cost
One reservation of S × Bmax bytes at construction. Finding a free buffer is O(S), writing is O(X) for the bytes copied, and publishing, sharing, or dropping a reference is a single atomic operation. Nothing after construction allocates.
Repair
Requesting the missing pieces
the writer says which pieces it has sent and some are still missing
Once per such announcement while a sample is incomplete. Stops as soon as the sample completes.
When the writer says which pieces it has sent, the reader can work out which it is missing and ask for them.
More gaps than one request can carry
The request is a bitmap holding 256 positions, and a sample can have more missing pieces than that. Rather than building a list of everything missing, the reader fills one window starting at the first gap, and sets a flag meaning there is more beyond it. The writer repairs that window; the next round covers the next one.
When to stop asking
Asking has to stop. A peer that has genuinely gone away will never satisfy a request, and repeating it forever turns one dead peer into steady traffic. But a plain retry limit would also cut off a peer that is slowly succeeding.
So the counter measures progress rather than time. It counts requests since the last newly accepted piece, and any new piece resets it to zero. A link that is delivering, however slowly, keeps its budget. A link delivering nothing spends it once and stops.
Repair-Decision(s, limit)
s the writer sequence number being assembled · limit the retry budget, spent only while nothing new arrives
- if Already-Accounted(s)
- return idle // the sample is done; never ask about it
- b = First-Absent-Piece(s)
- if b == nil
- return idle
- extent = min(256, last(s) − b + 1)
- for p = 0 to extent − 1
- if piece b + p is absent
- Select(bitmap, p)
- more = there is an absent piece after b + extent − 1
- t = Find-Or-Reserve-Retry-Record(s)
- if t == nil
- return capacity-exhausted // no other sample's record is taken
- if t.count == limit
- return retry-exhausted // and send nothing
- t.count = t.count + 1
- return request(b, bitmap, more)
On-New-Piece-Accepted(s)
s the sequence number a previously absent piece has just been accepted for
- t = Find-Retry-Record(s)
- if t ≠ nil
- t.count = 0 // progress restores the whole budget
Line 15 returns without sending anything. It would be easy to count the attempt and send it anyway, but then the limit would bound how often the reader gives up rather than how much traffic it generates, which is the opposite of the point.
Line 10 sets the flag by continuing the same scan until it finds one more absent piece, then stopping. Knowing whether anything is missing beyond the window does not require knowing what, so a single extra step answers it and no list is ever built.
Cost
Finding the first gap and filling the window is O(F) in the pieces scanned, bounded by the window. Expanding a received bitmap is O(K) for at most 256 positions. Retry records are a fixed set of slots, so a peer that opens many partial samples cannot make this grow.
Next: content filtering
A reader asks for only some of the samples, and the condition has to mean the same thing in three places.
These descriptions follow the implementations in Tin DDS and Retina. Evaluation access and the full algorithm notes are available from engineering@tinverse.com.