キャッシュ、CDN、ロードバランシング

大規模環境でキャッシュが不可欠な理由

# Demonstrating the 80/20 caching benefit
import random

# Simulate 1000 requests to 100 items with Zipf-like distribution
def zipf_sample(n_items, n_requests):
    access_counts = {}
    weights = [1.0 / (i + 1) for i in range(n_items)]  # Zipf: item 0 most popular
    total = sum(weights)
    probs = [w / total for w in weights]
    for _ in range(n_requests):
        item = random.choices(range(n_items), weights=probs)[0]
        access_counts[item] = access_counts.get(item, 0) + 1
    return access_counts

random.seed(42)
counts = zipf_sample(100, 10000)
top_20_items = sorted(counts, key=counts.get, reverse=True)[:20]
top_20_requests = sum(counts[i] for i in top_20_items)
print(f'Top 20% of items ({20} of 100) handle {top_20_requests/100:.1f}% of requests')

Cache-Asideパターン（遅延ロード）

# Cache-aside pattern in Python
class CacheAsideService:
    def __init__(self, db, cache):
        self.db = db
        self.cache = cache   # e.g., Redis client

    def get_user(self, user_id):
        cache_key = f'user:{user_id}'
        # 1. Check cache
        cached = self.cache.get(cache_key)
        if cached:
            return cached    # cache hit
        # 2. Cache miss: fetch from DB
        user = self.db.query('SELECT * FROM users WHERE id=%s', user_id)
        # 3. Write to cache with TTL
        self.cache.set(cache_key, user, ttl=3600)  # 1 hour TTL
        return user

    def update_user(self, user_id, data):
        # 1. Write to DB
        self.db.execute('UPDATE users SET ... WHERE id=%s', user_id, data)
        # 2. Invalidate cache (delete, not update)
        self.cache.delete(f'user:{user_id}')
        # Next read will re-populate cache from DB

print('Cache-aside: READ from cache, miss? load from DB + write cache')
print('         WRITE to DB, then DELETE from cache (invalidate)')

Write-ThroughとWrite-Behindキャッシュ

# Write-through vs Write-behind comparison
strategies = {
    'Cache-aside (Lazy)': {
        'read':  'Check cache; miss => DB + populate cache',
        'write': 'Write DB; delete from cache (invalidate)',
        'consistency': 'Strong (invalidation ensures freshness)',
        'write_latency': 'Fast (one DB write)',
        'risk': 'Cache stampede on popular key expiry',
    },
    'Write-through': {
        'read':  'Always check cache; miss => DB',
        'write': 'Write DB AND cache atomically',
        'consistency': 'Strong (cache always has latest)',
        'write_latency': 'Slower (two writes per operation)',
        'risk': 'Cache polluted with rarely-read data',
    },
    'Write-behind': {
        'read':  'Check cache; miss => DB',
        'write': 'Write cache only; async flush to DB',
        'consistency': 'Eventual (flush may be delayed)',
        'write_latency': 'Very fast (cache write only)',
        'risk': 'Data loss if cache crashes before flush',
    },
}
for name, info in strategies.items():
    print(f'\n{name}:')
    for k, v in info.items(): print(f'  {k}: {v}')

キャッシュのエビクションポリシー

# Implementing LRU cache
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()  # maintains insertion/access order

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)   # mark as recently used
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)   # evict LRU (oldest)

cache = LRUCache(3)
for k, v in [('a',1),('b',2),('c',3)]:
    cache.put(k, v)
print('Get a:', cache.get('a'))   # 1 (a now most recently used)
cache.put('d', 4)                  # evicts 'b' (LRU)
print('Get b:', cache.get('b'))   # -1 (evicted)
print('Get c:', cache.get('c'))   # 3

コンテンツ配信ネットワーク（CDN）

# CDN architecture flow
cdn_flow = [
    'User requests https://example.com/image.jpg',
    'DNS resolves to the nearest CDN PoP (e.g., Frankfurt for EU users)',
    'CDN edge checks its local cache:',
    '  HIT:  Return cached image directly (5ms latency)',
    '  MISS: Fetch from origin server (e.g., AWS S3 in us-east-1)',
    '        Cache image at edge with Cache-Control: max-age=86400',
    '        Future requests for this image served from edge (HIT)',
    'Cache-Control headers control CDN behaviour:',
    '  max-age=31536000 s-maxage=31536000  -- cache 1 year',
    '  no-cache                             -- always revalidate',
    '  private                              -- CDN must not cache (user-specific)',
]
for step in cdn_flow:
    print(step)

print('\nCDN providers: Cloudflare, AWS CloudFront, Fastly, Akamai')

負荷分散：トラフィックの分散

# Load balancing algorithms
algorithms = {
    'Round Robin': {
        'how': 'Rotate through servers in sequence',
        'best_for': 'Stateless servers with similar capacity',
        'weakness': 'Does not account for server load or response time',
    },
    'Weighted Round Robin': {
        'how': 'Round robin but servers with more capacity get more requests',
        'best_for': 'Heterogeneous server fleet',
        'weakness': 'Static weights; does not adapt to runtime load',
    },
    'Least Connections': {
        'how': 'Send to server with fewest active connections',
        'best_for': 'Long-lived connections (WebSocket, streaming)',
        'weakness': 'More complex tracking of connection state',
    },
    'Consistent Hashing': {
        'how': 'Hash request key (user_id, session) to server',
        'best_for': 'Sticky sessions, cache locality per server',
        'weakness': 'Uneven distribution if hash space is not balanced',
    },
    'Random': {
        'how': 'Choose server at random',
        'best_for': 'Simple stateless workloads',
        'weakness': 'No guarantee of load balance in short windows',
    },
}
for alg, info in algorithms.items():
    print(f'{alg}: {info["how"]}')

