"""
Ch5 配套代码 2 / 3 —— 采样 LRU vs 真 LRU 命中率对比

模拟一个有 1000 个 Key 的工作集，按 80/20 法则访问（80% 请求集中在 20% 热点 Key），
缓存容量 200，分别用：
  - 真 LRU（OrderedDict）
  - 采样 LRU（每次淘汰随机抽 N 个，挑最久未访问的）
比较两者命中率差异。复现 Redis 作者博客中的「采样 5 ≈ 真 LRU」结论。
"""

import random
import time
from collections import OrderedDict

import redis

r = redis.Redis(host="127.0.0.1", port=6379, decode_responses=True)


class TrueLRU:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.data: "OrderedDict[str, int]" = OrderedDict()
        self.hits = 0
        self.misses = 0

    def access(self, key: str) -> None:
        if key in self.data:
            self.data.move_to_end(key)
            self.hits += 1
        else:
            self.misses += 1
            self.data[key] = 1
            if len(self.data) > self.cap:
                self.data.popitem(last=False)


class SampledLRU:
    """模拟 Redis 的近似 LRU：access 时只更新时间戳，淘汰时随机采样。"""

    def __init__(self, capacity: int, samples: int):
        self.cap = capacity
        self.samples = samples
        self.data: dict[str, int] = {}
        self.tick = 0
        self.hits = 0
        self.misses = 0

    def access(self, key: str) -> None:
        self.tick += 1
        if key in self.data:
            self.data[key] = self.tick
            self.hits += 1
        else:
            self.misses += 1
            if len(self.data) >= self.cap:
                pool = random.sample(list(self.data.keys()), min(self.samples, len(self.data)))
                victim = min(pool, key=lambda k: self.data[k])
                del self.data[victim]
            self.data[key] = self.tick


def make_workload(n_requests: int = 50_000, n_keys: int = 1000) -> list[str]:
    """80% 请求落在 20% 的 Key 上"""
    hot = [f"hot:{i}" for i in range(n_keys // 5)]
    cold = [f"cold:{i}" for i in range(n_keys - len(hot))]
    seq = []
    for _ in range(n_requests):
        if random.random() < 0.8:
            seq.append(random.choice(hot))
        else:
            seq.append(random.choice(cold))
    return seq


def hit_rate(c) -> float:
    total = c.hits + c.misses
    return c.hits / total if total else 0.0


def run_simulation() -> None:
    print("=" * 60)
    print("采样 LRU vs 真 LRU 命中率对比（80/20 工作集）")
    print("=" * 60)

    workload = make_workload(n_requests=50_000, n_keys=1000)
    capacity = 200

    true_lru = TrueLRU(capacity)
    for k in workload:
        true_lru.access(k)

    print(f"\n  缓存容量={capacity}, 工作集={1000}, 请求数={len(workload)}\n")
    print(f"  {'方案':<22} {'命中率':>10} {'相对真LRU':>14}")
    print("  " + "-" * 50)
    base = hit_rate(true_lru)
    print(f"  {'真 LRU (基准)':<22} {base*100:>9.2f}% {'100.00%':>14}")

    for samples in [3, 5, 10, 20]:
        s_lru = SampledLRU(capacity, samples=samples)
        for k in workload:
            s_lru.access(k)
        rate = hit_rate(s_lru)
        print(f"  {'采样 LRU (N=' + str(samples) + ')':<22} {rate*100:>9.2f}% {rate/base*100:>13.2f}%")

    print("\n  💡 结论：采样 5 已经能逼近真 LRU 95%+ 精度，10 几乎无法区分。")
    print("     这就是 Redis 默认 maxmemory-samples=5 的原因。")


def verify_redis_alive() -> None:
    """顺便确认本机 Redis 可达，避免误以为脚本完全是离线的。"""
    pong = r.ping()
    print(f"\n  [check] Redis ping → {pong}（脚本本身是离线模拟，不写真 Redis）")


if __name__ == "__main__":
    try:
        random.seed(42)
        verify_redis_alive()
        t0 = time.time()
        run_simulation()
        print(f"\n  耗时 {time.time() - t0:.2f}s")
    except redis.ConnectionError as e:
        print(f"❌ Redis 连接失败: {e}")