Part 5 of 14
History, durability and instances
A sample that has passed the reader's condition still has to be put somewhere. How many are kept, what happens to a notification that carries no value, whether reading removes what it returns, and what a reader that starts an hour late receives are all separate decisions, and each is configurable.
Durability QoS decides whether late readers can receive retained data. Transient-local history lasts with its writer. Transient durability uses a service, and persistent durability can recover retained data from files after restart. Those are different lifetimes, not interchangeable names for a reliable queue.
Storage
Where a sample is stored
a writer publishes and when a reader admits
Once per sample on each side.
Writer history supports reliable repair and transient-local retention. A durability service supports longer-lived retention when configured. Reader history holds admitted samples for the application. Shared-memory slots can hold the payload behind those histories; they are a storage mechanism, not another durability policy.
Retained payloads stay unchanged while consumers still need them. Paths that share a retained payload reuse its bytes for repair instead of serializing the application value again. That does not mean every API, persistence operation, or C++ and Rust history uses the same storage or avoids every copy.
Publish(w, value)
w the writer, with its reliability, durability and matched readers · value the application's sample
- bytes = Serialize(value) // value-based serialized path
- seq = Next-Sequence(w)
- if w.reliable or w.durability == transient-local
- Retain(w.history, seq, bytes)
- if w.durability is transient or persistent
- Retain(w.service, seq, bytes)
- for each reader r in Matched(w)
- Deliver(r, seq, bytes)
This sketch shows retention responsibilities, not a sequence of separate payload allocations. Reliability and durability may share retained storage. Every operation can also reject admission when its configured resources are exhausted; the sketch omits that error handling.
Count retained instances without recounting history
A keyed history needs to know how many retained samples belong to a particular instance. It keeps a counter beside the samples: insertion increments it, removal decrements it, and the final removal drops the entry. Taking, evicting, clearing, and restoring history must all maintain the same invariant: the counter equals the samples actually retained for that key. A rejected insertion must not leave a counter behind.
- Tin DDS
retained_instance_countsuses a capacity-sized hash table with full-key comparisons. Lookup has expected constant probe count, but collisions can require a table scan. Removed entries leave markers that are periodically cleared by rebuilding the buckets. Bucket storage is prepared at construction; storing a new key can still require key storage allocation.- Retina
InstanceCountskeeps counters sorted by key. Lookup takes O(log I) key comparisons for I tracked instances. Adding or removing a key can shift O(I) entries, and a new key owns an allocated byte string. Shared reader-history operations maintain counts for ordinary samples and shared-memory samples.
Key comparison also costs time proportional to the bytes examined. These indexes avoid repeatedly counting one instance by scanning every sample; they do not make eviction, new-key churn, or the whole publication constant-time. KEEP_LAST and resource limits remain the DDS policy; the index is an implementation choice.
Instances
A notification with no value
a writer disposes or unregisters a keyed instance
Once per lifecycle change — far less often than samples.
A writer can announce that an instance is gone — that robot has left, that sensor is disconnected — without publishing a value for it. The notification identifies the key and deliberately carries nothing else, because there is no value to report.
That is a problem for a typed reader whose interface returns samples of type T. There is no T to return. Inventing a default-constructed one is the tempting move and is wrong: the application cannot distinguish it from a real sample that happens to hold zeroes.
So a take returns one of two things, and the caller sees which.
Take-Typed(r)
r the reader
- e = Take-Entry(r)
- if e == nil
- return nil
- if not e.valid-data
- return lifecycle(e.info) // no attempt to deserialize an absent value
- return data(Deserialize(e.bytes), e.info)
Line 4 is tested before line 6 runs, which is the whole point: the payload is empty, and asking the generated deserializer to read a value out of no bytes is not a recoverable error, it is a malformed-input rejection for something that is not malformed.
Two ways an instance can end
Disposing says the instance is gone. Unregistering says only that this writer is no longer publishing it — another writer may still be. They produce different public states, and the writer's own policy decides which state an unregister produces.
Worked example
| Operation | Writer's auto-dispose setting | Instance state seen | Writer's claim |
|---|---|---|---|
| dispose | either | not alive, disposed | kept |
| unregister | on | not alive, disposed | removed |
| unregister | off | not alive, no writers | removed |
Rows two and three both remove the claim; rows one and two show the same state to the application by different routes. The retained record therefore stores which of the four operations happened rather than the state seen by the application, because that state alone cannot be replayed back into the right claim behaviour for a late reader.
Cost
Instance records, writer claims, and the key bytes all live in flat arrays reserved when the reader is built, so an update is a scan over deployment-sized structures rather than a hash insert with an allocation. Fanning a lifecycle change to R readers costs one key copy each, since the metadata each reader keeps owns its key.
Access
Reading without consuming
the application reads or takes
Once per access.
DDS separates looking at history from removing from it. Reading leaves the sample where it is, so the same sample can be read again; taking transfers it out.
That distinction is easy while the sample is bytes the reader owns. It gets sharp when the payload is a loan into a shared-memory slot that the writer and other readers also refer to, because then "leaving it where it is" has to mean not releasing the reference — and a read that released it would make a later take return a slot that had been reused.
So the two operations produce different kinds of loan.
Worked example
| Serialized payload | Shared-memory payload | |
|---|---|---|
| read | borrows the bytes, copies only the metadata | loan that inspects; the reference stays held |
| take | removes the entry and transfers the bytes | loan that releases the reference when dropped |
Neither row copies the payload. The difference is entirely in what happens to the reference when the loan goes out of scope, which is why the two loans are different types rather than one type with a flag — the flag would be checkable only at run time, and getting it wrong is a use-after-free.
A read that finds a lifecycle notification preserves it, and a take consumes it. The convenience form that returns only values skips lifecycle entries, and it does so within the reader's configured depth so that a history full of lifecycle notifications terminates the search rather than scanning indefinitely.
Cost
An unkeyed single access is O(1). Selecting a particular instance scans at most the configured depth. A batch fills the caller's array, visiting each entry at most once and stopping when the array is full, and initializes only the part it filled — so asking for a hundred and receiving three costs three.
Grouping
Committing a group of samples
a group of samples opened as one update is closed
Once per group. Writers not inside a group never take this path.
Some updates are only meaningful as a set. A robot's arm position and its gripper state, published separately, can be read in a combination that never existed — the new arm position with the old gripper state. A coherent set marks a group of samples as one update: the reader sees all of them or none.
The set is opened, samples are written into it, and it is closed. Until it closes, the samples are held and are invisible: not in reader history, not sent, not available for repair. Closing makes them visible together.
Two things have to be true at the moment it closes. Every sample needs to know how many are in the set and which one it is, which is only knowable once the set is complete. And every history that has to hold the set must have room for all of it — admitting part of a set and then running out of space would produce exactly the half-updated state the whole mechanism exists to prevent. So both are counted first, and the set is rejected before anything becomes visible.
Commit-Set(changes)
changes the samples written into the group while it was open, across possibly several writers
- S = |changes|
- id = Fresh-Set-Id()
- for i = 0 to S − 1
- changes[i].set = id
- changes[i].index = i
- changes[i].size = S // knowable only now the set is closed
- for each writer w involved
- if not Can-Retain-All(w, changes of w)
- return rejected // still nothing visible
- for each reader r involved
- if not Can-Admit-All(r, changes for r)
- return rejected
- for each c in changes
- Retain(c.writer.history, c)
- for each c in changes
- Deliver(c)
- return ok
Cancelling a group
Cancelling has a loose end that is easy to miss. Sequence numbers were already assigned to the samples, and a reliable reader tracks sequence numbers — it will notice the gap and wait for samples that are never coming. So cancelling drops the payloads but still announces those numbers as deliberately absent, which lets the reader move past them.
Cost
Adding a sample to an open set is O(1) plus one copy to retain the payload. Closing is O(S · W + D) for S changes across W writers with D local deliveries — counted by walking the set rather than by building a temporary map. Cancelling is O(S). A writer not inside a set takes none of this path.
Grouping
Receiving a group
a sample arrives carrying a coherent-set identity
Once per member of a group.
The section above is the writer's side. The reader's side is harder, because the members arrive separately, possibly out of order, possibly split into pieces, and possibly with some of them rejected by the reader's own condition.
Each member carries the set it belongs to, its index, and how many there are. The reader holds them until all indexes are present.
Admit-Member(r, s, C)
r the reader and its table of sets in progress · s the arriving sample with its set id, index and declared size · C the configured total slot reservation
- if s.size == 0 or s.index ≥ s.size or s.size > C
- return malformed // no pending state is created
- if not r.wants-coherent or s.size == 1
- return Admit-Normally(r, s)
- e = Find(r.sets, s.writer, s.set)
- if e == nil
- if r.reserved + s.size > C
- return resource-limit
- e = Reserve(r.sets, s.writer, s.set, s.size)
- else if e.size ≠ s.size
- return malformed // the set changed size mid-flight
- if e.slot[s.index] is occupied
- return malformed
- e.slot[s.index] = Admitted-Or-Filtered-Marker(r, s)
- e.received = e.received + 1
- if e.received < e.size
- return withheld
- if not Room-For-All-Admitted(r, e)
- return resource-limit // history is not changed at all
- Release-In-Index-Order(r, e)
- Free(r.sets, e)
- return released
Line 14 stores a marker rather than nothing when the reader's own condition rejects a member. The set completes when every index is accounted for, and a filtered member is accounted for — it simply will not be delivered. Leaving its slot empty would make the set never complete, so one filtered member would strand the whole group and every slot it reserved.
Line 18 checks that every admitted member will fit before any of them moves, which is the same rule as the writer's side. Releasing four of five and then finding history full delivers exactly the partial group the mechanism exists to prevent.
A writer that goes away mid-set leaves reserved slots behind. When discovery expires that participant, every pending set it owns is dropped and its reservations returned, without any member being exposed.
Cost
Finding a set and an index within it is O(1) on average; completion is O(S) in the declared size. The tables are sized when the reader is built and their capacity does not change, so repeated sets cause no allocation at all.
Durability
Recovering a durability log
a durability log is opened, and periodically while it is in use
Recovery once per open. Rewriting happens on a schedule, not per sample.
A writer can be asked to keep its samples so that a reader starting later — including after the writer's process has restarted — still receives them. That means the samples go to a file, and files are where a process can be killed halfway through a write.
Each sample is one frame: a length, a checksum, then the bytes. A process that stops mid-write leaves a frame that is short, or one whose checksum does not match. The damage that matters is not the torn frame itself but what happens next: if a restarted writer simply appends after those bytes, the reader replaying the file stops at the torn frame and never sees anything after it. One interrupted write silently hides all later samples.
So opening the file walks it first and finds the longest prefix that is entirely complete frames, then truncates there. Appending after that point puts the new frame somewhere replay will reach.
Recover-Log(file, B, max-payload)
file the durability log · B its length in bytes, read from the filesystem · max-payload the largest record the configuration allows
- start = 0
- while true
- if B − start < 16
- Truncate(file, start); return ok // no room for a header
- (len, sum) = Read-Header(file, start)
- if len > max-payload or start + 16 + len overflows
- return error
- if start + 16 + len > B
- Truncate(file, start); return ok // frame runs past the end
- if Checksum(file, start + 16, len) ≠ sum
- return error // complete but corrupt: do not silently drop it
- start = start + 16 + len
- if start == B
- return ok // the whole file is valid; change nothing
A frame cut short, and a frame that is corrupt
Lines 9 and 11 look similar and are treated differently on purpose. A frame that runs past the end of the file was never finished being written, so discarding it loses nothing that was ever committed. A frame that is complete but whose checksum disagrees is a different situation — the bytes were written and then changed — and quietly dropping it would mean starting up with a history that is missing a sample nobody was told about.
Keeping the log from growing forever
Running out of disk is the other direction of the same problem. Samples that have been superseded stay in the file, which grows without bound, so the log is periodically rewritten to hold only what is still retained. That rewrite goes to a separate private file and replaces the installed one only once it is complete, so an interruption partway through leaves the original intact.
Cost
Recovery is O(F + B) for F frames and B payload bytes, using one fixed buffer to compute checksums, copying no payload, and making at most one truncation call. It runs when the file is opened and never on the path that publishes a sample.
Durability
One owner per directory
a durability service starts
Once, at construction. Publication and replay never touch it.
The logs live in a directory. Two services writing the same directory interleave frames into one another's files, truncate each other's recovery point, and can replay a state neither of them committed.
The fix is not coordination between the services. It is that there is only ever one: the directory carries a lock file, and a service that cannot take the lock does not start.
Claim-Directory(path)
path the durability directory
- fd = Open-Or-Create(path / lease)
- r = Try-Lock-Exclusive(fd) // non-blocking
- if r == would-block
- return in-use // another process owns it; do not wait
- if r == error
- return r
- return lease(fd) // held for the service's whole life
The lock is non-blocking on purpose. Waiting would turn a configuration mistake — two services pointed at one directory — into a process that starts and then hangs, which is much harder to diagnose than one that refuses immediately and says why.
Holding the descriptor for the service's lifetime means the operating system releases it when the process ends, however it ends. A lease written into a file as data would survive a crash and lock the directory against the restarted process.
Durability
One log per writer
a persistent writer registers, publishes, or is removed
Once per registration; compaction per writer, on its own file.
Several writers may publish the same topic and type. If the store is organised by topic, the most recent writer's checkpoint overwrites every other writer's retained history — and each writer also has its own sequence numbering, so merging them loses the frontier each one has to resume from.
So the file is named for the writer, not the topic: the topic and type hash form a prefix, and the writer's own identifier completes it.
Register-Persistent-Writer(svc, w)
svc the durability service and its retired-writer slots · w the writer being registered
- prefix = Path-Prefix(w.topic, w.type-hash)
- Purge-Expired(svc, prefix)
- for each file f matching prefix
- h = Recover-Log(f) // the torn-tail procedure below
- if h == error
- return error
- if Guid-Of(f) == w.guid
- Bind(w, f, resume after h.greatest-sequence)
- else
- slot = Free-Slot(svc)
- if slot == nil
- return resource-limit // never merge or discard another writer's history
- Adopt(slot, f, h)
- return ok
Line 12 refuses rather than doing something reasonable-looking. The two reasonable-looking options are both silent data loss: merging two writers' histories produces sequence numbers that belong to neither, and discarding the older one throws away samples a late reader was promised.
Line 13 keeps the other writers' histories in the service rather than attaching them to the new writer. A late reader is then served from both the active writers and these adopted histories, which is how a writer that has been gone since before the reader existed still delivers.
Cost
Publication compacts only the one writer's file, O(H + B) for its retained samples and their bytes. Registration scans the directory once and rebuilds the matching histories. Because expiry and removal also address the per-writer path, neither can select a sibling writer's file by topic alone.
Durability
What a late reader gets
a durable sample is retained, and when a log is replayed
Once per durable sample.
A durable writer's ordinary history depth is not what a late reader receives. The service has its own retention policy — its own kind, depth, total sample count, instance count, and samples per instance — and it is that policy which decides what is still there when somebody new appears.
Enforcing it has an ordering that is easy to get backwards, because several limits can be exceeded by one arriving sample.
Retain-For-Service(svc, s)
svc the service history and its configured limits · s the sample being retained
- if s.key is new and Instances(svc) == svc.max-instances
- Remove-All-Of(svc, Oldest-Other-Instance(svc)) // free a whole instance slot
- while Count-Of(svc, s.key) ≥ svc.max-per-instance
- Remove-Oldest-Of(svc, s.key)
- if svc.kind == keep-last
- while Count-Of(svc, s.key) ≥ min(svc.depth, svc.max-total, svc.max-per-instance)
- Remove-Oldest-Of(svc, s.key)
- while Total(svc) ≥ svc.max-total
- Remove-Oldest(svc)
- Append(svc, s)
Line 2 removes an entire instance rather than one sample. Making room for a new key by evicting one sample of an old key leaves that key present with fewer samples, and the instance count — which is what was actually full — has not moved.
Line 6 takes the smallest of three limits at once. Applying them one after another in some order gives a different result, because each eviction changes what the next limit sees.
The same procedure runs, in publication order, when a log is replayed from disk. That is what makes a recovered history identical to one that was never interrupted: not that the file holds exactly the retained set, but that reading it applies the same rule that produced it.
Cost
Unkeyed retention is O(1) amortized. Keyed retention counts and removes by scanning, which is O(H2) in the worst case against the configured capacity — deliberately, because the alternative is a temporary hash table built per publication. The payload copy is the one retention already required.
Durability
Retiring a writer
a durable writer is deleted, and when the service starts
Once per removal; a sweep at startup and before each late-reader replay.
Deleting a durable writer must not delete what it was keeping for late readers. The whole point of durability is to outlive the moment, and an application shutting a writer down has not said that its data is now worthless.
So the writer's history moves into a retirement slot and stays there for a configured delay — possibly forever, if the delay is infinite.
Retire-Writer(svc, w, now)
svc the service and its fixed retirement slots · w the writer being removed · now the current time
- if svc.cleanup-delay == 0
- Remove-Log(svc, w)
- return Remove-Writer(w)
- slot = Free-Slot(svc.retired)
- if slot == nil
- return resource-limit // before the writer leaves either table
- if w.durability == persistent
- Write-Expiry-Marker(svc, w, now + svc.cleanup-delay)
- Remove-Writer(w)
- Move-History(w, slot)
Line 6 is the ordering that matters. Removing the writer first and then discovering there is nowhere to put its history leaves an endpoint removed from the writer table and from the discovery graph, with its samples belonging to nothing. Checking for the slot first makes the refusal complete.
Line 8 writes the expiry to disk before the endpoint changes, so a process that dies between these lines restarts with a marker that says when this history should go. Deciding the expiry only in memory would leave a persistent log that never expires because nothing recorded when it should.
Cost
Reserving and expiring scan a fixed number of slots. Startup streams the directory once with constant memory per marker. A late reader is served from the retired histories directly into its own history, with no copy made merely to inspect or expire them.
Correlation
Matching a reply to its request
a client takes the reply to a request it made
Once per reply.
Request and reply over DDS is two topics and ordinary readers and writers. The complication is that one reply topic carries replies for every outstanding request, from every client, and a client taking its reply must not consume somebody else's.
Each reply carries the identity of the request it answers. Taking a reply is then a search for that identity rather than a take of whatever is oldest.
Take-Related(r, id)
r the reply reader · id the identity of the request this client sent
- for each entry e in r.history // delivery order
- if e.related == id
- return Remove-And-Return(r.history, e)
- for each descriptor d in r.shm-history
- if d.related == id
- return Remove-And-Return(r.shm-history, d)
- return nil // not arrived yet; nothing else was disturbed
Nothing is removed except an exact match, so replies for other clients stay where they are in their original order. A client polling for a reply that has not arrived leaves the reader exactly as it found it.
Both histories are searched because the transport is not the application's choice. A reply may have come through shared memory or over the network depending on where the service happened to be running, and the client asking for its reply should not have to know which.
The identity is attached to the reply without consuming a sequence number of its own, so correlation costs nothing in the reliability protocol — it is metadata on a sample that was being sent anyway.
Next: liveness, timing and status
Whether the writer has gone quiet, whether the reader is falling behind, and what it has lost.
These descriptions follow the implementations in Tin DDS and Retina. Evaluation access and the full algorithm notes are available from engineering@tinverse.com.