PS 하길 잘했다! 펜윅트리로 실시간 유저 집계하기

 

올해 삘 꽂혀서 PS를 시작한지 거의 1년이 되어가네요

 

근데 뭐 새로 시작한건 아니고 작년 상반기에 바짝하다가 작년 하반기에 좀 쉬고 올해 다시 시작했습니다

 

여러 주제를 풀고 있는데요, 갑자기 새로 배운 주제인 펜윅트리에서 아이디어가 하나 떠올랐습니다

 

저희 캠퍼스 실시간 정보 거래 서비스에서는 서비스 지역을 S2 셀로 나누어 관리하는데요

 

기존에 이 셀당, 혹은 현재 전체 셀 안에 있는 사용자들의 수를 파악하는 기능은

현재 유저 위치를 저장하는 레디스에 직접 요청을 넣어 다 가져오는 방식이었습니다

 

그럼 레디스에 셀별 개별 요청을 반복적으로 넣어 전체 사용자 수를 집계해야 하니까 많은 호출과 부하로 인해 응답 지연, 서버 과부하 등의 문제가 생깁니다

 

그럼 여기서 두 가지 개선점이 필요해보입니다.

1. 전체 집계 혹은 셀 안에 있는 사용자 수 파악 줄이기

2. 레디스와 분리해서 부하를 분산시킬 수 있도록

 

그래서 여기 펜윅트리를 적용해보기로 했습니다

펜윅트리란?

펜윅트리(Fenwick Tree)는 최하위 켜져있는 비트를 기반으로 트리를 만들어 동적배열에서 구간 합을 효율적으로 구할 수 있는 자료구조입니다

 

작동원리부터 봅시다

https://www.inflearn.com/course/10주완성-코딩테스트-큰돌

 

위와 같이 배열 (3, 4, 10, 11) 이 있다고 해봅니다

우리의 목표는 구간 합 빠르게 구하기 입니다

구간 합

펜윅트리는 각 구간의 합을 위 그림과 같이 블록으로 표현합니다

1번 블록에는 3, 2번 블록에는 7(3+4), 3번 블록에는 10, 4번 블록에는 28(3+4+10+11) 이 저장되어 있습니다

 

왜 이렇게 저장할까요? 이렇게만 저장해 놓으면 모든 구간합을 표현할 수 있기 때문입니다

 

예를 들어 구간 1~2의 합? = 2번 블록, 구간 2~3의 합? = 2번 + 3번 블록 - 1번 블록

이런식으로 확장해가면 모든 구간합에 대해 효율적으로 표현이 가능합니다

값 갱신

예를 들어 배열 3번째 항목(10)에 1을 더한다고 생각해봅시다

 

근데 지금 배열 3번째 항목과 연관이 있는 블록은 3번, 4번 블록이죠

 

그럼 일단 3번 블록에 +1을 하고

 

그 다음 블록 인덱스는

다음 인덱스 = 현재 인덱스 + (현재 인덱스 & -(현재 인덱스))

로 구할 수 있습니다

 

그럼 4 = 3 + (3&-3) 이라는 건데

 

이진수로 한번 생각해보면

100 = 11 + (11&1)

입니다

 

최하위 켜져있는 비트는 idx & -idx 로 구할 수 있는데요, 이걸 현재 인덱스에서 더해주면서 갱신하면 됩니다

 

아직도 이해가 잘 안될 수 있으니 코드로 봅시다

코드

data = [3, 4, 10, 11]
n = len(data)
tree = [0] * (n + 1) # 1번 인덱스부터 시작해야 하므로

 

시작할 때 제일 중요한 점은 트리를 만들 때 1번 인덱스부터 시작해야 하므로 n+1로 할당해줬습니다

def range_update(index, value):
    global tree
    while index < len(tree):
        tree[index] += value
        index += index & -index

for i in range(n):
    range_update(i + 1, data[i])

 

그리고  트리를 만들어 줘야 하는데, 위에서 봤던 대로 index에 갱신 시켜주고 최하위 켜져있는 비트만큼 계속 더해줘서 값 갱신을 전파시켜줬습니다

def _sum(index):
    ret = 0
    while index > 0:
        ret += tree[index]
        index -= index & -index
    return ret

def range_query(left, right):
    return _sum(right) - _sum(left - 1)

 

아까 말했던대로 범위 갱신은 누적합에서 값 구하듯이 right까지의 합에서 left-1까지의 합을 빼줬습니다

 

근데 합을 구하는 메서드가 좀 특이하죠

