SYSTEM DESIGN · DESIGN PROBLEMS · BUSINESS PLATFORMS · MEDIUM · 47 OF 51

Design an Audit Log System: Append-Only Storage, Hash Chains and Tenant Search

Design the audit trail a SaaS product offers its business customers: who did what, to which resource, when and from where. Scale math, the event schema and API, then the hard parts: never losing an event with an outbox, append-only storage, tamper evidence with per-tenant hash chains and signed checkpoints, tenant-scoped search, retention tiers, legal hold, erasure and large exports.

Try it on the practice board Drag the blocks, wire them up, and check your design against the reference.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
1 / 21

Press play to hear the narration, or step through at your own pace.

Notes

Listen

Listen first. Every service records sensitive actions: a user logged in, a role was granted, a record was exported. Each event says who did it, what they did, to which resource, when, from which IP, whether it worked, and what changed. Tenant admins search and filter their trail, export date ranges, or stream events into their own security tools. Retention depends on the plan, up to seven years, and we must be able to prove nothing was altered.

The qualities matter more than the features. Complete: an action that happened must be recorded, even if a service crashes mid-request. Immutable: no one edits or deletes events, including our own staff. Tamper-evident: if someone with database access does change one, we can detect and prove it. Strict tenant isolation. Search should return in a couple of seconds, and a few seconds to a minute of delay before an event is visible is fine.

Functional
  • record: actor, action, target,
  • time, IP, result, changes
  • events from every service
  • tenant admins can:
  • search and filter by field
  • export a date range
  • stream to their own SIEM
  • retention per plan: 1-7 years
  • prove nothing was altered
Non-functional
  • complete: no lost events,
  • even if a service crashes
  • immutable: no edit or delete,
  • not even by our own admins
  • tamper-evident: changes are
  • detectable and provable
  • isolated: tenant A never sees
  • tenant B
  • search ≤ 2 s on 90 days
  • visible within ~1 minute

Ask scale

Assume twenty thousand tenants producing five hundred million events a day. That is about fifty-eight hundred a second, twenty-five thousand at peak. At about a kilobyte each, with diffs and user agents, that is half a terabyte a day. Ninety days of hot search is around forty-five terabytes before replicas. Compressed five to one in the archive, seven years is roughly two hundred fifty terabytes. And one big tenant can burst to five thousand a second during a bulk import.

Back of the envelope
20,000 tenants, 500M events/day
  500M / 86,400 ≈ 5,800/s avg
  peak ×4 ≈ 25,000/s
event ≈ 1 KB (diff, user agent)
  → 500 GB/day raw
hot index 90 days ≈ 45 TB
  (+ index overhead, replicas)
archive: 5× compression
  100 GB/day × 365 × 7 ≈ 255 TB
largest tenant: 10% of traffic
  bulk import bursts 5,000/s

Define API

The write side is internal and batched, and each event carries an id chosen by the producer, so retries can be deduplicated. It returns two oh two: accepted, not yet searchable. The public read side never takes a tenant id from the query string; the tenant comes from the caller's token. Search uses filters plus a cursor, exports are asynchronous jobs, and a verify endpoint lets a customer check a time range against our signed checkpoints.

API
POST /internal/audit/events  (batch)
  [{ event_id, tenant_id, actor,
     action, target, occurred_at,
     ip, result, changes }]
  → 202
GET  /v1/audit/events
  ?actor=&action=&target=
  &from=&to=&cursor=
POST /v1/audit/exports → 202 {id}
GET  /v1/audit/verify?from=&to=
  → { ok, checkpoint, root }

Data model

Each event has a time-sorted id, the tenant, a per-tenant sequence number, two timestamps, the actor, a dotted action name like role granted, the target, the result and a field-level diff. It also carries the previous event's hash and its own, which we will explain shortly. Checkpoints are a separate small table: tenant, batch number, a root hash, a signature and a time. Nothing in either table is ever updated.

Data model
event
  event_id   UUIDv7 (time-sorted)
  tenant_id, seq (per tenant)
  occurred_at, received_at
  actor {type, id, ip, agent}
  action "role.granted"
  target {type, id}, result
  changes {field: [old, new]}
  prev_hash, hash
checkpoint
  tenant, batch, root, sig, at

High-level design

The write path. Services send batches to the ingest API, which validates the schema, stamps a received time and drops duplicate event ids. Events go to a Kafka topic keyed by tenant, so one tenant's events stay in order on one partition. The chain writer links each event to the previous one by hash, then writes it to a search index for the last ninety days and to the archive in object storage for the long term.

