[그때살껄] 매칭 시스템(2)

https://young-helloworld.tistory.com/29

[그때 살껄] 매칭 시스템(1)

 

 

 

전에 임시저장만 해놓고 완료를 안눌러서 글을 바로 작성하는 것처럼 보이지만 2주 텀이 있습니다..

 

내가 짠 랜덤 매칭에 적합한 유저를 찾아주는 로직이 너무 비효율적이라는 것을 깨달아버렸다.

그래서 뭔가 더 좋은 방법이 없을까 알고리즘을 찾아보고 후보가 몇개 있었다.

 

1. 그리디 알고리즘

가장 간단한 접근 방법이다. 각 단계에서 최선의 선택을 해 매칭을 시도하는 것. 자산이 자신과 비슷한 순으로 정렬한 후 검색.

redis에서 모든 대기열을 계속 가져와야함 -> 전이랑 똑같음

사용자를 정렬하는데 O(N log N), 매칭을 위한 검색에서 최악의 경우 O(N).

 

2. 균형 이분 탐색 트리

데이터를 균형 이진 탐색 트리에 저장하여, 범위 쿼리를 빠르게 수행.

실시간으로 많은 데이터가 추가되거나 삭제되는 환경에서 트리의 재조정이 빈번하게 필요.

각 삽입, 삭제, 검색 작업이 O(log ⁡N).

 

3. k-means 클러스터

사용자를 자산 기준으로 클러스터링 하여, 비슷한 자산 범위의 사용자들을 그룹화.

클러스터 수 k를 미리 설정해야 하며, 최적의 k를 찾기 어려움 ..

각 반복마다 O(Nk)로, 클러스터링 과정에서 여러 번의 반복이 필요.

 

뉴비라서 이 중 내가 아는건 그리디 알고리즘 밖에 없었다..

 

그러다가 찾아보니 redis 에서 Sorted Set을 이용하면 범위 쿼리를 매우 효율적으로 수행할 수 있다고 봤다.

zrangebyscore 명령은 범위 내의 사용자를 O(log N +M) 으로 조회할 수 있었다.(N -> 대기열 사용자 수, M -> 반환된 사용자 수)

 

이렇게 되면 redis에서 모든 대기열을 계속 가져와서 정렬을 해야되는 문제점을 해결할 수 있었다.

 

이걸 써야지 하고 막 신나있던 찰나.. 이걸 이렇게 끝내면 나는 프로젝트에서 CRUD만 했다는 생각이 스쳐 지나가면서 문제점을 찾기 시작했다.

 

생각을 해보니 유저들의 자산이 비슷할때 (모두 2900 ~ 3100만원인 자산을 가지고 대기열에 있는데, 3000만원인 유저가 매칭을 잡을때) 내가 처음 짠 코드와 똑같은 비효율을 자랑했다.

 

별로 상관 없는 문제일 수 있지만 이걸 해결해야된다는 생각이 들었다.

 

이걸 고민한건 다음에 쓰겠다 .. 머리가 아파 ..