Một tập 512 số nguyên trong Redis tốn 2,6 byte mỗi số — thêm đúng một phần tử nữa là nhảy lên 48,2 byte, gấp 18,6 lần

Nước ở 99 độ vẫn là chất lỏng; thêm đúng một độ nữa, nó thành hơi và chiếm thể tích gấp hàng nghìn lần. Chi phí không tăng đều — nó nhảy vọt tại một điểm chuyển pha. Cấu trúc dữ liệu của Redis có đúng những điểm chuyển pha như thế: một tập hợp nhỏ được lưu trong một biểu diễn gọn khít, và vượt qua một ngưỡng cụ thể — đôi khi chỉ một phần tử — nó chuyển sang cấu trúc "thật" tốn gấp nhiều lần. Bài này đo bốn kiểu tập hợp và tìm ra ba cái vách đá đó, cái dốc nhất rơi ở đúng một phần tử.

Phần trước đo được phụ trội 64 byte cho mỗi khoá chuỗi. Ta đo bốn kiểu tập hợp.

Gom vào một khoá rẻ hơn hẳn

100 phần tử, mỗi phần tử 20 byte:

Gom lại tiết kiệm 2,3 đến 2,8 lần, vì phụ trội 64 byte mỗi khoá biến mất — chỉ còn một khoá thay vì một trăm. Đây là lý do lời khuyên "dùng Hash thay cho nhiều khoá user:1:name, user:1:email" không phải chuyện phong cách mà là chuyện hoá đơn RAM.

Nhưng có vách đá

Redis lưu tập hợp nhỏ dưới dạng listpack — một mảng byte liền mạch, gọn nhưng tra cứu tuyến tính. Vượt ngưỡng, nó chuyển sang cấu trúc thật.

Dòng cuối là chỗ dốc nhất tôi từng đo trong Redis. Một tập 512 số nguyên dùng mã hoá intset — một mảng số đã sắp xếp, 2,6 byte mỗi số. Thêm đúng một phần tử là nó thành bảng băm và mỗi phần tử tốn 48,2 byte. Một phần tử, gấp 18,6 lần bộ nhớ — đúng cái độ thứ 100 biến nước thành hơi.

Ba ngưỡng mặc định đáng thuộc:

hash-max-listpack-entries   512
set-max-listpack-entries    128
set-max-intset-entries      512
zset-max-listpack-entries   128
list-max-listpack-size      128

Kèm theo ngưỡng độ dài giá trị (*-max-listpack-value, mặc định 64 byte) — vượt cái nào cũng chuyển.

Nâng ngưỡng có đáng không

Nâng được, và với dữ liệu nhiều tập hợp nhỏ thì rất đáng:

redis-cli config set hash-max-listpack-entries 1024

Đổi lại: listpack tra cứu tuyến tính. Với 128 phần tử thì quét tuyến tính vẫn nhanh hơn băm vì dữ liệu liền kề và vừa trong bộ nhớ đệm CPU. Với 5.000 phần tử thì không. Ranh giới thực dụng: nâng lên khoảng 1.000 thường an toàn nếu bạn chủ yếu đọc cả tập (HGETALL, SMEMBERS). Nếu bạn tra từng trường một trong một tập lớn, để nguyên mặc định.

Và đây là chỗ dễ mắc lỗi im lặng: đổi cấu hình không chuyển đổi các khoá đã tồn tại. Chúng giữ mã hoá cũ cho tới khi bị ghi lại. OBJECT ENCODING là cách duy nhất biết chắc.

LINDEX có hình chữ V

List 200.000 phần tử, mã hoá quicklist. Tôi đo LINDEX ở ba vị trí, ba lần:

Chậm nhất ở giữa, không phải ở cuối. Tài liệu ghi LINDEX là O(N), và điều đó đúng nhưng thiếu: quicklist là danh sách hai chiều, nên nó đi từ đầu gần nhất. Chi phí thật là O(min(i, N−i)).

Hệ quả thực dụng: dùng list làm hàng đợi thì hoàn toàn ổn — LPUSH/RPOP luôn chạm vào hai đầu. Dùng list làm mảng truy cập ngẫu nhiên thì sai kiểu dữ liệu, và phần tử ở giữa là chỗ đau nhất. Con số tuyệt đối cũng đáng nhớ: 0,3 µs cho một list 200.000 phần tử. "O(N) chậm" trong Redis vẫn nhanh hơn phần lớn thứ khác — nhưng nhân nó với 10.000 lệnh mỗi giây thì nó thành 3 mili giây CPU, trên một luồng duy nhất mà mọi khách hàng khác đang chờ.

