RedisのSorted setsを用いたランキング機能とその性能計測

# Redisとは
Redisとは，Key-Value型のインメモリデータベースである．
インメモリデータベースであるため，データは永続化されないが[^1]，MySQLなどよりも高速に読み書きをすることができる．
Key-ValueのValueには，Strings(文字列)だけではなく，Lists(リスト)やSets(集合)など様々なデータ構造を用いることができる．
[^1]: スナップショットなどを用いることで永続化のような機能を果たすこともできる
## Sorted setsとは
Sorted setsとは，データ構造の一種であり，ある規則に従ってソートされていることが特徴である．
Valueとしては，以下の2つの情報を保存する．

- Member: 文字列
- Score: 数値

保存された情報は，次の規則に従ってソートされる．
AとBに対して，

1. A.Score > B.Score であれば，A > B となる
1. A.Score = B.Score であれば，それぞれのMemberを参照し，A.Member > B.Member (辞書式)であれば，A > B となる

ここで，Memberは一意であるため，上の規則に従えば，ソート順は一意に定まる．

例えば，あるKeyに対して，以下のValueを保存した場合を考える．

```
{Member: "user1", Score: 100}
{Member: "user2", Score: 90}
{Member: "user3", Score: 100}
```
このとき，次のようにソートされて保存される．

```
{Member: "user2", Score: 90}
{Member: "user1", Score: 100}
{Member: "user3", Score: 100}
```
# ランキング機能の実装
以下ではGo言語を用いて実装を行い，Go言語のRedisクライアントは`go-redis`を用いることとする．
ランキング情報として以下の3つの情報を保持することを考える．

