บทที่ 10 — Distributed Data Structures & Algorithms

← บทที่ 9 | สารบัญ | บทที่ 11 →

หลังจบบท คุณจะ:

เข้าใจ probabilistic data structures (Bloom Filter — บลูม-ฟิล-เตอร์, HyperLogLog — ไฮ-เปอร์-ล็อก-ล็อก, Count-Min Sketch — เคาท์-มิน สเก็ตช์)
รู้จัก Merkle Tree (เมอร์-เคิล ทรี — hash tree) + ทำไม blockchain (Bitcoin) / Cassandra (anti-entropy) ใช้
เข้าใจ Consistent Hashing ลึก + Virtual Nodes
เห็นภาพ algorithms ที่อยู่เบื้องหลังเทคโนโลยีที่ใช้กันทั่วโลก

1. ทำไมต้อง "Probabilistic" Data Structures?

ในระบบใหญ่ — บางครั้งเราไม่ต้องการคำตอบ "100% ถูก" — แต่ต้องการคำตอบ "เร็ว + ใช้ memory น้อย"

text

ตัวอย่าง:
- "Email นี้เคยส่งให้คนนี้แล้วยัง?" 
  → 100% ถูก: ตรวจ DB (ช้า)
  → 99.9% ถูก: Bloom Filter (เร็ว 1000x)

- "วันนี้มี unique visitors กี่คน?"
  → 100% ถูก: COUNT(DISTINCT user_id) ใน Postgres (slow + memory เปลือง)
  → 99% ถูก: HyperLogLog (เร็ว + 12 KB memory!)

- "Hashtag นี้มี top 10 ไหม?"
  → 100% ถูก: scan + sort ทั้งหมด (slow)
  → 95% ถูก: Count-Min Sketch (เร็วมาก)

Trade-off: trade accuracy for space + speed

2. Bloom Filter — "เคยเห็น item นี้ไหม?"

ปัญหา

text

Database: 1 พันล้าน records
Query: "key X อยู่ใน DB ไหม?"
Naive: ค้น DB ทุกครั้ง → ช้า + DB load สูง

Idea: Bloom filter เก็บ "เคยเห็นหรือยัง" → ตอบเร็ว
- "ไม่มี" → ตอบทันที (ไม่ต้องไป DB)
- "อาจจะมี" → ค่อยไป DB เช็ค

หลักการทำงาน

text

Bloom Filter = bit array + k hash functions

Insert "Anna":
  h1("Anna") = 5  → set bit 5
  h2("Anna") = 12 → set bit 12
  h3("Anna") = 18 → set bit 18

Bit array: [0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0]
                    ↑               ↑           ↑
                  bit 5           bit 12      bit 18

Query "Anna":
  h1("Anna") = 5  → bit 5 = 1 ✓
  h2("Anna") = 12 → bit 12 = 1 ✓
  h3("Anna") = 18 → bit 18 = 1 ✓
  → "probably present"

Query "Bob":
  h1("Bob") = 7  → bit 7 = 0
  → "definitely not present" (ทันทีที่เห็น 0)

คุณสมบัติ

text

✅ "Definitely not in set" — guaranteed (no false negatives)
⚠️ "Probably in set" — may be false positive

🔑 KEY PROPERTY (จำไว้ให้แม่น): Bloom filter มี false positives ได้ (บอก "อยู่" ทั้งที่ไม่ได้อยู่) — แต่ NO false negatives (ไม่มีทางบอก "ไม่อยู่" ทั้งที่อยู่จริง)
⚠️ COMMON MISTAKE: หลายคนพูดผิดว่า "Bloom filter ไม่มี false positives" — กลับด้านกัน! ที่ถูกคือ ไม่มี false negatives (จะไม่บอกผิดว่า "ไม่อยู่" ตอนที่อยู่จริง) แต่ มี false positives ได้ (อาจบอกผิดว่า "อยู่" ตอนที่ไม่ได้อยู่)

📐 Sizing math (skip ได้ถ้าใช้ library — ทุก library คำนวณให้แล้ว):
False positive rate (p):
text
p ≈ (1 - e^(-kn/m))^k
โดย:
e = ค่าคงที่ของออยเลอร์ (Euler ~2.718) — มาจากคณิตศาสตร์ probability
k = จำนวน hash function ที่ใช้ (เช่น 7)
n = จำนวน item ที่ใส่ลงไป (เช่น 1,000,000)
m = ขนาด bit array (เช่น 9,600,000 bits ≈ 1.2 MB)
Trade-offs:
Bigger m (more bits) → lower false positive
More k (more hashes) → lower false positive (up to a point)
ตัวเลขสำเร็จรูปที่ใช้บ่อย (ไม่ต้องคำนวณเอง):
n (items) p (FP rate) m (memory) k (hashes)
1M 1% 1.2 MB 7
1M 0.1% 1.8 MB 10
10M 1% 12 MB 7
100M 1% 120 MB 7

n (items)	p (FP rate)	m (memory)	k (hashes)
1M	1%	1.2 MB	7
1M	0.1%	1.8 MB	10
10M	1%	12 MB	7
100M	1%	120 MB	7

