🎓 A1Learner
🔍
0 of 42 lessons completed

Rate Limiter: Where the Counters Live

A shared counter store is one fast store that holds the counts for every gateway machine. This lesson designs the data model for those counts and the update that keeps them exact.

Two machines lose an update

Two gateway machines read the same count before either writes back. Each writes back its own increase, and the printout shows one increase missing.

store = {"ana": 100}
read_by_a = store["ana"]
read_by_b = store["ana"]
store["ana"] = read_by_a + 1
store["ana"] = read_by_b + 1

print("two requests arrived")
print("final count", store["ana"])

An atomic increase keeps both updates

The store now performs each increase as one single step. Both machines add to the same key, and the final count keeps both increases.

store = {"ana": 100}

def atomic_add(key):
    store[key] = store[key] + 1
    return store[key]

print("machine A adds, count", atomic_add("ana"))
print("machine B adds, count", atomic_add("ana"))
print("final count", store["ana"])

Counts keyed per user, with a TTL

Each count lives under a key for one user and carries an expiry time as scripted data. An arrival after the expiry starts a fresh count for that user.

store = {}

def hit(user, now):
    if user not in store or now >= store[user][1]:
        store[user] = [0, now + 60]
    store[user][0] += 1
    return store[user][0]

print("ana at second 10, count", hit("ana", 10))
print("ana at second 20, count", hit("ana", 20))
print("ben at second 20, count", hit("ben", 20))
print("ana at second 80, count", hit("ana", 80))

Example

store = {}
limit = 4

def atomic_add(key):
    store[key] = store.get(key, 0) + 1
    return store[key]

arrivals = [("gateway 1", "ana"), ("gateway 2", "ana"), ("gateway 3", "ben"), ("gateway 1", "ana"), ("gateway 2", "ben"), ("gateway 3", "ana"), ("gateway 2", "ana")]

for gateway, user in arrivals:
    count = atomic_add(user)
    print(gateway, user, "count", count, "accepted" if count <= limit else "rejected")

print("final counts", store)

Key points

  • Shared store: many gateway machines read and update one fast shared store, building on the cache idea from earlier work.
  • Lost update: two machines read the same count and each writes back its own increase, so one increase is lost.
  • Lost update in numbers: two machines each add one to a count of 100 and the store ends at 101, not 102.
  • Atomic counter: a counter whose increase the store performs as one single step, so no other update can slip in between.
  • Counter key: each count is stored under a key for one user, so users never share a count.
  • TTL: the time after which a stored count is dropped, so old counts clear themselves away.

In this example, three gateway machines share one store and every increase happens as a single atomic step. The counts stay exact across machines, and the busiest user is rejected only after passing the shared limit.

Note

one shared store keeps every gateway machine working from the same count for a user.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

Two gateway machines update one shared count at the same moment. Which update style keeps the count exact?