Skip list — Probabilistic balanced, dễ implement hơn Red-Black tree

Module 3 lesson 06 đã dạy Red-Black tree: 5 invariant về màu sắc, rotation với parent pointer, fixup cascade 3 case khi insert và 4 case khi delete. Code TreeMap trong OpenJDK có hơn 300 dòng chỉ riêng phần rebalance. Invariant phức tạp đến mức một lỗi nhỏ trong rotation có thể corrupt cả cây mà không crash ngay — chỉ trả kết quả sai.

Skip list (William Pugh, 1990) đạt O(log n) expected cho search/insert/delete với code chỉ khoảng 50 dòng — không một invariant rotation nào. Redis ZSET, LevelDB MemTable, Java ConcurrentSkipListMap đều dùng. Bài này dạy skip list cấu trúc + probabilistic analysis + Java code, so sánh với RB tree, và lý do Redis pick skip list cho ZSET.

1. Analogy — Đường tàu nhiều tuyến

Hình dung hệ thống tàu hỏa có nhiều tuyến song song từ ga A đến ga Z.

Tàu chậm (level 0): ghé mọi ga — A, B, C, D, E, F, G, H, ..., Z. Tìm ga cần đến phải đi từng ga một — O(n).

Tàu nhanh (level 1): chỉ ghé ga lớn — A, C, E, G, I, ..., Z. Khoảng cách mỗi bước dài gấp đôi tàu chậm.

Tàu siêu tốc (level 2): chỉ ghé thành phố lớn — A, E, I, M, ..., Z. Mỗi bước dài gấp 4 lần tàu chậm.

Đi từ A đến Z: nhảy tàu siêu tốc đến gần Z, chuyển sang tàu nhanh, cuối cùng tàu chậm về đúng ga — tổng bước là O(log n) thay vì O(n).

2. Cấu trúc skip list

Skip list là multi-level linked list với cấu trúc phân tầng:

• Level 0: sorted linked list đầy đủ — mọi node đều xuất hiện.
• Level 1: khoảng 1/2 node của level 0 — sample ngẫu nhiên.
• Level 2: khoảng 1/2 node của level 1 = ~1/4 toàn bộ.
• Tiếp tục cho đến MAX_LEVEL.

Mỗi node có forward[] array — forward[i] trỏ đến node kế tiếp ở level i. Node header (sentinel) xuất hiện ở mọi level, là điểm bắt đầu của mọi search.

ASCII diagram -- 3-level skip list, 8 node (values 1..8):

Level 2: header ---------------------------> [5] ---------------------> null
Level 1: header ------------> [3] --------> [5] --------> [7] -------> null
Level 0: header -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> null

Node 5 xuất hiện ở cả 3 level — level cao nhất của nó là 2. Node 1, 2, 4, 6, 8 chỉ xuất hiện ở level 0. Node 3, 7 xuất hiện ở level 0 và 1.

// Node structure for skip list
class Node {
    int key;
    Integer value;
    Node[] forward;  // forward[i] = next node at level i

    Node(int key, Integer value, int level) {
        this.key = key;
        this.value = value;
        this.forward = new Node[level + 1];
    }
}

3. Search algorithm

Search đi từ top level xuống, tiến forward khi key tiếp theo nhỏ hơn target:

1. Bat dau top level tu header.
2. Move forward khi forward[level].key < target.
3. Khi forward[level].key >= target hoac null -> di xuong level - 1.
4. Lap lai den level 0.
5. Forward 1 buoc nua -> kiem tra key == target.

public Integer search(int key) {
    Node node = header;
    // Start from top level, descend
    for (int i = level; i >= 0; i--) {
        while (node.forward[i] != null && node.forward[i].key < key) {
            node = node.forward[i];
        }
        // node.forward[i].key >= key or null -- drop to lower level
    }
    // Move one step at level 0
    node = node.forward[0];
    return (node != null && node.key == key) ? node.value : null;
}

Trace ví dụ — tìm key 6 trong diagram trên:

Level 2: header -> [5] (5 < 6, move) -> null (stop, drop to level 1)
Level 1: [5] -> [7] (7 >= 6, stop, drop to level 0)
Level 0: [5] -> [6] (6 == 6, found!)

Chỉ 4 bước thay vì 6 bước nếu đi thẳng level 0.

4. Insert với probabilistic level

Insert gồm hai bước: (1) tìm vị trí insert và ghi lại update[] — con trỏ node ngay trước vị trí insert ở mỗi level; (2) chọn random level cho node mới, nối vào list.

private static final double P = 0.5;
private static final int MAX_LEVEL = 32;

// Randomly assign a level: 0 with probability (1-P),
// 1 with probability P*(1-P), 2 with P^2*(1-P), etc.
private int randomLevel() {
    int lvl = 0;
    while (Math.random() < P && lvl < MAX_LEVEL) lvl++;
    return lvl;
}

