Mini-challenge: P99 spike và collision DoS của ingest

Ba bài trước mổ từng cấu trúc riêng lẻ: ArrayList grow 1.5x, HashMap bucket/chaining/resize, treeify chống collision DoS. Lab này ghép cả ba vào một sự cố production duy nhất — nơi cùng lúc hai triệu chứng khác nhau cùng đến từ cách bạn khởi tạo collection.

Bạn nhận on-call một service MetricsIngest. Nó có một endpoint /ingest nhận một batch metric sample (mảng JSON), gom sample theo tên metric, trả về tổng hợp. Hai than phiền từ dashboard:

1. P99 của /ingest gấp khoảng 6 lần P50 ngay cả khi traffic bình thường — batch nào cũng chậm bất thường ở đuôi phân phối.
2. Thỉnh thoảng CPU cháy 100% trên vài batch, và lạ ở chỗ những batch đó nhỏ hơn batch bình thường — ít sample hơn nhưng tốn nhiều CPU hơn.

Nhiệm vụ: tìm ra vì sao, rồi fix. Cả hai triệu chứng đều nằm trong nội thất ArrayList/HashMap bạn vừa học.

🎯 Đề bài

Setup

Service gom mỗi batch theo hai bước, đúng như một handler thật:

• Parse: đọc sampleCount sample từ request vào một List.
• Aggregate: gom sample theo metricName vào một Map rồi cộng value mỗi nhóm.

Production: batch điển hình khoảng 50.000 sample, khoảng 2.000 tên metric phân biệt. Cả hai collection trong starter đều khởi tạo mặc định — không hint capacity.

Yêu cầu

1. Reproduce P99 spike: chạy benchmark trong starter, đọc P50 và P99. Giải thích chính xác hai chỗ nào trong một batch gây ra chi phí đuôi — mỗi chỗ liên quan tới một cấu trúc, và đếm số lần realloc thật sự cho batch 50.000 sample / 2.000 tên.

2. Fix resize storm: pre-size cả List (parse) lẫn Map (aggregate) để loại bỏ mọi grow/resize trong đường xử lý batch. Với Map, phải tính đúng capacity qua load factor — truyền thẳng số phần tử là bẫy.

3. Reproduce collision DoS: dùng bộ tên metric được chế sao cho tất cả cùng hashCode. Chạy một batch nhỏ (ví dụ 5.000 sample) chỉ gồm các tên collide này. Quan sát thời gian aggregate so với batch thường cùng cỡ, và giải thích vì sao ít phần tử lại tốn nhiều CPU hơn — kể cả sau khi bucket đã treeify.

4. Fix collision DoS: thêm tầng phòng thủ đúng chỗ. Xác định rõ tầng nào chặn được tấn công và tầng nào (treeify) chỉ giảm thiệt hại.

Cách phân biệt hai triệu chứng

Trước khi sửa, tách bạch hai lỗi bằng một câu hỏi duy nhất: batch gây sự cố to hơn hay nhỏ hơn bình thường?

flowchart TD
    A["P99 spike / CPU 100%"] --> B{"batch nho hon binh thuong?"}
    B -->|"Sai (batch to)"| C["Resize storm: JFR thay Arrays.copyOf + HashMap.resize"]
    B -->|"Dung (batch nho)"| D["Collision DoS: thread RUNNABLE o putVal / TreeNode.find"]
    C --> E["Fix: pre-size ArrayList + HashMap"]
    D --> F["Fix: gioi han input + rate limit; treeify chi la luoi cuoi"]

📦 Concept dùng trong bài

Mỗi yêu cầu map ngược về một learning outcome của module:

▶️ Starter code

MetricsIngestApp.java — một file, chạy được ngay:

import java.util.*;

public class MetricsIngestApp {

    public record Sample(String metricName, long timestamp, double value) { }

    public static class BatchAggregator {
        // Group samples by metric name, then sum value per metric.
        public Map<String, Double> aggregate(List<Sample> batch) {
            // Bucket each sample under its metric name.
            Map<String, List<Sample>> byMetric = new HashMap<>();
            for (Sample s : batch) {
                byMetric.computeIfAbsent(s.metricName(), k -> new ArrayList<>()).add(s);
            }
            Map<String, Double> result = new HashMap<>();
            for (Map.Entry<String, List<Sample>> e : byMetric.entrySet()) {
                double sum = 0;
                for (Sample s : e.getValue()) sum += s.value();
                result.put(e.getKey(), sum);
            }
            return result;
        }
    }

    // Simulates JSON parsing: reads sampleCount samples into a List.
    static List<Sample> parseBatch(int sampleCount, int distinctNames) {
        List<Sample> batch = new ArrayList<>();   // Parse: accumulate samples into the batch list.
        long now = System.currentTimeMillis();
        for (int i = 0; i < sampleCount; i++) {
            batch.add(new Sample("metric-" + (i % distinctNames), now, i));
        }
        return batch;
    }

    public static void main(String[] args) {
        int batches = 200, sampleCount = 50_000, distinctNames = 2_000;
        long[] lat = new long[batches];
        for (int b = 0; b < batches; b++) {
            long t0 = System.nanoTime();
            List<Sample> batch = parseBatch(sampleCount, distinctNames); // parse step
            new BatchAggregator().aggregate(batch);                       // aggregate step
            lat[b] = System.nanoTime() - t0;
        }
        Arrays.sort(lat);
        System.out.printf("p50 = %.2f ms, p99 = %.2f ms%n",
            lat[batches / 2] / 1e6, lat[(int) (batches * 0.99)] / 1e6);
    }
}

