Storage, and running more than one of them
==========================================
Notes towards a clustered SightingDB: a galaxy of servers behind an entry point,
each holding some or all of the namespaces, syncing with each other over the
same HTTP API a client uses.
Some of this is built. Each section says which, because the difference matters:
what is built can be relied on, and what is not is still a choice.
The measurements quoted below come from doc/sharding-experiment.py:
python3 doc/sharding-experiment.py
Storage today
-------------
Default storage is a simple tree which contains the path + value. The path is
usually the type of value, such as a host, an IP address, a hash etc.
Two properties of it decide everything that follows.
**One file per top-level namespace.** persistence::shard_of() takes
'feeds/misp/ips' to 'feeds', and that is the unit written out, paged in,
evicted and tiered. Namespaces beginning with '_' share one internal shard.
Because the namespace is already the storage unit, a galaxy that divides work
by namespace keeps every namespace-scoped operation local: listing a namespace,
counting it, deleting it, exporting it as STIX. A galaxy that divided by value
would turn each of those into a scatter-gather. That is why namespace mirroring
is the model here.
**A sighting is a set of merge-safe operations.** This is what makes clustering
possible without a consensus protocol, and it is already true:
count += 1 a counter
first_seen only ever moves back a min register
last_seen only ever moves forward a max register
tags union, de-duplicated a grow-only set
ttl assignment a last-write-wins register
stats += 1 per hour bucket a map of counters
Every one of those converges whatever order it is applied in. Two servers can
take writes for the same value independently and merge afterwards without
agreeing on anything first. No Raft, no quorum on the write path.
The exception was `count`, since an increment is not idempotent. That is now
kept per node and summed — see "Counters must be per node", which was the
prerequisite everything else waited on.
What a server is
----------------
BUILT.
A server has a storage set and a peer set, both optional. "Node" and "load
balancer" are not types — they are what those two settings add up to:
[storage]
namespaces = ["/"] everything: a full mirror (the default)
namespaces = ["feeds"] that subtree and nothing else
namespaces = [] nothing of its own: a pure router
[galaxy]
max_hops = 4
health_interval = 30
peers = [
{ url = "https://node-a:9999", key = "..." },
{ url = "https://lb2:9999", key = "..." },
]
stores something, no peers node
stores nothing, has peers router
stores something, has peers both
Any server can be any of them, and a router's peer may itself be a router, so a
router in front of routers is a cascade. /_management/api/info reports which
under `role`, and /_management/api/galaxy reports the peers with their health.
Prefixes match whole path segments, so `feeds` holds 'feeds/misp/ips' and never
'feeds-internal'. The internal namespaces are always held whatever the setting
says — a server cannot keep its own consensus tally otherwise — so listing one
is an error.
A write to a namespace a server does not store answers 421 Misdirected Request.
Not 403, which would say the caller may not; not 404, which would say there is
no such thing. The request arrived somewhere that cannot serve it, and once
forwarding exists that is what a router answers when no peer holds it either.
It has to stay distinguishable from a real 404 to be debuggable.
**The peer key is the capability bound.** Each peer carries the key this server
authenticates to it with, and the peer's own ACL decides what that key may
reach. A key granted `rw:feeds` on the peer cannot write anywhere else, however
this server is configured or compromised. This is the existing ACL doing the
work, not a new authorization model, and it is the reason a galaxy needs no
trust between members beyond what each key allows. Give each one the narrowest
grant that does the job.
Misconfiguration is refused at startup rather than at the first forward: a peer
without a key, a url without a scheme, the same peer twice, max_hops of 0.
Health
------
BUILT.
Each peer's /health is probed every `health_interval` seconds and the result
kept: online, consecutive failures, last successful probe, round trip, and the
peer's own version — a galaxy running mixed versions is worth seeing before it
starts behaving oddly.
/health needs no API key, so a probe carries no credential.
Three details that matter more than they look:
* "Not probed yet" is reported separately from "offline". A view that conflates
them says a galaxy is down for the first few seconds of its life.
* `last_seen` survives failure, so an operator can tell a peer that died a
minute ago from one that has been gone a week. Latency is cleared, because a
stale latency is a lie.
* What is reported is reachability *from this server*. A peer that is running
but unreachable from here is, for this server's purposes, down, and saying so
is more useful than saying it is up.
`verify_tls = false` exists for a galaxy of self-signed instances, which is what
--setup produces. It is on by default.
Consensus
---------
BUILT. A server in front of a galaxy keeps the galaxy-wide tally, read
back with /r/_all?val=, and rebuilds it from the nodes on a timer.
Consensus means "how many namespaces have seen this value". Each server keeps
its own tally in `_all`, which is a local fact: the namespaces *on this server*
that hold the value.
**The entry point is the right place for the global number**, because it sees
the logical write — (namespace, value) — while mirroring is a physical detail
below it. Its view is de-duplicated by construction, and it needs no polling, so
a peer going away does not make consensus drop for a value that still exists.
A router must therefore keep an `_all` of its own, which is why a storage set of
`[]` still holds the internal namespaces.
And because `_all` is an ordinary readable namespace, the global number needs no
new endpoint:
GET /r/feeds/ips?val=V the serving node's local consensus
GET /r/_all?val=V on a router: the global one
Leaving /r alone like this keeps a router a thin proxy for reads. The
alternative — rewriting the `consensus` field in every forwarded response —
couples it to the response schema and costs CPU per read.
**No internal namespace is writable from outside.** `_all`, `_shadow/*` and
`_config` answer 403 to every write route including /d. Before that guard a
client could write `_all` directly and give a value a consensus no namespace
supported — the one number this database exists to be trusted about. Reading
them stays open apart from `_config`.
Write responses carry `new`: whether the sighting was the first of that value
in that namespace, which is what gates a consensus increment and which a server
in front cannot work out without holding the namespace. It counts the value once
when the mirror that took the write reports new, however many mirrors took it.
Measured on a router over two *partial* mirrors, where neither node can know the
global number alone:
1.2.3.4 written into alpha/one, alpha/two (na) and beta/one (nb)
lb 3 na 2 nb 1 lb is the only one that is right
**And rebuilt, because that tally only ever rises.** Consensus is released when
a namespace is deleted and when the sweeper reclaims an expired value, both on
the node and both invisible from in front of it:
delete alpha/two on na
lb 3 na 1 nb 1 truth is 2; lb has drifted
after a reconciliation pass
lb 2 na 1 nb 1
A pass surveys the galaxy: for each namespace, walk its values and record which
namespaces hold each one. Consensus is then the size of that set — a set, not a
sum, because the same namespace mirrored three times is still one namespace. A
value the survey never sees at all is set to nothing: it has gone from
everywhere.
It **walks the galaxy**, which is why `reconcile_interval` is a setting of its
own with a long default of an hour. It is a repair, not a steady cost: the
incremental tally answers reads in between, and a pass that finds nothing wrong
says nothing.
**Parallel routers cannot share consensus.** Two entry points each see a
fraction of the writes, and a count cannot be reconciled — you cannot tell a
counter it has already counted something. So root-level redundancy costs either
an active/standby router that rebuilds its tally from the nodes on promotion, or
a router that stores presence pairs (value -> set of namespaces) instead of a
count, because sets union idempotently. Data availability is unaffected either
way; this is only about the global number.
A forwarded write is counted for its origin
------------------------------------------
BUILT. The subtlety that only appears once fan-out and syncing both work,
and it cost a round of measurement to find.
Fanning one write out to two mirrors has each mirror count it — and with
per-node counters, each counts it under *its own* name. The two then disagree
about nothing and yet merging them adds the counts together. Measured on a real
cascade: three writes through a load balancer became six once the mirrors
synced.
So the origin travels with the write, in X-SightingDB-Origin, and every mirror
counts it under the same name. Merging mirrors that already agree is then the
no-op it should be:
client writes 3 times to lb1 (lb1 -> lb2 -> two mirrors)
node-a {lb1: 3} node-b {lb1: 3}
mirrors sync with each other, three times over
node-a 3 node-b 3
In a cascade the header is passed along unchanged, so the attribution is the
entry point the client actually talked to — lb1 above, not lb2.
Honoured only on a request that also carries a hop count, which is to say only
on a forwarded one: the origin is part of the forwarding protocol, not the
client API. A client setting it anyway would mislabel its own writes without
changing any total, since one write is still one increment.
Counters must be per node
-------------------------
BUILT. `count` and the hourly buckets are kept per node, the snapshot
format is version 2, and version 1 is migrated on load. What is still
missing is the merge verb below.
`count` is an increment, and increments are not idempotent. Over HTTP, where
/w is the only write verb and it means "add one", any sync that reads a peer and
writes what it finds compounds. Measured against two real instances:
client wrote 3 times. A=3 B=3 correct
A syncs from B: A=6 B=3 A doubled
B syncs back from A: A=6 B=9
Three sightings, two sync rounds, and the cluster claims nine. It is unbounded.
The fix, now in place, is a map from node id to count, reported as the sum:
counts: node id -> count reported as the sum
node_stats: node id -> hour -> count reported merged
Each server only ever writes its own entry, so replication becomes "send my
entries", which is idempotent and order-independent. Releasing consensus takes
from the releasing server's own entry, so a server gives back only what it put
in and never spends a peer's contribution.
`node_id` in `[daemon]` names the server, defaulting to "local" so a standalone
one sums to exactly what it always did.
The verb that goes with it is POST /_api/merge, which combines rather than
increments, and GET /r/<ns>?val=V&for_merge, which answers in the shape that
route takes. Both are built. The read side matters as much as the write side:
offering a *total* rather than per-node counts would make the receiver
attribute every server's sightings to the sender, and two servers exchanging
totals inflate each other without bound. That was found by writing the sync and
watching it do exactly that.
Reading a version 1 snapshot folds its totals into the reading server's entry,
which is the only thing they can be. check_version was changed to accept older
versions rather than refuse them: a build that would not open the existing
database is indistinguishable from total data loss, and the next save would
make it real. A *newer* version is still refused.
A node that was down, and comes back
------------------------------------
BUILT. A worker on a timer, and the state that withholds reads while it
runs. A galaxy heals itself rather than needing someone with curl.
Measured on a real galaxy. node-b is killed, writes continue through the
router, node-b is restarted and nobody touches it:
nb down 1.2.3.4=3/- 9.9.9.9=4/- 7.7.7.7=2/-
+3s 1.2.3.4=3/3 9.9.9.9=4/4 7.7.7.7=2/2
+40s 1.2.3.4=3/3 9.9.9.9=4/4 7.7.7.7=2/2
nb's log: Caught up: 2 namespace(s) checked, 2 value(s) taken from peers
7.7.7.7 is in a namespace node-b had never heard of, created while it was
down — found through /_api/namespaces, which exists for exactly that. Writes
kept succeeding on the surviving mirror throughout, so the outage cost
availability on one server and nothing else. Forty seconds of five-second
passes after convergence moved nothing.
**How a pass works.** For each peer: ask what namespaces it holds, keep the
ones this server stores, and for each walk /r/<ns>?for_merge in pages,
applying each page in-process. The first pass after startup is a full one,
because a server that has just started has no idea what it missed. Later
passes use ?count as a trigger and skip a namespace whose peer has no more
values than we do — O(1) on both sides, which is what makes it usable on a
timer. That is a heuristic, not a proof: equal counts do not mean equal
contents. The full pass on startup is what stops the heuristic being
load-bearing.
**The Joining state.** `catching_up` is reported on /health and set from
startup until the first full pass finishes. A router reads it and sends reads
to a mirror that is current instead, because a mirror still catching up would
under-report. Writes go to it throughout — they land directly and the pass
fills in the history behind them. If *every* mirror is catching up one answers
anyway: an under-reported count beats no answer, and refusing would make a
whole galaxy unreadable for as long as it took to start.
`sync_interval` in [galaxy] sets the period; 0 switches catching up off.
The obvious design is for the entry point to buffer what a dead node missed and
push it on recovery. That is the wrong mechanism, for two reasons:
* The buffer is unbounded. A node down for an hour at ten thousand writes a
second is thirty-six million entries.
* There is no durable log anywhere in this system — snapshots only, no WAL. If
the router restarts while a node is away, the record of what was missed is
gone, and that node is permanently behind with nothing to say so.
**The surviving mirror is the log.** Catch-up is not replay, it is "pull the
delta from a peer that holds this namespace". Nothing unbounded, survives a
router restart, and works even when a different router saw the writes. This is
also the peer-to-peer sync a galaxy wants anyway.
**Write to a recovering node; withhold reads from it.** Stopping writes while it
catches up means the target keeps moving: under continuous load the sync has no
point at which it provably finishes. Writing to it during catch-up is both
correct and terminating, because new writes land directly while sync backfills
the history behind them, and per-node counters make the two unable to conflict.
What must be withheld is reads, because its data is genuinely incomplete and a
read would under-report:
state writes reads
Joining accepted not served
Live accepted served
Down - -
This is the opposite way round from the intuitive version, and it is the only
version that terminates.
**Never acknowledge a write that reached no holder.** If the entry point acks
when every mirror of a namespace is down, the write exists nowhere and no later
sync can recover it. This is the durability contract, and it is what makes
"the mirror is the log" sound rather than hopeful.
**Knowing how far behind.** There is no sequence number anywhere, so a
recovering node either always syncs on startup or compares itself against a
peer. /r/<namespace>?count is the cheap probe — it is O(1), and its `exact`
flag already says when TTLs make the comparison approximate.
Equal counts do *not* prove convergence: two servers can hold a hundred values
each that the other lacks and report the same total. Count is a good progress
indicator and is what a sync percentage in the interface should use. "Done"
needs a digest or a Merkle root over values. Those are different questions and a
sync that declares itself finished on count equality is quietly wrong.
**Expiry during an outage looks after itself.** A node returning after a week
holds values whose TTL expired while it was away, and may sync them to a peer
that already swept them. It does not matter: expiry is derived from
last_seen + ttl, so a resurrected value is immediately invisible and goes on the
next sweep. Keep catch-up pull-only and this needs no special handling.
Cascading and forwarding
------------------------
BUILT. A client talks to the entry point; writes fan out to every mirror
that holds the namespace, reads come from one, and a cycle dies on the hop
limit.
A router's peer may be a router. Three rules a cascade needs that a single
level does not:
* **A hop limit, which is not optional.** A diamond or a miswired cycle makes
writes circulate and counts inflate without bound. max_hops travels in
X-SightingDB-Hops, is spent on each hop and refused at zero, answering 508.
Measured on two routers pointing at each other: the write collapses in
0.05s rather than circulating.
* **Writes fan out; reads pick one path.** Fanning reads multiplies cost for
nothing. The exception is namespace-scoped reads — listing, ?count, STIX
export — which must gather from every peer holding the namespace. Keep that
list short and deliberate.
* **Fan-out multiplies with depth.** A root to three routers to three nodes
each is nine physical writes per client write. Two levels is usually plenty.
**Reads should be sticky per value.** Mirrors diverge transiently under async
sync, so two consecutive reads served by different mirrors can show a count
going *down*. Picking the mirror by rendezvous hashing over the mirror set for
that value fixes it: same value, same mirror, monotonic. This is the one place
rendezvous hashing belongs here — choosing among the servers that already hold a
namespace, not deciding where data lives.
Two things the measurements say about that choice, both in
doc/sharding-experiment.py:
* Select by rendezvous hashing, not by modulo. mod-n renumbers nearly
everything when the mirror set changes: 88.9% of keys move going from eight
mirrors to nine, against the 11.1% minimum. Rendezvous moves the minimum.
* The hash needs real avalanche. FNV-1a spreads values perfectly well but
makes a poor rendezvous weight — appending ':n0' / ':n1' perturbs it in a
structured way and the comparison between servers becomes correlated, moving
50% where the minimum is 11%. Use SHA-256, already a dependency. Never
std's DefaultHasher: it is not stable across Rust releases, and a toolchain
upgrade would silently repoint every read.
Shadow sightings belong at the entry point
------------------------------------------
BUILT.
Every read records a shadow sighting, so there is no such thing as a read-only
replica and serving more clients roughly doubles write load.
A router is the right place for them, because it is where the client actually
is. It records the shadow locally and forwards the read with `noshadow`, so a
search is counted once, at the entry point, instead of once on whichever mirror
happened to serve it. Nodes stop writing on read entirely, which is what keeps
serving more clients from multiplying write load across a galaxy.
Measured: five reads through a router, with the value held on both mirrors.
shadow on lb (entry point) 5
shadow on node-a 0
shadow on node-b 0
A miss is recorded too, as it already was on a single server: the shadow is
written before the read is forwarded, because a search happened either way.
Under a router that stores only internal namespaces this costs nothing extra:
`_shadow/*` is already held.
Keys are gossiped, not shared
-----------------------------
BUILT, with one limit worth knowing — see the warning below.
acl_file is rewritten by whichever server served the management request, so
saving a key on one used to leave the others ignorant of it. It is now passed
on to the peers, through each peer's own management interface — which means
**the peer's ACL decides whether the change is allowed.**
That is what makes gossip safe here rather than needing a shared file and the
trust that goes with one. A server can only administer a peer it holds an
`admin` key for; a server holding a narrow `rw:feeds` key there cannot change
anything, and gossip therefore flows from whoever holds the credentials towards
the servers they administer. A narrowly-scoped peer cannot push back.
Measured. A router with an admin key on node-a and only `rw` on node-b:
save 'analyst' on the router
router [analyst, changeme]
node-a [analyst, changeme, lb-admin] took it
node-b [changeme, lb-narrow] not ours to administer
the key then works on node-a exactly as granted
/r with 'analyst' 404 accepted, value absent
/w with 'analyst' 403 read-only, as granted
node-b 403 never heard of it
Safe to repeat, which is what lets it be retried and re-offered: saving a key
*sets* its grants rather than adding to them, so the same change arriving twice
is the same as once. Unlike a sighting, where exactly that was the difficulty.
A change is pushed as it happens, and this server's keys are offered again
every `gossip_interval` so a peer that was down for a change picks it up:
node-a down, 'added-while-down' saved on the router
node-a down
node-a back, nobody touches it
+12s node-a [added-while-down, changeme, lb-admin]
A change that arrived *as* gossip is passed along with one hop less, so a
cascade propagates and a cycle dies on the same budget a forwarded write does.
**The limit, which is security relevant.** The periodic offer is additive: it
never deletes a key a peer has and this server does not, because this server is
not necessarily the only place keys are managed and a timer that quietly revoked
a key somebody added elsewhere would be far worse than one that failed to
propagate a deletion. The consequence, confirmed by running it:
node-a down, 'added-while-down' revoked on the router
router [changeme]
node-a [added-while-down, changeme, lb-admin] still live, 18s later
**A revocation made while a server was offline does not reach it.** Repeat the
revocation once it is back, or check that server's own key list. Making this
authoritative instead — peers mirroring one server's ACL exactly — would need a
server to be declared the owner of the galaxy's keys, and that is a decision for
whoever runs it rather than one to assume.
Tiers travel the same way and under the same rule. A tier has no "unset", only
a different value, so unlike a key it has no deletion to miss: offering what
this server holds leaves a peer with exactly that.
**One place to manage keys, if a galaxy wants one.** The additive offer cannot
carry a revocation to a server that was offline for it. `acl_authority` on the
owner makes its offer the whole list, to be held exactly, which does remove —
and `acl_replaceable` on each server that accepts one is what lets it. Both ends
must agree, so arriving here takes two deliberate settings rather than one, and
a server that has not opted in keeps its own keys with the offer falling back to
additive. Setting both on one server is refused at startup: they would take
turns overwriting each other.
A replace must contain an admin key and the key making the request, or it locks
out either the interface or the server doing the replacing.
Still unsolved
--------------
**Durability.** Snapshots every snapshot_interval, 300s by default, and no WAL,
so a crash loses up to five minutes. Replication can stand in for a log, but
only if a write reaches a peer before it is acknowledged; otherwise every server
independently keeps the same five-minute hole. For sighting counts, replicating
asynchronously and accepting the window is defensible — but it should be a
choice rather than an accident.
**Anti-entropy.** Something has to find and repair divergence between mirrors
that are both up, as opposed to catching up one that was down. The per-shard
snapshot files are a natural unit; a version vector per namespace, or Merkle
trees over values once shards get large.
**Membership.** Peers are configured, not discovered. A galaxy that gains and
loses members by hand is fine to start with, and sticky read routing is only as
consistent as the mirror list every server computes against — so two servers
disagreeing about membership will disagree about which mirror serves a value.
Order of work
-------------
DONE 1. Roles: storage set, peer set, 421 for what a server does not hold.
DONE 2. Internal namespaces unwritable, so `_all` cannot be forged.
DONE 3. Peer health, and the galaxy endpoint a topology view reads.
DONE 4. Per-node counters and the snapshot format bump.
DONE 5. The merge verb and its read side, and `new` on write responses.
DONE 6. Forwarding: writes fan out, reads pick one, the hop limit is
enforced, and a forwarded write is counted for its origin.
DONE 7. The galaxy view: one request walks the cascade, and the
management interface draws it.
DONE 8. Catch-up on a timer, and the Joining state that withholds reads
while it runs.
DONE 9. Shadow sightings at the entry point.
DONE 10. The consensus tally in front of a galaxy, and reconciling it
against the nodes.
DONE 11. Keys gossiped to the peers a server administers.
DONE 12. Tiers gossiped the same way.
DONE 13. Authoritative ACL, for a galaxy that wants one server to own its
keys — which is what makes a revocation reach one that was
offline.
Steps 4 and 5 were refactors with no distributed systems in them, and they were
where the difficulty lived. What remains is plumbing by comparison — with the
exception of step 7, whose protocol is written down above.
A note on whether to divide the data at all
-------------------------------------------
Dividing namespaces between servers scales data volume. Serving many more
*clients* is a connection and throughput problem, and full mirrors behind an
entry point solve that with no placement logic, no rebalancing and no
scatter-gather — every server answers everything, and clients change nothing.
The merge properties at the top of this document are what make that safe, and it
is a great deal less work than the rest.
So: mirror everything until the data outgrows one server, then narrow each
server's storage set. The measured snapshot limits are what say which ceiling is
close.