Sizing — กฎทอง

text

ต้องการ:
- 1M items
- 1% false positive rate

Math:
- Optimal m = -n * ln(p) / (ln(2)²) = ~9.6M bits = 1.2 MB
- Optimal k = (m/n) * ln(2) = ~7 hash functions

เทียบกับ HashSet<String>:
- HashSet: 1M strings × 50 bytes avg = 50 MB
- Bloom: 1.2 MB → save 40x!

การใช้งาน

text

1. Cache: "key มีใน cache ไหม?" — skip DB if not
2. Web crawler: "URL crawled แล้วยัง?"
3. Database (Cassandra, RocksDB): "key อยู่ใน SSTable (เอส-เอส-เทเบิล = Sorted String Table — ไฟล์เรียงลำดับที่ LSM-tree DB ใช้เก็บข้อมูลบน disk) ไหน?"
4. Blockchain (Bitcoin SPV): light wallet sync
5. Spell check: "word เป็น valid English ไหม?"
6. Spam filter: "email นี้เป็น spam ไหม?"

ตัวอย่างโค้ด

typescript

class BloomFilter {
    private bits: Uint8Array;
    private size: number;
    private hashCount: number;
    
    constructor(size: number, hashCount: number) {
        this.size = size;
        this.hashCount = hashCount;
        this.bits = new Uint8Array(Math.ceil(size / 8));
    }
    
    private hash(item: string, seed: number): number {
        // Simple example — production should use MurmurHash3 or similar
        let h = seed;
        for (const c of item) {
            h = (h * 31 + c.charCodeAt(0)) % this.size;
        }
        return h;
    }
    
    add(item: string) {
        for (let i = 0; i < this.hashCount; i++) {
            const pos = this.hash(item, i);
            this.bits[Math.floor(pos / 8)] |= (1 << (pos % 8));
        }
    }
    
    mightContain(item: string): boolean {
        for (let i = 0; i < this.hashCount; i++) {
            const pos = this.hash(item, i);
            if (!(this.bits[Math.floor(pos / 8)] & (1 << (pos % 8)))) {
                return false;  // definitely not
            }
        }
        return true;  // probably yes
    }
}

// Usage
const bloom = new BloomFilter(10_000_000, 7);
bloom.add("anna@example.com");
bloom.mightContain("anna@example.com");  // true
bloom.mightContain("bob@example.com");   // false (very likely)

Variants — รุ่นย่อย

text

- Counting Bloom Filter: support DELETE (uses counters not bits)
- Cuckoo Filter (คุก-คู ฟิล-เตอร์): support DELETE + lower false positive
- Scalable Bloom Filter: auto-resize when full
- Stable Bloom Filter: for streams (auto-decay old items)

3. HyperLogLog (HLL) — ประมาณจำนวน unique items

ปัญหา

text

Twitter / X: "How many unique users tweeted today?"
- Naive: SET of all user IDs → 200M+ DAU × 50 bytes = 10+ GB
- กับใน multiple servers — ส่ง full set ไป merge = ช้ามาก

HyperLogLog (ไฮ-เปอร์-ล็อก-ล็อก): estimate cardinality (คา-ดิ-นาล-ลิ-ตี้ = จำนวน unique = ความหลากหลายของค่า) with ~12 KB!
- Error: ~0.81%
- 99%+ accuracy → enough for analytics

หลักการทำงาน (Intuition)

text

Idea: นับ "leading zeros" (เลข 0 ที่นำหน้า) ของ hash

📖 leading zeros = จำนวนเลข 0 ติดกันที่ต้นของเลขฐาน 2
   ตัวอย่าง: 00010110 → มี 0 นำหน้า 3 ตัว → leading zeros = 3
            00000101 → leading zeros = 5
            10000000 → leading zeros = 0

ถ้า hash(item) = 0b00010110... (3 leading zeros)
→ "rare event" — 1 in 2^3 = 1/8 chance
→ ถ้าเห็น item ที่มี k leading zeros → estimate set size ≈ 2^k

Real algorithm (HLL):
1. Hash item → 64-bit
2. ใช้ first M bits → bucket index (e.g., M=14 → 16384 buckets)
3. Count leading zeros of remaining bits
4. Store max in each bucket
5. Estimate = harmonic mean (ค่าเฉลี่ยฮาร์โมนิก — เฉลี่ยแบบกลับเศษส่วน ทนต่อค่าผิดปกติได้ดีกว่า mean ปกติ) ของ buckets × constant

คุณสมบัติของ HLL

text

Memory: O(log log n) — แต่ละ register ใช้ ~6 bits; รวมแล้วใช้ memory คงที่ ~12 KB
- 1 พันล้าน items → ใช้แค่ 12 KB (เพิ่ม item เท่าไร memory ไม่โต)
- O(log log n) อ่านว่า "บิ๊กโอ ล็อก ล็อก เอ็น" = memory โตช้ามาก ๆ
  (ปกติ log n ก็โตช้าแล้ว; log(log n) ยิ่งช้ากว่านั้นอีก)

Accuracy: ~0.81% error (with 16384 buckets)
- คำนวณจาก: 1.04 / √16384 = 1.04 / 128 ≈ 0.81%