The read path. Admins call the audit API, which adds the tenant filter from their token and queries the search index. Older ranges and big exports read the archive through export workers, which also stream to customers' security tools. Every minute the chain writer signs a checkpoint over the newest hashes and stores it separately. That checkpoint is what lets anyone verify the trail later.

Deep dive: completeness

Deep dive one: completeness. The naive version saves the change, then calls the audit service. If the process crashes between those two steps, or the audit service is down, the role was granted and there is no record of it. For an audit log that is the worst possible bug, because the missing event is exactly the one an attacker would want missing.

The fix is the transactional outbox, from Concepts episode thirty-three. The service writes the business change and the audit event into an outbox table in one database transaction, so either both exist or neither does. A relay reads the outbox and ships batches to ingest, retrying until they are accepted. Retries mean duplicates, so ingest keeps recent event ids and drops repeats. At least once in, exactly once in the trail.

Transactional outbox
BEGIN
  UPDATE roles SET ...
  INSERT INTO audit_outbox
    (event_id, payload)
COMMIT

relay: read outbox in order,
  send batch, mark sent
resend after crash → same id
  → ingest drops the duplicate

Deep dive: append-only

Next, append-only. There is simply no code path that updates or deletes an event; mistakes are fixed by writing a new, correcting event. The archive is the source of truth, stored in object storage with write-once object lock in compliance mode, so even an account owner cannot delete files before their retention date. It lives in a separate account that few people can touch. The search index is only a copy that can always be rebuilt.

Make edits impossible
  • write path has INSERT only;
  • no API can edit an event
  • archive bucket: object lock
  • (WORM) in compliance mode,
  • retention set per tenant
  • separate cloud account, few
  • people, every access logged
  • a mistake? write a new event
  • that corrects it
  • index is a copy: rebuildable

Deep dive: tamper proof

Deep dive two: tamper evidence. For each tenant, every event's hash is computed over the previous hash plus a canonical encoding of the event, with fixed field order so the bytes are always the same. Change event five hundred and its hash changes, so every later hash stops matching. Delete it and the sequence has a gap. To verify a range, recompute the hashes from a trusted starting point and compare.

A chain alone has a hole: an insider could rewrite every event after five hundred and recompute all the hashes. So every minute we sign the newest root with a key held in a key management service, which the writer can use but never export, and we store checkpoints apart from the events. We also hand them to the tenant, by API or by email. Once a customer holds a signed root, we cannot rewrite history before it without being caught.

A chain per tenant is serial by design. Hashing costs about a microsecond, but strictly ordered writes are slow when a big tenant bursts to five thousand a second. So chain batches instead: each second, build a Merkle tree over that tenant's events and chain the batch roots. Order is preserved because Kafka keeps one tenant on one partition, and proving that a single event is included takes only about thirteen hashes.

Hash chain per tenant
h0 = SHA-256("genesis" | tenant)
hN = SHA-256(hN-1 | canonical(eN))

edit e500 → h500 changes
  → h501, h502 ... all mismatch
delete e500 → seq gap + mismatch

verify: recompute from the last
  trusted checkpoint, compare
Anchoring the chain
  • a chain alone is not enough:
  • rewrite everything from e500
  • and recompute all hashes
  • so every minute:
  • sign the latest root with a
  • KMS key the writer can use
  • but cannot export
  • store it apart from events
  • give it to the tenant too
  • old roots are now witnesses
Keeping the chain fast
  • one chain per tenant = serial
  • hashing is cheap (≈ 1 µs);
  • the ordered write is not
  • batch: every 1 s per tenant
  • build a Merkle tree of the
  • batch, chain the batch roots
  • proof that one event is in:
  • log2(5,000) ≈ 13 hashes
  • Kafka key = tenant keeps order

Deep dive: search

Deep dive three: search. Use one index per day, shared by small tenants and routed by tenant id, so a query touches few shards. The API adds the tenant filter itself from the token, never trusting a parameter. The largest tenants get their own indices and their own rate limits, so one huge customer cannot slow everyone else. Retention is simply dropping a whole daily index after ninety days. Older ranges are queried from the archive.

Tenant-scoped search
indices: one per day, shared
  routing = tenant_id
tenant filter added server side
  from the token, never the URL
top 1% tenants: own indices
  (noisy neighbour, own limits)
index: actor, action, target,
  ip, time; changes as text
retention 90 days: drop the
  whole daily index, no deletes
older: query the archive

Deep dive: retention

