😈
【Redis】Sorted Setからランダムに要素を取得する方法
概要
Webサービスを開発していると、たまに「ある条件を満たす集合をランダムで取得したい」という要件がある。
個人開発であれば、RDBに対して叩くSQLを無理やり頑張って工夫すれば何とかなるが、
- RDBに入ってるデータが10万件
- 秒間200リクエストが来る
- ユーザー体感を向上させたいので、レスポンスは800ms以内に帰って来て欲しい
など、実際の現場では規模や状況が違うので、RDBでは用途を満たせない場合がある。
「ランダム性を持たせつつ、パフォーマンスも損なわれないようにする」、、という要件があった時、NoSQLデータベースは候補として上がってくる。
今回はNoSQLデーターベースの1つである、Redisで実現する方法について書いていく。
前提
- 言語はGo。
- Redisのライブラリにはgo-redisを使用する。
今回の例とする要件
ユーザーごとにLevelが存在する。
自分のLevelから+-10の範囲で、ランダムでUserIDを10件取得したい。
- Levelの下限、上限は1~100。
- 1Levelあたり、複数人のユーザーがいる場合がある。
- 自分のLevelより下の人と上の人が大体5対5になるように表示する。(尚、自分がレベル1や、100など上や下にユーザーがいない場合は比率が偏るのを許容する)
Redisに追加
RedisのSorted Setに追加する際に、
score: {Level}{ランダム5桁}
member: userID
にして登録する。
Sorted Setの仕様で、同じScoreだった場合にASCIIコード順になってしまうので、末尾に{ランダム5桁}を追加して、同じScoreでもランダム性を持たせるようにする。
add.go
const levelRandomRange = 100000
func Add(ctx context.Context, userID string,myLevel int32) error {
// DIした方が良いけど、ここでは簡略化の為適宜Newを行う
redisClient := redis.NewClient(&redis.Options{})
score := createSearchScore(myLevel)
zMember := &redis.Z{
Score: score,
Member: userID,
}
if cmd := redisClient.ZAdd(ctx, "search", zMember);cmd.Err() != nil {
return err
}
return nil
}
func createSearchScore(level int32) float64 {
return float64(int(level)*levelRandomRange + rand.Intn(levelRandomRange))
}
Redisから検索
まずは自分のレベルより下の範囲、自分のレベルより上の範囲で、それぞれ基準とするレベルをランダムで決める。
minLevel,maxLevel := getMinAndMaxLv(myLevel)
minTargetLevel := rand.Intn(myLevel - minLevel + 1) + minLevel
maxTargetLevel := rand.Intn(maxLevel - myLevel + 1) + myLevel
func getMinAndMaxLv(myLevel int32) (int32, int32) {
minLevel := myLevel - 10
maxLevel := myLevel + 10
// 下限と上限を超えてたらそれぞれ丸める
if minLevel < 1 {
minLevel = 1
}
if maxLevel < 1 {
maxLevel = 1
}
if minLevel > 100 {
minLevel = 100
}
if maxLevel > 100 {
maxLevel = 100
}
return minMlv, maxMlv
}
次に、それぞれの範囲で昇順、降順で検索するかを確定させていく。
意図としては、例えば
- 自分のレベルが50
- 先ほどランダムで決めた基準レベルが49
の場合、常に昇順で検索すると、49 → 50で検索出来る範囲が狭くなってしまい、取得件数が少なくなってしまうからである。
(本来は40~48のレベルも取れたはずなのに)
その為、ランダムで決めた基準レベルが、ちょうど範囲内で半分より下か上かで昇順降順を切り分ける。
こうすることによって、取りこぼしが少なくなる。
lowerInfo := getLowerSearchScoreInfo(minLevel, minTargetLevel, myLevel)
higherInfo := getHigherSearchScoreInfo(maxLevel, maxTargetLevel, myLevel)
type searchScoreInfo struct {
minScore float64
maxScore float64
isDesc bool
}
func getLowerSearchScoreInfo(minLevel, targetLevel, myLevel int32) searchScoreInfo {
/*
自分のLevel: 50
targetLevelが45 ~ 50なら、minLevel ← targetLevelの降順
targetLevelが40 ~ 44なら、targetLevel → myLevelの昇順
*/
isDesc := (targetLevel - minLevel) >= 5
var min float64
var max float64
if isDesc {
min = createSearchScore(minLevel)
max = createSearchScore(targetLevel)
} else {
min = createSearchScore(targetLevel)
max = createSearchScore(myLevel)
}
return searchScoreInfo {
minScore: min
maxScore: max
isDesc: isDesc,
}
}
func getHigherSearchScoreInfo(maxLevel, targetLevel, myLevel int32) searchScoreInfo {
/*
自分のLevel: 50
targetLevelが55 ~ 60なら、myLevel ← targetLevelの降順
targetLevelが50 ~ 54なら、targetLevel → maxLevelの昇順
*/
isDesc := (maxLevel - targetLevel) <= 5
var min float64
var max float64
if isDesc {
min = createSearchScore(myLevel)
max = createSearchScore(targetLevel)
} else {
min = createSearchScore(targetLevel)
max = createSearchScore(maxLevel)
}
return searchScoreInfo {
minScore: min
maxScore: max
isDesc: isDesc,
}
}
準備ができたので、Redisにアクセスする。
5対5になるようにする。
// Redisにアクセス
lowerIDs := rangeByScore(lowerInfo.minScore, lowerInfo.maxScore, 10,lowerInfo.isDesc)
higherIDs := rangeByScore(higherInfo.minScore, higherInfo.maxScore, 10,higherInfo.isDesc)
// 5対5になるように仕分けてappend
lowerTargetIDs, lowerSurplusIDs := assortIDs(lowerIDs)
higherTargetIDs, higherSurplusIDs := assortIDs(higherIDs)
targetUserIDs := make([]string, 0, 10)
targetUserIDs = append(targetUserIDs, lowerTargetIDs...)
targetUserIDs = append(targetUserIDs, higherTargetIDs...)
// 表示件数に足りなければ、下か上の範囲で余っている方で補う
if len(targetUserIDs) < 10 {
surplusUserIDs := make([]string, 0, len(lowerSurplusIDs)+len(higherSurplusIDs))
surplusUserIDs = append(surplusUserIDs, lowerTargetIDs...)
surplusUserIDs = append(surplusUserIDs, higherTargetIDs...)
for _, id := range surplusUserIDs {
targetUserIDs = append(targetUserIDs, id)
if len(targetUserIDs) < 10 {
break
}
}
}
func rangeByScore(min,max,count int64, isDesc bool) ([]string,error) {
// DIした方が良いけど、ここでは簡略化の為適宜Newを行う
redisClient := redis.NewClient(&redis.Options{})
rangeBy := &redis.ZRangeBy{
Min: strconv.FormatInt(min, 10)
Max: strconv.FormatInt(max, 10)
Offset: 0,
Count: count,
}
var cmd *redis.StringSliceCmd
if isDesc {
cmd = redisClient.ZRevRangeByScore(ctx, key, rangeBy)
} else {
cmd = s.redisClient.ZRangeByScore(ctx, key, rangeBy)
}
if cmd.Err() != nil {
return err
}
return cmd.Val()
}
func assortIDs(ids []string) ([]string, []string) {
targetUserIDs := make([]string, 0, 5)
surplusUserIDs := make([]string, 0, 5)
for _, id := range ids {
if len(targetUserIDs) < 5 {
targetUserIDs = append(targetUserIDs, id)
} else {
surplusUserIDs = append(surplusUserIDs, id)
}
}
return targetUserIDs, surplusUserIDs
}
最後にまとめると下記のような感じになる。
search.go
search.go
const levelRandomRange = 100000
func Add(ctx context.Context, userID string,myLevel int32) error {
// DIした方が良いけど、ここでは簡略化の為適宜Newを行う
redisClient := redis.NewClient(&redis.Options{})
score := createSearchScore(myLevel)
zMember := &redis.Z{
Score: score,
Member: userID,
}
if cmd := redisClient.ZAdd(ctx, "search", zMember);cmd.Err() != nil {
return err
}
return nil
}
func createSearchScore(level int32) float64 {
return float64(int(level)*levelRandomRange + rand.Intn(levelRandomRange))
}
type searchScoreInfo struct {
minScore float64
maxScore float64
isDesc bool
}
func Search(ctx context.Context, userID string, myLevel int32) error {
minLevel,maxLevel := getMinAndMaxLv(myLevel)
// 自分のレベルより下の範囲、自分のレベルより上の範囲で、それぞれ基準とするレベルを決める。
minTargetLevel := rand.Intn(myLevel - minLevel + 1) + minLevel
maxTargetLevel := rand.Intn(maxLevel - myLevel + 1) + myLevel
// それぞれの範囲で昇順、降順で検索するかを確定する。
lowerInfo := getLowerSearchScoreInfo(minLevel, minTargetLevel, myLevel)
higherInfo := getHigherSearchScoreInfo(maxLevel, maxTargetLevel, myLevel)
// Redisにアクセス
lowerIDs := rangeByScore(lowerInfo.minScore, lowerInfo.maxScore, 10,lowerInfo.isDesc)
higherIDs := rangeByScore(higherInfo.minScore, higherInfo.maxScore, 10,higherInfo.isDesc)
// 5対5になるように仕分けてappend
lowerTargetIDs, lowerSurplusIDs := assortIDs(lowerIDs)
higherTargetIDs, higherSurplusIDs := assortIDs(higherIDs)
targetUserIDs := make([]string, 0, 10)
targetUserIDs = append(targetUserIDs, lowerTargetIDs...)
targetUserIDs = append(targetUserIDs, higherTargetIDs...)
// 表示件数に足りなければ、下か上の範囲で余っている方で補う
if len(targetUserIDs) < 10 {
surplusUserIDs := make([]string, 0, len(lowerSurplusIDs)+len(higherSurplusIDs))
surplusUserIDs = append(surplusUserIDs, lowerTargetIDs...)
surplusUserIDs = append(surplusUserIDs, higherTargetIDs...)
for _, id := range surplusUserIDs {
targetUserIDs = append(targetUserIDs, id)
if len(targetUserIDs) < 10 {
break
}
}
}
return nil
}
func getMinAndMaxLv(myLevel int32) (int32, int32) {
minLevel := myLevel - 10
maxLevel := myLevel + 10
// 下限と上限を超えてたらそれぞれ丸める
if minLevel < 1 {
minLevel = 1
}
if maxLevel < 1 {
maxLevel = 1
}
if minLevel > 100 {
minLevel = 100
}
if maxLevel > 100 {
maxLevel = 100
}
return minMlv, maxMlv
}
func getLowerSearchScoreInfo(minLevel, targetLevel, myLevel int32) searchScoreInfo {
/*
自分のLevel: 50
targetLevelが45 ~ 50なら、minLevel ← targetLevelの降順
targetLevelが40 ~ 44なら、targetLevel → myLevelの昇順
*/
isDesc := (targetLevel - minLevel) >= 5
var min float64
var max float64
if isDesc {
min = createSearchScore(minLevel)
max = createSearchScore(targetLevel)
} else {
min = createSearchScore(targetLevel)
max = createSearchScore(myLevel)
}
return searchScoreInfo {
minScore: min
maxScore: max
isDesc: isDesc,
}
}
func getHigherSearchScoreInfo(maxLevel, targetLevel, myLevel int32) searchScoreInfo {
/*
自分のLevel: 50
targetLevelが55 ~ 60なら、myLevel ← targetLevelの降順
targetLevelが50 ~ 54なら、targetLevel → maxLevelの昇順
*/
isDesc := (maxLevel - targetLevel) <= 5
var min float64
var max float64
if isDesc {
min = createSearchScore(myLevel)
max = createSearchScore(targetLevel)
} else {
min = createSearchScore(targetLevel)
max = createSearchScore(maxLevel)
}
return searchScoreInfo {
minScore: min
maxScore: max
isDesc: isDesc,
}
}
func rangeByScore(min,max,count int64, isDesc bool) ([]string,error) {
// DIした方が良いけど、ここでは簡略化の為適宜Newを行う
redisClient := redis.NewClient(&redis.Options{})
rangeBy := &redis.ZRangeBy{
Min: strconv.FormatInt(min, 10)
Max: strconv.FormatInt(max, 10)
Offset: 0,
Count: count,
}
var cmd *redis.StringSliceCmd
if isDesc {
cmd = redisClient.ZRevRangeByScore(ctx, key, rangeBy)
} else {
cmd = s.redisClient.ZRangeByScore(ctx, key, rangeBy)
}
if cmd.Err() != nil {
return err
}
return cmd.Val()
}
func assortIDs(ids []string) ([]string, []string) {
targetUserIDs := make([]string, 0, 5)
surplusUserIDs := make([]string, 0, 5)
for _, id := range ids {
if len(targetUserIDs) < 5 {
targetUserIDs = append(targetUserIDs, id)
} else {
surplusUserIDs = append(surplusUserIDs, id)
}
}
return targetUserIDs, surplusUserIDs
}
Discussion