Mergeable: 
- HLL_A + HLL_B = HLL of (A ∪ B)  (รวมแบบ element-wise max)
- → distributed cardinality estimation!

การใช้งานจริง

text

1. Analytics: unique visitors per day/hour/region
2. A/B testing: unique users per experiment
3. SEO: unique URLs crawled
4. Database: ANALYZE table cardinality (Postgres, Redshift use HLL)
5. Network monitoring: unique IPs seen
6. Trending: distinct count for hashtags

Redis HyperLogLog — ตัวอย่างจริง

text

# Add items
PFADD users:2026-05-26 anna bob charlie diana ...

# Count
PFCOUNT users:2026-05-26
→ 9_847_123 (estimated)

# Merge multiple
PFMERGE users:week users:2026-05-26 users:2026-05-27 ...
PFCOUNT users:week
→ 35_000_000 (estimated unique users this week)

→ Each HLL key uses fixed 12 KB regardless of cardinality

💼 Production note: Apache DataSketches ให้ implementation ของ HLL ที่ cross-language compatible — ใช้กันเป็นมาตรฐานใน Hive, Spark, Druid, Apache Pinot (พวก big data stack) สามารถเอา sketch จากระบบหนึ่งไป merge กับอีกระบบได้

4. Count-Min Sketch — หา Heavy hitters / Top-K

ปัญหาที่เจอ

text

"What are the top 10 trending hashtags?"
- 1 billion tweets/day
- Track count per hashtag → memory explode

Count-Min Sketch: approximate count per item, with bounded error
- Memory: O(log n / ε)
- Accurate for "heavy hitters" (high count items)
- May overestimate low-count items

หลักการทำงาน CMS

text

2D array: width W × depth D (small)
D hash functions: h1, h2, ..., hD

Increment count(item):
  for each d in 1..D:
    column = h_d(item) % W
    array[d][column]++

Query count(item):
  return min(array[d][h_d(item)]) over all d
  
"Take minimum across rows" — least overestimated

Trace ตัวอย่าง

📝 Note on indexing: ในตัวอย่างนี้ "row 1" = แถวของ h1 (แถวแรก), "row 2" = แถว h2 — เรานับแถวเริ่มที่ 1 ตามชื่อ hash function (h1, h2, h3) เพื่อให้อ่านง่าย ส่วน column ใช้ 0-indexed (col0, col1, ...)

text

Width = 4, Depth = 3, Hash functions h1, h2, h3

Sketch (initially all 0):
       col0  col1  col2  col3
  h1:   [0]   [0]   [0]   [0]
  h2:   [0]   [0]   [0]   [0]
  h3:   [0]   [0]   [0]   [0]

Insert "trump" → h1=2, h2=0, h3=3:
       col0  col1  col2  col3
  h1:   [0]   [0]   [1]   [0]
  h2:   [1]   [0]   [0]   [0]
  h3:   [0]   [0]   [0]   [1]

Insert "biden" → h1=2, h2=1, h3=0  (collision at row h1, col2!)
       col0  col1  col2  col3
  h1:   [0]   [0]   [2]   [0]  ← +1 (now 2, but "trump" only count 1)
  h2:   [1]   [1]   [0]   [0]
  h3:   [1]   [0]   [0]   [1]

Query count("trump"):
  min(row h1[col2]=2, row h2[col0]=1, row h3[col3]=1) = 1 ✓
  → ตอบถูก เพราะ "min" filter collision

Query count("biden"):
  min(row h1[col2]=2, row h2[col1]=1, row h3[col0]=1) = 1 ✓

การใช้งาน CMS

text

1. Network: top talkers (heavy IP source)
2. Trending: top hashtags, top URLs
3. Anomaly detection: count of events per IP
4. Stream processing: distinct count + frequency
5. Database query optimizer: cardinality estimates

→ ใช้ใน Flink, Spark, ClickHouse, Druid

💡 Top-K variants ที่ memory-efficient กว่า CMS ตรง ๆ:
CMS + heap (Cormode) — CMS เก็บ count + heap เก็บ top-K
Misra-Gries summary — เรียบง่ายมาก ใช้ memory คงที่สำหรับ K elements
SpaceSaving (Metwally) — variant ที่ดีกว่า Misra-Gries สำหรับ heavy hitters
ถ้าโจทย์คือ Top-K โดยเฉพาะ (ไม่ใช่ frequency ของทุก item) → algorithm พวกนี้ประหยัด memory กว่า CMS

5. Merkle Tree — hash tree ตรวจสอบความถูกต้องของข้อมูลใหญ่

ปัญหาที่ Merkle Tree แก้

text

2 servers ต้องตรวจสอบว่า data ตรงกันไหม
- Naive: ส่ง data ทั้งหมด เปรียบเทียบ
- 1 TB → 1 TB transfer (เปลือง)

Merkle Tree: ส่งแค่ root hash → ถ้าตรง = data ตรง
                                  ถ้าไม่ตรง = navigate tree หา block ผิด

โครงสร้าง

text

                          Root Hash
                       /             \
                  Hash(AB)          Hash(CD)
                  /     \           /      \
              Hash(A)  Hash(B)  Hash(C)  Hash(D)
                |        |       |         |
              Block A  Block B  Block C   Block D
              (data)   (data)   (data)    (data)

Each node = hash of children (e.g., SHA-256)
Root = hash of entire tree

Algorithm เปรียบเทียบสองต้น

text

Server X has Merkle tree T_X
Server Y has Merkle tree T_Y

1. Compare root_X vs root_Y
   - Same? → identical, no transfer ✅
   - Different? → drill down

2. Compare children (Hash(AB), Hash(CD))
   - Same hash → that subtree ตรงกัน, skip
   - Different → recurse

3. Continue until find specific block ที่ต่าง
   → ส่งแค่ block นั้น (small)

Cost: O(log n) hash comparisons
       O(1) block transfers (worst case = same as data anyway)

การใช้งาน Merkle Tree

Cassandra Anti-Entropy Repair — ซ่อม replica ที่ไม่ตรงกัน

text

Cassandra periodically:
1. Each node builds Merkle tree of its data
2. Compare with peer's tree
3. Find diff → repair (replicate divergent data)

→ Eventually consistent ตามทฤษฎี

Git — ใช้ Merkle DAG เก็บประวัติ commit

text

Git commit = Merkle tree
- Each file → blob (hashed)
- Each directory → tree (hash of children)
- Each commit → tree + parent commit hash

→ Identical commits have identical hashes
→ Detect tampering: change any byte → root hash เปลี่ยน

Bitcoin / Blockchain — ใช้ Merkle root ใน block

text

Block contains:
- Block header (small)
  - Merkle root of all transactions
- Transactions (large)

Light clients (SPV):
- Don't store full block
- Store block headers only
- Verify a transaction is in block:
  - Get Merkle path from full node
  - Verify hash chain to root
  - Trust if root matches header

IPFS / Distributed Storage — content-addressable storage

text

Files chunked + hashed
Merkle tree of chunks
Address by hash → tamper-evident

ตัวอย่างโค้ด Merkle Tree

typescript

interface MerkleNode {
    hash: string;
    left?: MerkleNode;
    right?: MerkleNode;
    data?: any;  // leaf
}

function hash(s: string): string {
    return sha256(s);  // simplified
}

function buildMerkle(blocks: any[]): MerkleNode {
    if (blocks.length === 1) {
        return { hash: hash(JSON.stringify(blocks[0])), data: blocks[0] };
    }
    
    const mid = Math.floor(blocks.length / 2);
    const left = buildMerkle(blocks.slice(0, mid));
    const right = buildMerkle(blocks.slice(mid));
    
    return {
        hash: hash(left.hash + right.hash),
        left,
        right,
    };
}

function compareTrees(a: MerkleNode, b: MerkleNode, differences: any[] = []) {
    if (a.hash === b.hash) return differences;  // same, skip
    if (a.data && b.data) {
        differences.push({ a: a.data, b: b.data });
        return differences;
    }
    if (a.left && b.left) compareTrees(a.left, b.left, differences);
    if (a.right && b.right) compareTrees(a.right, b.right, differences);
    return differences;
}

6. Consistent Hashing — ลึกกว่า บท 6

ดู บทที่ 6 — DHT + Consistent Hashing สำหรับพื้นฐาน

ในบทนี้ — ลึกในแง่ implementation + variants

ทบทวน

text

Hash ring (0 to 2^32-1)
Each node = position on ring
Each key → walk clockwise to nearest node

ดี: add/remove node = move ~1/N data

Virtual Nodes (vnodes) — ทำไมต้องมี?

text

Without vnodes:
- 3 nodes A, B, C at positions 0, 120°, 240°
- Hash random → keys spread randomly
- บาง node อาจรับ keys เยอะกว่า (variance สูง)

With vnodes (128 per physical node):
- A → A_0, A_1, ..., A_127 (random positions on ring)
- B → B_0, B_1, ..., B_127
- C → C_0, C_1, ..., C_127

Result:
- 384 positions on ring (3 × 128)
- Keys spread evenly across 384 positions
- Each physical node gets ~1/3 of keys
- Variance ลดลงตาม law of large numbers

Jump Consistent Hash — algorithm ของ Google ปี 2014

text

Improvement over traditional consistent hashing:
- No need to store ring positions
- O(log N) computation
- Perfectly uniform distribution

Algorithm (key ต้องเป็น 64-bit unsigned integer):
function jumpHash(key, numBuckets):
    b = -1
    j = 0
    while j < numBuckets:
        b = j
        // 2862933555777941757 = LCG multiplier จาก Google's paper
        key = (key * 2862933555777941757) + 1
        // ">> 33" = bit shift; ต้องการ key 64-bit เพราะใช้บิตบน 31 บิต
        j = floor((b + 1) * (2^31 / ((key >> 33) + 1)))
    return b

ดี:
- O(log N) but very fast constants
- ใช้ใน Discord, Vimeo

ไม่ดี:
- Only supports "increase numBuckets" (no remove arbitrary node)
- จำกัดให้ใช้กับระบบที่ buckets เพิ่ม/ลดได้แค่ที่ปลาย (append-only) เท่านั้น
- ดังนั้น scope แคบกว่า traditional consistent hashing

Rendezvous Hashing (HRW) — Highest Random Weight

text

Highest Random Weight (HRW):

For each key:
  Compute weight(key, node) = hash(key + node_id) for every node
  Pick node with HIGHEST weight

Properties:
- No ring → no vnodes needed
- Even distribution naturally
- Add/remove node → only ~1/N keys move
- Compute: O(N) per key (vs O(log N) for ring)

Used in: Cassandra (alternative to vnodes), some load balancers

เปรียบเทียบสามแบบ

	Ring + vnodes	Jump Hash	Rendezvous
Lookup	O(log N)	O(log N)	O(N)
Memory	O(N × V)	O(0)	O(0)
Add node	move 1/N	only "append"	move 1/N
Remove node	move 1/N	❌ ลำบาก	move 1/N
Even distribution	ดี (with vnodes)	Perfect	Good
Code complexity	กลาง	ง่าย	ง่าย

Variants อื่นที่ใช้จริงใน production (รู้ไว้สำหรับ senior+)

text

- Maglev (Google, 2016) — connection-tracking consistent hash
  → ใช้ใน Google Cloud Load Balancing (GCLB), Envoy
  → เร็วมาก lookup O(1) ผ่าน precomputed lookup table

- Bounded-load consistent hashing (Mirrokni et al., 2018)
  → รับประกันว่าไม่มี node ไหนรับ load เกิน (1+ε) เท่าของค่าเฉลี่ย
  → ใช้ที่ Vimeo, Google
  → แก้ปัญหา "lucky node ได้ key เยอะเกิน" ที่ ring แบบดั้งเดิมมี

7. Skip List — sorted structure ที่ search O(log n)

skip list เป็นโครงสร้างข้อมูลแบบเรียงลำดับที่ค้นหาได้ O(log n) เหมือน balanced tree แต่ใช้ความน่าจะเป็นแทนการ balance ทำให้โค้ดง่ายกว่ามากและทำ concurrent update ได้ดี — Redis sorted set (ZSET) และ RocksDB memtable ใช้มัน ส่วนนี้อธิบายโครงสร้างหลายชั้นและการ search:

ภาพรวม

text

Problem: ordered map with O(log n) operations
- Binary search tree → ดี แต่ต้อง balance (red-black, AVL — complex)
- Skip list: simpler, probabilistic O(log n)

โครงสร้าง Skip List

text

Level 3: [1] ────────────────→ [10] ───────────────────→ [end]
Level 2: [1] ──→ [4] ─────→ [10] ──→ [16] ─────────→ [end]
Level 1: [1] →[3]→[4]→ [7] →[10]→[13]→[16]→ [22] ──→ [end]
Level 0: [1]→[3]→[4]→[7]→[10]→[13]→[16]→[19]→[22]→[31]→[end]

Search 13:
  Level 3: 1 → 10 → end (back to level 2)
  Level 2: 10 → 16 (overshoot, back)
  Level 1: 10 → 13 ✓

การใช้งาน Skip List

text

- Redis sorted sets (ZSET): leaderboard, time-series indexing
- LevelDB / RocksDB: memtable (in-memory sorted structure)
- LucidDB, MemSQL: secondary indexes
- Some kernel structures (Linux scheduler)

ทำไมไม่ใช้ B-tree?
- Concurrent updates ง่ายกว่า (lock-free implementations exist)
- Code simpler
- Cache-friendly (sequential pointer chase)

8. LSM-Tree — โครงสร้างข้อมูลที่ optimize การเขียน

แนวคิด

text

LSM = Log-Structured Merge Tree (ดู glossary บท 11)

B-tree แบบดั้งเดิม (Postgres, MySQL):
- update ในที่ → เกิด random I/O
- อ่านเร็ว แต่เขียนช้ากว่า

LSM-tree:
- เขียนแบบ append-only → sequential I/O (เร็ว!)
- merge เป็นระยะ → คงข้อมูลให้เป็นระเบียบ
- อ่านอาจต้อง scan หลาย "level" (ช้ากว่า)

แลก: เขียนเร็วกว่า แต่อ่านช้ากว่า
ใช้กับ: งานที่เขียนเยอะ (write-heavy)

สถาปัตยกรรม

text

[Write] → MemTable (in-memory, sorted)
              ↓ (when full)
          Flush to L0 SSTable (on disk)
              ↓ (when L0 has N files)
          Compact + merge → L1 SSTable
              ↓
          ... → Ln (largest, oldest)

[Read]:
  Check MemTable → check L0 → check L1 → ... → return first hit
  + use Bloom filters per SSTable to skip

ใช้ที่ไหนบ้าง

text

- LevelDB / RocksDB (Google / Facebook embedded KV)
- Cassandra, ScyllaDB (wide-column DB)
- HBase (BigTable inspired)
- InfluxDB, TimescaleDB (time-series)
- DynamoDB (likely)
- Bitcoin / Ethereum (LevelDB underneath)

Trade-offs ของ LSM

