Redis
 sql >> Teknologi Basis Data >  >> NoSQL >> Redis

Pengantar Struktur Data Redis:Kumpulan yang Diurutkan

Sorted Set adalah beberapa struktur data paling canggih di Redis. Kumpulan yang diurutkan pada dasarnya adalah kumpulan unik dari String Redis terurut yang memiliki skor numerik yang terkait dengannya. Pengurutan didasarkan pada skor dan urutan leksikografis string (lebih lanjut tentang ini nanti). Senar harus unik sementara skor dapat diulang.

Selain Daftar, ini adalah satu-satunya yang dipesan struktur data di Redis dan lebih disukai daripada Daftar ketika akses ke bagian mana pun dari daftar itu penting (tidak seperti Daftar yang menyediakan akses ke ujung daftar). Penyisipan, penghapusan, dan pencarian kasus rata-rata dalam himpunan terurut adalah O(N), di mana N adalah jumlah elemen dalam himpunan.

Penyortiran

Skor dalam kumpulan yang diurutkan adalah angka floating point 64-bit ganda dalam kisaran -(2^) dan +(2^) disertakan. Set yang diurutkan diurutkan berdasarkan skor mereka dalam urutan menaik. Skor dapat diperbarui untuk kunci yang ada. Untuk memutuskan ikatan skor, string dalam set yang diurutkan diurutkan secara leksikografis dalam urutan menaik. Di Redis 2.8, fitur baru diimplementasikan untuk mengeksploitasi urutan leksikografis ini:kueri rentang leksikografis. Ini memiliki kasus penggunaan yang menarik yang akan kita lihat nanti.

Perintah

Set yang diurutkan ulang mendukung berbagai operasi dari set sederhana, dapatkan, jumlah anggota hingga penghitungan rentang leksikografis yang kompleks. Ada sekitar 25+ operasi yang didukung. Kami akan melihat subset dari mereka. Mari kita mulai dengan yang dasar:

# ZADD key [NX|XX] [CH] [INCR] score member [score member ...] Add elements into the set
# O(log(N) where N is the number of elements in the set
# [NX|XX], [CH] & [INCR] available on > 3.0.2
127.0.0.1:6379> zadd scoreboard 999 "anorak"
(integer) 1
# Analogous: use ZREM key member [member ...] to remove members from a sorted set.
# ZCARD key O(1): Cardinality of the set
127.0.0.1:6379> zcard scoreboard
(integer) 1
# Insert multi
127.0.0.1:6379> zadd scoreboard 99 "daito" 99 "shoto" 199 "aech" 299 "art3mis" 399 "parzival"
(integer) 5
# ZSCORE key member. O(1) Returns the score of member in the sorted set at key.
127.0.0.1:6379> zscore scoreboard parzival
"399"
# ZRANK key member O(log(N)) Get the rank of the member.
127.0.0.1:6379> zrank scoreboard anorak
(integer) 5
127.0.0.1:6379> zrank scoreboard shoto
(integer) 1
# ZREVRANK key member O(log(N)) Get the rank of the member with scores ordered high to low
127.0.0.1:6379> zrevrank scoreboard anorak
(integer) 0
127.0.0.1:6379> zrevrank scoreboard shoto
(integer) 4
# ZINCRBY key increment member O(log(N)) Increments the score of member in the sorted set stored at key by increment.
127.0.0.1:6379> zincrby scoreboard 100 parzival
"499"

Yang di atas adalah beberapa operasi dasar yang mungkin dilakukan pada kumpulan yang diurutkan. Nilai sebenarnya dari kumpulan yang diurutkan bersinar dalam rentangnya berdasarkan kueri dalam kumpulan tersebut. Mari kita lihat mereka.

# ZRANGE key start stop [WITHSCORES]. O(log(N)+M) with N being the number of elements in the sorted set and M the number of elements returned.
# start and stop are inclusive zero based indexes.
127.0.0.1:6379> zrange scoreboard 0 -1 WITHSCORES
 1) "daito"
 2) "99"
 3) "shoto"
 4) "99"
 5) "aech"
 6) "199"
 7) "art3mis"
 8) "299"
 9) "parzival"
10) "499"
11) "anorak"
# 0: 1st member. -1: last member
# Analogous: ZREVRANGE key start stop [WITHSCORES]
127.0.0.1:6379> zrevrange scoreboard 0 -1 WITHSCORES
 1) "anorak"
 2) "999"
 3) "parzival"
 4) "499"
 5) "art3mis"
 6) "299"
 7) "aech"
 8) "199"
 9) "shoto"
10) "99"
11) "daito"
12) "99"
# ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]. O(log(N)+M) Returns all the elements in the sorted set at key with a score between min and max (inclusive)
# Analogous: ZREVRANGEBYSCORE key max min [WITHSCORES] [LIMIT offset count]
# 499 <= score <= +inf 127.0.0.1:6379> zrangebyscore scoreboard 499 +inf
1) "parzival"
2) "anorak"
# 499 < score <= +inf 127.0.0.1:6379> zrangebyscore scoreboard (499 +inf
1) "anorak"
# ZCOUNT key min max O(log(N)) Returns the number of elements in the sorted set at key with a score between min and max.
127.0.0.1:6379> zcount scoreboard -inf 499
(integer) 5
127.0.0.1:6379> zcount scoreboard -inf +inf
(integer) 6

Perintah terkait rentang serupa lainnya adalah ZREMRANGEBYRANK, ZREMRANGEBYSCORE, dll.

Ada set perintah kueri lain yang diperkenalkan di Redis 2.8:perintah rentang leksikografis (*BYLEX). Detail tentang bagaimana interval ditentukan untuk perintah ini didokumentasikan di sini. Persyaratan agar perintah ini berfungsi dengan benar adalah bahwa anggota himpunan yang diurutkan harus memiliki skor yang sama. Perintah utama untuk beroperasi dengan rentang leksikografis adalah ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX, dan ZLEXCOUNT. Mari kita lihat beberapa contohnya:

127.0.0.1:6379> zadd lexscores 0 dd 0 aa 0 ccc 0 aaa 0 bb 0 d 
(integer) 6
# Once inserted, lexicographic sorting for free!
127.0.0.1:6379> zrange lexscores 0 -1
1) "aa"
2) "aaa"
3) "bb"
4) "ccc"
5) "d"
6) "dd"
# ZRANGEBYLEX key min max [LIMIT offset count]. O(log(N)+M). min max specify range. LIMIT is like limit in SQL.
# min: exclude a max: exclude c
127.0.0.1:6379> ZRANGEBYLEX lexscores (a (c
1) "aa"
2) "aaa"
3) "bb"
# min: exclude a max: include c
127.0.0.1:6379> ZRANGEBYLEX lexscores (a [c
1) "aa"
2) "aaa"
3) "bb"
# min: exclude a max: include ccc
127.0.0.1:6379> ZRANGEBYLEX lexscores (a [ccc
1) "aa"
2) "aaa"
3) "bb"
4) "ccc"
# min: exclude aa max: include cccc
127.0.0.1:6379> ZRANGEBYLEX lexscores (aa [ccc
1) "aaa"
2) "bb"
3) "ccc"
# min: exclude aa max: upto all
127.0.0.1:6379> ZRANGEBYLEX lexscores (aa +
1) "aaa"
2) "bb"
3) "ccc"
4) "d"
5) "dd"

Satu lagi kumpulan perintah untuk kumpulan yang diurutkan adalah operasi gabungan dan persimpangan.

Internal

Set yang diurutkan diimplementasikan sebagai struktur data ganda:Ini adalah kombinasi dari daftar hash dan skip. Bagian hash memetakan objek ke skor dan daftar lewati memetakan skor ke objek. Kami sudah tahu bagaimana hash diimplementasikan di Redis dari posting kami sebelumnya. Daftar Lewati memastikan bahwa pencarian dilakukan dengan cepat dan sebagian besar operasi rata-rata adalah O(log N). Daftar Lewati diimplementasikan di file t_zset.c.

