Zenn
😈

【Redis】Sorted Setからランダムに要素を取得する方法

2022/05/03に公開
Golang
Redis
tech

概要

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