Retention. Archive files are partitioned by tenant and date, with a lock period matching the tenant's plan, and expired files are deleted whole. A legal hold on a tenant blocks all deletion. Erasure requests clash with immutability, so encrypt personal fields with a key per person. Erasing that person means destroying their key: the data becomes unreadable, while the hashes, which cover the encrypted bytes, still verify.

Retention and erasure
  • archive path: tenant/date/
  • files, lock = plan retention
  • expired: delete whole files
  • legal hold: flag on tenant
  • blocks every deletion
  • right to erasure vs immutable:
  • encrypt personal fields with
  • a per-person key
  • erase = destroy the key
  • hashes cover ciphertext → ok

Deep dive: export

Exports. A request for a full year might be a billion events, so it becomes a background job. Workers read only that tenant's archive partitions, filter, write compressed files to object storage, and return a signed download link together with the checkpoints for that range, so the customer can verify the export offline. For continuous streaming into a customer's security tool, a worker follows the stream with a saved cursor per tenant.

Trade-offs

Trade-offs. Ingest is asynchronous, so an event may take up to a minute to appear, but product requests never wait on auditing. If ingest is down, outboxes grow and nothing is lost. If the index is down, search degrades but the archive is complete. Service clocks disagree, so keep both the source time and the received time, and order by the sequence number. Cost is mostly storage, so compress and move old files to colder tiers.

Monitor the age of the oldest outbox row in each service, ingest lag, sequence gaps per tenant, which must be zero, and run a nightly job that verifies every tenant's chain against its checkpoints. At ten times the scale, add partitions and per-tenant indices, and split into regional cells so European tenants' events stay in Europe, a common requirement for this kind of data.

Trade-offs and failures
  • async ingest: ~1 min to show
  • up, but producers never wait
  • ingest down → outbox grows,
  • nothing is lost
  • index down → search degraded,
  • archive still complete
  • clock skew: keep occurred_at
  • and received_at, sort by seq
  • cost: compress, tier to cold
  • storage after 1 year
Monitor and grow
  • outbox age per service
  • ingest lag, dropped duplicates
  • seq gaps per tenant (must be 0)
  • nightly verify job over every
  • tenant: chain must hold
  • search p99, export duration
  • 10x: more partitions, more
  • per-tenant indices, regional
  • cells for data residency

Interview summary

In the interview: about six thousand events a second and two hundred fifty terabytes over seven years. Events enter through an outbox in the same transaction as the change. Kafka keyed by tenant keeps order. The write-once archive is the truth. A hash chain per tenant, built from Merkle batches and anchored by signed checkpoints, makes tampering detectable. Search uses daily indices scoped by token, retention drops whole partitions, and erasure destroys a key.

Say it like this
  • 6k events/s, 255 TB over 7 yrs
  • outbox: event in the same tx
  • Kafka keyed by tenant
  • archive is truth: WORM objects
  • hash chain per tenant, Merkle
  • batches, signed checkpoints
  • search: daily indices, tenant
  • from token, big tenants alone
  • retention = drop partitions
  • erasure = destroy the key

Interview questions

How do you guarantee an audit event is never lost?

Write the event into an outbox table in the same database transaction as the business change, then have a relay deliver it to the audit pipeline with retries. Duplicates from retries are removed at ingest using the producer-assigned event id.

How does a hash chain make an audit log tamper-evident?

Each event hash is computed over the previous hash plus the canonical event bytes, so changing or deleting any event changes every later hash. Verification recomputes the chain from a trusted point and compares.

Could an insider simply recompute the whole chain after editing?

Yes, which is why the latest root is signed periodically with a non-exportable key and stored separately, and given to the customer. A rewritten history would no longer match roots that others already hold.

How do you keep one tenant from seeing another tenant's events?

The tenant id is taken from the authenticated token and added to every query on the server side, indices are routed by tenant, and the largest tenants get dedicated indices with their own limits.

How do you reconcile an immutable log with a request to erase personal data?

Encrypt personal fields with a per-person key and destroy the key on erasure. The ciphertext and its hashes remain, so the chain still verifies, but the personal data can no longer be read.

How is retention implemented cheaply?

Partition data by tenant and date, using daily indices for search and dated files in the archive, then drop whole indices or files when they expire instead of deleting individual events. A legal hold flag blocks deletion.

Why not chain every event one by one for a very large tenant?

A strict per-event chain forces serial ordered writes. Building a Merkle tree over each short batch and chaining the batch roots keeps the same guarantees, with small inclusion proofs, at much higher throughput.

Which timestamp do you sort audit events by?

Keep both the time the action happened at the source and the time ingest received it, since clocks drift. Order within a tenant by the assigned sequence number and show the source time to users.