List và Array — hàng đợi, N mới nhất, ring buffer, và kiểu Array mới của Redis 8.8

List là kiểu đầu tiên làm nên tên tuổi Redis: LPUSH + LTRIM cho "N lượt xem gần nhất", BRPOP cho hàng đợi việc — Laravel queue, Resque, Sidekiq đều đứng trên list. Redis 8.8 thêm một kiểu dãy thứ hai: Array — truy cập theo index như mảng, thưa, có sẵn ring buffer, tìm kiếm và cộng dồn ngay trên server. Bài này đặt hai kiểu cạnh nhau: list là deque (thêm/lấy nhanh ở hai đầu), array là bảng theo số thứ tự. Ví dụ: hàng đợi gửi email hoá đơn, feed hoạt động, log API gần nhất (e-commerce); số học viên online theo từng phút (LMS). Nền tảng ở bài 1.

Thuật ngữ dùng trong bài
deque (hàng đợi hai đầu: thêm/lấy ở đầu và cuối đều nhanh) · quicklist (danh sách liên kết hai chiều, mỗi node là một listpack ~8 KB) · LZF (thuật toán nén nhanh Redis dùng cho node list) · blocking pop (BLPOP, BLMOVE: chờ tới khi có phần tử) · at-most-once / at-least-once (việc chạy tối đa một lần — có thể mất / ít nhất một lần — có thể trùng) · visibility timeout / retry_after (job đã lấy mà quá hạn chưa xong thì giao lại cho worker khác) · reaper (tiến trình dọn job kẹt) · idempotent (chạy nhiều lần cho cùng kết quả như một lần) · ring buffer (vòng đệm cố định N ô, ghi đè ô cũ nhất) · slice (khúc 4 096 ô liên tiếp của array) · dense / sparse slice (slice lưu dạng mảng liền / dạng danh sách cặp (vị trí, giá trị)) · tagged pointer (ô 8 byte vừa là con trỏ vừa chứa thẳng số nhỏ/chuỗi ≤ 7 byte).

Kiểm chứng: tài liệu Redis qua Context7 ngày 03/10/2026 (LMOVE — mục "Pattern: reliable queue", LTRIM, BLMOVE; trang "Redis arrays", ARRING, ARGREP, AROP, ARSCAN, ARLASTITEMS). Source Redis 8.8.0: t_list.c (listTypeTryConvertQuicklist), sparsearray.h, t_array.c (ARGETRANGE_MAX_ITEMS). Source Laravel 12.64: Queue/RedisQueue.php. Lab chạy thật: Redis 8.8.0, PHP 8.3.33 + phpredis 6.3.0 + Laravel 12.64. Output: labs/redis/out/04*.txt.

Trả lời 30 giây

List là deque: O(1) ở hai đầu, O(N) ở giữa. Dùng cho hàng đợi và "N mới nhất" (LPUSH + LTRIM: 1 triệu lần ghi vẫn 1 KB). Hàng đợi LPOP/BRPOP là at-most-once: worker chết là job mất không dấu vết. BLMOVE sang list "processing" giữ được job nhưng list không biết job bị lấy lúc nào — nên Laravel dùng zset :reserved với score = hạn retry_after; quá hạn thì giao lại, kể cả khi worker cũ vẫn đang chạy (lab: cùng job, attempts 1 rồi 2) → job phải idempotent. Lệnh giữa list (LINSERT, LPOS, LREM) tốn 9–293 ms ở 1 triệu phần tử. Array (8.8, đang preview) truy cập theo index O(1), có ARRING (ring buffer nhanh gấp 3 lần LPUSH+LTRIM), ARGREP, AROP. Bẫy lớn: "thưa" không có nghĩa là rẻ — 100 000 phần tử rải ngẫu nhiên tốn 47 tới 11 558 byte/phần tử tuỳ dải index (zset chỉ 85).

1. Bài toán gốc và bối cảnh ra đời

