Bài 106: Eviction Policies — LRU vs LFU Sâu

• Hiểu cơ chế LRU approximation của Redis: 24-bit clock, sampling thay vì linked list.
• Hiểu cơ chế LFU: logarithmic counter 8-bit, probabilistic increment, decay timer.
• Phân biệt allkeys-* và volatile-*; biết trường hợp nào volatile tương đương noeviction.
• Tune lfu-log-factor và lfu-decay-time theo đặc điểm phân phối truy cập.
• Debug eviction bằng OBJECT IDLETIME, OBJECT FREQ, INFO stats evicted_keys.
• Hiểu eviction được replicate như thế nào trong master-replica và Cluster.

Khi used_memory chạm maxmemory, Redis cần giải phóng chỗ trước khi xử lý lệnh write tiếp theo. Cơ chế này được gọi là eviction. Bài 105 đã phân tích encoding internals và fragmentation; phần maxmemory ở đó mang tính giới thiệu. Bài này tập trung vào cơ chế bên trong của hai thuật toán eviction chính: LRU và LFU.

Tóm tắt điều kiện kích hoạt:

# redis.conf
maxmemory 4gb
maxmemory-policy allkeys-lru

# Kiểm tra runtime
redis-cli CONFIG GET maxmemory
redis-cli CONFIG GET maxmemory-policy

Nếu maxmemory 0 (default khi không set), Redis không giới hạn memory và không có eviction — instance sẽ tăng cho đến khi OOM killer của OS can thiệp.

LRU (Least Recently Used) chuẩn — theo lý thuyết — dùng một doubly linked list kết hợp với hash map:

• Mỗi lần key được truy cập, node tương ứng được chuyển lên đầu list — thao tác O(1).
• Khi cần evict, lấy node ở đuôi list — key không được truy cập lâu nhất.
• Hash map để lookup node theo key trong O(1).

Overhead của pure LRU:

• Mỗi entry trong linked list cần hai pointer (prev/next) — 8 bytes mỗi pointer trên hệ thống 64-bit.
• Tổng: ~24 bytes per entry chỉ riêng cho cấu trúc LRU list (pointer prev, pointer next, và pointer trong hash map).
• Với 10 triệu key: 24 × 10M = 240MB overhead — chỉ cho metadata eviction, chưa tính data.

Ngoài ra, mỗi write path phải move node lên đầu list — gây pointer chasing và cache miss liên tục trong workload nhiều key khác nhau.

Redis chọn giải pháp khác để tránh overhead này.

Thay vì duy trì linked list, Redis lưu một 24-bit timestamp (giây) trong mỗi Redis object. Đây là trường lru trong struct redisObject. Khi key được truy cập, timestamp được cập nhật thành giá trị hiện tại của LRU clock.

Khi cần evict (policy LRU), Redis không scan toàn bộ keyspace. Thay vào đó:

1. Lấy ngẫu nhiên N keys (N = maxmemory-samples, default 5).
2. So sánh timestamp của N keys đó với LRU clock hiện tại.
3. Chọn key có idle time lớn nhất (timestamp cũ nhất) để evict.

Overhead so với pure LRU:

• Thay vì 24 bytes pointer per key, chỉ cần 3 bytes cho 24-bit timestamp — nằm trong struct redisObject vốn đã tồn tại.
• Không có linked list phải duy trì; không có pointer chasing.
• Trade-off: không chính xác 100% — key thực sự oldest có thể không nằm trong mẫu N keys ngẫu nhiên.

Nghiên cứu của Antirez cho thấy với maxmemory-samples 10, Redis LRU approximation gần như tương đương pure LRU về hit ratio trong thực tế. Với default 5, kết quả tốt trong hầu hết workload production.

maxmemory-samples kiểm soát số key được lấy mẫu trong mỗi lần eviction cho cả LRU và LFU approximation:

# redis.conf
maxmemory-samples 5   # default

Lưu ý: tăng samples từ 5 lên 10 làm tăng CPU per eviction ~2x. Khi hệ thống đang evict nặng (gần maxmemory liên tục), CPU overhead này tích lũy thành latency tăng rõ rệt.

Áp dụng không cần restart:

CONFIG SET maxmemory-samples 5

LRU clock là một bộ đếm 24-bit đơn vị giây, được đọc từ wall clock và lưu trong trường lru của redisObject. Giá trị tối đa của 24-bit là 2²⁴ = 16,777,216 giây ≈ 194 ngày.

