Bài 22: List — Timeline, Capped List & Queue Cơ Bản

• Hiểu bản chất Redis List: ordered, cho phép duplicate, push/pop O(1) từ 2 đầu.
• Implement timeline / activity feed newest-first với LPUSH + LRANGE.
• Implement capped list với LTRIM và làm atomic bằng pipeline hoặc Lua.
• Dùng LPUSH + BRPOP làm FIFO queue cơ bản, hiểu giới hạn at-most-once.
• Biết encoding listpack/quicklist ảnh hưởng tới memory.
• Nhận biết các anti-pattern: list không cap, LRANGE 0 -1, List làm reliable queue.

Redis List là một ordered collection of string, các phần tử được sắp xếp theo thứ tự chèn, cho phép duplicate. Điểm nổi bật so với Array thông thường là push/pop từ cả hai đầu (head và tail) đều O(1).

Đặc điểm cơ bản

• Ordered: thứ tự phần tử được bảo toàn theo thứ tự chèn.
• Duplicate: cùng một giá trị có thể xuất hiện nhiều lần.
• Push/pop 2 đầu O(1): LPUSH/RPUSH thêm vào head/tail, LPOP/RPOP xoá từ head/tail.
• Index access: LINDEX truy cập theo index (0-based), LRANGE lấy một đoạn.
• Tối đa 2^32 - 1 phần tử (~4 tỷ) trong một List.

Command cốt lõi

# Thêm vào đầu (head)
LPUSH timeline:user:123 "post:789"
LPUSH timeline:user:123 "post:790" "post:791"   # multi-push, thứ tự ngược

# Thêm vào cuối (tail)
RPUSH log:events "event:A"

# Đọc đoạn [start, stop] (inclusive, 0-based, -1 = cuối cùng)
LRANGE timeline:user:123 0 9    # 10 phần tử đầu
LRANGE timeline:user:123 0 -1   # toàn bộ (TRÁNH trên list lớn)

# Độ dài
LLEN timeline:user:123

# Pop từ đầu / cuối
LPOP timeline:user:123          # xoá và trả về phần tử đầu
RPOP timeline:user:123          # xoá và trả về phần tử cuối
LPOP timeline:user:123 5        # Redis 6.2+: pop nhiều phần tử

# Truy cập theo index
LINDEX timeline:user:123 0      # phần tử đầu
LINDEX timeline:user:123 -1     # phần tử cuối (O(N) nếu list lớn)

# Cắt list, giữ [start, stop]
LTRIM timeline:user:123 0 99    # giữ 100 phần tử đầu, xoá phần còn lại

LPUSH trả về độ dài list mới sau khi push. Với multi-push LPUSH key a b c, Redis push lần lượt từ trái sang phải nên thứ tự cuối cùng trong list là [c, b, a, ...] — c ở head.

Một trong những use case trực tiếp nhất của List là timeline (danh sách bài đăng / sự kiện gần đây, mới nhất lên đầu).

Pattern: LPUSH + LRANGE 0 N

# User đăng bài → push ID bài vào đầu timeline
LPUSH timeline:user:123 "post:789"

# Đọc 20 bài gần nhất
LRANGE timeline:user:123 0 19

Vì LPUSH thêm vào head, bài mới nhất luôn ở index 0. LRANGE 0 19 trả về 20 bài mới nhất với thứ tự newest-first, không cần sort thêm.

Fan-out-on-write

Khi user A có nhiều follower, mỗi lần A đăng bài, hệ thống push ID bài đó vào timeline của từng follower:

def publish_post(author_id: int, post_id: str, follower_ids: list[int]) -> None:
    pipe = r.pipeline()
    for follower_id in follower_ids:
        pipe.lpush(f"timeline:{follower_id}", post_id)
        pipe.ltrim(f"timeline:{follower_id}", 0, 999)  # capped 1000
    pipe.execute()

Mô hình này gọi là fan-out-on-write: ghi tốn công hơn (N lần LPUSH) nhưng đọc cực nhanh (một LRANGE). Phù hợp khi đọc nhiều hơn ghi nhiều lần. Với user có hàng triệu follower, fan-out-on-write cần chiến lược riêng (dùng hybrid với Streams) — nhưng với quy mô hàng nghìn follower thì List đủ tốt.

Lưu ý về thứ tự đọc

LRANGE 0 N đọc từ head — nhanh vì quicklist bắt đầu duyệt từ đầu. Tránh dùng LRANGE giữa hoặc cuối list lớn (xem phần Performance).

Nếu chỉ dùng LPUSH mà không giới hạn độ dài, list sẽ grow vô hạn theo thời gian — dẫn đến big key và tốn RAM. Giải pháp là capped list: sau mỗi lần push, dùng LTRIM để giữ đúng N phần tử gần nhất.

# Thêm item mới vào đầu
LPUSH recent:user:123 "search:keyword"

# Giữ 100 item gần nhất (index 0..99), xoá phần còn lại
LTRIM recent:user:123 0 99

LTRIM chỉ giữ lại đoạn [start, stop] và xoá phần ngoài đoạn đó. Nếu list đang có 101 phần tử sau LPUSH, LTRIM 0 99 xoá phần tử thứ 101 ở tail.

Use case phù hợp

• Recent searches: lưu 10-20 từ khoá tìm kiếm gần nhất của user.
• Last N notifications: lưu 50-100 thông báo gần nhất để hiển thị trong app.
• Recent activity: lịch sử hoạt động gần đây trên màn hình profile.
• Log vòng (ring buffer): giữ N event log gần nhất mà không cần xoá thủ công cũ.

Tại sao không dùng EXPIRE thay LTRIM?

EXPIRE xoá key theo thời gian, không theo số lượng phần tử. Với capped list, mục tiêu là giữ đúng N item gần nhất bất kể thời gian — nên LTRIM là đúng công cụ. Hai thứ không loại trừ nhau: có thể dùng cả LTRIM (giới hạn N) lẫn EXPIRE (TTL cho toàn key) song song.

LPUSH và LTRIM là hai lệnh riêng biệt. Nếu gọi tuần tự trong code mà không pipeline, giữa hai lệnh có thể có request khác chen vào và đọc list chưa được trim. Trong hầu hết use case (timeline, recent search), điều này không phải lỗi nghiêm trọng — nhưng nếu cần đảm bảo chặt chẽ hơn, có hai cách.

Cách 1: Pipeline (batch round-trip, không atomic)

import redis

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

def push_capped(key: str, item: str, max_len: int) -> None:
    pipe = r.pipeline()
    pipe.lpush(key, item)
    pipe.ltrim(key, 0, max_len - 1)
    pipe.execute()

# Ví dụ: giữ 100 recent searches
push_capped("recent:user:123", "redis tutorial", 100)

Pipeline gộp 2 lệnh vào 1 round-trip, giảm latency. Tuy nhiên pipeline không atomic: hai lệnh chạy tuần tự trên server và vẫn có thể bị xen giữa bởi lệnh từ client khác (dù xác suất thấp và window nhỏ).

Cách 2: Lua script (thực sự atomic)

-- Script: push + trim atomic
-- KEYS[1] = key, ARGV[1] = item, ARGV[2] = max_len
redis.call('LPUSH', KEYS[1], ARGV[1])
redis.call('LTRIM', KEYS[1], 0, tonumber(ARGV[2]) - 1)

LUA_PUSH_CAPPED = """
redis.call('LPUSH', KEYS[1], ARGV[1])
redis.call('LTRIM', KEYS[1], 0, tonumber(ARGV[2]) - 1)
"""

script = r.register_script(LUA_PUSH_CAPPED)

def push_capped_atomic(key: str, item: str, max_len: int) -> None:
    script(keys=[key], args=[item, str(max_len)])

Redis đảm bảo Lua script chạy atomically — không lệnh nào khác được xử lý giữa hai dòng trong script. Đây là lựa chọn phù hợp khi nhiều writer concurrent cùng push vào một key và cần đảm bảo trim ngay lập tức.

