Redisで最新更新されたN件を実装

redis

たとえば最近更新されたN件を表示させるには

  • 最近更新したアイテムほど上位に表示
  • 下位にあるアイテムも、更新すれば最上位に表示
  • 同じアイテムは重複して表示しない
  • N件を超えると古いものから順に破棄

といったことが必要になる。

このデータ構造を Redis のデータ型 Sorted Set で実装する方法をメモ。

Sorted Set を少し触ってみる

Redis のデータ型 sorted set は文字通り順序付けられた集合で Z で始まるコマンドを使ってデータを操作する。

ZADD key score member のシンタックスで集合のメンバーを追加
計算量は O(log(N))

redis> ZADD myzset 1 foo
(integer) 1
redis> ZADD myzset 2 bar
(integer) 1
redis> ZADD myzset 3 baz
(integer) 1

myzset 集合のメンバーを score でソート

redis> ZRANGE myzset 0 -1 WITHSCORES
1) "foo"
2) "1"
3) "bar"
4) "2"
5) "baz"
6) "3"

メンバー baz のスコアを3から1に変更

redis> ZADD myzset 1 baz
(integer) 0

myzset 集合のメンバーを score のランキング順で再ソート

redis> ZRANGE myzset 0 -1 WITHSCORES
1) "baz"
2) "1"
3) "foo"
4) "1"
5) "bar"
6) "2"

集合なのでメンバー baz は重複登録されず、スコアが 2 のメンバー bar よりも上位に表示されている。

Sorted Set で 最近のN件を実装

音楽再生サイトを運営しているとして、この Sorted Set を使って最近再生された曲N件を実装してみる。
まずは再生するたびに UNIX TIME を score に設定して楽曲をメンバーに ZADD する。

redis> zadd music 0 "Anyway"
(integer) 1
redis> zadd music 10 "Cuckoo Cocoon"
(integer) 1
redis> zadd music 15 "In the Cage"
(integer) 1
redis> zadd music 20 "Back in N.Y.C."
(integer) 1
redis> zadd music 30 "The Lamia"
(integer) 1

SCORE で並べると

redis> ZRANGE music 0 -1 WITHSCORES
 1) "Anyway"
 2) "0"
 3) "Cuckoo Cocoon"
 4) "10"
 5) "In the Cage"
 6) "15"
 7) "Back in N.Y.C."
 8) "20"
 9) "The Lamia"
10) "30"

というように時系列に並んでいる。

最新をより上位に表示させるために、 ZREVRANGE で SCORE を降順(REV=reverse)にする。(SCORE は UNIX TIME なので値が大きいほど最新)

redis> ZREVRANGE music 0 -1 WITHSCORES
 1) "The Lamia"
 2) "30"
 3) "Back in N.Y.C."
 4) "20"
 5) "In the Cage"
 6) "15"
 7) "Cuckoo Cocoon"
 8) "10"
 9) "Anyway"
10) "0"

Cuckoo Cocoon をもう一回再生させる

redis> zadd music 50 "Cuckoo Cocoon"
(integer) 0

当然 Cuckoo Cocoon は最上位に表示されるようになる。

redis> ZREVRANGE music 0 -1 WITHSCORES
 1) "Cuckoo Cocoon"
 2) "50"
 3) "The Lamia"
 4) "30"
 5) "Back in N.Y.C."
 6) "20"
 7) "In the Cage"
 8) "15"
 9) "Anyway"
10) "0"

最新3件を表示したい場合、ランキング指定で 0 から 2 までを指定する

redis> ZREVRANGE music 0 2 WITHSCORES
1) "Cuckoo Cocoon"
2) "50"
3) "The Lamia"
4) "30"
5) "Back in N.Y.C."
6) "20"

ZADD を繰り返すと、集合がぶくぶく膨れ上がるので、古いデータは削除させる。

ZCARD で集合の基数(cardinality)を確認

redis> ZCARD music
(integer) 5

最近3件だけが欲しい場合、古い5-3=2件はいらない。
SCORE が低い2件を削除する。
ZREMRANGEBYRANK を使ってランク指定で削除する(ZREMRANGEBYRANK には REVERSE 版は存在しない)

redis> ZREMRANGEBYRANK music 0 1
(integer) 2

削除後の集合を確認

redis> ZCARD music
(integer) 3
redis> ZREVRANGE music 0 -1 WITHSCORES
1) "Cuckoo Cocoon"
2) "50"
3) "The Lamia"
4) "30"
5) "Back in N.Y.C."
6) "20"

最新の3件だけが残った。
めでたしめでたし

注意

SCOREが重複しているとき

redis> ZADD test 0 a
(integer) 1
redis> ZADD test 0 b
(integer) 1
redis> ZADD test 1 c
(integer) 1
redis> ZRANGE test 0 -1 WITHSCORES
1) "a"
2) "0"
3) "b"
4) "0"
5) "c"
6) "1"

というように SCORE が重複していることを考える。

redis> ZRANGE test 0 0 WITHSCORES
1) "a"
2) "0"
redis> ZRANGE test 0 1 WITHSCORES
1) "a"
2) "0"
3) "b"
4) "0"

というように SCORE が重複していても、RANK はかぶらない。

redis> ZREMRANGEBYRANK test 0 0
(integer) 1
redis> ZRANGE test 0 -1 WITHSCORES
1) "b"
2) "0"
3) "c"
4) "1"

というようにランク指定する start/stop が同じであれば、1メンバーだけが削除される。

SCOREに整数以外も指定可能

redis> ZADD test 0 a
(integer) 1
redis> ZADD test 0.1 b
(integer) 1
redis> ZRANGE test 0 -1 WITHSCORES
1) "a"
2) "0"
3) "b"
4) "0.10000000000000001"

今回のケースであれば、UNIX TIME にミリ秒を指定してもよい。

List 型を使った場合

楽曲再生のたびに LREM & LPUSH のコンボでリストの先頭に最新楽曲がいるようにすればリスト型でも実現できるけれども、Sorted Set を使ったほうがスマートだと思う。

Tagged with: ,
Posted in database

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners. docs.google.com/presentation/d… /cc @inwyrd 1 week ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 3 weeks ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 3 weeks ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 6 months ago
  • RT @mattcutts: Google's world-class Site Reliability Engineering team wrote a new book: amazon.com/Site-Reliabili… It's about managing produc… 9 months ago
%d bloggers like this: