Sorted Set에서 요소를 임의로 가져오는 방법

개요

웹 서비스를 개발하면'어떤 조건을 충족하는 집합을 무작위로 얻고 싶다'는 조건이 간혹 있을 수 있다.
개인개발이라면 RDB가 두드리는 SQL에 무리하게 노력하면 방법이 있을 거예요.

RDB의 데이터 10만 건

초 200요청

사용자 체감 향상을 원하므로 800ms 이내로 응답

등, 실제 현장에서 규모와 상황이 달라 RDB가 용도를 충족하지 못하는 경우가 있다.
"임의성을 유지하면서 성능을 해치지 않습니다"라는 필수 조건이 있을 때 NosQL 데이터베이스는 후보 데이터베이스로 상승합니다.
이번에는 NoSQL 데이터를 바탕으로 Redis를 통해 구현되는 방법에 대해 쓰겠습니다.

전제 조건

언어는 Go입니다.

는 Redis의 라이브러리에서 사용go-redis.

이번 예의 필요조건으로

모든 사용자에게는 Level이 있습니다.
자신의 Level에서 +-10까지 랜덤으로 10개의 UserID를 획득합니다.

Level의 하한선, 상한선은 1~100이다.

Level당 여러 사용자가 있을 수 있습니다.

자신의 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
}