Sau 194 ngày kể từ khi Redis khởi động, clock wrap về 0 và đếm lại. Điều này không gây lỗi nhưng có một hệ quả cần biết:

• Idle time được tính là (clock_now - key_lru_clock) mod 2^24.
• Khi clock wrap, key có timestamp gần 0 (vừa được tạo trước khi wrap) sẽ có idle time tính ra rất lớn — có thể bị evict ưu tiên sai.
• Trong thực tế với workload active, key nào không được truy cập gần 194 ngày thường đã có idle time lớn thực sự và evict chúng trước vẫn đúng về mặt logic.

Kiểm tra LRU clock hiện tại:

redis-cli DEBUG SLEEP 0
# Không cần DEBUG SLEEP — OBJECT IDLETIME cho thấy idle time trực tiếp
OBJECT IDLETIME mykey
# 3742   ← seconds since last access

Wrap issue chỉ đáng lo ngại với Redis instance chạy liên tục hơn 6 tháng không restart, trong khi key access pattern có gap lớn. Hầu hết production cluster restart định kỳ (rolling update) trước khi wrap xảy ra.

LFU (Least Frequently Used) — có sẵn từ Redis 4.0 — evict key được truy cập ít lần nhất. Ý tưởng: dù key không được truy cập trong vài giây gần đây, nếu tổng tần suất truy cập của nó cao thì vẫn nên giữ.

Ví dụ minh họa sự khác biệt LRU vs LFU:

Key A: truy cập 10.000 lần trong 30 ngày qua, lần cuối 2 giờ trước
Key B: truy cập 3 lần tổng cộng, lần cuối 5 phút trước

LRU → evict Key A (idle time lớn hơn)
LFU → evict Key B (tần suất thấp hơn nhiều)

Với cache có hot keys ổn định, LFU giữ lại Key A là đúng.

Redis không đếm access count chính xác vì một counter int64 per key sẽ tốn 8 bytes/key — tương tự vấn đề của pure LRU. Thay vào đó, Redis dùng một counter 8-bit (0–255) với hai cơ chế đặc biệt: logarithmic increment và decay.

Probabilistic increment

Mỗi lần key được truy cập, counter không tăng chắc chắn mà tăng với xác suất:

p = 1 / (current_counter × lfu-log-factor + 1)

Hệ quả:

• Counter nhỏ (0, 1, 2): xác suất tăng cao — counter tăng nhanh cho key mới.
• Counter lớn (100, 200): xác suất tăng rất thấp — cần nhiều nghìn access mới tăng thêm 1.
• Counter tối đa là 255; không bao giờ overflow.

Ví dụ với lfu-log-factor 10 (default):

counter = 1   → p = 1 / (1×10 + 1) = 1/11 ≈ 9.1%
counter = 10  → p = 1 / (10×10 + 1) = 1/101 ≈ 1.0%
counter = 100 → p = 1 / (100×10 + 1) = 1/1001 ≈ 0.1%

Số lượng access cần thiết để counter đạt các mức (với lfu-log-factor 10):

Decay — tránh counter stuck

Nếu counter chỉ tăng không giảm, key hot trong quá khứ sẽ chiếm counter cao mãi dù đã không được dùng. Redis giải quyết bằng cách giảm counter theo thời gian không được truy cập:

# redis.conf
lfu-decay-time 1   # minutes per decay unit (default 1)

Cơ chế: mỗi khi key được đọc (kể cả lúc eviction sampling), Redis tính:

elapsed_minutes = (now - last_decay_time) / 60
decrement = elapsed_minutes / lfu-decay-time
new_counter = max(0, current_counter - decrement)

Với lfu-decay-time 1: key không truy cập trong 1 phút giảm 1 điểm counter. Key có counter 100 nhưng không dùng 100 phút sẽ về 0.

Lưu ý quan trọng: decay không chạy theo background job. Nó chạy lazy — chỉ cập nhật khi key được access (dù là read, write, hay sampling của eviction engine). Key không bao giờ được access có thể giữ counter stale cho đến lần đầu tiên bị sample.

lfu-log-factor kiểm soát tốc độ tăng của counter. Giá trị cao hơn → counter tăng chậm hơn → phân biệt tốt hơn giữa các key có tần suất cao. Giá trị thấp hơn → counter tăng nhanh, sớm bão hoà.

