Konteks dan cakupan
Ini adalah pertanyaan wawancara data-engineering dan stream-processing. Platform menerima miliaran event, melayani query berdasarkan jam, tenant, dan region, serta mentoleransi sekitar 1% relative error untuk dashboard. Penagihan (billing), penegakan kuota, dan laporan audit tetap memerlukan nilai eksak. Klarifikasi batasan toleransi error, jenis window, lateness bound, kebutuhan operasi himpunan (set operations), dan apakah identifier merupakan data pribadi.
Bank soal telah mencakup streaming, hot partition, dan arsitektur batch-versus-stream. Pokok bahasan ini berfokus pada bagaimana cardinality sketch yang dapat digabungkan (mergeable) mengubah biaya distinct-count terdistribusi, bukan pada satu produk basis data tertentu.
Apa yang dievaluasi oleh pewawancara
- Apakah Anda membedakan kardinalitas, keanggotaan (membership), dan frekuensi alih-alih memperlakukan HLL seperti Bloom filter atau Count-Min Sketch.
- Apakah Anda menjelaskan sketch berukuran tetap per shard dan penggabungan nilai maksimum per register, bukan menjumlahkan estimasi lokal.
- Apakah Anda mengubah aspek error, kelambatan data, reset, privasi, dan ketepatan bisnis menjadi kontrak yang dapat diuji.
Jawaban yang lemah akan mengatakan "gunakan Redis HLL karena ukurannya kecil." Jawaban yang kuat memberikan baseline eksak, menyebutkan potensi kegagalan aproksimasi, serta mendefinisikan replay, sampling, dan pemantauan drift.
Klarifikasi sebelum menjawab
- Berapa tingkat error yang dapat diterima? Dashboard mungkin menerima sekitar 1%; penagihan atau laporan kepatuhan membutuhkan jalur eksak atau jalur rekonsiliasi yang terkalibrasi.
- Apakah query menggunakan fixed window atau rentang arbitrer? Sketch per jam cocok untuk bucket tetap; rentang arbitrer membutuhkan bucket yang dapat digabungkan dengan batasan dan retensi yang eksplisit.
- Berapa lama batas keterlambatan event yang masuk? Batas keterlambatan (lateness bound) menentukan apakah perlu membuka kembali bucket, mempertahankan raw event, atau menerima watermark finalisasi.
- Apakah diperlukan operasi intersection, difference, atau daftar anggota? HLL sangat andal untuk kardinalitas union; keanggotaan, intersection, atau penghapusan memerlukan struktur lain atau komputasi ulang secara eksak.
Jawaban 30 detik
"Saya akan mempertahankan set eksak sebagai baseline kebenaran data, tetapi biaya memori, network shuffle, dan penggabungan lintas-shard meningkat seiring bertambahnya unique user. Jika dashboard menerima toleransi error sekitar 1%, setiap shard mempertahankan HyperLogLog dengan presisi tetap yang dikunci berdasarkan jam, tenant, dan region. Pada saat query, saya mengambil nilai maksimum per register di seluruh sketch dan menjalankan satu estimator; saya tidak pernah menjumlahkan estimasi lokal. HLL menjawab perkiraan kardinalitas union, bukan keanggotaan, penghapusan, atau daftar identitas. Saya menggunakan event time dan watermark untuk menutup bucket, menerima keterlambatan terbatas, dan mengirim koreksi yang lebih lama ke replay eksak. Terakhir, saya merekonsiliasi sampel bucket tertutup terhadap hitungan eksak dan memantau relative error, bucket kosong, duplikasi, penggabungan sketch, serta risiko privasi."
Jawaban mendalam langkah demi langkah
Langkah 1: Bangun baseline eksak.
Simpan kumpulan user-ID untuk setiap (hour, tenant, region). Ini bersifat eksak, tetapi shard harus mengirim banyak ID atau melakukan global shuffle. Menjumlahkan nilai lokal COUNT(DISTINCT) akan menghitung ganda user yang berada di beberapa shard.
Langkah 2: Jelaskan state HLL.
Bagi hash yang stabil menjadi indeks register dan rank leading-zero. Setiap input hanya memperbarui registernya sendiri dengan rank maksimum. Estimator memperoleh kardinalitas dari semua register dan menerapkan koreksi untuk rentang kecil. Jangan menjanjikan tingkat error universal tanpa menyebutkan presisi, perilaku fungsi hash, dan rentang estimator.
Langkah 3: Jelaskan penggabungan terdistribusi.
Sketch untuk satu dimensi harus menggunakan jumlah register, konvensi hash, dan encoding yang sama. Gabungkan dengan mengambil nilai maksimum di setiap register, bukan dengan menjumlahkan estimasi. Oleh karena itu, sketch per menit dapat digabungkan menjadi hasil per jam tanpa melakukan shuffle pada raw ID.
for each event(user_id, bucket, tenant, region):
i, rank = hash_and_rank(user_id, precision)
sketch[bucket, tenant, region][i] = max(sketch[...][i], rank)
merged[i] = max(sketch_a[i], sketch_b[i])
estimate = hll_estimator(merged)Langkah 4: Tangani data terlambat dan windowing.
Kelompokkan ke dalam bucket berdasarkan event time dan gunakan watermark untuk menandai bucket sebagai final. Terima pembaruan hanya dalam batas keterlambatan maksimum; kirim event yang lebih lama ke replay raw-log atau tabel koreksi eksak. HLL tidak dapat menghapus satu user, sehingga pembatalan event memerlukan pembuatan ulang bucket yang terpengaruh.
Langkah 5: Pisahkan hasil perkiraan dari kebenaran bisnis.
Proses rekonsiliasi mengambil sampel bucket tertutup dan menghitung nilai sebenarnya menggunakan set eksak atau SQL offline. Catat relative error, arah bias, dan dimensi yang mengalami anomali. Pertahankan ledger eksak untuk penagihan, kuota, dan penghapusan data privasi; gunakan sketch untuk observasi atau estimasi berbiaya rendah.
Langkah 6: Kontrol biaya dan privasi.
Batasi kombinasi dimensi, retensi bucket, dan sketch per tenant sehingga label berkardinalitas tinggi tidak menciptakan state yang tak terbatas. Lakukan normalisasi input hash secara konsisten dan kelola rotasi kunci; terapkan otorisasi pada akses sketch. Sketch bukan merupakan jaminan anonimisasi karena ukuran agregat masih dapat mengungkapkan suatu kelompok.
Contoh jawaban berkualitas tinggi
"Pertama, saya akan menanyakan apakah hasilnya boleh berupa perkiraan. Set eksak cocok untuk penagihan dan audit, tetapi miliaran event di berbagai shard dan window yang panjang membuat memori dan shuffle menjadi mahal. Untuk dashboard dengan toleransi sekitar 1%, setiap shard mempertahankan HLL yang dikonfigurasi secara identik per bucket waktu dan dimensi. Hash yang stabil memperbarui satu register, dan query mengambil nilai maksimum per register sebelum menjalankan estimator; menjumlahkan estimasi lokal akan menghitung user dua kali.
Saya menutup bucket event-time dengan watermark dan mempertahankan window keterlambatan yang terbatas. Koreksi di luar window tersebut diproses melalui replay raw-log karena HLL tidak dapat menghapus satu elemen. Metadata mencatat presisi, konvensi hash, dan batas bucket agar sketch tetap dapat digabungkan. Saya memantau ukuran sketch, latensi penggabungan, tingkat duplikasi, dan relative error, serta merekonsiliasi sampel bucket dengan set eksak. Penagihan dan penghapusan untuk kepatuhan tetap dilakukan secara eksak; HLL berfungsi sebagai lapisan akselerasi analitik."
Kesalahan umum
- Menjumlahkan estimasi shard → user yang sama dapat muncul di beberapa shard → gabungkan register, lalu lakukan estimasi sekali.
- Mengklaim HLL dapat menjawab apakah seorang user pernah muncul → HLL hanya menyimpan ringkasan statistik → gunakan set atau Bloom filter untuk keanggotaan dan nyatakan adanya false positive.
- Mengurangkan event yang terlambat atau dihapus dari sketch → nilai maksimum register tidak memiliki kontributor yang dapat dibalikkan (irreversible) → bangun ulang bucket atau gunakan tabel koreksi eksak.
- Menggabungkan format presisi atau hash yang berbeda secara sembarangan → arti register menjadi berbeda → simpan metadata presisi, hash, encoding, dan versi.
- Memperlakukan sketch sebagai perlindungan privasi → ukuran agregat masih dapat membocorkan informasi kelompok → gabungkan otorisasi, dimensi minimal, retensi, dan tinjauan privasi.
Pertanyaan lanjutan dan tanggapan
Pertanyaan lanjutan 1: Bisnis meminta rentang 37 hari arbitrer. Bagaimana Anda mengelompokkannya ke dalam bucket?
Sketch per menit menghasilkan lebih banyak state, tetapi query dapat menggabungkan menit-menit yang berurutan; sketch per jam dan per hari mengurangi beban pembacaan untuk rentang yang panjang. Bucket bertingkat (multi-level) memerlukan batasan yang eksplisit dan tidak tumpang tindih. Query planner memilih kombinasi non-overlapping yang paling kasar dan mengisi batas antar-tingkat dengan bucket yang lebih halus.
Pertanyaan lanjutan 2: Penghapusan user harus berlaku dalam waktu 24 jam. Apakah HLL dapat tetap digunakan?
HLL tidak dapat melakukan penghapusan per user. Pertahankan indeks event eksak yang dapat dihapus atau pemetaan terenkripsi, bangun ulang bucket yang terpengaruh, dan sembunyikan versi lama pada lapisan dashboard; perlakukan sketch sebagai data non-otoritatif. Jika regulasi memerlukan bukti penghapusan, gunakan ledger penghapusan eksak dan verifikasi melalui replay.
Pertanyaan lanjutan 3: Tingkat error melonjak dari 1% ke 8% setelah proses penggabungan. Apa yang Anda periksa terlebih dahulu?
Bandingkan metadata sketch: presisi, seed hash, encoding register, dan versi. Periksa apakah ada shard yang melakukan serialisasi pada nilai estimasi alih-alih data register, menggabungkan input yang sama dua kali, atau menerima distribusi hash yang anomali. Reproduksi set kecil langkah demi langkah dengan satu shard, dua shard, dan satu penggabungan untuk mengisolasi kerusakan pada estimator atau serialisasi.