Working through the classic designs

import math

ALPHABET = 62          # a-z A-Z 0-9

print("key length   keyspace        after 1 billion URLs: expected collisions")
for length in [5, 6, 7, 8, 10]:
    space = ALPHABET ** length
    n = 1e9
    expected = n * n / (2 * space)                 # birthday approximation
    print(f"{length:10}   {space:.3e}   {expected:38,.1f}")

print()
print("chance the NEXT random key collides, at 1 billion keys already stored")
for length in [6, 7, 8]:
    space = ALPHABET ** length
    print(f"  {length} chars: {1e9/space:.2e}  ->  one retry every "
          f"{space/1e9:,.0f} inserts on average")

print()
print("counter-based keys instead: no collisions by construction")
for n in [1e6, 1e9, 1e12]:
    print(f"  {n:.0e} URLs needs {math.ceil(math.log(n, ALPHABET))} base-62 characters")

# key length   keyspace        after 1 billion URLs: expected collisions
#          5   9.161e+08                            545,772,384.2
#          6   5.680e+10                              8,802,780.4
#          7   3.522e+12                                141,980.3
#          8   2.183e+14                                  2,290.0
#         10   8.393e+17                                      0.6
#
# chance the NEXT random key collides, at 1 billion keys already stored
#   6 chars: 1.76e-02  ->  one retry every 57 inserts on average
#   7 chars: 2.84e-04  ->  one retry every 3,522 inserts on average
#   8 chars: 4.58e-06  ->  one retry every 218,340 inserts on average
#
# counter-based keys instead: no collisions by construction
#   1e+06 URLs needs 4 base-62 characters
#   1e+09 URLs needs 6 base-62 characters
#   1e+12 URLs needs 7 base-62 characters

Token bucket
  capacity 100, refill 10 per second
  request arrives: if tokens >= 1, spend one and allow
                   otherwise reject with 429

Allows a burst of 100, then sustains 10 per second.

class TokenBucket:
    def __init__(self, capacity, refill_per_second, now=0.0):
        self.capacity, self.rate = capacity, refill_per_second
        self.tokens, self.stamp = float(capacity), now

    def allow(self, now):
        self.tokens = min(self.capacity, self.tokens + (now - self.stamp) * self.rate)
        self.stamp = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

bucket = TokenBucket(capacity=100, refill_per_second=10)
allowed = []
for second in range(6):
    n = sum(bucket.allow(second + i * 0.004) for i in range(200))   # 200 requests/s
    allowed.append(n)
print("200 requests a second, bucket capacity 100, refill 10/s")
print("  allowed per second:", allowed)
print("  total allowed", sum(allowed), "of 1200; the first second spends the burst,")
print("  after that the caller gets the refill rate and nothing more")

# 200 requests a second, bucket capacity 100, refill 10/s
#   allowed per second: [107, 10, 10, 10, 10, 10]
#   total allowed 157 of 1200; the first second spends the burst,
#   after that the caller gets the refill rate and nothing more

import threading, time

LIMIT = 100

class Store:
    """Stands in for Redis. Every operation pays a small network delay."""
    def __init__(self):
        self.n = 0
        self.lock = threading.Lock()
    def get(self):
        time.sleep(0.0005)
        return self.n
    def set(self, v):
        time.sleep(0.0005)
        self.n = v
    def incr_if_below(self, limit):        # one atomic server-side operation
        with self.lock:
            time.sleep(0.001)
            if self.n < limit:
                self.n += 1
                return True
            return False

def race(store, atomic):
    allowed = []
    def worker():
        for _ in range(20):
            if atomic:
                ok = store.incr_if_below(LIMIT)
            else:
                n = store.get()            # read
                ok = n < LIMIT
                if ok:
                    store.set(n + 1)       # write, after someone else may have read
            allowed.append(ok)
    threads = [threading.Thread(target=worker) for _ in range(20)]
    for t in threads: t.start()
    for t in threads: t.join()
    return sum(allowed)

for label, atomic in [("read then write", False), ("atomic check-and-increment", True)]:
    s = Store()
    n = race(s, atomic)
    print(f"{label:28} allowed {n:4} of 400 requests against a limit of {LIMIT}"
          f"   {'OVER BY ' + str(n - LIMIT) if n > LIMIT else 'exact'}")

# read then write              allowed  400 of 400 requests against a limit of 100   OVER BY 300
# atomic check-and-increment   allowed  100 of 400 requests against a limit of 100   exact

import random

random.seed(4)
USERS = 1_000_000
# A realistic shape: nearly everyone small, a thin tail of enormous accounts.
followers = [int(random.paretovariate(1.2) * 30) for _ in range(USERS)]
followers[0] = 50_000_000                       # one celebrity

posts_per_user_per_day = 0.5

write_cost = sum(f * posts_per_user_per_day for f in followers)
print(f"fan-out on write: {write_cost:,.0f} feed rows written a day")
print(f"  the single largest account is "
      f"{followers[0]*posts_per_user_per_day/write_cost:.0%} of that")

# Hybrid: anyone above the threshold is pulled at read time instead.
for threshold in [10_000, 100_000, 1_000_000]:
    written = sum(f * posts_per_user_per_day for f in followers if f <= threshold)
    big = sum(1 for f in followers if f > threshold)
    print(f"  threshold {threshold:>9,}: {written:15,.0f} rows written a day, "
          f"{big:3} accounts pulled at read time")

print(f"average account follows {sum(followers)/USERS:.0f} others, so a read-time "
      f"assembly touches that many timelines")

# fan-out on write: 124,530,152 feed rows written a day
#   the single largest account is 20% of that
#   threshold    10,000:      61,457,893 rows written a day, 919 accounts pulled at read time
#   threshold   100,000:      71,206,486 rows written a day,  58 accounts pulled at read time
#   threshold 1,000,000:      77,776,094 rows written a day,   6 accounts pulled at read time
# average account follows 249 others, so a read-time assembly touches that many timelines