# redis.conf
lfu-log-factor 0    # linear increment — counter tăng theo mỗi access, bão hoà nhanh
lfu-log-factor 10   # default — cân bằng
lfu-log-factor 100  # chậm — phân biệt được workload 10M+ access/key

Chọn lfu-log-factor theo phân phối truy cập

Để xác định workload có skewed hay không: xem OBJECT FREQ của một số key sau khi chạy được vài giờ, so sánh counter giữa hot và cold keys. Nếu hầu hết keys đều có counter 255 (saturated), tăng lfu-log-factor. Nếu hot keys có counter chỉ nhỉnh hơn cold keys một chút, giảm lfu-log-factor.

# Kiểm tra counter sau khi tuning
redis-cli OBJECT FREQ homepage:data
redis-cli OBJECT FREQ user:profile:12345
redis-cli OBJECT FREQ old:report:2025

Lưu ý về scan workload: nếu ứng dụng thực hiện SCAN định kỳ trên toàn keyspace (ví dụ export data, analytics batch), mỗi key bị scan sẽ cập nhật LRU timestamp — làm mất thông tin "key thực sự không được dùng". LFU ít bị ảnh hưởng hơn vì counter không tăng đáng kể từ một lần access đơn lẻ (xác suất increment thấp khi counter đã cao).

Trong thực tế, khi không rõ workload, allkeys-lru là lựa chọn an toàn vì hành vi dễ dự đoán. Chỉ chuyển sang LFU khi có evidence rõ ràng về hot key pattern.

Hai nhóm policy phân biệt bởi prefix:

• allkeys-*: pool eviction là toàn bộ keyspace — Redis có thể evict bất kỳ key nào, kể cả key không có TTL.
• volatile-*: pool eviction chỉ gồm keys có TTL (expire được set). Key không có TTL không bao giờ bị evict.

Hệ quả quan trọng của volatile-*:

# Tình huống nguy hiểm:
# maxmemory-policy = volatile-lru
# Toàn bộ keys trong Redis đều không có TTL

# Khi maxmemory hit → Redis cần evict từ pool volatile
# Pool volatile rỗng (không có key nào có TTL)
# → Redis không thể evict → hành vi tương đương noeviction
# → Write bị từ chối với lỗi OOM

Đây là một trong những anti-pattern phổ biến nhất: team nghĩ rằng đã set eviction policy nhưng thực tế không có key nào thuộc pool eviction.

Kiểm tra nhanh số key có TTL:

redis-cli INFO keyspace
# db0:keys=50000,expires=12000,avg_ttl=180000
# expires=12000 → 12.000 keys có TTL trong pool volatile
# Nếu expires=0 mà dùng volatile-* → sẽ không evict được gì

Nguyên tắc chọn prefix:

• Pure cache: dùng allkeys-*. Mọi key đều là cache, không có gì "không được phép xoá".
• Mix persistent + cache: dùng volatile-*. Cache key được set TTL; persistent key không TTL được bảo vệ. Nhưng cần đảm bảo mọi cache key đều có TTL.

Khuyến nghị theo use case

• Pure cache (cache-aside, cache-aside + TTL): allkeys-lru nếu workload temporal; allkeys-lfu nếu có hot subset rõ ràng.
• Mix cache + persistent data trong cùng 1 instance: volatile-lru hoặc volatile-lfu — cache key phải có TTL, persistent key không TTL. Xem phần 18 về caveat.
• Session store: noeviction với TTL trên mỗi session key và monitor chặt used_memory. Không nên evict session vì user sẽ bị logout ngẫu nhiên.
• Counter/analytics realtime: noeviction. Mất counter = số liệu sai. Kết hợp sizing đúng và pre-emptive scaling.

OBJECT IDLETIME trả về số giây kể từ lần truy cập cuối của key — giá trị này được tính từ 24-bit LRU clock:

OBJECT IDLETIME user:profile:1001
# 3742     ← key không được truy cập trong 3742 giây (~62 phút)

OBJECT IDLETIME config:feature_flags
# 12       ← key vừa được đọc 12 giây trước

Lưu ý: OBJECT IDLETIME không hoạt động khi policy đang là LFU (allkeys-lfu hoặc volatile-lfu). Redis tái sử dụng trường lru trong redisObject để lưu LFU counter thay vì LRU timestamp — hai cơ chế chia sẻ cùng storage. Khi dùng LFU policy, OBJECT IDLETIME trả về 0 hoặc sai.