아까 갱신때하고 반대로 최하위 켜져있는 비트만큼 계속 빼주는 것이 특징입니다

print(tree) # [0, 3, 7, 10, 28]

print(range_query(1, 2)) # 7
print(range_query(2, 4)) # 25

range_update(2, 5)
print(tree) # [0, 3, 12, 10, 33]

print(range_query(1, 2)) # 12
print(range_query(2, 4)) # 30

 

이쯤 되면 뭔가 드는 생각이 있을 것 같습니다

어 이거 갱신하고 누적합을 O(logN)만에 구할 수 있으니까 기존에 전체 유저 수 구할 때 O(N) 만큼 소요됐던거 보다 효율적일 것 같은데?

 

근데 그럼 이거 갱신이 실시간으로 계속 되어야 하는데 그럼 부하가 더 많이 생기는거 아님?

이건 메시지큐 적용하면 트래픽 조절해서 부하 좀 줄일 수 있겠다

 

근데 지금 분산 서버를 사용하므로 서버마다 동적큐로 하나씩 생성해서 fanout exchange로 뿌려주면 될 것 같습니다

프로젝트에 적용

@Component
@RequiredArgsConstructor
public class FenwickTree {

    private final LocationReader locationReader;

    private int[] tree;
    private int size;

    @PostConstruct
    public void init() {
        List<String> cellIds = locationReader.findAllCellIds();

        size = cellIds.size();
        tree = new int[size + 1];
    }

    // 값 업데이트
    public void update(int idx, int value) {
        while (idx <= size) {
            tree[idx] += value;
            idx += (idx & -idx); // 가장 낮은 1비트만큼 인덱스 증가
        }
    }

    // prefix sum: 1~idx까지 합
    public int prefixSum(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= (idx & -idx); // 가장 낮은 1비트만큼 인덱스 감소
        }
        return sum;
    }

    // 구간합: l~r
    public int rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }

    public void clear() {
        tree = new int[size + 1];
    }

}

 

서버마다 펜윅트리 하나씩만 있으면 되니까 @Component로 등록해서 사용하도록 했고 나머지는 파이썬 코드와 똑같이 구현했습니다

 

그리고 사용자 수 확인 로직에는

@Component
@RequiredArgsConstructor
@Transactional(readOnly = true)
public class CellStatusService {

    private final LocationReader locationReader;

    private final FenwickTree fenwickTree;

    private final Map<String, Integer> cellIdToIndex = new HashMap<>();

    @PostConstruct
    public void init() {
        List<String> cellIds = locationReader.findAllCellIds();

        for (int i = 0; i < cellIds.size(); i++) {
            cellIdToIndex.put(cellIds.get(i), i + 1);
        }
    }

    public int getAllCurrentUsersCount() {
        return fenwickTree.prefixSum(cellIdToIndex.size());
    }

    public int getCurrentUsersCountByCellId(String cellId) {
        Integer idx = cellIdToIndex.get(cellId);
        return idx == null ? 0 : fenwickTree.rangeSum(idx, idx);
    }

    public void updateUserCountByCellId(String cellId, int count) {
        int index = cellIdToIndex.get(cellId);
        fenwickTree.update(index, count);
    }

    public void clearUserCount() {
        fenwickTree.clear();
    }

}

 

기존에 있던 셀들을 인덱스로 변환시켜준 다음 펜윅트리에 O(logN)만에 업데이트해주고 O(logN)만에 전체 유저 수를 구하고 O(logN)만에 특정 셀에 유저 수를 구할 수 있게 됐습니다

성능 측정

이제 신나는 성능 측정 시간입니다

레디스에 각각 요청 넣는 방식

10,000 명 기준으로
allCurrentUsersCount = 105,788,709ns
allCurrentUsersCountByCellID = 411,719,125ns

 

이정도 나오고

펜윅 트리 구현 및 적용

10,000 명 기준으로

allCurrentUsersCount = 1,262,875ns
allCurrentUsersCountByCellID = 319,287,750ns

 

이 정도 걸렸습니다

 

전체 집계 성능 기준 84배 정도 개선됐네요

 

근데 더 놀라운건 유저 수를 100,000 명으로 늘려도

 

allCurrentUsersCount = 2,256,458ns

allCurrentUsersCountByCellID = 487,542,708ns

 

전체 집계 성능이 기존보다 47배 개선된 모습을 볼 수 있습니다

결론

그래서 오늘의 결론

 

PS는 코딩테스트 할 때만 쓰는게 아니다

좋은 자료구조를 쓰는 것이 중요하다

 

끝