[Nest.js] 랜덤매칭 기능 구현하기

김지엽·2024년 2월 24일

algorithm nest redis socket

1. 개요

프로젝트에서 랜덤매칭 기능을 맡게되었다. 랜덤매칭이라는 기능은 아예 처음 접해보는 기능이라 많은 고민을 하게되었고 구현에 앞서 전체적인 흐름과 이론적으로 알고리즘을 정리해두었다.

먼저, 전체적인 흐름은 다음과 같다.

2. 생각해야할 것

전체적인 흐름을 작성한 뒤에 구현에 중요한 것은 다음과 같다.

매칭 상태를 관리하는 대기열
매칭 조건에 따라 유저를 조회 및 분류하는 유저 분류 알고리즘

위의 조건들을 구현하기 위해서 socket과 redis를 통해 구현하는 방법들을 생각해보았다.

3. Socket Room을 이용한 분류

- socket room를 이용한 대기열

유저가 선택한 매칭조건으로 동일한 패턴의 roomId를 생성하고 유저의 소켓 클라이언트를 해당 룸에 조인시킨다.

- roomId를 이용한 분류

한 유저를 기준으로 해당 유저와 동일한 room에 있는 유저들 중 역할이 안겹치게 그룹을 생성한다.

- 문제점

팬텀 리드(Phantom Read)와 같은 동시성 이슈 발생

왼쪽의 경우는 2인 매칭의 예시이다.

A와 B가 동시에 매칭 대기열에 입장한다.
A와 B는 각각 대기열에 본인을 추구한다.
A와 B는 대기열에서 C와 본인만이 존재하는 것으로 데이터를 읽어온다.
A와 B는 각각 본인과 자기 자신이 매칭될수 있다고 착각한다.
A와 C는 성공적으로 그룹이 되지만 B는 혼자 그룹이 되는 현상이 발생한다.

오른쪽의 경우는 3인 매칭의 예시이다.

1~3번은 동일
A와 B는 각각 현재 대기열에 본인과 C인 2명만 존재하기에 매칭될수 없다고 착각한다.
결과적으로 대기열에는 3명이 존재하지만 아무도 매칭되지 않는 현상이 발생한다.

4. Redis Key를 이용한 분류

- Redis Key를 이용한 대기열

매칭조건으로 생성한 Key가 Redis에 존재하는지 없는지 여부를 통해 매칭중 상태를 구분한다.

- Key 패턴을 이용한 분류

한 유저를 기준으로 해당 유저의 매칭 조건으로 Redis Key 패턴을 통해 유저를 조회하고 역할군이 안겹치게 그룹화한다.

- 동시성 문제 해결

Redis에서 동시성 문제 해결

- 샘플 코드

// 매칭 조건에 따라 동일한 패턴으로 key 생성
private genMatchingUserKey(
    matchingClientId: string,
    startMatchingDto: StartMatchingDto,
) {
    const { mode, people, tier, position } = startMatchingDto;

    return `matching:user:${matchingClientId}:${mode}:${people}:${tier}:${position}`;
}

// 조건을 통해 매칭하는 유저 찾기
async findUserMatchingKeysByOption(
    findMatchingUserDto: FindMatchingUserDto,
) {
    const { matchingClientId, mode, people, tier, position } =
        findMatchingUserDto;

    const matchingUserKeyOptions: string[] = [];

    // 티어 범위는 한 단계 위아래 까지 매칭
    const tierRange = [tier - 1, tier, tier + 1];

    // 매칭 옵션을 통해 키 생성
    tierRange.forEach((tier) => {
        const matchingUserKeyOption = genMatchingKeyOption(
            matchingClientId,
            mode,
            people,
            tier,
            position,
        );

        matchingUserKeyOptions.push(matchingUserKeyOption);
    });

    // 매칭 키 옵션을 통해 매칭중인 유저 목록 불러오기
    const matchingPromises = matchingUserKeyOptions.map((keyOption) => {
        return this.redisClient.keys(keyOption);
    });
    const matchingUserKeyLists = await Promise.all([...matchingPromises]);

    // 매칭된 키 목록
    const matchingUserKeys = [];
    matchingUserKeyLists.forEach((keys) => {
        matchingUserKeys.push(...keys);
    });

    return matchingUserKeys;
}

// 들어온 사람을 방장으로 삼아 그룹 형성
async makeMatching(startMatchingDto: StartMatchingDto) {
    const { mode, tier, people } = startMatchingDto;

    const matchingUserLockKey = this.genMatchingLockKey(startMatchingDto);
    const lock = await this.redlock.acquire([matchingUserLockKey], 1000);

    const matchedGroup: MatchedUser[] = [];
    const matchedPosition: Position[] = [];
    const matchedUserKeys: string[] = [];
    let isMatchComplete = false;

    const matchingUserKeys = await this.findUserMatchingKeysByOption({
        ...startMatchingDto,
        position: null,
    });

    try {
        for (let key of matchingUserKeys) {
            const { matchingClientId, position } =
                getDataFromMatchingKey(key);

            const groupClientId = await this.redisService.get(key);

            // 포지션이 겹치지 않게 매칭
            if (matchedPosition.includes(position)) continue;

            // 매칭된 그룹에 참여
            matchedGroup.push({ matchingClientId, groupClientId });
            matchedUserKeys.push(key);
            matchedPosition.push(position);

            // 인원이 가득 차면 매칭 종료
            if (matchedGroup.length === people) {
                isMatchComplete = true;
                break;
            }
        }

        // 만약 매칭이 성공했다면 대기열에서 삭제
        if (isMatchComplete) {
            await this.redisService.del(matchedUserKeys);
            return {
                mode,
                tier,
                matchedPosition,
                matchedGroup,
            };
        }

        return null;
    } catch (e) {
        throw new WsException(e.message);
    } finally {
        await lock.release();
    }
}