TAO lets go of some consistency for availability and efficiency, and a follower catches up with a write through an invalidation or a refill.
The CAP theorem rules out perfect consistency with perfect availability. TAO serves stale data rather than go to a remote database. A post has 300 likes, the latest count is 301, and TAO keeps 300 for now.
- Writes are sent to the master. The follower that got the original write request gets a response after success, so it is consistent.
- Other followers are sent invalidation messages on a queue. A follower with an equal or greater version number ignores the message, and one with older data accepts it.
- The leader serializes concurrent writes, so a larger version number is always newer.
- An invalidation deletes the entire key. A group of 20 thousand people gains a member and the list is fetched from the database again.
- A refill names the updated range. The cache keeps the list and fetches only the new users.
Refills are idempotent and can be replayed using logs.