Pengantar Struktur Data Redis:Bitmap

Bitmaps (juga disebut bit arrays, bit vectors, dll.) adalah struktur data yang langsung muncul di kepala Anda saat Anda perlu memetakan informasi boolean untuk domain besar menjadi kompak perwakilan. Ini adalah struktur data yang sangat populer setiap kali ruang memori berada pada tingkat premium:kernel OS (halaman memori, inode, dll), pencitraan digital, dll.

Redis, sebagai server struktur data dalam memori, menyediakan dukungan untuk operasi manipulasi bit. Namun, tidak ada struktur data khusus untuk Bitmap di Redis. Sebaliknya, operasi tingkat bit didukung pada struktur Redis dasar:Strings. Sekarang, panjang maksimum string Redis adalah 512 MB. Dengan demikian, domain terbesar yang dapat dipetakan Redis sebagai Bitmap adalah 2 (512 MB =2 byte =2 bit).

Operasi terkait bit di Redis terdiri dari dua jenis:Waktu konstan (O(1)) mis. operasi untuk mendapatkan/mengatur bit tertentu dan operasi yang O(N) yang pada dasarnya beroperasi pada sekelompok bit. N dalam kasus ini adalah panjang bit yang perlu dikerjakan oleh operasi. Mari kita lihat beberapa contohnya.

Perintah

# SETBIT key offset value: Store bit value 'value' at offset 'offset' for 'key'. O(1)
# Returns the original bit value stored at that offset.
127.0.0.1:6379> setbit k 10 1
(integer) 0
# GETBIT key offset: Fetch value of 'offset' in 'key'. O(1)
127.0.0.1:6379> getbit k 10
(integer) 1
127.0.0.1:6379> getbit k 11
(integer) 0
127.0.0.1:6379> getbit k 0
(integer) 0
127.0.0.1:6379> setbit k 9 1
(integer) 0
127.0.0.1:6379> setbit k 8 1
(integer) 0
# And since it is still a generic String, here's a get.
127.0.0.1:6379> get k
"\x00\xe0"
# "\x00\xe0" -> "0000 0000 111"
# BITCOUNT key [start end]: Number of set bits in the range. O(N)
# IMPORTANT: start & end are bytes not bits
127.0.0.1:6379> bitcount k
(integer) 3
127.0.0.1:6379> set m "meow"
OK
# meow -> 01101101 01100101 01101111 01110111 
127.0.0.1:6379> bitcount m
(integer) 21
# BITPOS key bit [start] [end]: 1st position of 1 or 0 in the key in range. O(N)
127.0.0.1:6379> SET mykey "\xff\xf0\x00"
OK
127.0.0.1:6379> BITPOS mykey 0
(integer) 12

Selain ada operator yang bekerja pada kunci itu sendiri, BITOP operator digunakan untuk operasi logika bit-bijaksana antara beberapa kunci.

# BITOP operation destkey key [key ...]. O(N)
# operation can be  AND, OR, XOR and NOT
127.0.0.1:6379> set a "\xff\xff"
OK
127.0.0.1:6379> bitop not nota a
(integer) 2
127.0.0.1:6379> get nota
"\x00\x00"
127.0.0.1:6379> set b "\x0f\x0f"
OK
127.0.0.1:6379> set c "\xf0\xf0"
OK
127.0.0.1:6379> BITOP OR orbc b c
(integer) 2
127.0.0.1:6379> get orbc
"\xff\xff"
127.0.0.1:6379> BITOP AND andbc b c
(integer) 2
127.0.0.1:6379> get andbc
"\x00\x00"
127.0.0.1:6379> BITOP XOR xorbc b c
(integer) 2
127.0.0.1:6379> get xorbc
"\xff\xff"

Internal

Karena operasi bitmap tidak memiliki struktur datanya sendiri, tidak ada struktur data khusus untuk dijelaskan. String Redis sendiri diimplementasikan sebagai string aman biner. Struktur data string redis secara internal disebut Simple Dynamic String (SDS). Ini pada dasarnya adalah char [] asli dengan beberapa informasi pembukuan tambahan. Detail implementasi dapat ditemukan di sini.

Implementasi fungsi bitmap ada di file bitops.c .

P.S.:Mengingat pentingnya algoritma manipulasi bit untuk OS kritis dan fungsionalitas grafis, sebagian besar arsitektur menyediakan instruksi khusus untuk operasi semacam itu. Tempat yang bagus untuk membaca berbagai algoritme aritmatika komputer yang menarik adalah Hacker's Delight klasik yang tak lekang oleh waktu.

Aplikasi

Blog GetSpool yang populer ini adalah contoh bagus penggunaan bitmap untuk analisis waktu nyata pada kumpulan data yang besar. Ini juga merupakan contoh kasus penggunaan klasik bitmap:untuk menyimpan informasi boolean dari domain yang sangat besar ke dalam ruang (relatif) kecil sambil mempertahankan kinerja yang layak.

