[나만무] 게임 MVP 선정 과정 개선

개요

게임 진행엣 최후의 1인 이외의 폭탄을 가장 많이 옮긴 사람이나

가장 유저를 많이 때린사람 or 가장 유저를 많이 공격 성공한 유저 ( 초기에는 가장 많이 맞은 유저로 했는데 그러면 게임 공격을 서로 안하고 맞으려고 할테니 공격을 가장 많이 성공한 유저로 기획을 변경했다)

무튼 이렇게해서 추가 MVP를 선정하자는 의견이 나왔다

 

 

Prioritiy Queue

https://github.com/mini-game-world/BE-mini-game-world/pull/61

#60 ranking by J-Jaeh · Pull Request #61 · mini-game-world/BE-mini-game-world

 

일단 레디스를 적용하기전 우선순위 큐를  사용해서 추가 MVP를 구현했었다

상호작용 이벤트가 성공적으로 발생하고, 해당 유저들이 선정되면 다시 클라이언트 측으로 emit을 보내는데, 보낼때 같이 카운트를 증가시켜줘서 우선순위 큐에 넣어줬고 이미 큐에 있으면 값을 증가시킨뒤 재정렬을 수행하는 방식으로 진행했다.

 

구현한 priority queue 코드이다.

export class PriorityQueue<T> {
  private heap: T[] = [];
  private comparator: (a: T, b: T) => number;

  constructor(comparator: (a: T, b: T) => number) {
    this.comparator = comparator;
  }

  public push(item: T): void {
    this.heap.push(item);
    this.bubbleUp();
  }

  public pop(): T | undefined {
    const top = this.peek();
    const bottom = this.heap.pop();
    if (this.heap.length > 0 && bottom) {
      this.heap[0] = bottom;
      this.bubbleDown();
    }
    return top;
  }

  public peek(): T | undefined {
    return this.heap[0];
  }

  public clear(): void {
    this.heap = [];
  }

  public update(item: T, newCount: number, getItemKey: (item: T) => any): void {
    const index = this.heap.findIndex(i => getItemKey(i) === getItemKey(item));
    if (index !== -1) {
      this.heap[index] = item;
      this.bubbleUp(index);
      this.bubbleDown(index);
    } else {
      this.push(item); // 값이 존재하지 않으면 새로 추가
    }
  }

  public printHeap(): void {
    console.log('Current state of heap:');
    this.heap.forEach((item, index) => {
      console.log(`Index ${index}: ${JSON.stringify(item)}`);
    });
  }

  private bubbleUp(index?: number): void {
    let idx = index ?? this.heap.length - 1;
    const element = this.heap[idx];
    while (idx > 0) {
      const parentIdx = Math.floor((idx - 1) / 2);
      const parent = this.heap[parentIdx];
      if (this.comparator(element, parent) <= 0) break;
      this.heap[idx] = parent;
      idx = parentIdx;
    }
    this.heap[idx] = element;
  }

  private bubbleDown(index = 0): void {
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.heap[leftChildIdx];
        if (this.comparator(leftChild, element) > 0) {
          swap = leftChildIdx;
        }
      }

      if (rightChildIdx < length) {
        rightChild = this.heap[rightChildIdx];
        if (
          (swap === null && this.comparator(rightChild, element) > 0) ||
          (swap !== null && this.comparator(rightChild, leftChild!) > 0)
        ) {
          swap = rightChildIdx;
        }
      }

      if (swap === null) break;
      this.heap[index] = this.heap[swap];
      index = swap;
    }
    this.heap[index] = element;
  }
}

 

일단 간략하게 시간 복잡도는 update 에서 선형탐색을 해서 O(n)이고 해당유저 선정이나 이런건 O(1)로 끝난다.

나름 선정에 시간복잡도가 좋지만 레디스서버를 이용해서 좀더 효율적으로 만들고 싶었다.

 

 

 

Redis - String

https://github.com/mini-game-world/BE-mini-game-world/pull/90

#34 redis by jayjayppark · Pull Request #90 · mini-game-world/BE-mini-game-world

 

팀장님이 적용한 레디스이다.

 

일단 레디스를 이용해서 캐시서버를 이용해 서버에 부하를 줄였다는 점에서 더 좋아졌다고 할 수있다.

 

다만 아쉬웠던 점은 redis의 다양한 자료구조를 활용하지 못해서 여기서는 업데이트는 key값을 이용해서 바로 되지만 나중에 MVP를 선정할때 선형탐색을 해야하기 때문에 이번엔 선정에 O(N)의 시간 복잡도가 나왔다. 

여기서 뭔가 더 개선할것이 있지 않을까 해서  찾아보았고 MVP 선정에서 시간복잡도를 더 줄일 방법을 찾았고 이를 개선하기로 했다

 

 

redis -sorted set

그렇게 해서 찾은게 redis가 지원하는 자료구조 중 sorted set이다.

 

중복을 제외시키는 set과 기준 값으로 정렬을 지원해준다, 사실상 랭킹기능에 쓰라고 있는 자료구조인 듯 하다.

 

따라서 해당 기능을 이용해 개선을 햇다

https://github.com/mini-game-world/BE-mini-game-world/pull/102

#97 redis ranking by J-Jaeh · Pull Request #102 · mini-game-world/BE-mini-game-world

 

여기서 내가 의외라고 생각한점은 랭킹선정이 O(logN) 이였다는점

 

그래서 찾아보니 레디스의 sorted set의 경우, 특정 범위 내의 요소를 가져오는 작업의 시간 복잡도는 O(logN +M)인데,

여기서 N은 집합의 크기, M은 반환되는 요수의수인데,

그 이유는 레디스는 sorted set을 구현하기 위해 Skip list와 hash table의 조합을 사용하기 때문..!

 

skip list 는...

 

레벨이 있는 링크드 리스트 구조로 평균적으로 O(logN)의 시간 복잡도로 요소를 검색, 삽입, 삭제를 할 수있는 자료 구조인데,

각 레벨은 특정 확률에 따라 요소를 선택적으로 포함... 따라서 요소를 검색 할때 상위 레벨에서부터 하위 레벨로 이동하면서 운하는 요소를 찾아간다.

 

hash table은 요소의 score와 rank를 빠르게 찾기 위해 사용됨.. 

 

결국 skip list를 이용해서 요소의 정렬된 상태를 유지한다는것 ..

 

 

 

결론

그동안 레디스를 string 구조로 밖에 활용을 못 했었는데 이제는 좀 더 다양하게 활용 할 수 있다고 생각이 든다

 

추가로 지금은 aws elasticache 를 이용해서 구성을 했지만 온전하게 활용을 못했다는 생각이 드는데, 왜냐하면 

 

외부서버에서 단일 노드로만 사용 했기 때문.. 공부하다보니 sentinel이나 cluster 구조로 레디스를 구성해서 고가용성을 생각 해 볼수도있었을 듯 하다 ..