1. Pertanyaan
Sebuah sistem logging menerima miliaran pengidentifikasi pengguna setiap hari dan harus memperkirakan jumlah pengguna unik untuk hari tersebut secara real time. Anggaran memori hanya beberapa KB, dan kesalahan kecil dapat diterima. Rancang algoritma streaming dan jelaskan kesalahannya, cara menggabungkan shard, dan di mana algoritma ini tidak dapat menggantikan deduplikasi tepat.
2. Batasan dan klarifikasi
- Input berupa stream pengidentifikasi yang terus berjalan; gunakan satu kali lintasan (one pass) dan memori tetap.
- Kueri meminta kardinalitas perkiraan (distinct count) pada suatu jendela waktu.
- Asumsikan hash terdistribusi secara seragam dan setiap shard menggunakan algoritma hash, jumlah register, dan pengodean yang sama.
- Penghapusan data tidak diperlukan; sliding window, kedaluwarsa, dan nilai tepat yang konsisten kuat memerlukan struktur tambahan.
3. Ide utama
HyperLogLog (HLL) membagi sebuah hash menjadi indeks register dan bit-bit yang tersisa. Dengan m = 2^p register, p bit pertama memilih register; pada bit-bit yang tersisa, jumlah nol di depan ditambah satu adalah rho. Setiap register hanya menyimpan rho terbesar yang pernah diamatinya.
Intuisinya adalah bahwa deretan nol di depan yang sangat panjang dalam sebuah register merupakan bukti bahwa lebih banyak elemen unik telah muncul di ruang sampel. Perkirakan kardinalitas dengan rata-rata harmonik:
E = alpha_m * m^2 / sum(2^(-M[j]))
Di sini M[j] adalah register j dan alpha_m adalah konstanta koreksi berdasarkan jumlah register. Implementasi tingkat produksi juga menggunakan koreksi linear-counting untuk kardinalitas kecil dan koreksi rentang besar di dekat batas ruang hash.
4. Implementasi referensi
Pseudokode di bawah ini menunjukkan pembaruan, estimasi, dan penggabungan. Implementasi nyata harus menggunakan integer dengan lebar tetap, fungsi hash eksplisit, dan batasan untuk rho.
init(p):
m = 1 << p
M = array(m, fill=0)
add(x):
h = hash64(x)
j = high_bits(h, p)
w = remaining_bits(h, p)
r = leading_zero_count(w) + 1
M[j] = max(M[j], r)
estimate():
z = sum over j of 2^(-M[j])
e = alpha(m) * m * m / z
if e <= small_range_threshold(m) and zero_registers(M) != 0:
e = m * log(m / zero_registers(M))
return large_range_correction_if_needed(e)
merge(other):
require same p, hash function, and register encoding
for j in 0..m-1:
M[j] = max(M[j], other.M[j])5. Kompleksitas dan kebenaran
Setiap elemen membutuhkan satu operasi hash dan satu pembaruan register, sehingga kompleksitas waktunya adalah O(1); kompleksitas ruangnya adalah O(m), tidak bergantung pada panjang stream. HLL standar memiliki kesalahan standar relatif sekitar 1.04 / sqrt(m): untuk m = 16,384, itu sekitar 0.81%. Ini adalah kesalahan estimasi probabilistik, bukan jaminan pasti bahwa setiap kueri berada dalam interval tetap.
Karena pembaruan mengambil nilai maksimum, menambahkan elemen yang sama berulang kali tidak terus mengubah status, sehingga memberikan sifat idempoten. Shard dapat digabungkan dengan mengambil nilai maksimum per register, asalkan fungsi hash, p, dan pengodeannya identik; jika tidak, distribusi statistik mereka tidak kompatibel.
6. Tindak lanjut dan jebakan
- HLL mengembalikan sebuah estimasi; ini tidak dapat menggantikan himpunan tepat ketika produk membutuhkan daftar per pengguna yang presisi, jejak audit, atau kuantitas penagihan.
- Mengosongkan register hanya mewakili jendela baru. Sliding window memerlukan bucket waktu, beberapa HLL, atau varian yang mendukung penghapusan, ditambah penanganan batas dan penyimpanan.
- Tabrakan hash dan bias input memengaruhi estimasi. Pilih hash 64-bit atau lebih lebar yang stabil dan standarkan di seluruh batas layanan.
- Estimator harmonik mentah memiliki bias untuk kardinalitas kecil; linear counting menggunakan jumlah register bernilai nol untuk mengurangi bias tersebut.
7. Bacaan lanjutan
- Dokumentasi tipe data Redis PFCOUNT dan HyperLogLog.
- Dokumentasi kardinalitas perkiraan Snowflake.
- Gambaran umum Meta Engineering tentang HyperLogLog di Presto.
8. Poin penilaian wawancara
Mampu menjelaskan state
Kandidat harus menjelaskan register m = 2^p, indeks, asal-usul rho, dan mengapa setiap register hanya menyimpan nilai maksimum.
Mampu menurunkan kesalahan dan koreksi
Mereka harus menyebutkan tingkat besaran 1.04 / sqrt(m), menjelaskan linear counting untuk rentang kecil dan koreksi rentang besar, serta membedakan kesalahan probabilistik dari jaminan eksak.
Mampu menangani penggabungan terdistribusi
Mereka harus menyatakan bahwa penggabungan dilakukan dengan mengambil nilai maksimum per register dan bahwa setiap shard harus menggunakan fungsi hash, presisi, dan pengodean yang sama.
Mampu mengidentifikasi batasan produk
Mereka harus membedakan analitik perkiraan dari daftar tepat, sliding window, penghapusan, dan penagihan, serta menjelaskan mengapa persyaratan tersebut memerlukan desain tambahan.