Ứng dụng debug:

import redis

r = redis.Redis()

def list_idle_keys(pattern: str, idle_threshold_sec: int = 3600) -> list[str]:
    """Tìm keys không được truy cập trong hơn idle_threshold_sec giây."""
    result = []
    cursor = 0
    while True:
        cursor, keys = r.scan(cursor, match=pattern, count=100)
        for key in keys:
            try:
                idle = r.object_idletime(key)
                if idle is not None and idle > idle_threshold_sec:
                    result.append((key.decode(), idle))
            except Exception:
                pass
        if cursor == 0:
            break
    return sorted(result, key=lambda x: -x[1])

OBJECT FREQ trả về LFU counter hiện tại của key (0–255). Lệnh này chỉ có ý nghĩa khi policy đang là LFU:

OBJECT FREQ homepage:rendered
# 248     ← counter gần tối đa, key rất hot

OBJECT FREQ report:quarterly:2024
# 2      ← counter thấp, key ít được dùng

OBJECT FREQ user:session:abc123
# 45     ← trung bình

Nếu gọi OBJECT FREQ khi policy là LRU, Redis vẫn trả về giá trị nhưng đó là LRU timestamp được diễn giải sai — không có ý nghĩa. Dùng đúng lệnh theo policy đang active:

# Kiểm tra policy đang dùng
redis-cli CONFIG GET maxmemory-policy
# maxmemory-policy
# allkeys-lfu

# Khi dùng LFU policy → OBJECT FREQ
# Khi dùng LRU policy → OBJECT IDLETIME

Workflow debug khi hit ratio thấp với LFU policy:

1. Sample một số key đại diện cho hot path và cold path của ứng dụng.
2. So sánh counter của chúng với OBJECT FREQ.
3. Nếu hot keys và cold keys có counter gần nhau (cả hai đều ~255 hoặc cả hai thấp), điều chỉnh lfu-log-factor.
4. Nếu hot keys có counter ~255 mà vẫn bị evict, pool eviction quá nhỏ hoặc maxmemory quá thấp.

Eviction xảy ra trong write path: trước khi Redis xử lý lệnh write (SET, HSET, LPUSH, ...), nó kiểm tra used_memory >= maxmemory. Nếu đúng, Redis thực hiện eviction cycle.

Hệ quả về latency:

• Mỗi write command có thể phải chờ một hoặc nhiều vòng eviction trước khi thực thi.
• Một vòng eviction = sample N keys + tính LRU/LFU + DEL key + cập nhật index = vài microsecond.
• Khi hệ thống liên tục ở mức gần maxmemory (ví dụ 95–100%), mỗi write đều phải evict → latency p99 tăng.

Dấu hiệu eviction heavy:

redis-cli INFO stats | grep evicted_keys
# evicted_keys:182043   ← tổng cộng từ khi start

# Theo dõi rate (lấy 2 điểm cách nhau 60 giây và tính delta)
# Nếu evicted_keys tăng > 1000/phút → eviction đang ảnh hưởng latency

Giải pháp khi eviction heavy:

• Tăng maxmemory nếu server còn RAM.
• Thêm Redis node (Cluster hoặc sharding ở tầng application).
• Review TTL — nếu cache TTL quá dài, data tích lũy lâu hơn cần thiết.
• Không nên giảm maxmemory-samples để "nhanh hơn" — eviction kém chính xác hơn không giải quyết nguyên nhân gốc.

evicted_keys từ INFO stats là counter cumulative từ khi Redis start. Để monitor rate, cần lấy delta giữa hai điểm thời gian:

redis-cli INFO stats | grep evicted_keys
# evicted_keys:5432190

Kịch bản cần alert:

• Cache với allkeys-lru: evicted_keys tăng là bình thường — đó là cơ chế hoạt động. Alert khi rate tăng đột ngột (cache thrashing) hoặc hit ratio giảm mạnh.
• Mix persistent + cache với volatile-lru: evicted_keys tăng nhanh nghĩa là cache key bị xoá liên tục — maxmemory không đủ cho cả persistent lẫn cache.
• noeviction: evicted_keys luôn = 0. Alert khi used_memory > 80% maxmemory để có thời gian scale trước khi write bị từ chối.