Với redis-py, register_script() tự dùng EVALSHA (gửi hash của script thay vì toàn bộ source sau lần đầu) — tiết kiệm băng thông khi script được gọi thường xuyên.

Redis List có thể làm FIFO queue đơn giản: producer push vào một đầu, consumer pop từ đầu kia.

# Producer: push job vào tail
RPUSH jobs "job:001"
RPUSH jobs "job:002"

# Consumer: pop từ head (FIFO)
LPOP jobs              # "job:001"
LPOP jobs              # "job:002"

Hoặc chiều ngược lại cũng được (LPUSH + RPOP), miễn là push và pop ở hai đầu khác nhau.

BRPOP — Blocking Pop

Consumer thường không biết khi nào có job mới. Thay vì polling (lặp RPOP liên tục), dùng BRPOP để block chờ:

# Consumer block tối đa 5 giây chờ job
BRPOP jobs 5
# Nếu có job trong 5s: trả về ["jobs", "job:001"]
# Nếu timeout:         trả về nil

def consume_jobs(queue_key: str) -> None:
    while True:
        result = r.brpop(queue_key, timeout=5)
        if result is None:
            # timeout, tiếp tục vòng lặp
            continue
        _queue_name, job_data = result
        process_job(job_data)

BRPOP hiệu quả hơn polling vì chỉ wake up khi thực sự có dữ liệu. Với nhiều consumer cùng BRPOP một key, Redis phân phát job theo kiểu first-come-first-served.

Giới hạn quan trọng: at-most-once

BRPOP (và RPOP) xoá phần tử ngay lập tức khi pop. Nếu consumer crash sau khi pop nhưng trước khi xử lý xong job, job đó bị mất vĩnh viễn — không có cách recover. Đây là at-most-once delivery.

Nếu hệ thống cần at-least-once hoặc exactly-once delivery, List không đủ — cần Streams với consumer group (Module 5).

Redis 6.2 giới thiệu LMOVE để di chuyển phần tử từ list này sang list khác một cách atomic, thay thế cho RPOPLPUSH (deprecated).

# Di chuyển phần tử đầu của "jobs" sang đầu "processing"
LMOVE jobs processing LEFT RIGHT
# Tương đương RPOPLPUSH nhưng linh hoạt hơn (4 hướng)

LMOVE đảm bảo tính atomic: hoặc phần tử được di chuyển hoàn toàn, hoặc không gì thay đổi. Nếu consumer crash sau LMOVE, phần tử vẫn còn trong list processing — một recovery process có thể dọn lại sau.

# Pattern: safe pop
LMOVE jobs processing LEFT RIGHT   # atomic move
# ... xử lý job ...
LREM processing 1 "job:001"        # xoá khỏi processing khi xong

Đây là bước đệm giữa at-most-once (BRPOP) và reliable queue (Streams). Tuy nhiên pattern này vẫn cần application tự xử lý recovery, và không có consumer group hay acknowledgment tích hợp sẵn. Module 5 sẽ so sánh chi tiết với Streams.

BLMOVE là phiên bản blocking của LMOVE (cũng Redis 6.2+), tương tự BRPOP nhưng di chuyển sang list khác thay vì trả về client.

Redis List dùng hai encoding nội bộ tuỳ theo kích thước:

Encoding	Khi nào áp dụng	Đặc điểm
listpack	List nhỏ: < 128 entry và mọi value < 64 bytes	Compact memory layout, traversal O(N) nhưng overhead thấp
quicklist	Vượt ngưỡng listpack	Linked list của listpack node, cân bằng giữa memory và tốc độ truy cập đầu/cuối

# Kiểm tra encoding thực tế
OBJECT ENCODING timeline:user:123
# "listpack"   — list nhỏ
# "quicklist"  — list lớn

Cấu hình ngưỡng

# redis.conf
list-max-listpack-size 128    # số entry tối đa dùng listpack
                              # giá trị dương = số entry
                              # giá trị âm = giới hạn byte per node:
                              #   -1 = 4KB, -2 = 8KB (default), -3 = 16KB...

