Cara menggunakan algoritma HyperLogLog Redis

Anda dengan senang hati bermalas-malasan, tetapi pengurus produk menghantar dokumen keperluan kepada anda melalui e-mel. Syarikat itu perlu menyimpan statistik jangka panjang pada IP pelawat harian tapak web, dan masa statistik mungkin bertahan selama berbulan-bulan atau bahkan bertahun-tahun.

Selepas membaca keperluan, anda akan fikir ini sangat mudah Anda boleh melaksanakan fungsi ini dengan mudah menggunakan jenis koleksi Redis: menjana kunci jenis koleksi setiap hari, gunakan SADD untuk menyimpan IP pelawat harian, dan. gunakan arahan SCARD untuk mendapatkan bilangan IP pelawat setiap hari dengan mudah.

Anda cepat selesai menaip kod dan lulus ujian, dan fungsi itu dalam talian. Selepas pergi dalam talian dan berjalan untuk seketika, anda akan mendapati bahawa pelayan di mana Redis berada mula penggera Sebabnya ialah penggunaan memori bagi beberapa kekunci terlalu besar yang menyimpan IP pelawat. Selepas itu baru anda menepuk kepala anda, mengetahui bahawa anda telah menggali lubang besar untuk diri anda sendiri.

Anggapkan bahawa menyimpan alamat IP dalam format IPv4 mengambil masa sehingga 15 bait dan tapak web tersebut mempunyai sehingga 1 juta pelawat setiap hari. Kekunci set ini akan menggunakan memori 0.45 GB sebulan dan memori 5.4 GB setahun Ini hanya anggaran format IPv4 Jika format IPv6 akan menduduki lebih banyak memori. Walaupun kerumitan masa SADD dan SCARD ialah O(1), penggunaan ingatan mereka tidak boleh diterima.

Anda melayari laman web rasmi Redis dan mendapati bahawa Redis juga menyediakan jenis data HyperLogLog, yang bukan sahaja dapat memenuhi keperluan produk tetapi juga menduduki kurang memori.

Algoritma HyperLogLog

HyperLogLog ialah algoritma probabilistik yang dicipta khusus untuk mengira kardinaliti set. Ia boleh mengira anggaran kardinaliti set tertentu.

Kardinaliti anggaran bukanlah kardinaliti sebenar set Ia mungkin lebih kecil sedikit atau lebih besar daripada kardinaliti sebenar, tetapi ralat antara kardinaliti anggaran dan kardinaliti sebenar akan berada dalam julat yang munasabah mereka yang tidak memerlukan statistik yang sangat tepat boleh dicapai menggunakan algoritma HyperLogLog.

Kelebihan HyperLogLog ialah memori yang diperlukan untuk mengira kardinaliti anggaran tidak berubah kerana saiz set Tidak kira berapa banyak elemen yang terkandung dalam set, memori yang diperlukan untuk mengira HyperLogLog sentiasa tetap , dan sangat sedikit.

Setiap jenis HyperLogLog Redis hanya perlu menggunakan 12KB ruang memori untuk mengira hampir: 2⁶⁴ elemen, dan ralat standard algoritma hanya 0.81%.

Jika anda menggunakan jenis HyperLogLog untuk melaksanakan fungsi di atas, jika terdapat 1 juta pelawat setiap hari, ia hanya akan menduduki 360KB memori dalam satu bulan.

PFADD

Arahan PFADD boleh mengira satu atau lebih elemen set yang diberikan.

PFADD key element [element...]

Bergantung pada sama ada elemen yang diberikan telah dikira, arahan PFADD boleh mengembalikan 0 atau 1:

• Jika Jika semua elemen yang diberikan telah dikira, arahan PFADD akan mengembalikan 0, menunjukkan bahawa kardinaliti anggaran yang dikira oleh HyperLogLog tidak berubah.

• Arahan PFADD akan mengembalikan 1 jika kardinaliti anggaran yang dikira oleh HyperLogLog berubah disebabkan kehadiran sekurang-kurangnya satu elemen dalam elemen tertentu yang belum dikira sebelum ini.

Contohnya:

redis> PFADD letters a b c -- 第一次添加
(integer) 1
redis> PFADD letters a     -- 第二次添加
(integer) 0

Ia juga mungkin untuk menentukan kunci sahaja tanpa menyatakan elemen semasa memanggil arahan ini Jika kunci itu wujud, tiada operasi . Jika ia tidak wujud, struktur data akan dibuat (kembali 1).

PFCOUNT

Gunakan arahan PFCOUNT untuk mendapatkan kardinaliti yang ditetapkan berdasarkan pengiraan anggaran HyperLogLog. Jika kunci yang diberikan tidak wujud, 0 akan dikembalikan.

PFCOUNT key [key...]

Contohnya:

redis> PFCOUNT letters
(integer) 3

Apabila berbilang HyperLogLog dihantar ke PFCOUNT, arahan PFCOUNT akan mula-mula mencari kesatuan semua HyperLogLogs, dan kemudian mengembalikan anggaran asas .

redis> PFADD letters1 a b c
(integer) 1
redis> PFADD letters2 c d e
(integer) 1
redis> PFCOUNT letters1 letters2
(integer) 5

PFMERGE

Arahan PFMERGE boleh melakukan pengiraan kesatuan pada berbilang HyperLogLog, dan kemudian simpan HyperLogLog kesatuan yang dikira pada kekunci yang ditentukan.

PFMERGE destKey sourceKey [sourceKey...]

Jika kunci yang ditentukan sudah wujud, arahan PFMERGE akan menimpa kekunci sedia ada.

redis> PFADD letters1 a b c
(integer) 1
redis> PFADD letters2 c d e
(integer) 1
redis> PFMERGE res letters1 letters2
OK
redis> PFCOUNT res
(integer) 5

Anda boleh melihat bahawa arahan PFMERGE dan PFCOUNT adalah sangat serupa Malah, arahan PFCOUNT melakukan operasi berikut apabila mengira asas anggaran berbilang HyperLogLog:

• dipanggil secara dalaman Perintah PFMERGE mengira penyatuan semua HyperLogLog yang diberikan dan menyimpan kesatuan itu ke dalam HyperLogLog sementara.

• Laksanakan arahan PFCOUNT pada HyperLogLog sementara untuk mendapatkan kardinaliti anggarannya.

• Padamkan HyperLogLog sementara.

• Mengembalikan pangkalan anggaran yang terhasil.

Apabila program perlu memanggil arahan PFCOUNT pada berbilang HyperLogLogs, dan panggilan ini mungkin diulang beberapa kali, anda boleh mempertimbangkan untuk menggantikan panggilan ini dengan panggilan arahan PFMERGE yang sepadan: dengan menggabungkan keputusan pengiraan disimpan dalam HyperLogLog yang ditentukan dan bukannya mengira semula kesatuan setiap kali, dan program boleh meminimumkan pengiraan kesatuan yang tidak perlu.

Senario Perniagaan

Ciri HyperLogLog sangat sesuai untuk: pengiraan (statistik bulanan, tahunan), penyahduplikasi (pengesanan SMS spam) dan senario lain.

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