Chọn kiểu nào

Sorted Set là kiểu mạnh nhất và đắt nhất — nó giữ cả bảng băm lẫn danh sách bỏ qua. Dùng nó khi thật sự cần thứ tự; nếu chỉ cần kiểm tra thành viên thì Set rẻ hơn. Và với Set toàn số nguyên dưới 512 phần tử, intset là cấu trúc rẻ nhất trong toàn bộ Redis — 2,6 byte mỗi phần tử. Nếu id của bạn là số, hãy lưu chúng dưới dạng số.

Mẫu số chung: chọn cấu trúc theo thao tác chủ đạo, và độ phức tạp giấu cả hằng số lẫn hướng đi

Bài này gói hai quy luật chung của mọi cấu trúc dữ liệu. Thứ nhất: chọn kiểu theo thao tác bạn làm nhiều nhất, và một cấu trúc mang khả năng bạn không dùng là phụ trội thuần — Sorted Set giữ cả chỉ mục thứ tự, nếu bạn chỉ hỏi "có thuộc tập không" thì bạn đang trả tiền cho thứ tự mình không cần. Thứ hai: big-O giấu cả hằng số lẫn hướng đi — LINDEX "O(N)" thực ra là O(min(i, N−i)), chậm nhất ở giữa chứ không ở cuối, điều mà chỉ đo mới thấy.

Trong thế giới Java, đây đúng là chọn giữa ArrayList (truy cập ngẫu nhiên O(1), chèn giữa đắt) và LinkedList (get(i) cũng đi từ đầu gần hơn, đúng hình chữ V), giữa HashSet (chỉ thành viên) và TreeMap (thành viên và thứ tự, đắt hơn) — dùng TreeMap khi chỉ cần HashSet là trả phụ trội cây cân bằng vô ích. Trong Go, đây là map cho thành viên so với slice đã sắp cho khoảng, và container/list cho hai đầu. Còn ở cơ sở dữ liệu, đây là chọn chỉ mục theo truy vấn chủ đạo: một B-tree index phục vụ cả tra điểm lẫn khoảng nhưng đắt hơn hash index chỉ tra điểm — thừa khả năng là thừa chi phí ghi và bộ nhớ.

Mẫu số chung: cấu trúc rẻ nhất là cấu trúc hẹp nhất trả lời đúng thao tác bạn làm nhiều nhất — mang thêm khả năng (thứ tự, chỉ mục, truy cập ngẫu nhiên) mà không dùng là phụ trội thuần; và đừng đọc big-O rồi tin, hãy đo, vì nó giấu hằng số và giấu chuyện worst-case nằm ở đâu. Câu hỏi đúng khi chọn kiểu không phải "cái nào làm được nhiều thứ nhất" mà là "thao tác tôi gọi mười nghìn lần mỗi giây là gì, và kiểu nào phục vụ đúng nó mà không gánh gì thừa". Với Redis, id số thì để intset, chỉ-thành-viên thì Set, cần thứ tự mới Sorted Set.

Muốn tự tìm khoá nào vừa vượt ngưỡng mã hoá — tức là khoá vừa đắt lên gấp đôi mà không ai biết:

redis-cli --scan --count 500 | head -2000 | while read k; do
  t=$(redis-cli type "$k")
  e=$(redis-cli object encoding "$k")
  case "$e" in
    hashtable|skiplist|quicklist)
      n=$(case "$t" in
            hash) redis-cli hlen "$k";;
            set) redis-cli scard "$k";;
            zset) redis-cli zcard "$k";;
            list) redis-cli llen "$k";;
          esac)
      [ "${n:-0}" -lt 2000 ] && echo "$n phan tu  $e  $k"
      ;;
  esac
done | sort -n | head -20

Khoá nào dùng mã hoá "lớn" mà chỉ có vài trăm phần tử là ứng viên tốt để nâng ngưỡng — nó đang trả giá của cấu trúc lớn mà không dùng tới lợi ích.

Phần sau: TTL và chính sách đuổi khoá — đo xem Redis xoá khoá hết hạn lúc nào, và cái gì xảy ra khi đầy bộ nhớ.