Giá trị mặc định -2 nghĩa là mỗi quicklist node không quá 8KB. Tăng list-max-listpack-size giúp list nhỏ tiết kiệm RAM hơn; tăng quá cao làm các operation trên node đó chậm đi.

Encoding tự động chuyển đổi khi vượt ngưỡng: listpack → quicklist (không bao giờ quay lại quicklist → listpack).

Lệnh	Complexity	Ghi chú
LPUSH / RPUSH	O(1) per element	Multi-push O(N) với N elements
LPOP / RPOP	O(N) với Redis 6.2+ multi-pop, O(1) với 1 element
LLEN	O(1)
LRANGE 0 N (đầu list)	O(N) với N = số phần tử trả về	Nhanh vì bắt đầu từ head
LRANGE giữa / cuối	O(S + N)	S = số node phải bỏ qua; chậm trên list lớn
LINDEX	O(N)	Duyệt từ đầu/cuối tuỳ index; O(1) chỉ với index 0 hoặc -1 trên quicklist
LTRIM	O(N) với N = số phần tử bị xoá	Nhanh khi chỉ xoá ít phần tử ở tail
LINSERT / LREM	O(N)	Duyệt toàn list; tránh trên list lớn
LMOVE	O(1)

Điểm cần nhớ: List được tối ưu cho đầu và cuối, không phải giữa. Mọi thao tác đọc/tìm kiếm ở giữa đều O(N). Nếu hay cần truy cập phần tử theo vị trí tuỳ ý, Sorted Set thường là lựa chọn tốt hơn.

Yêu cầu	Structure phù hợp	Lý do
Simple FIFO, at-most-once, không cần ack	List (LPUSH + BRPOP)	Đơn giản, O(1) push/pop
Reliable delivery, consumer group, replay, acknowledgment	Stream (Module 5)	XADD/XREADGROUP/XACK, consumer group tích hợp, PEL tracking
Delayed queue, priority queue (job chạy theo thứ tự ưu tiên)	Sorted Set (score = priority hoặc timestamp)	ZADD/ZPOPMIN, score làm priority/deadline tự nhiên
Pub/sub fan-out, không cần lưu lịch sử	Pub/Sub (PUBLISH/SUBSCRIBE)	Fire-and-forget, không persist

List queue phù hợp cho các tác vụ mà mất message khi crash là chấp nhận được (ví dụ: gửi push notification best-effort, update cache warm-up). Khi mất message không thể chấp nhận — dùng Streams.

• Quên LTRIM — list grow vô hạn. LPUSH mà không có LTRIM tương ứng làm list phình to theo thời gian. Với timeline 1 triệu user mỗi người có 10.000 post, một List không cap có thể chiếm hàng GB RAM. Luôn cap list khi dữ liệu không bounded.
• LRANGE 0 -1 (toàn bộ) trên list lớn. LRANGE key 0 -1 trả về toàn bộ list — có thể là hàng triệu phần tử, block Redis trong vài trăm ms và tốn băng thông lớn. Luôn giới hạn range cụ thể (LRANGE key 0 99).
• List làm reliable queue — mất message khi crash. RPOP/BRPOP xoá phần tử ngay lập tức. Consumer crash sau pop = job biến mất. Dùng Streams nếu cần guaranteed delivery.
• LINSERT / LREM trên list lớn — O(N) chậm. LINSERT tìm pivot element bằng cách duyệt toàn list; LREM duyệt toàn list để xoá theo value. Cả hai O(N) và block Redis đáng kể trên list lớn (>10.000 phần tử). Nếu cần xoá phần tử giữa list thường xuyên, xem xét Sorted Set.
• Dùng LINDEX để đọc phần tử ở giữa list lớn. LINDEX key 5000 phải duyệt 5000 node — O(N). Không dùng List như array có random access.
• Nhiều LPUSH riêng lẻ thay vì multi-push. LPUSH key a rồi LPUSH key b là 2 round-trip. Dùng LPUSH key a b c hoặc pipeline để gom lại.

Tổng kết