public void insert(int key, Integer value) {
    // update[i] = last node at level i whose key < key
    Node[] update = new Node[MAX_LEVEL + 1];
    Node node = header;

    for (int i = level; i >= 0; i--) {
        while (node.forward[i] != null && node.forward[i].key < key) {
            node = node.forward[i];
        }
        update[i] = node;
    }

    int lvl = randomLevel();
    if (lvl > level) {
        // New node reaches levels not yet used -- link to header
        for (int i = level + 1; i <= lvl; i++) update[i] = header;
        level = lvl;
    }

    Node newNode = new Node(key, value, lvl);
    for (int i = 0; i <= lvl; i++) {
        newNode.forward[i] = update[i].forward[i];
        update[i].forward[i] = newNode;
    }
}

Key insight: mỗi node nhận level theo geometric distribution với parameter P. Với P = 0.5: xác suất level 0 là 50%, level 1 là 25%, level 2 là 12.5%... Expected level trung bình của mỗi node là 1/(1-P) = 2. Không cần kiểm tra hay maintain invariant nào — randomization tự cân bằng.

5. Probabilistic analysis

Vì sao random level đảm bảo O(log n)?

Số node ở mỗi level (expected):

Level 0: n nodes         (moi node deu o level 0)
Level 1: n * P nodes     (xac suat P = 0.5 => n/2 nodes)
Level 2: n * P^2 nodes   (=> n/4 nodes)
Level k: n * P^k nodes

Số level tối đa có ý nghĩa = log_(1/P)(n). Với P = 0.5 và n = 1,000,000: khoảng 20 level.

Expected số bước mỗi level khi search:

• Tại mỗi level, trung bình cần đi forward 1/P bước trước khi gặp node quá lớn và phải xuống level dưới.
• Số level cần đi qua: log_(1/P)(n).
• Tổng expected steps ≈ (1/P) * log_(1/P)(n) = O(log n).

Với P = 0.5: expected bước ≈ 2 * log₂(n). Với n = 1,000,000: khoảng 40 bước — tương đương RB tree.

6. Skip list vs Red-Black tree

Memory tính cụ thể với n = 1,000,000 node Integer:

• RB tree: mỗi TreeMap.Entry = left + right + parent + color + key ref + value ref ≈ 48 byte → tổng ~48 MB.
• Skip list: mỗi node có trung bình 1/(1-P) = 2 forward pointer (P=0.5) + key + value ref ≈ 48 byte → tổng ~48 MB baseline, nhưng các node level cao có nhiều pointer hơn → thực tế ~60-80 MB.

7. Vì sao Redis ZSET chọn skip list

Redis Sorted Set (ZSET) dùng skip list thay vì RB tree. Salvatore Sanfilippo (tác giả Redis) đã giải thích quyết định này:

Score range query rất phổ biến. ZRANGEBYSCORE min max là operation thường gặp nhất trên ZSET. Với skip list, sau khi tìm được node đầu tiên trong range, chỉ cần đi forward trên level 0 — native scan, O(k) với k là số phần tử trong range. Với RB tree, range scan cần in-order traversal phức tạp hơn.

Concurrent ops dễ hơn. Skip list cho phép lock-free implementation (dùng CAS trên forward pointer). Java ConcurrentSkipListMap là ví dụ thực tế. RB tree rất khó lock-free vì rotation phải update nhiều pointer cùng lúc — thường phải lock toàn bộ subtree.

Code maintainability. Skip list code đơn giản hơn đáng kể. Salvatore ưu tiên simplicity — Redis là project một người maintain trong nhiều năm đầu.

Memory penalty chấp nhận được. Redis là in-memory store — memory overhead của skip list (20-30% so với RB) không phải vấn đề nghiêm trọng khi đã phân bổ toàn bộ data vào RAM.

8. Pitfall tổng hợp

Pitfall 1 — Random source và adversarial input:

Math.random() trong Java đủ tốt cho non-adversary workload. Nhưng nếu attacker biết seed của random source, họ có thể craft input để tất cả node nhận level 0 → cấu trúc degraded thành O(n) linked list.

// VULNERABLE: predictable seed
private int randomLevel() {
    Random rng = new Random(42);  // fixed seed -- attacker can predict
    int lvl = 0;
    while (rng.nextDouble() < P && lvl < MAX_LEVEL) lvl++;
    return lvl;
}

// SAFER: thread-local random with unpredictable seed
private static final ThreadLocalRandom rng = ThreadLocalRandom.current();
private int randomLevel() {
    int lvl = 0;
    while (rng.nextDouble() < P && lvl < MAX_LEVEL) lvl++;
    return lvl;
}

Production skip list nên dùng ThreadLocalRandom (seed từ OS entropy) hoặc SecureRandom cho high-security context.

Pitfall 2 — Memory overhead với dataset lớn:

Với P = 0.5, mỗi node có trung bình 2 forward pointer. Với P = 0.25, trung bình chỉ 1.33 pointer/node — tiết kiệm memory hơn nhưng search cần nhiều bước hơn (expected 4/3 * log₄(n)). Không có giá trị P "đúng" — phải cân bằng giữa memory và speed tùy bài toán.

