Analisis ringkas HyperLogLog untuk pembelajaran jenis data Redis

Artikel ini akan membawa anda memahami HyperLogLog dalam jenis data Redis, yang biasanya digunakan untuk mengira bilangan elemen unik dalam koleksi saya harap ia akan membantu anda!

Hari ini adalah hari Jumaat, anda sedang memancing dengan gembira, dan pengurus produk menghantar dokumen keperluan kepada anda melalui e-mel. Permintaan itu mungkin: syarikat perlu mengira IP pelawat harian tapak web, dan statistik ini adalah tingkah laku jangka panjang, antara beberapa bulan hingga beberapa 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 satu tempoh masa, anda akan mendapati bahawa pelayan di mana Redis berada mula penggera Sebabnya ialah penggunaan memori beberapa kekunci terlalu besar tetapkan kunci 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. [Cadangan berkaitan: Tutorial video Redis]

Algoritma HyperLogLog

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

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 disebabkan 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 elemen yang diberikan Semua elemen mempunyai telah dikira, maka 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 boleh dilakukan jika anda hanya menentukan kunci tanpa menyatakan elemen semasa memanggil arahan ini Jika kunci itu wujud, tiada operasi . Jika tidak wujud, struktur data akan dibuat (kembali 1).

PFCOUNT

Anggaran kardinaliti yang dikira oleh HyperLogLog untuk koleksi boleh diperolehi melalui arahan PFCOUNT. 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:

• Dalam Perintah PFMERGE dipanggil secara dalaman untuk mengira kesatuan semua HyperLogLog yang diberikan dan menyimpan kesatuan 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 (pengesan SMS spam) dan senario lain.

Untuk lebih banyak pengetahuan berkaitan pengaturcaraan, sila lawati: Pengenalan kepada Pengaturcaraan! !

Atas ialah kandungan terperinci Analisis ringkas HyperLogLog untuk pembelajaran jenis data Redis. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!