• Redis List: ordered collection of string, push/pop 2 đầu O(1), cho phép duplicate.
• Timeline/activity feed: LPUSH (newest-first ở head) + LRANGE 0 N để đọc N bài mới nhất.
• Capped list: LPUSH + LTRIM sau mỗi push để giới hạn N phần tử. Atomic hơn với Lua script.
• Queue FIFO cơ bản: LPUSH + BRPOP (blocking consumer). Giới hạn: at-most-once delivery.
• LMOVE (Redis 6.2+): di chuyển phần tử atomic giữa hai list — cơ sở của reliable-er pattern.
• Encoding: listpack cho list nhỏ (<128 entry, value <64B), quicklist cho list lớn.
• Performance: đầu/cuối O(1); giữa O(N). Tránh LRANGE 0 -1, LINSERT, LREM trên list lớn.
• Reliable queue → Streams (Module 5); delayed/priority queue → Sorted Set.

Quiz 5 câu

1. Viết 2 lệnh Redis để implement "10 tìm kiếm gần nhất" của user. Giải thích tại sao chọn LPUSH thay RPUSH cho use case này.
2. Tại sao LPUSH + LTRIM cần được atomic trong một số trường hợp? Pipeline có đảm bảo atomic không?
3. Consumer dùng BRPOP nhận được job, nhưng crash ngay sau đó. Job có recover được không? Vì sao? Giải pháp?
4. Một list có 100.000 phần tử. Lệnh nào sau đây chậm hơn và tại sao: LRANGE key 0 99 hay LRANGE key 50000 50099?
5. LMOVE giúp gì so với BRPOP trong pattern queue? Nó có giải quyết hoàn toàn vấn đề mất message không?

Đáp án gợi ý

1. LPUSH recent:search:{uid} "keyword" rồi LTRIM recent:search:{uid} 0 9. LPUSH để item mới ở head (index 0), LRANGE 0 9 sau đó trả về 10 item mới nhất theo thứ tự newest-first. Dùng RPUSH thì item cũ ở head, đọc LRANGE 0 9 sẽ ra 10 item cũ nhất — không đúng.
2. Nếu hai concurrent writer cùng LPUSH một key, giữa LPUSH và LTRIM của writer A, writer B có thể LPUSH thêm — kết quả sau trim của A có thể bị lệch. Pipeline giảm latency nhưng không atomic: hai lệnh vẫn có thể bị xen giữa bởi lệnh từ client khác. Lua script mới thực sự atomic.
3. Không recover được. BRPOP xoá phần tử ngay khi trả về — consumer crash sau đó là mất job hoàn toàn (at-most-once). Giải pháp: dùng LMOVE để pop sang list processing trước (phần tử vẫn còn trong Redis); hoặc dùng Streams với consumer group + XACK để track job đang xử lý.
4. LRANGE key 50000 50099 chậm hơn nhiều. Redis quicklist phải duyệt từ đầu (hoặc cuối nếu index âm) để tới offset 50.000 — O(S) với S = 50.000 node bỏ qua. LRANGE key 0 99 bắt đầu từ head ngay lập tức.
5. LMOVE di chuyển job atomic sang list processing: nếu consumer crash, job vẫn còn trong processing và recovery process có thể lấy lại. Tuy nhiên application tự phải implement logic recovery (scan processing list, retry job timeout). LMOVE không cung cấp acknowledgment, timeout tracking hay consumer group tích hợp — nên không giải quyết hoàn toàn. Streams giải quyết triệt để hơn.

Bài tiếp theo

Bài 23 chuyển sang Set: unordered collection of unique string, các phép toán tập hợp (SUNION, SINTER, SDIFF), và use case tags, permission, unique members.

Tham khảo

• Redis Docs — List data type
• Redis Docs — LPUSH
• Redis Docs — LRANGE
• Redis Docs — LTRIM
• Redis Docs — BRPOP
• Redis Docs — LMOVE (Redis 6.2+)
• Redis Docs — BLMOVE (Redis 6.2+)
• Redis Docs — List internal encoding (listpack, quicklist)
• Redis Docs — EVAL (Lua scripting)