Trong Prometheus/Grafana, metric thường được expose qua redis_exporter:

redis_evicted_keys_total          # counter, dùng rate() để tính/giây
redis_memory_used_bytes           # used_memory
redis_memory_max_bytes            # maxmemory
redis_keyspace_hits_total         # hits
redis_keyspace_misses_total       # misses

Alert rule mẫu (PromQL):

# Cảnh báo khi eviction rate vượt 100 keys/giây trong 5 phút liên tục
rate(redis_evicted_keys_total[5m]) > 100

# Cảnh báo khi used_memory vượt 80% maxmemory
redis_memory_used_bytes / redis_memory_max_bytes > 0.8

Redis 7 thêm maxmemory-eviction-tenacity (0–100, default 10). Đây là mức độ "hung hăng" của eviction cycle:

• Thấp (0–10): eviction dừng sớm sau khi giải phóng đủ memory cho command hiện tại. Latency per command nhỏ hơn nhưng cần nhiều vòng eviction hơn về tổng thể.
• Cao (50–100): eviction tiếp tục evict nhiều key hơn trong một vòng, đưa used_memory xuống dưới maxmemory xa hơn. Latency per command cao hơn nhưng ít vòng eviction được trigger hơn.

# redis.conf
maxmemory-eviction-tenacity 10   # default

# Tăng lên 50 khi muốn giảm số lần eviction trigger
# (trade-off: command nào trigger eviction sẽ bị chậm hơn)
CONFIG SET maxmemory-eviction-tenacity 50

Cài đặt này hữu ích khi hệ thống có workload burst: nhiều write trong thời gian ngắn → muốn eviction "dọn sạch" nhiều hơn mỗi lần để tránh trigger liên tục. Với workload đều đặn, default 10 là hợp lý.

Một pattern phổ biến là dùng cùng 1 Redis instance cho cả dữ liệu persistent (không TTL) và cache (có TTL), với policy volatile-lru hoặc volatile-lfu:

# Key persistent — không TTL, sẽ không bao giờ bị evict
SET config:rate-limit-rules '{"default":100,"premium":1000}'

# Key cache — có TTL, sẽ bị evict khi cần
SET cache:user:1001:profile '{...}' EX 300
SET cache:product:9999 '{...}' EX 600

Pattern này hoạt động đúng khi:

• Mọi cache key đều có TTL — không có ngoại lệ.
• Persistent data không tăng trưởng vô hạn — nếu persistent keys tích lũy dần, chúng chiếm hết maxmemory và cache không còn chỗ để evict.

Caveat nghiêm trọng:

Scenario:
- maxmemory 4GB
- Persistent data: 1GB (lúc đầu)
- Cache data: 3GB
- Sau 6 tháng, persistent data tăng lên 3.5GB
- Cache chỉ còn 500MB
- Eviction chỉ evict cache keys → hit rate giảm mạnh
- Persistent tiếp tục tăng → eventual OOM

Giải pháp tốt nhất khi workload lớn: tách thành 2 Redis instance — một instance pure cache (allkeys-lru), một instance persistent (noeviction). Tốn thêm tài nguyên nhưng không có conflict.

Master-replica replication

Khi master evict một key, nó replicate lệnh DEL key xuống các replica. Replica không tự quyết định eviction độc lập — replica luôn follow master về mặt data set (replica nhận lệnh xoá từ master).

Điểm cần lưu ý:

• Replica có maxmemory và policy riêng trong config nhưng policy trên replica chỉ ảnh hưởng đến lệnh write trực tiếp vào replica (ít gặp trong production).
• Trong quá trình full resync, replica nhận toàn bộ dataset từ master — nếu master dataset lớn hơn replica maxmemory, replica sẽ evict trong quá trình load. Cần đảm bảo replica có maxmemory đủ lớn.
• Không nên set maxmemory trên replica thấp hơn master — gây divergence.

Redis Cluster

Eviction trong Cluster là per-node: mỗi node có maxmemory riêng và tự quyết định evict key của slot mình phụ trách. Không có global eviction coordinator.

# Xem eviction stats từng node
redis-cli -h node1 -p 7000 INFO stats | grep evicted_keys
redis-cli -h node2 -p 7001 INFO stats | grep evicted_keys
redis-cli -h node3 -p 7002 INFO stats | grep evicted_keys

Khuyến nghị cho Cluster:

• Dùng cùng maxmemory-policy trên tất cả nodes. Node có policy khác nhau dẫn đến eviction behavior không nhất quán — khó debug khi hit rate thấp.
• Set maxmemory để cluster-wide capacity = N nodes × maxmemory-per-node. Monitor từng node riêng biệt.
• Nếu một node nóng hơn (nhiều hot slot) và evict nhiều hơn, cân nhắc resharding để phân phối đều hơn.

Khi policy là noeviction và maxmemory đã đầy, Redis trả lỗi OOM command not allowed when used memory > 'maxmemory'. Application cần xử lý trường hợp này thay vì để exception lan ra ngoài:

import redis
import logging

logger = logging.getLogger(__name__)
r = redis.Redis(host="localhost", port=6379, decode_responses=True)

def safe_cache_set(key: str, value: str, ttl: int = 300) -> bool:
    """
    Ghi vào cache. Trả về True nếu thành công, False nếu Redis OOM.
    Với noeviction policy, OOM xảy ra khi maxmemory đầy.
    """
    try:
        r.set(key, value, ex=ttl)
        return True
    except redis.ResponseError as e:
        if "OOM" in str(e):
            logger.error(
                "Redis OOM: maxmemory exhausted, cache write skipped",
                extra={"key": key}
            )
            # Gửi alert — đây là dấu hiệu cần scale ngay
            _alert_ops_team("redis_oom", detail=str(e))
            # Cache write thất bại nhưng application vẫn tiếp tục
            # bằng cách đọc trực tiếp từ DB khi cần
            return False
        raise  # Lỗi khác (auth, syntax) → propagate

def _alert_ops_team(alert_type: str, detail: str):
    # Gửi tới PagerDuty / Slack / metric system
    pass

Với policy allkeys-lru hoặc allkeys-lfu, OOM error không xảy ra (Redis luôn evict key để nhường chỗ). Nhưng cần theo dõi evicted_keys để phát hiện cache thrashing.

Test OOM handling trong staging:

# Set maxmemory nhỏ để trigger OOM
redis-cli CONFIG SET maxmemory 1mb
redis-cli CONFIG SET maxmemory-policy noeviction
# Sau đó ghi đủ data để fill 1mb

Anti-patterns

• noeviction + dataset tăng trưởng liên tục không giới hạn: writes bị từ chối khi đầy. Cần sizing rõ ràng và alert sớm.
• allkeys-lru cho session store: user bị logout khi session bị evict ngẫu nhiên. Session store cần noeviction.
• volatile-* khi không có key nào có TTL: tương đương noeviction về mặt hành vi — writes bị từ chối khi đầy dù đã nghĩ có eviction.
• LFU với lfu-decay-time quá lớn: counter của hot keys cũ luôn ở mức cao, hot keys mới khó vượt qua — cache bị "chiếm đóng" bởi keys hot từ lâu.
• Không monitor evicted_keys: với allkeys-lru, data bị xoá âm thầm — nếu đó là data quan trọng hơn cache thuần, không có gì cảnh báo trước.
• Set maxmemory gần sát RAM vật lý: Redis cần memory cho fork (BGSAVE/BGREWRITEAOF), buffer network, Lua overhead. Giữ maxmemory ≤ 75–80% RAM vật lý.
• Replica có maxmemory thấp hơn master: full resync có thể fail hoặc gây eviction không kiểm soát trên replica.

Best practices

• Chọn policy theo use case rõ ràng — không dùng policy mặc định mà không có lý do.
• Set maxmemory ≤ 75% RAM vật lý để có headroom cho fork copy-on-write.
• Monitor evicted_keys rate; alert khi tăng đột ngột với workload không phải pure cache.
• Với LFU: set lfu-log-factor theo skew của workload; kiểm tra với OBJECT FREQ sau khi chạy vài giờ.
• Với mix persistent + cache: tách thành 2 instances nếu workload scale lớn.
• Test eviction behavior trong staging với maxmemory nhỏ trước khi deploy production.
• Với Cluster: đồng bộ maxmemory-policy trên tất cả nodes; monitor evicted_keys per-node.

Tổng kết