text

✅ Write throughput สูง (sequential)
✅ Compression friendly (large sorted files)
✅ Time-series + log workloads

❌ Read amplification (multiple levels to check)
❌ Write amplification (compaction)
❌ Space amplification (transient old + new data)

→ Tune via compaction strategy + Bloom filters

9. SWIM Protocol — ลึก

ดู บทที่ 9 สำหรับพื้นฐาน

รายละเอียด Algorithm

text

Each node maintains: membership list (alive, suspect, failed)

Failure Detection (every T seconds):
1. Pick random member M
2. Send "ping" → wait T1 for ack
3. If no ack:
   a. Pick K random members (K=3-5)
   b. Ask each: "ping M for me"
   c. If any get response → M alive
   d. If none → mark M as suspect

Suspicion timeout (e.g., 3-5 sec):
- If M still suspect → declare FAILED
- Broadcast via gossip

Recovery:
- ถ้า M ส่ง message มา → mark alive
- Reset suspect / failed status

Gossip Dissemination — กระจายข่าวสาร

text

Information attached to ping/ack:
- "I heard X joined at time T"
- "I heard Y left at time T"

Each node merges info into local state
→ Eventually all nodes know about changes
→ Spread rate: O(log N) rounds for full propagation

การ tuning

text

T (ping interval): 1-2 sec
T1 (ack timeout): 200-500 ms
K (indirect ping count): 3-5
Suspect timeout: 3-5 sec
Failed timeout: 30+ sec (allow rejoin)

Trade:
- Smaller T → faster detection, higher load
- Larger K → fewer false positives, more network

ใช้ที่ไหนบ้าง (SWIM)

text

- Hashicorp Memberlist (Consul, Nomad, Serf)
- Cassandra (gossip + phi accrual)
- Hazelcast
- Akka Cluster

10. ตารางเปรียบเทียบ

เรียนโครงสร้างข้อมูลมาหลายตัว ตารางนี้สรุปเทียบให้เห็นภาพรวมในที่เดียว — แต่ละตัวแลก "ความแม่นยำ" กับ "พื้นที่/ความเร็ว" ต่างกัน (เช่น Bloom/HyperLogLog ยอมพลาดนิดหน่อยเพื่อประหยัด memory มหาศาล) ใช้เลือกเครื่องมือให้ตรงกับโจทย์:

Data Structure	Purpose	Accuracy	Space	Use Case
Bloom Filter	Membership test	False positive	~1.2 MB/1M items	Cache, dedup, crawler
Counting Bloom	Membership + delete	False positive	4x Bloom	Eviction logs
HyperLogLog	Cardinality	~0.8% error	12 KB	Unique visitors
Count-Min Sketch	Frequency	Overestimate	O(log/ε)	Top-K, heavy hitters
Merkle Tree	Integrity + sync	100%	O(n)	Cassandra, Git, blockchain
Skip List	Ordered map	100%	O(n)	Redis ZSET, LevelDB
LSM-Tree	Write-heavy KV	100%	O(n) + overhead	Cassandra, RocksDB
Consistent Hash	Distributed map	100%	O(N×V)	Sharding, LB

11. Algorithm จริงใน Production

ตัวอย่างที่ 1: Twitter Trends

text

Stream of tweets → HyperLogLog (unique users per hashtag)
                 → Count-Min Sketch (count per hashtag)
                 → Heavy Hitters → top 10 trending

Memory: few MB (vs full counts = GB)
Latency: ~1 ms (vs DB scan = sec)

ตัวอย่างที่ 2: Google BigTable / Spanner

text

Storage: LSM-tree (writes)
Index: B-tree on top
Bloom filters: per SSTable → fast "not present" check
Merkle trees: anti-entropy across replicas

ตัวอย่างที่ 3: Cassandra Read Path

text

1. Bloom filter: in this SSTable?
   - No → skip (fast!)
2. Partition summary: which page?
3. Compression offset: which block?
4. Read block + decompress
5. Find row in block

→ Bloom filters reduce I/O significantly

ตัวอย่างที่ 4: Discord Voice Servers

text

1B users → which server has their state?

Old: DB lookup per request (slow)
New: Rendezvous hashing
- Compute weight for every server
- Pick highest
- O(N) but fast (small N)

12. ลึกขึ้น — Probabilistic Counting

Linear Counting — counting แบบเชิงเส้น (เก่า)

text

Simpler than HLL:
- Bit array of size m
- Insert: hash(item) % m → set bit
- Count = m * ln(m / unset_bits)

Less accurate than HLL but smaller code

LogLog → SuperLogLog → HyperLogLog — วิวัฒนาการของ algorithm

text

LogLog (1996): basic, ~5% error
SuperLogLog (2003): better averaging
HyperLogLog (2007): harmonic mean → ~0.8% error
HLL++ (Google, 2013): bias correction + sparse representation