```go
type User struct {
	ID        string
	Name      string
	HighScore int
}
```
以下で出てくるコードは全て[ここ](https://github.com/arkuchy/redis-ranking)に置いてあるので参考にしてください．
## ランキングへの追加
大まかな流れとしては，以下の通りである．

1. Memberとして保存したいデータをJSON文字列にエンコードする
1. `ZADD`コマンドを用いて，Sorted setsにデータを追加する

### JSON文字列へのエンコード
今回，Memberとして保存したいデータは`ID`と`Name`なので，それらを持つ構造体を定義する．

```go
// userIDとuserNameを持った構造体(json文字列にして扱う)
type Member struct {
	ID   string `json:"id"`
	Name string `json:"name"`
}
```
そして，`encoding/json.Marshal`を用いてJSON文字列に変換すれば良い．

```go
member := &Member{
	ID:   id,
	Name: name,
}
// memberをserializeする
serializedMember, err := json.Marshal(member)
```

### ZADDコマンド
ZADDコマンドとは，Sorted setsにデータを追加するときのコマンドである．
`go-redis`では，以下のようなメソッドが定義されている．

```go:go-redis/redis/v8/commands.go
// Redis `ZADD key score member [score member ...]` command.
func (c cmdable) ZAdd(ctx context.Context, key string, members ...*Z) *IntCmd {
	// 略
}
```
ここで，`cmdable`とは簡単にRedisとのコネクションと考えてよい．
また，引数の`Z`とは以下のようなMemberとScoreを持つ構造体のことである．

```go:go-redis/redis/v8/commands.go
type Z struct {
	Score  float64
	Member interface{}
}
```

さらに，返り値の`IntCmd`とは，`context.Context`や`error`などを持つ以下のような構造体である．

```go:go-redis/redis/v8/command.go
type IntCmd struct {
	baseCmd

	val int64
}

type baseCmd struct {
	ctx    context.Context
	args   []interface{}
	err    error
	keyPos int8

	_readTimeout *time.Duration
}
```
今回は，`error`が欲しいので，`baseCmd`のメソッドである`Err()`を呼び出し，エラーハンドリングを行えば良い．

```go:go-redis/redis/v8/command.go
func (cmd *baseCmd) Err() error {
	return cmd.err
}
```
### 全体のコード
以上のことから，全体のコードは次のようになる．

```go:arkuchy/redis-ranking/src/redis/ranking.go
package redis

import (
	"context"
	"encoding/json"

	"github.com/arkuchy/redis-ranking/src/db"
	goRedis "github.com/go-redis/redis/v8"
)

const (
	RedisRanking string = "RedisRanking" // key名
)

// userIDとuserNameを持った構造体(json文字列にして扱う)
type Member struct {
	ID   string `json:"id"`
	Name string `json:"name"`
}

// AddRanking は，ランキングにユーザデータを追加します
func AddRanking(ctx context.Context, id string, name string, score int) error {
	conn := db.Conn.GetRedisConn() // Redisとのコネクションを取得(各自作成する必要あり)
	member := &Member{
		ID:   id,
		Name: name,
	}
	// memberをserializeする
	serializedMember, err := json.Marshal(member)
	if err != nil {
		return err
	}
	if err := conn.ZAdd(ctx, RedisRanking, &goRedis.Z{
		Score:  float64(score),
		Member: serializedMember,
	}).Err(); err != nil {
		return err
	}
	return nil
}
```

## ランキングの取得
大まかな流れとしては，以下の通りである．

1. `ZREVRANGE(WITHSCORES)`コマンドを用いて，Sorted setsからデータを取得する
1. 取得したJSON文字列をデコードする

### `ZREVRANGE(WITHSCORES)`コマンド
`ZREVRANGE`コマンドとは，Sorted setsが保持しているMemberを，Scoreの降順から指定した件数だけ取得するコマンドである．
また，Memberだけでなく，Scoreも取得したいときは，`WITHSCORES`というオプションを付ければ良い．
`go-redis`では，以下のようなメソッドが定義されている．

```go:go-redis/redis/v8/commands.go
func (c cmdable) ZRevRangeWithScores(ctx context.Context, key string, start, stop int64) *ZSliceCmd {
	// 略
}
```
ここで，引数の`start, stop`とは，Scoreの降順に並べたとき，「何番目」から「何番目」まで取得するかを表している変数である．ただし，Redisは0始まりであることに注意する．
例えば，ランキング1位から10位まで取得したいときは，`start=0, stop=9`とし，5位から20位まで取得したいときは，`start=4, stop=19`とする．
また，返り値の`ZSliceCmd`とは，`context.Context`や`error`などに加えて，`Z`のスライスを持つ以下のような構造体である．

```go:go-redis/redis/v8/command(s).go
type ZSliceCmd struct {
	baseCmd

	val []Z
}

type baseCmd struct {
	ctx    context.Context
	args   []interface{}
	err    error
	keyPos int8

	_readTimeout *time.Duration
}

type Z struct {
	Score  float64
	Member interface{}
}
```
今回は，`[]Z`と`error`が欲しいので，`ZSliceCmd`のメソッドである`Result()`を呼び出せば良い．

```go:go-redis/redis/v8/command.go
func (cmd *ZSliceCmd) Result() ([]Z, error) {
	return cmd.val, cmd.err
}
```

### JSON文字列のデコード
`ZREVRANGE`を用いて取得したデータは，JSON文字列であるので，それをデコードする．
`encoding/json.Unmarshal`を用いて構造体に変換すれば良い．

```go
member := &Member{
	ID:   id,
	Name: name,
}
err := json.Unmarshal([]byte(serializedMember.(string)), member)
```

### 全体のコード
以上のことから，全体のコードは次のようになる．

```go:arkuchy/redis-ranking/src/redis/ranking.go
package redis

import (
	"context"
	"encoding/json"

	"github.com/arkuchy/redis-ranking/src/db"
	goRedis "github.com/go-redis/redis/v8"
)

const (
	RedisRanking string = "RedisRanking"
)

type UserResponse struct {
	ID        string
	Name      string
	HighScore int
	Rank      int
}

// userIDとuserNameを持った構造体(json文字列にして扱う)
type Member struct {
	ID   string `json:"id"`
	Name string `json:"name"`
}

// GetRankings は，上位{limit}件のユーザデータを返します
func GetRankings(ctx context.Context, limit int) ([]*UserResponse, error) {
	// redisは0始まり
	// ex) 1~10 -> start:0, stop:9
	start := 0
	stop := start + limit - 1
	conn := db.Conn.GetRedisConn() // Redisとのコネクションを取得(各自作成する必要あり)
	serializedMembersWithScores, err := conn.ZRevRangeWithScores(ctx, RedisRanking, int64(start), int64(stop)).Result()
	if err != nil {
		return nil, err
	}
	res := make([]*UserResponse, 0, limit)
	member := &Member{}
	for i, serializedMemberWithScore := range serializedMembersWithScores {
		serializedMember := serializedMemberWithScore.Member // 構造体ZからMemberを取得
		score := serializedMemberWithScore.Score // 構造体ZからScoreを取得
		if err := json.Unmarshal([]byte(serializedMember.(string)), member); err != nil {
			return nil, err
		}
		u := &UserResponse{
			ID:        member.ID,
			Name:      member.Name,
			HighScore: int(score),
			Rank:      i + 1,
		}
		res = append(res, u)
	}
	return res, nil
}
```

# 性能計測
次の2つのランキング取得の方法を，Go言語のBenchmarkを用いて比較する．

- RedisのSorted setsを用いた方法
- MySQLの`Select ~ ORDER BY`を用いた方法(適切にインデックスを張った状態とする)

1000, 5000, 10000の3通りの保持データ数に対して，上位100件のデータを取得するときの性能を計測する．
ただし，実行環境は以下の通りである．

```
CPU: 1.8GHz Intel Core i5
メモリ: 8GB
言語: Golang 1.15.4
```
また，MySQLでのランキング機能の実装は[ここ](https://github.com/arkuchy/redis-ranking/blob/main/src/mysql/ranking.go)に置いてあるので参考にしてください．

## 結果
左側から，

```
実行したベンチマーク名 / 実行した回数 / 1回あたりの実行時間(ns/op) / 1回あたりの確保容量(B/op) / 1回あたりのアロケーション回数(allocs/op) 
```
となっている．

- 保持データ数が1000の場合

```
# Redis
BenchmarkGetRankings-4   	     328	   3576331 ns/op	   41288 B/op	     908 allocs/op

# MySQL
BenchmarkGetRankings-4   	      63	  18586058 ns/op	  392967 B/op	   18051 allocs/op
```

- 保持データ数が5000の場合

```
# Redis
BenchmarkGetRankings-4   	     348	   3679865 ns/op	   41952 B/op	     908 allocs/op

# MySQL
BenchmarkGetRankings-4   	      20	  58493116 ns/op	 2169418 B/op	   90068 allocs/op
```

- 保持データ数が10000の場合

```
# Redis
BenchmarkGetRankings-4   	     301	   3582936 ns/op	   42096 B/op	     908 allocs/op

# MySQL
BenchmarkGetRankings-4   	      12	 105611875 ns/op	 4443574 B/op	  180075 allocs/op
```

# まとめ
計測の結果，保持データ数が1000, 5000, 10000のいずれの場合に対しても，MySQLを用いたランキング取得よりもRedisのSorted setsを用いたランキング取得の方が性能が良いことが読み取れる．
また，保持データ数の増加に伴い，MySQLを用いた方よりもRedisのSorted setsを用いた方がより優位になっているため，保持データ数が多いランキング機能を実現する際には検討しても良い選択肢なのではないだろうか．
一方で，Redisを用いた場合，データが消えてしまうといった可能性も大いにあるため，ランキング追加時にはMySQLとRedisの両方に追加しておくなど，データ消失時に対応できるような対策を考えておくべきだろう．

# 参考文献
この記事は以下の情報を参考にして執筆しました．
・[Redis公式ドキュメント](https://redis.io/)
・[redis-cli コマンド操作まとめ](https://qiita.com/rubytomato@github/items/d66d932959d596876ab5)
・[go-redis リファレンス](https://pkg.go.dev/github.com/go-redis/redis/v8)