List tối ưu cho: thêm/lấy ở hai đầu, chặn chờ phần tử mới, giữ thứ tự chèn, RAM gọn (10 byte/phần tử nhỏ). Không tối ưu cho: truy cập/sửa/tìm ở giữa, hàng đợi cần ack/giao lại/nhiều nhóm consumer (stream — bài 6), lưu lâu. Array tối ưu cho: đọc/ghi theo index, dãy có lỗ vừa phải, vòng đệm. Không tối ưu cho: index rải rác trên miền rất rộng (mục 3.6), hệ thống cần chạy trên Valkey/Redis cũ/Redis Cloud (array chưa hỗ trợ).

2. Mô hình tư duy cốt lõi

1. List là deque, không phải mảng. Mọi thao tác ở hai đầu là O(1); thao tác theo vị trí ở giữa là "đi bộ" từ đầu gần nhất. Hệ quả: hợp làm queue, stack, feed có trần; không hợp làm "mảng có index" hay tập để tìm kiếm.
2. Lấy phần tử khỏi list là xoá nó khỏi Redis. Muốn không mất việc khi worker chết phải chuyển nó sang chỗ khác (list processing, zset reserved) — và từ đó phải có người dọn, có hạn, có giao lại → luôn là at-least-once.
3. Array là bảng index → giá trị, chia thành slice 4 096 ô. Truy cập theo index O(1), không cấp phát cho khoảng trống giữa các slice. Hệ quả: RAM phụ thuộc vào có bao nhiêu slice bị chạm và mỗi slice đặc hay thưa, không chỉ vào số phần tử.

3. Internals và quyết định thiết kế

3.1 List làm hàng đợi: lấy ra là mất, chuyển đi thì phải dọn

### A. LPOP/BRPOP: lấy ra là xoá khỏi Redis                                   (04a-queue.txt)
worker 1: LPOP q → j1 … rồi process bị kill trước khi xử lý xong
còn lại: LRANGE q = [j2,j3] — j1 không còn ở đâu trong Redis

### B. LMOVE/BLMOVE sang list 'processing': job vẫn nằm trong Redis khi worker chết
worker 1: LMOVE q processing LEFT RIGHT → j1 … rồi bị kill
q = [j2,j3], processing = [j1]
reaper: job nào trong processing đã quá hạn? — list không lưu thời điểm lấy → không biết, chỉ biết 'đang có'
reaper đưa lại: LMOVE processing q RIGHT LEFT → j1; q = [j1,j2,j3]
worker 1 xong muộn: LREM processing 1 j1 → 0 (đã bị reaper lấy đi, không còn để xoá)

Mẫu "reliable queue" trong docs LMOVE chỉ nói "một client khác theo dõi list processing". Lab cho thấy chỗ hở: list không có thời điểm, nên reaper không phân biệt "worker chết" với "worker đang chạy job dài". Mọi hệ thống thật đều phải thêm hạn ở đâu đó — Laravel chọn zset.

3.2 Laravel Redis queue: list + zset + Lua

### retry_after = 2 giây; worker A lấy job rồi "chậm", worker B lấy sau 3 giây          (04f-laravel-queue.txt)
1. push 1 job
    lab:queues:default           list  [{id:job-1, attempts:0}]
    lab:queues:default:notify    list  [1]
    lab:queues:default:reserved  none
2. worker A pop → job job-1, attempts=1, giờ = 1791010017
    lab:queues:default           none
    lab:queues:default:reserved  zset  {id:job-1, attempts:1} score=1791010019        ← score = giờ lấy + retry_after
3. 3 giây sau (quá retry_after=2), worker B pop → job job-1, attempts=2  ← cùng job, A vẫn đang chạy
    lab:queues:default:reserved  zset  {id:job-1, attempts:2} score=1791010022
4. A xong muộn, delete() → ZREM bản reserved của A (đã bị migrate đi) → không xoá được gì
    lab:queues:default:reserved  zset  {id:job-1, attempts:2} score=1791010022
5. B xong, delete()
    lab:queues:default:reserved  none

Đọc RedisQueue.php: push là Lua RPUSH queues:X payload + RPUSH queues:X:notify 1; pop trước hết chạy migrate (chuyển job hết hạn từ :delayed và :reserved về list), rồi một Lua LPOP + tăng attempts + ZADD :reserved với score = giờ + retry_after. Worker chặn chờ bằng BLPOP trên list :notify (dòng 371) chứ không trên list job — vì không thể chặn chờ bên trong Lua. Thiết kế này đúng với at-least-once, và mang theo đúng bẫy của bản database driver đã phân tích ở bài scale-out queue worker: job chạy lâu hơn retry_after thì chạy 2 lần cùng lúc, và delete() của lần đầu im lặng không xoá gì.

3.3 Nhiều worker cùng chờ: ai chờ trước được trước

### 3 worker BLPOP cùng list rỗng, vào chờ lần lượt w1 → w2 → w3; rồi RPUSH 3 job      (04b-fifo.txt)
đang chờ: name=w1 name=w2 name=w3 | blocked_clients=3
w1 nhận: jobs job-A
w2 nhận: jobs job-B
w3 nhận: jobs job-C

Redis giữ danh sách client đang chặn theo thứ tự vào chờ, mỗi phần tử chỉ giao cho đúng một client. Không có cân bằng theo tải hay theo năng lực worker — worker nhanh quay lại chờ trước nên tự nhiên lấy nhiều hơn. Một client đang BLPOP … 0 (chờ vô hạn) trên kết nối đã chết ngầm (NAT/firewall cắt) thì không bao giờ nhận gì (suy ra, chưa đo) — đặt timeout và TCP keepalive.

3.4 "N mới nhất": LPUSH + LTRIM

### 1 000 000 lần (LPUSH feed x; LTRIM feed 0 99) — RAM giữ nguyên                      (04c-capped.txt)
LLEN feed = 100, MEMORY USAGE = 1031, 3 phần tử đầu = ev999999,ev999998,ev999997
LPUSH: 14 µs | LTRIM bỏ 1 phần tử: 11 µs | LRANGE feed 0 9: 9 µs
### quên LTRIM 1 ngày: list 1 triệu phần tử, LTRIM 0 99 xoá 999 900 phần tử một lần
LTRIM feed 0 99 → 741 µs

LTRIM là O(số phần tử bị bỏ), nhưng quicklist giải phóng nguyên node nên bỏ cả triệu phần tử nhỏ chỉ 0,7 ms. Hai lệnh nên gửi chung một pipeline/MULTI; quên LTRIM ở một nhánh code là list phình vô hạn.

3.5 Lệnh ở giữa list: O(N) đắt hay rẻ tuỳ cỡ phần tử

### list 1 000 000 phần tử: 8 byte/phần tử vs 512 byte/phần tử                         (04d-ops.txt)
                                     8 byte     512 byte
MEMORY USAGE                       10057600    513937572
LINDEX giữa (500 000), µs             16          235
LSET giữa, µs                         21          300
LINSERT trước phần tử giữa, µs      9186        30950      ← phải TÌM pivot theo giá trị từ đầu list
LPOS tìm phần tử cuối, µs          24459       292507
LREM (quét hết), µs                16350        71673
LRANGE 0 99, µs                       38           68

### 200 000 phần tử JSON ~115 byte (các phần tử giống nhau nhiều → nén tốt)             (04e-compress.txt)
list-compress-depth 0: MEMORY USAGE=25361856  LINDEX giữa=21   µs LRANGE 1000 phần tử giữa=595   µs LPUSH=19µs
list-compress-depth 1: MEMORY USAGE=2476869   LINDEX giữa=760  µs LRANGE 1000 phần tử giữa=359   µs LPUSH=13µs

3.6 Array (8.8): slice, tagged pointer, và RAM phụ thuộc cách rải index

Theo sparsearray.h: array là một thư mục trỏ tới các slice 4 096 ô (array-slice-size); index rất xa thì thêm một tầng super-directory gồm các khối 2 048 con trỏ (16 KB mỗi khối). Mỗi slice ở một trong hai dạng: sparse — mảng cặp (vị trí, giá trị) đã sắp xếp, khi ít phần tử; dense — mảng liền, khi nhiều hơn array-sparse-kmax (10). Mỗi ô 8 byte là tagged pointer: số nguyên 62 bit, số thực, hoặc chuỗi ≤ 7 byte nằm thẳng trong ô; chuỗi dài hơn mới cấp phát riêng. Đánh đổi: truy cập O(1) và không tốn RAM cho khoảng trống giữa các slice — nhưng mỗi slice/khối thư mục bị chạm vẫn tốn phí cố định.

### cơ bản                                                                         (04g-array.txt)
ARSET a 0 x; ARSET a 1000000 y → ARLEN=1000001 ARCOUNT=2 MEMORY USAGE=2312
ARGET a 5 (ô trống) → (nil)
ARSET b 18446744073709551614 z (index lớn nhất) → 1; ARLEN=18446744073709551615; MEMORY USAGE=16664
ARSET b 18446744073709551615 z → ERR invalid array index
ARGETRANGE a 0 1000000 (1 000 001 ô) → ERR range exceeds maximum of 1000000 items
ARINSERT log e1/e2 → 0 1; ARNEXT=2; ARDEL log 1 → 1; ARINSERT e3 → 2 (không lấp ô vừa xoá); ARLEN=3 ARCOUNT=2

### RAM: 100 000 giá trị (số nhỏ) ở index ngẫu nhiên trong 0…2^B
array 0…2^20: ARCOUNT=95406  MEMORY USAGE=10487912     109.9 byte/phần tử | slices=256    dense=256   sparse=0      super-dir-entries=0
array 0…2^24: ARCOUNT=99726  MEMORY USAGE=167723528   1681.8 byte/phần tử | slices=4096   dense=4094  sparse=2      super-dir-entries=2
array 0…2^28: ARCOUNT=99983  MEMORY USAGE=4658360       46.6 byte/phần tử | slices=51144  dense=0     sparse=51144  super-dir-entries=32
array 0…2^32: ARCOUNT=99999  MEMORY USAGE=16033480     160.3 byte/phần tử | slices=95406  dense=0     sparse=95406  super-dir-entries=512
array 0…2^36: ARCOUNT=100000 MEMORY USAGE=142392520   1423.9 byte/phần tử | slices=99726  dense=0     sparse=99726  super-dir-entries=8192
(chạy riêng 1 lần với 0…2^40: MEMORY USAGE=1155763480, 11557.6 byte/phần tử, used_memory 1.10G)
zset (score = index):  MEMORY USAGE=8553200       85.5 byte/phần tử (không phụ thuộc độ rộng index)
hash (field = index):  MEMORY USAGE=5962046       59.6 byte/phần tử
### cùng 100 000 giá trị nhưng index liền nhau 0…99 999
dn  sliced-array  MEMORY USAGE=1003880   10.0 byte/phần tử

3.7 Ring buffer: ARRING so với LPUSH + LTRIM

### 1 000 000 lần ghi, chỉ giữ 1 000 mới nhất                                         (04h-ring.txt)
ARRING ring 1000 x:      1801 ms cho 1 000 000 lệnh | ARCOUNT=1000 ARLEN=1000 MEMORY USAGE=26352 | 1 lệnh: 13 µs
LPUSH + LTRIM (2 lệnh): 5794 ms cho 1 000 000 lượt | LLEN=1000 MEMORY USAGE=10166
3 mới nhất: ARLASTITEMS ring 3 REV → evX,ev999999,ev999998 | LRANGE lst 0 2 → ev999999,ev999998,ev999997
ARGET ring 0 → evX   (index trong ring = số thứ tự % 1000, không phải 'mới nhất')
ARRING ring 10 y (thu nhỏ vòng) → 0; ARCOUNT=10   (truncate về 10)

3.8 Tìm và cộng ngay trên server: ARGREP, AROP

### index = phút trong ngày (0…1439): số học viên online mỗi phút                      (04g-array.txt)
MEMORY USAGE=20608 | AROP 480 1019 MAX (8h–17h) = 1199 | AROP 0 1439 SUM = 1042938 | ARGET 600 (10:00) = 944
AROP SUM trên 1440 ô: 23 µs

### ring log 10 000 dòng API gần nhất, 1% có 'error'                                  (04i-grep.txt)
ARGREP log:api - + MATCH error → 77 dòng, 1005 µs
ARGREP … RE '_[0-9]{3}ms$' (chậm ≥ 100ms) LIMIT 3 WITHVALUES → 0 info:GET_/api/lesson/0_175ms 2 info:GET_/api/lesson/2_168ms 3 info:GET_/api/lesson/3_165ms
AROP SUM trên 10 dòng log (không phải số) → (nil) | ARMSET mix 10, abc, 5 → AROP SUM = "15" (bỏ qua ô không phải số, không báo lỗi)

Index = phút trong ngày là chỗ array tự nhiên nhất: 1 440 ô liền nhau, 14 byte/ô, AROP lấy đỉnh/tổng trong 23 µs. ARGREP quét có điều kiện (chuỗi, glob, regex) ngay trên server — 1 ms cho 10 000 dòng; nhớ nó là O(số ô quét), chạy trên luồng duy nhất. AROP SUM bỏ qua ô không phải số mà không báo lỗi — dữ liệu bẩn cho ra tổng sai im lặng.

4. Đảm bảo và giới hạn

Khung lý thuyết: hàng đợi trên list là bài toán "giao việc qua kênh không tin cậy" — không thể vừa không mất vừa không trùng nếu worker có thể chết sau khi làm xong và trước khi xác nhận (hai vị tướng). Chọn at-least-once + idempotent consumer là lời giải chuẩn; retry_after là ước lượng "chết hay chậm" — đặt nhỏ thì trùng, đặt lớn thì job của worker chết chờ lâu.

5. Failure modes

6. Vận hành trong production

• Metric: độ dài queue (LLEN queues:X), số job reserved (ZCARD queues:X:reserved) và job delayed — báo động khi tăng đều; blocked_clients (số worker đang chờ — tụt về 0 là worker chết hết); INFO keysizes → lists_items; với array: ARINFO … FULL cho key lớn.
• Cấu hình: list-max-listpack-size -2 (node 8 KB), list-compress-depth 0 mặc định; array-slice-size 4096, array-sparse-kmin/kmax 5/10 — giữ mặc định nếu chưa đo.
• Laravel: retry_after đặt theo connection; job dài thì tách connection/queue riêng có retry_after lớn; block_for để worker chặn chờ trên :notify thay vì poll; Horizon/queue:monitor theo dõi độ dài queue.
• Capacity — ví dụ minh hoạ: queue email hoá đơn cao điểm 50 000 job × payload ~1 KB → ~50 MB nếu worker dừng 1 giờ; với noeviction Redis đầy RAM thì đẩy job lỗi OOM — app phải chịu được lỗi khi push.
• Debug lúc 3 giờ sáng: "email gửi 2 lần" → so thời gian chạy job với retry_after; "job biến mất" → tìm chỗ dùng LPOP/BRPOP trần; "Redis chậm" → SLOWLOG tìm LREM/LPOS/LINSERT.

7. So sánh và ma trận quyết định

Dùng list khi: queue đơn giản chấp nhận mất/trùng có kiểm soát, feed/log có trần, stack. Tránh khi: cần ack/đọc lại/nhiều nhóm consumer (stream), cần truy cập giữa. Dùng array khi: chạy Redis ≥ 8.8 tự quản, index liền nhau, cần ring buffer/tìm/cộng trên server. Tránh khi: cần Valkey/Redis Cloud, index rải rộng, dữ liệu quan trọng mà tính năng còn preview.

8. Góc nhìn tech lead: tác động tổ chức

• Queue là hợp đồng giao việc: ghi rõ trong ADR "at-least-once, job phải idempotent, retry_after = X vì job dài nhất là Y". Mọi job mới phải qua checklist idempotency trước khi merge.
• Đừng chạy queue quan trọng chung instance với cache: cache cần allkeys-lru, queue cần noeviction — chung một instance thì một trong hai bị sai (bài Redis — những thứ cần biết, bẫy 5).
• Array là tính năng preview: chưa có trên Redis Cloud/Software, Valkey, bản cũ; client library (phpredis 6.3) chưa có method → phải executeRaw (nhớ prefix — bài 2). Chỉ nên dùng cho dữ liệu dựng lại được và đặt sau adapter, có đường lui sang zset/list.
• Exit strategy cho queue: giữ payload job độc lập với Redis (JSON thuần, không phụ thuộc cấu trúc list/zset) để chuyển sang SQS/RabbitMQ chỉ bằng đổi driver.
• Onboarding: người mới cần hiểu "pop là xoá" và "quá retry_after là giao lại" trước khi viết job.

