Bagaimana untuk melaksanakan Redis menggunakan HyperLogLog

1. Gambaran Keseluruhan

Redis menambah struktur data HyperLogLog dalam versi 2.8.9, yang digunakan untuk statistik kardinaliti ialah apabila bilangan elemen input sangat besar, ruang yang diperlukan untuk mengira kardinalitinya agak kecil Dan secara amnya agak malar.

Dalam Redis, setiap kunci HyperLogLog hanya mengambil 12 KB memori untuk mengira kardinaliti hampir 2^64 elemen berbeza. Ini sangat berbeza dengan pengiraan kardinaliti, di mana koleksi dengan lebih banyak elemen menggunakan lebih banyak memori. Walau bagaimanapun, kerana HyperLogLog hanya mengira kardinaliti berdasarkan elemen input dan tidak menyimpan elemen input itu sendiri, HyperLogLog tidak boleh mengembalikan elemen individu input seperti koleksi.

2. Apakah kardinaliti?

Sebagai contoh, jika set data ialah {1, 3, 5, 7, 5, 7, 8}, maka set kardinaliti data ini set ialah {1, 3, 5 ,7, 8}, kardinaliti (elemen tidak berulang) ialah 5. Anggaran kardinaliti adalah untuk mengira kardinaliti dengan cepat dalam julat ralat yang boleh diterima.

3. Perintah

Pada masa ini, hanya tiga arahan, PFADD, PFCOUNT dan PFMERGE, disokong oleh HyperLogLog. Mari kita perkenalkan mereka satu persatu terlebih dahulu.

3.1 PFADD

Versi terawal tersedia: 2.8.9. Kerumitan masa: O(1).

Arahan PFADD boleh menambah elemen (berbilang elemen boleh ditentukan) pada struktur data HyperLogLog dan menyimpannya dalam kunci yang ditentukan oleh kunci parameter pertama. Mengembalikan 1 jika anggaran kardinaliti (bilangan elemen yang dinilai) telah berubah, sebaliknya mengembalikan 0, iaitu untuk mengesahkan sama ada anggaran kardinaliti telah berubah selepas melaksanakan arahan. Jika kunci yang ditentukan tidak wujud, struktur data HyperLogLog kosong dicipta (iaitu, Redis String dengan panjang rentetan dan pengekodan yang ditentukan). Ia juga mungkin untuk memanggil arahan tanpa menentukan parameter elemen dan hanya menentukan kunci. Jika kunci wujud, jangan lakukan apa-apa dan kembalikan 0 jika kunci itu tidak wujud, nod data HyperLogLog baharu dibuat dan 1 dikembalikan. Pada asasnya ia hanya menjana struktur data HyperLogLog baharu tanpa menyimpan sebarang elemen.

(1) Format sintaks:

PFADD key element [element ...]

(2) Nilai pulangan:

integer, jika sekurang-kurangnya satu elemen ditambah, 1 dikembalikan, jika tidak 0 dikembalikan.

(3) Contoh:

127.0.0.1:6379> PFADD hll a b c d e f g
(integer) 1
127.0.0.1:6379> pfcount hll
(integer) 7

3.2 PFCOUNT

Versi terawal tersedia: 2.8.9. Kerumitan masa: O(1) Untuk berbilang kunci yang agak besar, kerumitan masa ialah O(N).

Gunakan arahan PFCOUNT untuk mendapatkan nilai kardinaliti anggaran HyperLogLog (iaitu, bilangan elemen). Perintah ini mengembalikan 0 jika kunci tidak wujud, jika tidak, ia mengembalikan anggaran kardinaliti kunci. Untuk berbilang kunci, dikembalikan ialah anggaran kardinaliti untuk penyatuan berbilang HyperLogLog, dikira dengan menggabungkan berbilang HyperLogLog ke dalam HyperLogLog sementara. Menggunakan jumlah memori yang minimum dan konsisten, HyperLogLog boleh mengira bilangan elemen unik koleksi. Setiap HyperLogLog hanya menggunakan 12K ditambah beberapa bait kunci itu sendiri.

(1) Format sintaks:

PFCOUNT key [key ...]

(2) Nilai pulangan:

integer, mengembalikan anggaran kardinaliti HyperLogLog yang ditentukan Jika terdapat berbilang HyperLogLog, kesatuan Anggaran kardinaliti dikembalikan.

(3) Contoh:

127.0.0.1:6379> PFADD hll foo bar zap
(integer) 1
127.0.0.1:6379> PFADD hll zap zap zap
(integer) 0
127.0.0.1:6379> PFADD hll foo bar
(integer) 0
127.0.0.1:6379> PFCOUNT hll
(integer) 3
127.0.0.1:6379> PFADD some-other-hll 1 2 3
(integer) 1
127.0.0.1:6379> PFCOUNT some-other-hll
(integer) 3
127.0.0.1:6379> PFCOUNT hll some-other-hll
(integer) 6

(4) Had:

Keputusan yang dikembalikan oleh HyperLogLog tidak tepat dan kadar ralat adalah kira-kira 0.81%.

Menggunakan arahan ini akan menukar HyperLogLog dan menggunakan 8 bait untuk menyimpan pangkalan pengiraan terakhir. Jadi, secara teknikalnya, PFCOUNT ialah arahan tulis.

(5) Isu Prestasi

Walaupun secara teorinya mengambil masa yang lebih lama untuk memproses HyperLogLog intensif, arahan PFCOUNT masih mempunyai prestasi tinggi apabila hanya satu kunci ditentukan. Ini kerana PFCOUNT menyimpan cache asas pengiraan terakhir, dan pangkalan ini tidak berubah sepanjang masa, kerana arahan PFADD tidak mengemas kini daftar dalam kebanyakan kes. Oleh itu, kesan ratusan permintaan sesaat boleh dicapai.

Apabila menggunakan perintah PFCOUNT untuk memproses berbilang kunci, HyperLogLog akan digabungkan. Langkah ini sangat memakan masa. Apabila menggunakan berbilang kunci, pelaksanaan PFCOUNT boleh mengambil sedikit masa (biasanya mengikut urutan milisaat), jadi penggunaan berlebihan tidak disyorkan.

Perlu diambil perhatian bahawa semantik pelaksanaan satu kekunci dan berbilang kunci bagi arahan ini adalah berbeza dan mempunyai prestasi yang berbeza. Penggunaan berlebihan semantik pelaksanaan berbilang kunci tidak disyorkan.

3.3 PFMERGE

Versi terawal tersedia: 2.8.9. Kerumitan masa: O(N), N ialah bilangan HyperLogLogs untuk digabungkan.

Berbilang HyperLogLog boleh digabungkan menjadi satu HyperLogLog melalui arahan PFMERGE. Anggaran kardinaliti HyperLogLog yang digabungkan dikira dengan mengambil penyatuan semua HyperLogLog yang diberikan. Hasil yang dikira disimpan ke kunci yang ditentukan.

Format sintaks:

PFMERGE destkey sourcekey [sourcekey ...]

Nilai pulangan:

Kembalikan OK.

Contoh:

127.0.0.1:6379> PFADD hll1 foo bar zap a
(integer) 1
127.0.0.1:6379> PFADD hll2 a b c foo
(integer) 1
127.0.0.1:6379> PFMERGE hll3 hll1 hll2
OK
127.0.0.1:6379> PFCOUNT hll3
(integer) 6

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan Redis menggunakan HyperLogLog. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!