コンシステントハッシュ法：ノードの追加と削除

import hashlib
import bisect

class ConsistentHashRing:
    def __init__(self, replicas=100):
        self.replicas = replicas      # virtual nodes per server
        self.ring = {}
        self.sorted_keys = []

    def add_server(self, server):
        for i in range(self.replicas):
            key = int(hashlib.md5(f'{server}:{i}'.encode()).hexdigest(), 16)
            self.ring[key] = server
            bisect.insort(self.sorted_keys, key)

    def remove_server(self, server):
        for i in range(self.replicas):
            key = int(hashlib.md5(f'{server}:{i}'.encode()).hexdigest(), 16)
            del self.ring[key]
            self.sorted_keys.remove(key)

    def get_server(self, item):
        key = int(hashlib.md5(item.encode()).hexdigest(), 16)
        idx = bisect.bisect(self.sorted_keys, key) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[idx]]

ring = ConsistentHashRing()
for s in ['server-1', 'server-2', 'server-3']:
    ring.add_server(s)
for item in ['user:1', 'user:2', 'product:abc', 'session:xyz']:
    print(f'{item} => {ring.get_server(item)}')

キャッシュスタンピードと解決策

import time, threading, random

# Probabilistic early expiry (XFetch algorithm)
class ProbabilisticCache:
    def __init__(self):
        self._cache = {}

    def get(self, key, ttl, recompute_fn, beta=1.0):
        if key in self._cache:
            value, expiry, delta = self._cache[key]
            # XFetch: decide to refresh early with probability proportional to delta/TTL
            remaining = expiry - time.time()
            if remaining > 0:
                early_refresh_score = delta * beta * (-1) * (remaining / ttl)
                if random.random() > (1 - early_refresh_score):  # simplified
                    pass  # could trigger async refresh here
                return value
        # Cache miss or expired
        start = time.time()
        value = recompute_fn()
        delta = time.time() - start          # computation time
        expiry = time.time() + ttl
        self._cache[key] = (value, expiry, delta)
        return value

print('XFetch: refresh probabilistically before expiry based on computation cost')
print('High-cost computations => refresh earlier to avoid stampede')
print('Low-cost computations => refresh closer to TTL')

CDNキャッシュの無効化

# Cache invalidation strategies for CDN/browser
strategies = [
    {
        'name': 'Long TTL + URL versioning (best for static assets)',
        'example': '<script src="/app.a3f2b1c.js"></script>',
        'ttl': 'Cache-Control: max-age=31536000 (1 year)',
        'how': 'Content hash in filename; new deploy = new URL; old URL cached forever (OK)',
    },
    {
        'name': 'Short TTL (for frequently changing content)',
        'example': '/api/v1/config',
        'ttl': 'Cache-Control: max-age=60 (1 minute)',
        'how': 'Simple; content is at most 60s stale; no invalidation needed',
    },
    {
        'name': 'CDN API purge (for news / social media)',
        'example': '/news/breaking-story.html',
        'ttl': 'Cache-Control: s-maxage=3600',
        'how': 'On publish, call CDN.purge(url); edge serves new version immediately',
    },
]
for s in strategies:
    print(f'{s["name"]}:')
    print(f'  Example: {s["example"]}')
    print(f'  TTL: {s["ttl"]}')
    print(f'  Strategy: {s["how"]}\n')

アーキテクチャ：すべてを組み合わせる

# Request flow with cache hit rates
request_flow = [
    ('Browser Cache',       '10%',  '0ms',   'Browser caches GET responses per Cache-Control'),
    ('CDN Edge Cache',      '60%',  '5ms',   'CloudFront/Fastly caches cacheable API responses'),
    ('Load Balancer',        None,  '1ms',   'Routes to healthy app server replica'),
    ('App Server',           None,  '2ms',   'Business logic, auth check'),
    ('Redis Cache',         '25%',  '1ms',   'Caches computed data, hot DB rows'),
    ('Database Read Replica','5%',  '10ms',  'Cache miss: query read replica'),
    ('Database Primary',    '0.1%', '15ms',  'Cache+replica miss: query primary (rare for reads)'),
]
print(f'{'Layer':30s} {'Hit Rate':10s} {'Latency':10s} {'Notes'}')
print('-'*80)
for layer, hit_rate, latency, note in request_flow:
    hr = hit_rate if hit_rate else '-'
    print(f'{layer:30s} {hr:10s} {latency:10s} {note}')
print('\nResult: DB sees ~5% of requests; Redis sees ~25%; CDN absorbs 60%; browser 10%')

面接のヒント：キャッシュと負荷分散

# Caching design questions checklist
cache_checklist = [
    'What data to cache? (read-heavy, expensive to compute, rarely updated)',
    'Cache layer: client-side / CDN / app-level / DB query cache?',
    'Cache invalidation strategy: TTL / event-driven / write-through?',
    'Eviction policy: LRU / LFU?',
    'Cache key design: ensure uniqueness, avoid hotspots',
    'Consistency window: acceptable staleness in seconds?',
    'Cache stampede prevention: mutex / stale-while-revalidate?',
    'Cache capacity: how much RAM needed for hot set?',
]
lb_checklist = [
    'Layer 4 vs Layer 7: routing by IP or by URL/headers?',
    'Algorithm: round robin / least-connections / consistent hashing?',
    'Health checks: interval, failure threshold, recovery',
    'Session stickiness: needed? Use cookie-based affinity or external session store',
    'Auto-scaling: scale out when CPU > 70%; scale in when < 30%',
]
print('Cache checklist:')
for item in cache_checklist: print(f'  [ ] {item}')
print('\nLoad balancer checklist:')
for item in lb_checklist: print(f'  [ ] {item}')

理解度チェック

レッスンのまとめ