9. Anti-patterns và bài học thực tế

1. Queue quan trọng bằng BRPOP trần: deploy (kill worker) giữa lúc xử lý là mất job.
2. retry_after mặc định 90 giây cho job chạy 5 phút: job chạy song song nhiều bản, gửi email trùng.
3. List làm "mảng" hoặc "tập": LREM/LPOS trên list lớn để xoá/tìm phần tử — 16–293 ms mỗi lần.
4. Feed không trần: list "hoạt động của user" lớn dần theo năm tháng.
5. Array với index là timestamp mili-giây: rải trên miền 2⁴⁰ → 11 KB mỗi phần tử.

Bài học công khai: GitHub giới thiệu Resque (2009) đặt job trên list; Sidekiq sau đó tách "reliable fetch" thành tính năng riêng (Sidekiq Pro super_fetch) chính vì BRPOP mất job khi process chết — nguồn: wiki Sidekiq "Reliability", chưa đối chiếu nguyên văn. Docs Redis LMOVE có sẵn mẫu reliable queue.

Điều docs không nói rõ: list processing không biết job bị lấy lúc nào (nên ai cũng phải thêm zset/hạn); Laravel chặn chờ trên :notify; nén list làm đọc giữa chậm hàng chục lần; RAM của array thưa phụ thuộc mật độ trên slice.

10. Câu hỏi phụ interviewer hay hỏi tiếp

Làm queue tin cậy trên Redis list thế nào?

BLMOVE sang danh sách đang xử lý + lưu thời điểm lấy (zset) + reaper giao lại khi quá hạn + LREM/ZREM khi xong. Kết quả là at-least-once → job idempotent. Hoặc dùng stream (PEL có sẵn).

Laravel Redis queue dùng những kiểu nào?

List queues:X (job chờ), zset :delayed (score = giờ chạy), zset :reserved (score = hạn retry_after), list :notify (để BLPOP), tất cả thao tác qua Lua cho nguyên tử.

Vì sao job chạy hai lần?

Chạy lâu hơn retry_after (hoặc worker treo) → migrate đưa về queue → worker khác lấy. Lab: cùng job-1, attempts 1 rồi 2.

LINDEX là O(N) — có chậm không?

Nhảy theo node nên phần tử nhỏ khá nhanh (16 µs ở 1 triệu); phần tử lớn hoặc list nén thì chậm (235–760 µs). Lệnh tìm theo giá trị mới thật sự đắt (9–293 ms).

Lấy N phần tử mới nhất?

LPUSH + LTRIM 0 N-1 trong một MULTI, đọc LRANGE 0 N-1. Redis 8.8: ARRING key N value + ARLASTITEMS.

Array của Redis 8.8 khác list thế nào? Khi nào không dùng?

Truy cập theo index O(1), thưa, có ring buffer/tìm/cộng trên server. Không dùng khi index rải rác rộng (RAM có thể gấp 135 lần zset), khi cần chạy trên Valkey/Redis Cloud, hoặc cho dữ liệu khó dựng lại khi tính năng còn preview.

Nhiều worker cùng chờ thì ai nhận?

Ai chờ trước nhận trước (FIFO), mỗi phần tử một client. Không cân bằng theo năng lực.

Phụ lục: lab đã chạy

Môi trường: Redis 8.8.0 (redis:alpine), PHP 8.3.33 + phpredis 6.3.0 + Laravel 12.64 (project laravel-livewire mount read-only, REDIS_PREFIX=lab:, retry_after ghi đè = 2 giây trong script). Container tmp-rdt-redis, network tmp-rdt-net.

cd labs/redis
./04-list-array.sh           # chạy hết → out/04a … 04i
./04-list-array.sh laravel   # 1 phần: queue | fifo | capped | ops | compress | laravel | array | ring | grep

Chưa verify: mất/trùng job khi Redis failover; hành vi BLPOP khi mạng bị cắt ngầm (chỉ suy ra); Sidekiq super_fetch (theo tài liệu của Sidekiq); array-sparse-kmax khác mặc định thay đổi bảng RAM thế nào.