Chạy:

javac MetricsIngestApp.java
java -XX:+UseParallelGC MetricsIngestApp
# Muon nhin resize storm bang JFR:
# java -XX:StartFlightRecording=duration=30s,filename=ingest.jfr MetricsIngestApp

Để reproduce collision DoS (yêu cầu 3), bạn cần một hàm sinh tên metric cùng hashCode — tự viết trước khi xem gợi ý. Tự làm từng yêu cầu trước khi mở phần Lời giải.

💡 Gợi ý

✅ Lời giải

public Map<String, Double> aggregate(List<Sample> batch, int distinctNameHint) {
    // capacity = tableSizeFor(ceil(distinctNameHint / 0.75)); 0 resize during batch
    Map<String, List<Sample>> byMetric = HashMap.newHashMap(distinctNameHint);
    for (Sample s : batch) {
        byMetric.computeIfAbsent(s.metricName(), k -> new ArrayList<>()).add(s);
    }
    Map<String, Double> result = HashMap.newHashMap(byMetric.size());
    for (Map.Entry<String, List<Sample>> e : byMetric.entrySet()) {
        double sum = 0;
        for (Sample s : e.getValue()) sum += s.value();
        result.put(e.getKey(), sum);
    }
    return result;
}

static List<Sample> parseBatch(int sampleCount, int distinctNames) {
    List<Sample> batch = new ArrayList<>(sampleCount);  // pre-sized: 0 grow
    long now = System.currentTimeMillis();
    for (int i = 0; i < sampleCount; i++) {
        batch.add(new Sample("metric-" + (i % distinctNames), now, i));
    }
    return batch;
}

// Every returned string has the SAME String.hashCode() -> one bucket.
static List<String> collidingNames(int count) {
    String[] seeds = { "Aa", "BB" };  // both hash to 2112
    List<String> names = new ArrayList<>(List.of(""));
    while (names.size() < count) {
        List<String> next = new ArrayList<>(names.size() * 2);
        for (String base : names)
            for (String seed : seeds)
                next.add(base + seed);
        names = next;
    }
    return new ArrayList<>(names.subList(0, count));
}

static final int MAX_SAMPLES = 100_000;
static final int MAX_DISTINCT_NAMES = 10_000;

public static Map<String, Double> handleIngest(List<Sample> batch) {
    // Layer 1: cap input size BEFORE building any map -- cheapest, blocks at the door
    if (batch.size() > MAX_SAMPLES) {
        throw new IllegalArgumentException("batch too large: " + batch.size());
    }
    Map<String, Double> result = new BatchAggregator()
        .aggregate(batch, Math.min(batch.size(), MAX_DISTINCT_NAMES));
    // Layer 1b: reject batches with an implausible number of distinct names
    if (result.size() > MAX_DISTINCT_NAMES) {
        throw new IllegalArgumentException("too many distinct metrics");
    }
    return result;
}

🎓 Mở rộng

Mức 1 — đo grow bằng JFR thay vì đếm tay. Chạy -XX:StartFlightRecording=duration=30s,filename=ingest.jfr, mở bằng JMC, xem tab Memory → Allocation: hot allocation site sẽ là Arrays.copyOf (ArrayList grow) và HashMap.resize/resize. Sau khi pre-size, hai site này biến mất.

Mức 2 — Collectors.groupingBy có pre-size không? Viết lại aggregate bằng batch.stream().collect(Collectors.groupingBy(Sample::metricName)) và đọc source: nó dùng HashMap::new mặc định (không hint), nên vẫn resize storm. Muốn pre-size phải dùng overload groupingBy(classifier, HashMap::new, downstream) với supplier tự cấp — hoặc groupingBy không cứu được P99.

Mức 3 — vì sao ConcurrentHashMap không miễn nhiễm collision DoS? ConcurrentHashMap cũng chaining + treeify theo cùng ngưỡng. Nó chống data race, không chống hash abuse — cùng batch collide vẫn dồn một bucket. Phòng thủ vẫn là validate input, không phải đổi map.

✨ Điều bạn vừa làm được

Hoàn thành lab này, bạn đã:

• Chẩn đoán P99 spike và truy ra hai nguồn resize storm độc lập trong một batch — ArrayList grow và HashMap resize — rồi đếm chính xác số lần realloc.
• Pre-size đúng cách: ArrayList theo N, HashMap qua load factor (HashMap.newHashMap), loại bỏ mọi grow trong đường xử lý.
• Reproduce hash-collision DoS bằng key chế cùng hashCode, và giải thích vì sao batch nhỏ lại đắt kể cả sau treeify.
• Chọn tầng phòng thủ đúng chỗ: giới hạn input + rate limiting chặn tấn công; treeify chỉ là lưới cuối.

Đây là ba mảnh của module ghép lại thành một kỹ năng debug production duy nhất — từ triệu chứng ở dashboard tới root cause trong nội thất collection.

Bài tiếp theo: Tổng kết module — Collections Internals