Seperti kebanyakan struktur data Redis lainnya, bahkan kumpulan yang Diurutkan dioptimalkan untuk ukuran ketika mereka kecil. Set yang diurutkan disimpan hanya sebagai hash sampai mereka tumbuh ke ukuran tertentu. Parameter konfigurasi yang mengontrol ukuran ini adalah: zset-max-ziplist-entries (default 128) dan zset-max-ziplist-value (default 64).
Estimasi ukuran:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

Aplikasi

Sebagai struktur data tingkat lanjut, kumpulan yang diurutkan memiliki kasus penggunaan yang bervariasi:

  1. Kasus penggunaannya yang paling jelas adalah sebagai papan skor:mempertahankan daftar anggota unik yang diurutkan berdasarkan skor mereka. Untuk misalnya papan skor pemimpin untuk MMORPG seperti yang dijelaskan dalam dokumentasi resmi Redis.
  2. Set yang diurutkan dengan skor identik digunakan sebagai indeks di Redis. Ini dapat berkisar dari kasus penggunaan yang sangat sederhana hingga yang sangat kompleks. Dokumentasi Redis memiliki artikel bagus tentang Pengindeksan menggunakan kumpulan yang diurutkan.
  3. Kasus khusus pengindeksan menggunakan kumpulan yang diurutkan adalah API GEO untuk Redis yang diperkenalkan di Redis 3.2.0.
  4. Ukuran adalah pertimbangan saat menggunakan kumpulan yang diurutkan. Mengingat struktur data pendukung yang kompleks, kumpulan yang diurutkan akan memiliki jejak memori yang relatif lebih besar. Angka yang tepat akan tergantung pada sifat kumpulan data. Postingan StackOverflow ini menyebutkan nomor kasar untuk kumpulan data berukuran layak.

Karena set yang diurutkan memiliki kasus penggunaan yang cukup lanjut, kami akan membahas kasus penggunaan tersebut untuk set yang diurutkan di posting berikutnya. Untuk saat ini, mari kita lihat contoh sederhana.

Gamify MOOC Anda!

Dalam posting kami sebelumnya tentang bitmap Redis, kami adalah pengembang yang mendukung MOOC yang sangat populer. Fasilitator memutuskan bahwa mereka ingin mengatur kursus dengan papan pemimpin yang melacak siswa terbaik yang berkontribusi pada pos komunitas. Siswa dengan jumlah jawaban teratas yang diterima untuk masalah yang diposting di posting komunitas kursus akan menerima perhatian khusus setiap minggu.
Ini akan menjadi kasus penggunaan klasik untuk pengurutan kunci unik berbasis skor alias kumpulan Redis yang diurutkan. ID siswa akan menjadi anggota sedangkan skor akan jumlah jawaban yang diterima. Kami mungkin memperbarui skor menggunakan ZINCRBY dalam waktu nyata atau dalam pekerjaan latar belakang yang dapat dijalankan setiap hari atau setiap minggu. Jelas memperbarui skor secara real time diperlukan untuk kasus penggunaan kami. Untuk penyisipan awal ZADD dengan salah satu bendera baru akan berguna. Menampilkan papan skor kepada siswa perlu menggunakan kueri rentang terbalik (ZREVRANGE dll)

Catatan kaki

Pos lain dalam seri struktur data Redis kami:

  • Set
  • Hash
  • Bitmap

  1. Redis
    2.   
  2. MongoDB
    3.   
  3. Memcached
    4.   
  4. HBase
    5.   
  5. CouchDB

  1. redis-py :Apa perbedaan antara StrictRedis() dan Redis()?

  2. Redis zrevrangebyscore, pengurutan selain urutan leksikografis

  3. Menggunakan redis dengan node.js (ekspres)

  4. Alternatif untuk Struktur Bersarang di Redis?

  5. Query Gabungan dengan Redis