→ Current state-of-the-art: HLL++ (Google's improvement)

13. เมื่อไหร่ที่ "ไม่ควร" ใช้ probabilistic

โครงสร้างแบบ probabilistic (Bloom, HLL, CMS) ทรงพลังแต่ไม่ใช่คำตอบทุกเคส — มันแลกความแม่นยำกับพื้นที่ ดังนั้นถ้าต้องการตัวเลขเป๊ะ (การเงิน, audit) หรือ dataset เล็ก ก็ไม่ควรใช้ ส่วนนี้สรุปเส้นแบ่งว่าเมื่อไหร่ควรและไม่ควร:

text

❌ Don't use when:
- Need exact counts (financial, audit)
- Small dataset (just store full)
- One-time query (overhead not worth)
- High precision needed for decision

✅ Use when:
- Scale (millions+ items)
- Approximate is OK
- Stream processing
- Memory-constrained
- Need merge (distributed aggregation)

14. Checkpoint — แบบฝึกหัด

ลงมือ implement โครงสร้างเหล่านี้เองเพื่อให้เข้าใจจริง — แบบฝึกหัดนี้ให้คุณสร้าง Bloom filter, ลอง HyperLogLog บน Redis, สร้าง Merkle tree, consistent hashing และ Count-Min Sketch ทำแล้วจะเห็นกับตาว่า "ยอมพลาดนิดหน่อยเพื่อประหยัด memory" คุ้มแค่ไหน:

🛠️ Checkpoint 10.1 — Bloom Filter Lab

implement Bloom filter ในภาษาของคุณ
ใส่ string สุ่ม 1M ตัว
ทดสอบ query + วัด false positive rate
เทียบ memory กับ HashSet

🛠️ Checkpoint 10.2 — HyperLogLog กับ Redis

ใช้ Redis PFADD / PFCOUNT
เพิ่ม 1M item → เช็ค PFCOUNT
เทียบกับจำนวน unique จริง
วัด error %

🛠️ Checkpoint 10.3 — Merkle Tree

สร้าง Merkle tree ง่าย ๆ
เทียบ 2 tree → หา block ที่ต่างกัน
ทดสอบความถูกต้อง (เปลี่ยน byte → root hash เปลี่ยน)

🛠️ Checkpoint 10.4 — Consistent Hashing

implement consistent hash พร้อม vnodes
5 node × 100 vnodes
ใส่ 100K key → ตรวจสอบการกระจาย
ลบ node → วัดว่า key ย้ายมากแค่ไหน

🛠️ Checkpoint 10.5 — Count-Min Sketch

implement CMS สำหรับ top-K
stream 10M event → ติดตาม top 10
เทียบกับ top 10 จริง (HashMap)

15. สรุปบท

ทบทวนโครงสร้างข้อมูลแบบกระจายทั้งหมดในบทนี้ — Bloom filter, HyperLogLog, Count-Min Sketch, Merkle tree, consistent hashing, skip list, LSM-tree และ SWIM เช็กลิสต์นี้คือชุดเครื่องมือที่ช่วยให้ระบบขนาดใหญ่ทำงานได้ด้วย memory และเวลาที่จำกัด:

✅ Bloom Filter — "definitely not / probably yes" — cache, dedup, crawl ✅ HyperLogLog — cardinality estimation, 12 KB for billions of items ✅ Count-Min Sketch — frequency + top-K, stream-friendly ✅ Merkle Tree — integrity + sync — Cassandra, Git, blockchain ✅ Consistent Hashing + vnodes — distributed map, minimal data movement ✅ Rendezvous Hashing — alternative to ring, simpler code ✅ Skip List — ordered map, Redis ZSET, LevelDB memtable ✅ LSM-Tree — write-optimized storage, Cassandra/RocksDB ✅ SWIM — scalable failure detection (Memberlist, Consul) ✅ Trade accuracy for space + speed — มี use case ที่เหมาะ

← บทที่ 9 | บทที่ 11 → Glossary + Cheat Sheet

บทที่ 10 — Distributed Data Structures & Algorithms ​

1. ทำไมต้อง "Probabilistic" Data Structures? ​

2. Bloom Filter — "เคยเห็น item นี้ไหม?" ​

ปัญหา ​

หลักการทำงาน ​

คุณสมบัติ ​

Sizing — กฎทอง ​

การใช้งาน ​

ตัวอย่างโค้ด ​

Variants — รุ่นย่อย ​

3. HyperLogLog (HLL) — ประมาณจำนวน unique items ​

ปัญหา ​

หลักการทำงาน (Intuition) ​

คุณสมบัติของ HLL ​

การใช้งานจริง ​

Redis HyperLogLog — ตัวอย่างจริง ​

4. Count-Min Sketch — หา Heavy hitters / Top-K ​

ปัญหาที่เจอ ​

หลักการทำงาน CMS ​

Trace ตัวอย่าง ​

การใช้งาน CMS ​

5. Merkle Tree — hash tree ตรวจสอบความถูกต้องของข้อมูลใหญ่ ​

ปัญหาที่ Merkle Tree แก้ ​

โครงสร้าง ​

Algorithm เปรียบเทียบสองต้น ​

การใช้งาน Merkle Tree ​

Cassandra Anti-Entropy Repair — ซ่อม replica ที่ไม่ตรงกัน ​

Git — ใช้ Merkle DAG เก็บประวัติ commit ​

Bitcoin / Blockchain — ใช้ Merkle root ใน block ​

IPFS / Distributed Storage — content-addressable storage ​

ตัวอย่างโค้ด Merkle Tree ​

6. Consistent Hashing — ลึกกว่า บท 6 ​

ทบทวน ​

Virtual Nodes (vnodes) — ทำไมต้องมี? ​

Jump Consistent Hash — algorithm ของ Google ปี 2014 ​

Rendezvous Hashing (HRW) — Highest Random Weight ​

เปรียบเทียบสามแบบ ​

Variants อื่นที่ใช้จริงใน production (รู้ไว้สำหรับ senior+) ​

7. Skip List — sorted structure ที่ search O(log n) ​

ภาพรวม ​

โครงสร้าง Skip List ​

การใช้งาน Skip List ​

8. LSM-Tree — โครงสร้างข้อมูลที่ optimize การเขียน ​

แนวคิด ​

สถาปัตยกรรม ​

ใช้ที่ไหนบ้าง ​

Trade-offs ของ LSM ​

9. SWIM Protocol — ลึก ​

รายละเอียด Algorithm ​

Gossip Dissemination — กระจายข่าวสาร ​

การ tuning ​

ใช้ที่ไหนบ้าง (SWIM) ​

10. ตารางเปรียบเทียบ ​

11. Algorithm จริงใน Production ​

ตัวอย่างที่ 1: Twitter Trends ​

ตัวอย่างที่ 2: Google BigTable / Spanner ​

ตัวอย่างที่ 3: Cassandra Read Path ​

ตัวอย่างที่ 4: Discord Voice Servers ​

12. ลึกขึ้น — Probabilistic Counting ​

Linear Counting — counting แบบเชิงเส้น (เก่า) ​

LogLog → SuperLogLog → HyperLogLog — วิวัฒนาการของ algorithm ​

13. เมื่อไหร่ที่ "ไม่ควร" ใช้ probabilistic ​

14. Checkpoint — แบบฝึกหัด ​

15. สรุปบท ​

บทที่ 10 — Distributed Data Structures & Algorithms

1. ทำไมต้อง "Probabilistic" Data Structures?

2. Bloom Filter — "เคยเห็น item นี้ไหม?"

ปัญหา

หลักการทำงาน

คุณสมบัติ

Sizing — กฎทอง

การใช้งาน

ตัวอย่างโค้ด

Variants — รุ่นย่อย

3. HyperLogLog (HLL) — ประมาณจำนวน unique items

ปัญหา

หลักการทำงาน (Intuition)

คุณสมบัติของ HLL

การใช้งานจริง

Redis HyperLogLog — ตัวอย่างจริง

4. Count-Min Sketch — หา Heavy hitters / Top-K

ปัญหาที่เจอ

หลักการทำงาน CMS

Trace ตัวอย่าง

การใช้งาน CMS

5. Merkle Tree — hash tree ตรวจสอบความถูกต้องของข้อมูลใหญ่

ปัญหาที่ Merkle Tree แก้

โครงสร้าง

Algorithm เปรียบเทียบสองต้น

การใช้งาน Merkle Tree

Cassandra Anti-Entropy Repair — ซ่อม replica ที่ไม่ตรงกัน

Git — ใช้ Merkle DAG เก็บประวัติ commit

Bitcoin / Blockchain — ใช้ Merkle root ใน block

IPFS / Distributed Storage — content-addressable storage

ตัวอย่างโค้ด Merkle Tree

6. Consistent Hashing — ลึกกว่า บท 6

ทบทวน

Virtual Nodes (vnodes) — ทำไมต้องมี?

Jump Consistent Hash — algorithm ของ Google ปี 2014

Rendezvous Hashing (HRW) — Highest Random Weight

เปรียบเทียบสามแบบ

Variants อื่นที่ใช้จริงใน production (รู้ไว้สำหรับ senior+)

7. Skip List — sorted structure ที่ search O(log n)

ภาพรวม

โครงสร้าง Skip List

การใช้งาน Skip List

8. LSM-Tree — โครงสร้างข้อมูลที่ optimize การเขียน

แนวคิด

สถาปัตยกรรม

ใช้ที่ไหนบ้าง

Trade-offs ของ LSM

9. SWIM Protocol — ลึก

รายละเอียด Algorithm

Gossip Dissemination — กระจายข่าวสาร

การ tuning

ใช้ที่ไหนบ้าง (SWIM)

10. ตารางเปรียบเทียบ

11. Algorithm จริงใน Production

ตัวอย่างที่ 1: Twitter Trends

ตัวอย่างที่ 2: Google BigTable / Spanner

ตัวอย่างที่ 3: Cassandra Read Path

ตัวอย่างที่ 4: Discord Voice Servers

12. ลึกขึ้น — Probabilistic Counting

Linear Counting — counting แบบเชิงเส้น (เก่า)

LogLog → SuperLogLog → HyperLogLog — วิวัฒนาการของ algorithm

13. เมื่อไหร่ที่ "ไม่ควร" ใช้ probabilistic

14. Checkpoint — แบบฝึกหัด

15. สรุปบท