Ukuran biasanya menjadi perhatian untuk bitmap yang sangat besar, karena operasi yang paling berguna di atasnya adalah O(N). Untuk menghindari bekerja dengan kunci besar, dokumentasi Redis merekomendasikan untuk membagi kunci besar menjadi beberapa yang lebih kecil. Performa BITCOUNT tetap dapat diterima hingga kuncinya menjadi besar. Pada saat itu, rekomendasinya adalah membagi kunci atau menggunakan argumen rentang untuk kueri secara bertahap. Rekomendasi untuk menangani operasi BITOP yang lambat adalah dengan menjalankannya pada slave. Jadi, secara umum masuk akal untuk menangani kunci berukuran sedang dan merencanakan potensi pertumbuhan di masa depan dengan membagi kunci menjadi beberapa kunci.

 Set Redis vs Redis Bitmap

Sifat fungsionalitas yang disediakan oleh Redis Sets dan operasi bitmap serupa. Jadi sering membingungkan mana dari dua pendekatan yang lebih baik. Yah, itu benar-benar tergantung pada sifat pasti dari use case. Jelas, diskusi ini hanya valid untuk jenis operasi yang dapat dicapai oleh set dan bitmap.

Set Redis secara umum efisien dan berskala baik dan harus menjadi struktur data pilihan sampai ukurannya menjadi tidak dapat dipertahankan. Redis Sets juga lebih mudah untuk dikelola, program dan debug akan bekerja dengan baik untuk sebagian besar aplikasi. Kemudahan penggunaan Set tidak boleh diremehkan:Kode yang memanipulasi bitmap biasanya sulit dibaca, dipahami, di-debug, dan dipelihara. Bahkan ketika domainnya sangat besar, set mungkin masih sesuai. Untuk misalnya jika aplikasi dimaksudkan untuk melacak kunjungan harian ke situs e-niaga populer, hasilnya mungkin masih cocok dengan kumpulan karena biasanya hanya 5-10% dari seluruh basis pengguna yang akan mengunjungi situs setiap hari. Ini jelas berubah untuk situs di mana 60% dari seluruh basis pengguna diharapkan untuk masuk setiap hari. Kemudian bitmap menjadi lebih relevan mengingat ukuran dan kinerja operasi logika bit bijaksana pada sejumlah besar kunci. Redis Sets juga memiliki keuntungan tersendiri karena tidak perlu memetakan ID ke bit offset. Demikian pula, jika nilai Anda berasal dari domain yang lebih besar dari 2, maka Set Redis harus lebih mudah digunakan daripada mencari tahu mekanisme untuk membagi domain untuk bitmap.

Analitik untuk MOOC

Ini adalah contoh yang dibuat (tapi cukup nyata!) untuk tempat di mana seseorang dapat menerapkan operasi bitmap Redis. Katakanlah, Anda menjalankan MOOC online yang sangat populer yang diikuti oleh ratusan ribu siswa. Tim akademik yang memfasilitasi kursus menginginkan dashboard yang dapat melihat status kemajuan siswa secara real time serta latar belakang umum siswa yang terdaftar. Anda memutuskan untuk menerapkan ini melalui operasi bitmap Redis. Inilah pendekatan langkah demi langkah untuk itu.

1. Buat rencana untuk memetakan antara ID siswa ke offset bitmap. Ini bisa sesederhana ID yang menjadi offset dalam bitmap.
2. Buat dan isi berbagai bitmap terkait demografis setelah kursus dimulai. Untuk misalnya siswa yang terdaftar di MOOC lain dari universitas yang sama, tingkat pendidikan, jenis kelamin, dll.
3. Sekarang saat kursus berlangsung, Anda dapat membuat bitmap baru untuk merekam kemajuan kursus. Untuk misalnya siswa yang selesai menonton semua kuliah minggu 1, siswa yang menyelesaikan semua tugas minggu 1. dll.
4. Sekarang, membuat analisis waktu nyata berdasarkan tombol-tombol ini akan menjadi latihan yang sangat sederhana dan dapat dilakukan pada UI seret dan lepas. Misalnya

• Seorang profesor yang ingin melihat berapa banyak siswa yang menonton kuliah selama minggu 1 (A) tetapi tidak menyelesaikan tugas untuk minggu 1 (B):Operator:BITOP. Operasi:A DAN (BUKAN B).
• Siswa yang menyelesaikan semua tugas untuk minggu 1 (A), minggu 2 (B), minggu 3 (C) dan minggu 4 (D):Operator:BITOP. Operasi A DAN B DAN C DAN D. Katakanlah, ini adalah orang-orang yang lulus kursus.
• Semua siswa laki-laki (L) yang lulus kursus (seperti yang dihitung di atas, katakanlah, P):Operator:BITOP. Operasi:M DAN P.
• Jumlah siswa yang lulus kursus:BITCOUNT P.

Demikian pula, sejumlah kohort yang menarik dapat disetel sebagai bitmap dan permutasi semacam itu dijalankan di atasnya.

Catatan kaki

Pos lain dalam seri struktur data Redis kami:

• Set
• Hash
• Kumpulan yang Diurutkan