1. Gesaan
Sistem pengelogan menerima berbilion-bilion pengecam pengguna setiap hari dan mesti menganggarkan bilangan pengguna unik bagi hari tersebut secara masa nyata. Belanjawan memori hanyalah beberapa KB, dan ralat kecil boleh diterima. Reka bentuk algoritma penstriman dan terangkan ralatnya, cara menggabungkan shard, serta situasi di mana ia tidak boleh menggantikan penyahduplikasian tepat.
2. Kekangan dan penjelasan
- Input ialah strim pengecam yang berterusan; gunakan satu laluan (one pass) dan memori tetap.
- Pertanyaan meminta anggaran kardinaliti (kiraan unik) bagi suatu tetingkap masa.
- Andaikan cincangan tertabur secara seragam dan setiap shard menggunakan algoritma cincangan, bilangan daftar, dan pengekodan yang sama.
- Pemadaman tidak diperlukan; tetingkap gelongsor (sliding windows), tempoh tamat, dan nilai tepat yang konsisten secara teguh memerlukan struktur tambahan.
3. Idea teras
HyperLogLog (HLL) membahagikan cincangan kepada indeks daftar dan bit selebihnya. Dengan m = 2^p daftar, p bit pertama memilih daftar; dalam bit selebihnya, bilangan sifar pendahulu (leading zeroes) ditambah satu ialah rho. Setiap daftar hanya menyimpan rho terbesar yang pernah diperhatikannya.
Intuisinya ialah jujukan sifar pendahulu yang sangat panjang dalam daftar membuktikan bahawa lebih banyak elemen unik telah muncul dalam ruang sampel. Anggarkan kardinaliti dengan min harmonik:
E = alpha_m * m^2 / sum(2^(-M[j]))
Di sini M[j] ialah daftar j dan alpha_m ialah pemalar pembetulan berdasarkan bilangan daftar. Pelaksanaan pengeluaran juga menggunakan pembetulan pengiraan linear (linear counting) untuk kardinaliti kecil dan pembetulan julat besar berhampiran had ruang cincangan.
4. Pelaksanaan rujukan
Kod pseudo di bawah menunjukkan kemas kini, penganggaran, dan penggabungan. Pelaksanaan sebenar harus menggunakan integer lebar tetap, fungsi cincangan eksplisit, dan batas 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. Kerumitan dan ketepatan
Setiap elemen memerlukan satu cincangan dan satu kemas kini daftar, jadi kerumitan masa ialah O(1); kerumitan ruang ialah O(m), tidak bergantung pada panjang strim. HLL standard mempunyai ralat piawai relatif kira-kira 1.04 / sqrt(m): untuk m = 16,384, nilainya adalah kira-kira 0.81%. Ini ialah ralat anggaran kebarangkalian, bukannya jaminan bahawa setiap pertanyaan berada dalam selang tetap.
Oleh sebab kemas kini mengambil nilai maksimum, penambahan elemen yang sama secara berulang kali tidak terus mengubah keadaan, memberikan ciri idempoten. Shard boleh digabungkan dengan mengambil nilai maksimum mengikut daftar, dengan syarat fungsi cincangan, p, dan pengekodan adalah serupa; jika tidak, taburan statistiknya tidak serasi.
6. Tindakan susulan dan perangkap
- HLL mengembalikan anggaran; ia tidak boleh menggantikan set tepat apabila produk memerlukan senarai per pengguna yang tepat, jejak audit, atau kuantiti pengebilan.
- Mengosongkan daftar hanya mewakili tetingkap baharu. Tetingkap gelongsor memerlukan baldi masa, berbilang HLL, atau varian yang boleh dipadamkan, berserta pengendalian sempadan dan storan.
- Percanggahan cincangan (hash collisions) dan pincang input mempengaruhi anggaran. Pilih cincangan 64-bit atau lebih lebar yang stabil dan piawaikannya merentasi sempadan perkhidmatan.
- Penganggar harmonik mentah adalah berpincang bagi kardinaliti kecil; pengiraan linear menggunakan bilangan daftar sifar untuk mengurangkan kepincangan tersebut.
7. Bacaan lanjut
- Dokumentasi jenis data Redis PFCOUNT dan HyperLogLog.
- Dokumentasi kardinaliti anggaran Snowflake.
- Gambaran keseluruhan Meta Engineering tentang HyperLogLog dalam Presto.
8. Poin pemarkahan temu duga
Boleh menerangkan keadaan
Calon harus menerangkan daftar m = 2^p, indeks, asal-usul rho, dan sebab setiap daftar hanya menyimpan nilai maksimum.
Boleh menerbitkan ralat dan pembetulan
Mereka harus memberikan magnitud tertib 1.04 / sqrt(m), menerangkan pengiraan linear julat kecil dan pembetulan julat besar, serta membezakan ralat kebarangkalian daripada jaminan tepat.
Boleh mengendalikan penggabungan teragih
Mereka harus menyatakan bahawa penggabungan adalah nilai maksimum mengikut daftar dan setiap shard mesti berkongsi fungsi cincangan, kepersisan, dan pengekodan yang sama.
Boleh mengenal pasti sempadan produk
Mereka harus membezakan analitik anggaran daripada senarai tepat, tetingkap gelongsor, pemadaman, dan pengebilan, serta menerangkan sebab keperluan tersebut memerlukan reka bentuk tambahan.