• Redis LRU không dùng linked list mà lưu 24-bit timestamp per key và evict bằng sampling N keys ngẫu nhiên — tiết kiệm memory, đủ chính xác với maxmemory-samples 5.
• LRU clock 24-bit giới hạn độ chính xác trong ~194 ngày; idle time được tính xấp xỉ từ diff với clock hiện tại.
• LFU dùng logarithmic counter 8-bit với probabilistic increment (tăng chậm dần khi counter cao) và lazy decay theo thời gian không truy cập. lfu-log-factor kiểm soát tốc độ tăng counter.
• allkeys-*: evict bất kỳ key. volatile-*: chỉ evict key có TTL — nếu không có key nào có TTL, volatile-* tương đương noeviction.
• Eviction xảy ra trong write path → heavy eviction gây latency spike. Giải pháp: tăng maxmemory hoặc thêm node trước khi gần limit.
• Monitor evicted_keys rate; debug LRU bằng OBJECT IDLETIME, debug LFU bằng OBJECT FREQ — hai lệnh này không hoán đổi được.
• Trong replication: master evict → replicate DEL xuống replica. Trong Cluster: eviction per-node, cần đồng bộ policy.

Quiz 5 câu

1. Redis LRU approximation khác pure LRU ở điểm nào? Overhead tiết kiệm được bao nhiêu per key?
2. LFU counter 8-bit có thể bị "stuck" cao dù key đã không được dùng. Cơ chế nào ngăn điều này và khi nào nó chạy?
3. Bạn set maxmemory-policy volatile-lru nhưng evicted_keys không tăng dù used_memory đã chạm maxmemory. Nguyên nhân có thể là gì?
4. Giải thích khi nào dùng OBJECT IDLETIME và khi nào dùng OBJECT FREQ. Có thể dùng cả hai cùng lúc không?
5. Trong Redis Cluster 6 nodes, một node eviction rate cao bất thường so với 5 nodes còn lại. Hai nguyên nhân phổ biến nhất là gì và giải quyết thế nào?

Đáp án gợi ý

1. Pure LRU dùng doubly linked list + hash map — ~24 bytes per key overhead, thao tác move-to-front tốn pointer chasing. Redis LRU lưu 24-bit timestamp trong trường lru của redisObject — 3 bytes, không có linked list. Eviction chọn oldest trong N keys ngẫu nhiên (sampling), không chính xác 100% nhưng tiết kiệm >20 bytes per key.
2. Cơ chế là decay: khi key được đọc (kể cả lúc eviction sampling), Redis tính số phút đã trôi qua từ lần decay cuối và giảm counter tương ứng (decrement = elapsed_minutes / lfu-decay-time). Decay chạy lazy — không có background job — chỉ khi key được access. Key chưa bao giờ bị sample hoặc access sẽ không decay cho đến lần đầu tiên bị touch.
3. Khả năng cao nhất: không có key nào có TTL trong keyspace. volatile-lru chỉ evict từ pool "keys có TTL"; nếu pool rỗng, Redis không evict được và hành vi giống noeviction — write bị từ chối. Kiểm tra: INFO keyspace, xem trường expires. Nếu expires=0 → đó là nguyên nhân.
4. OBJECT IDLETIME dùng khi policy là LRU (đọc LRU timestamp). OBJECT FREQ dùng khi policy là LFU (đọc LFU counter). Không thể dùng cả hai cùng lúc vì cả hai trường này (lru trong redisObject) chia sẻ cùng 24 bits storage — khi LFU policy active, bits đó lưu counter chứ không lưu timestamp.
5. Hai nguyên nhân phổ biến: (1) Hot slot concentration — nhiều hot keys tình cờ hash vào cùng một node → node đó phải evict nhiều hơn. Giải quyết bằng resharding hoặc thêm hashtag để phân tán. (2) maxmemory không đồng đều giữa nodes — node có RAM vật lý nhỏ hơn hoặc maxmemory config thấp hơn sẽ evict nhiều hơn dù dataset tương đương. Đồng bộ maxmemory config trên tất cả nodes.

Bài tiếp theo

Bài 107 phân tích big keys: cách phát hiện bằng redis-cli --bigkeys, SCAN + MEMORY USAGE, và DEBUG OBJECT; tác động của big key lên latency và replication; cách split và migrate.

Tham khảo

• Redis Docs — Configuration (maxmemory, LFU, eviction)
• Redis Docs — OBJECT FREQ
• Redis Docs — OBJECT IDLETIME
• Redis Docs — INFO stats (evicted_keys)
• Redis Blog — Cache Eviction Strategies
• Redis Docs — Replication