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

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

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

 

대기열에 있는 많은 유저 자산이 비슷할때 성능이 매우 안좋아지는 불상사를 막기위해 고민을 몇개 해봤다.

 

1. 3차원 그라디언트

 

자산 가중치(k), 대기 시간 가중치(l), 평균 자산 가중치(m)을 파라미터로 둔다.

 

자산 (k)

사용자의 자산에 크기를 반영한다.

k가 높을수록 개개인 자산의 크기에 따라 더 공평한 게임을 할 수 있지만, 너무 큰 k값은 개개인의 초점을 맞추기 때문에 

처음 고민했던 자산이 비슷할때 성능이 안좋아지는 문제를 넘어 아예 매칭이 잡히지 않는 상황이 생길 수도 있다.

 

 

대기 시간 (l)

사용자가 기다린 시간을 반영한다.

l이 높을 수록 대기열에 들어온 순서대로 나가 거의 확정적인 매칭을 할 수 있어 시간에 대한 만족도를 높여주지만, 너무 큰 l값은 매칭이 잡혔을때 자산의 크기에 따른 공평한 게임인지에 대한 불만이 나올 수 있다.

 

 

평균 자산 (m)

평균 자산, 즉 대기열 그리고 대기열에 있지 않는 모든 사용자들의 자산의 평균을 반영한다.

m이 높을수록 매칭이 잘 잡히게 만들지만, 너무 높은 m은 모든 유저의 자산을 비슷하게 만들 수 있어, 성능에 문제가 생길 수 있다.

 

f(k,l,m) = 매칭 성공률(k,l,m) + 사용자 만족도(k,l,m) + 시스템 효율성(k,l,m) 의 그라디언트를 구해,

그라디언트의 방향대로 크기를 조절해 가중치의 최적값을 찾는다.

 

최적화 과정은 반복적으로 수행하고, 각 단계에서 그라디언트 방향을 따라 파라미터를 조정한다. 발산을 방지하기 위한 수렴 조건은 성능의 개선이 임계점에 도달하거나 임계점 이하로 떨어질 때 최적화를 멈춘다. 또한, 적절한 조정값을 지정해서 값이 너무 커지거나, 최적값에 도달하는데 오래 걸리지 않게 한다.

---

2. 표준 정규 분포 테이블을 이용한 매칭 큐 관리

 

사용자의 수에 따라 최대 10% 자산이 랜덤으로 늘거나 줄게한다.

사용자가 성능에 문제가 생길 정도로 많은 경우라면 정규분포를 따를거라고 가정하고, 표준 정규 분포 테이블을 사용하여 어림잡아 계산한다.

 

평균 자산이 5000만원, 표준 편차를 1000만원으로 가정한다.

 

import org.apache.commons.math3.distribution.NormalDistribution;

public class AssetRangeCalculator {

    public static void main(String[] args) {
        double mean = 50000000; // 평균 자산
        double stdDev = 10000000; // 표준 편차
        double lowerBound = 47500000; // 자산 하한
        double upperBound = 52500000; // 자산 상한

        // 표준 정규 분포 객체 생성
        NormalDistribution distribution = new NormalDistribution(mean, stdDev);

        // 하한과 상한에 대한 누적 분포 함수 값 계산
        double cdfLower = distribution.cumulativeProbability(lowerBound);
        double cdfUpper = distribution.cumulativeProbability(upperBound);

        // 두 CDF 값의 차이로 해당 범위에 있는 사용자의 비율 계산
        double probability = cdfUpper - cdfLower;
    }
}

 

평균 자산을 기준으로 처음 매칭이 잡히는 5%기준에 들어오는 사람의 비율을 probability로 잡고 성능 저하를 일으킬만한 인원수(여기서는 대충 10000명으로) 를 잡는다. 10000 / probability > 매칭큐크기 이면 다음 들어오는 유저부터 1 ~ 10%의 자산을 랜덤으로 줄거나 늘려준다. 그러면 성능 저하를 일으킬 만한 인원 유입이 절반정도로 감소하고 매칭이 잡혀서 계속 빠져 나가므로 성능 저하를 막을 수 있다고 생각했다.

---

나는 여기서 2번째를 선택했다. 왜냐하면 그라디언트를 써서 최적값을 찾는 시간도 능력도 없다고 판단했기 때문이다..

두번째는 너무 직관적으로 했지만 표준편차, 평균자산, 자산의 하한, 상한만 바꾸면 되는 문제라 비교적 쉽게 접근할 수 있다고 생각했다.

 

그리고 자산의 범위를 늘려주는 로직도 아래와 같은 방식으로 수정할 예정이다.

 

---

지수함수를 이용한 자산범위

 

대기 시간이 30분이 되었을때 매칭이 잡히는 자산의 범위가 20%가 되도록 지수함수 그래프를 이용한다.

매칭이 빠르게 이루어지고 범위에 제한을 두기 위해 지수함수를 사용했다.

 

지수함수의 형태를 f(t) = 5 + 15*(1-e^(-bt)) 로 설정해 대기 시간이 0일때는 5%부터 시작해서 5분일때 10%, 30분이 됐을때 거의 20에 가까워지게 할수 있다. f(5) = 10이 되기 위해 b의 값을 정하면 된다.

public class AssetRangeCalculator {

    public static void main(String[] args) {
    	// 5분을 시간으로 변환 (5분 / 60분)
        double t = 0.0833; 
        // 목표 자산 범위
        double x = 10;     
        
        // b 값을 찾기 위해 목표 자산 범위 식을 재정리
        double desiredExp = (x - 5) / 15;
        
        // e^(-b * t) = 1 - desiredExp 식을 b에 대해 풀기
        double b = -Math.log(1 - desiredExp) / t;

        // 추가: 대기 시간 30분(0.5시간)일 때 자산 범위 계산
        double assetRangeAt30Min = calculateAssetRange(0.5, b);
    }
    
    // 자산 범위 계산 메서드
    public static double calculateAssetRange(double t, double b) {
        return 5 + 15 * (1 - Math.exp(-b * t));
    }
}

 

 

---

고민을 많이 해봤는데 딱히 끌릴만한 아이디어가 나오지 않은것같아 아쉽다..

일단 이대로 개발을 해보고 추후에 수정을 해야될거같다.