Memory-bound application (embedded, mobile) cần benchmark P thực tế trước khi chọn.

Pitfall 3 — Không có deterministic worst case bound:

Real-time system và latency-critical application thường cần worst-case guarantee. Skip list expected O(log n) là probability — trong practice với n nhỏ hoặc biased random source, bạn có thể gặp outlier. Hard deadline system (financial trading, control system) nên prefer RB tree với O(log n) guaranteed, không phải expected.

// Wrong choice for latency-sensitive path:
SkipList<Integer, Order> orderBook;  // O(log n) expected, outlier possible

// Safer choice for guaranteed latency:
TreeMap<Integer, Order> orderBook;  // O(log n) guaranteed, no outlier

9. Java standard library — ConcurrentSkipListMap

Java 6 đưa vào java.util.concurrent.ConcurrentSkipListMap — lock-free skip list implement bằng CAS (Compare-And-Swap) trên forward pointer. Đây là SortedMap concurrent-friendly, không có lock contention như Collections.synchronizedMap(new TreeMap<>()).

// High-concurrency ordered cache with range query
ConcurrentSkipListMap<Long, Session> sessionsByExpiry = new ConcurrentSkipListMap<>();

sessionsByExpiry.put(expiresAt, session);           // O(log n) expected, lock-free
sessionsByExpiry.headMap(System.currentTimeMillis()) // O(1) -- view of expired sessions
    .clear();                                         // evict expired -- O(k log n)

OpenJDK source (rút gọn, java.util.concurrent.ConcurrentSkipListMap):

// Node structure in OpenJDK ConcurrentSkipListMap (simplified)
static final class Node<K, V> {
    final K key;
    volatile Object val;   // volatile for visibility
    volatile Node<K, V> next;  // CAS target for lock-free insert
}

val và next đều volatile — update qua CAS thay vì synchronized block. Khi insert, algorithm dùng compareAndSet trên next để link node mới mà không cần lock. Nếu CAS fail (concurrent insert), retry từ đầu — wait-free bounded.

Use case phù hợp: high-concurrency cache cần range query (expire by timestamp, leaderboard by score), thay thế Collections.synchronizedMap(new TreeMap<>()) để tránh global lock.

10. Ứng dụng thực tế

Redis ZSET: skip list + hash table kết hợp. Hash table cho O(1) lookup by member, skip list cho O(log n) by score và range scan. ZRANGEBYSCORE, ZRANK, ZADD đều O(log n). Source: src/t_zset.c trong Redis repo.

LevelDB / RocksDB MemTable: skip list là cấu trúc chính trong RAM trước khi data được flush xuống SSTable (Sorted String Table) trên disk. Write vào MemTable là O(log n) skip list insert. Khi MemTable đầy, compact xuống level 0 SSTable và merge sort.

Apache Ignite: distributed in-memory cache dùng ConcurrentSkipListMap cho concurrent ordered cache với range query — tương tự use case session expiry ở trên nhưng ở scale cluster.

Lucene posting list: một số index structure trong Lucene sử dụng skip pointer (dạng đơn giản hóa của skip list) để acceleration traversal posting list khi merge nhiều term query — giảm cost AND query từ O(n) xuống O(n/k) với k là skip interval.

11. Deep Dive

12. Tóm tắt

• Skip list là multi-level linked list — level 0 đầy đủ, level cao hơn sample ngẫu nhiên ~1/2 node, search O(log n) expected bằng cách bắt đầu top level và đi xuống.
• Probabilistic balance thay deterministic invariant: không cần rotation hay recolor, level mỗi node chọn random với geometric distribution. Expected số level trung bình là 1/(1-P).
• So với RB tree: skip list đơn giản hơn (~50 vs ~300 dòng), concurrent friendly hơn (CAS thay vì lock), range query tự nhiên hơn. Đổi lại: memory cao hơn, worst case O(n) (hiếm), không guaranteed O(log n).
• Redis ZSET chọn skip list vì range query phổ biến (ZRANGEBYSCORE), dễ lock-free, và code đơn giản — memory overhead chấp nhận được trong in-memory store.
• Java ConcurrentSkipListMap là lock-free skip list built-in — dùng khi cần sorted map concurrent-friendly thay Collections.synchronizedMap(new TreeMap<>()).
• Pitfall quan trọng: random source phải unpredictable (dùng ThreadLocalRandom); memory overhead tăng tuyến tính với P; không dùng cho hard latency deadline — RB tree có guarantee tốt hơn.
• LevelDB, RocksDB MemTable dùng skip list làm in-memory buffer trước khi flush xuống SSTable — pattern phổ biến trong LSM-tree architecture.

13. Tự kiểm tra

private int randomLevel() {
  return 5; // always level 5
}
public void insert(int key, Integer value) { ... }

Bài tiếp theo: Mini-challenge: External merge sort