TBB - 병렬 컨테이너 사용 (concurrent_hash_map) : GameServer에서 유저의 <id, index> 정보 관리

서론 : 게임서버에서 유저 정보를 포인터로 관리하면 안되는 이유

---

졸업작품 게임 서버를 만들고 있는 지금, 안그래도 시간이 부족한데

포스트까지 작성할 시간이 있을지 고민이 많이 되었다.

하지만 경험 상 내가 겪었던 문제를 기록하지 않으면 같은 문제에 똑같이 시간을 낭비할 수 있으므로..

 

지난 NDC 2014에서 정내훈 교수님께서 발표하셨던

 

"멀티스레딩 왜이리 힘드나요 시즌 2"

시즌 2: 멀티쓰레드 프로그래밍이 왜이리 힘드나요?

에서 concurrent_hash_map을 이용한 <id, index> 쌍으로 유저 관리! 라는 부분을 보고

'아차' 싶은 생각이 들었다.

이제는 더 이상 미룰 수 없는 때가 왔다는 것을 직감했다.

 

현재 내 서버는 유저가 접속할 때마다 내가 만든 Memory Pool에서 메모리를 할당받고,

해당 유저가 어떤 이유에서든 로그아웃되면 할당 받은 메모리를 해제하는 방식으로 구현되어 있다.

 

게임 서버 강의를 들으면서, 배열의 인덱스로 유저를 관리하는 것을 보고

Memory Pool 로 인해 메모리 단편화 문제가 해결되었으니,

번거롭게 배열의 인덱스로 유저를 접근하는 것은 성능 상 별로 도움이 안 될 것이다.

라고 생각했기 때문에, 할당받은 메모리의 포인터를 직접 역참조하여 유저 정보를 접근했다.

 

중간발표까지의 완성도에서는 별다른 문제가 없었으나,

이제 로비와 대기실, 그리고 게임 룸 등 여러가지 Location에서의 유저 정보를 다루려다 보니,

포인터를 자칫 잘못 다루면, 댕글링 포인터를 역참조 할 가능성이 점점 높아지고 있었다.

 

예상 가능한 가장 끔찍한 시나리오는 다음과 같다.

 

1. 두 유저 A와 B가 한 게임룸에서 1:1 로 게임을 하고 있다.

2. 유저 A가 다른 유저 B에게 총을 쏘았다.

3. 유저 B에게 피격 판정 패킷이 전송된다.

 

이 시나리오에서 2번과 3번 사이에 유저 B가 로그아웃 한다면,

유저 B의 메모리가 해제되고, 유저 B를 가리키던 메모리는 댕글링 포인터가 된다.

서버는 당연히 멀티쓰레드로 돌아가고 있으므로, 유저 B가 로그아웃된 사실을,

피격 판정을 보내려는 쓰레드는 모르고 있다.

 

쓰레드는 이미 해제된 유저 B의 메모리를 역참조한다.

운이 좋으면 서버는 여기서 이상을 발견하고 해당 작업을 중지한다.

 

하지만 운이 나쁘면, 해제된 메모리에서 이미 close된 소켓을 읽어오게 되고,

close된 소켓에 SendPacket을 시도 -> 당연히 Fail -> closesocekt 및 해당 유저 정보 delete

의 순서를 따르게 된다.

 

이 때 이미 해제된 메모리를 다시 해제하려 하므로, 서버가 죽게 된다.

유저가 접속을 종료할 때 해당 메모리를 해제하게 되면 그 메모리 안에 유저의 상태를 저장할 수 없다.

connect인지 아닌지, loaction이 어딘지 등의 정보는 메모리가 해제되는 순간 접근이 불가능하다.

 

유저 정보를 안전하고 효율적으로 식별하기

---

그렇다면 이러한 정보만을 모은 배열을 따로 만들면 어떨까?

 

ConnectionTable 을 만들어 각 인덱스를 각 유저에게 매핑시켜,

유저 정보에 접근할 때마다 테이블의 값을 확인하도록 하면,

해제된 메모리를 참조하는 문제를 해결할 수 있지 않을까?

 

하지만 역시 사람이 하는 일이다 보니, 메모리를 동적으로 할당받고 해제하는 이상

메모리 누수 등의 잠재적인 이슈들을 안고 가는 셈이다.

 

그렇다면 결론은 이거다.

최대 동시접속자만큼의 유저 정보 배열을 미리 할당해 놓고,

배열의 index로 유저 정보를 관리하는 것이다.

 

유저가 접속하면 index를 부여하고,

미리 할당해 놓은 players\[\] 배열의 index번째 원소를 유저 정보로 사용하는 것이다.

 

players\[index\] 를 초기화 한 후,

players\[index\].connect = true;

를 해주면 해당 index의 유저가 접속중임을 표시할 수 있다.

 

유저가 로그아웃 했을 땐 반대로

players\[index\].connect = false; 

해주면 메모리 해제 없이 유저가 접속중이 아님을 표시할 수 있다.

 

메모리가 해제된 것이 아니기 때문에,

이후 비동기 함수에서 이 유저의 메모리에 접근을 시도하더라도

메모리 익셉션이 발생하지 않으며,

유저가 접속 중인지 아닌지를 안전하게 확인할 수 있다.

 

이와 같이 소스를 수정한다면, sendPacket()함수의 원형은 다음과 같이 바뀔 것이다.

 

before : bool sendPacket(Player\* dest, Packet p);
after   : bool sendPacket(int index, Packet p);

 

이렇게 되면 sendPacket()함수 내부에서 players\[\] 배열에 해당 원소에 접근하여,

해당 원소의 플레이어가 connect 상태인지 아닌지를 확인할 수 있고,

때문에 이미 접속을 종료한 플레이어에 대해 메모리 익셉션 없이 안전하게 처리가 가능하다.

 

그렇다면 만사 오케이인가?

 

아니다. index를 효율적으로 분배할 수 있어야 한다.

index를 하나씩 증가하며 순서대로 부여한다고 생각해보자.

 

0번은 혹시 모르니까 에러 검사용으로 비워놓고,

첫번째 유저에겐 1, 두번째 유저에겐 2..

이런식으로 players[]배열을 채워나간다고 생각해보자.

 

이런 구현은 보통 static변수를 이용한다.

 

static int Player::count = 1;

 

이후 유저가 접속 할 때마다..

players\[Player::count++\].connect = true;

 

이런 구현이 가장 생각하기 쉬울 것이다.

 

이렇게 2, 3, 4, ... 쭉쭉쭉 증가해 나가다가

count가 players\[\]배열의 크기보다 커지면 count를 다시 0으로 되돌려 할당해준다.

편의상 players\[\]배열의 크기를 10,000으로 가정한다.

count는 1부터 2, 3, 4, 5, .... 9999 까지 증가하다가

10,000 이 되는 순간 1로 돌아간다.

 

그런데, 한바퀴 돌았음에도 1번 유저가 아직 종료를 안했다면?

 

이미 사용중인 메모리에 다른 유저를 우겨넣을 순 없으므로,

다음 인덱스를 찾아봐야 할 것이다.

 

이때 빈 공간을 찾을 때까지 루프를 돌아야 함을 알 수 있다.

하지만 진짜 심각한 문제는 빈 공간이 없을 때 일어난다.

 

사용가능한 인덱스가 없다는 것을 확신하기 위해서는

10000(-1)개의 배열 원소를 일일이 확인해봐야하는 것이다.

 

Player클래스가 한 캐시라인에 여러 개가 들어갈 만큼 아담한 클래스가 아니므로

이 작업을 모두 수행하는 데는 무시할 수 없는 시간이 걸릴 것이다.

 

그렇다면 이 문제는 어떻게 해결해야 할 것인가?

 

Free-Index-Queue를 만들어 해결할 수 있다.

유저를 받아들이기 전부터, 1부터 9999까지의 숫자가 담긴 큐를 만들어 놓고,

유저가 접속 할 때마다 사용할 인덱스를 큐에서 하나씩 꺼내서 쓰는 것이다.

 

즉 처음에 유저가 한 명도 접속하지 않았을 때,

freeQueue는 9999개의 숫자를 가지고 있고,

players\[\] 배열은 0명의 유저 정보를 저장하고 있다.

 

유저가 한 명 접속하면

freeQueue에서 pop한 인덱스를 players\[\]배열에 사용한다.

 

그러면

freeQueue는 9998개의 숫자를 가지고 있고,

players\[\] 배열은 1명의 유저 정보를 저장하고 있는 형태가 된다.

 

게임이 흥하여 동접자 수가 꽉 차면

freeQueue의 원소는 0개,

players\[\]배열은 9999명의 정보를 저장하고 있는 형태가 된다.

 

어느정도 공기를 넣은 풍선 두 개가 있을 때,

두 풍선의 입구를 맞붙이고, 한 쪽 풍선만을 쥐어짜면 다른 쪽 풍선이 부풀어 오르는 것과

비슷한 형태라고 보면 되겠다.

 

이러면 players\[\]배열이 가득 찼을 때, 배열을 순회 할 필요 없이 유저가 가득 찼음을 알아낼 수 있다.

어떻게? freeQueue.size()가 0인 걸로.

이렇게 index 재사용에서의 성능 문제도 개선했다.

 

이제 정말 만사 오케이인가?

 

아니다. 유저는 수시로 접속과 종료를 반복한다.

첫번째로 접속한, index == 1인 유저가 종료 후 다시 접속한다고 해서

또다시 index를 1로 할당받을리는 없다. 1번 유저가 종료한 후 재접속 하기 전에,

다른 유저가 접속하여 index 1을 할당받을 수도 있는 법이다.

 

이 재할당이 문제가 된다.

게임 서버 강의 시간에 정말 많은 것을 배웠지만, 가장 감사한 것은 이러한 시행착오를 크게 줄일 수 있었다는 점이다.

이 index재할당이 왜 문제가 되는지는 조금만 생각해보면 답이 나온다.

 

아까 보았던 메모리 익셉션 시나리오를 조금 수정해서 다시 생각해보자.

 

a. 두 유저 1과 2가 한 게임룸에서 1:1 로 게임을 하고 있다.

b. 유저 1이 다른 유저 2에게 총을 쏘았다.

c. 유저 2에게 피격 판정 패킷이 전송된다.

(유저에게 부여된 숫자는 해당 유저의 index다)

 

이 시나리오에서 b와 c 사이에 유저 2가 종료한다고 하자.

 

그런데 공교롭게도 바로 다른 유저가 접속하여, 2번 index를 재할당 받았다고 하자.

방금 접속한 불쌍한 유저2는 시작하자 마자 헤드샷을 맞고 사망할지도 모른다.

 

그렇다면 index를 재할당하지 않으려면 어떻게 해야할까?

 

바로 접속한 플레이어마다 유니크한 id를 부여하는 것이다.

(이제서야 NDC슬라이드의 내용에 근접해가고 있다.)

 

(이론상)무한히 증가하는 id를 유저에게 부여하고, index는 id와 매핑하여 사용하는 것이다.

id는 index와는 다르게 독립적인 값으로써, 값이 10,000 이 넘어가도 줄어들지 않고 계속 증가한다.

게임 서버 실행 시부터 종료 시까지 접속하는 모든 유저는 각각 고유한 id값을 갖게 된다.

 

때문에 이전과 같은 재할당 문제가 발생하지 않는다

id로 구분이 가능하기 때문이다.

 

이 id의 자료형으로는 64bit 정수를 사용해도 되지만,

2주에 1번 서버를 리부팅한다고 가정하면 unsigned int 형으로 충분할 수도 있다.

 

리부팅 후엔 id를 다시 1부터 할당해 줄 것이기 때문이다.

이 방법을 사용하면 중간 단계(id->index 바꾸는 것)가 늘어남에 따라,

 

유저 정보에 접근 할 때마다 검색 비용이 추가된다.

이진 탐색을 사용하더라도 동접자가 10000명이면 최대 14번의 메모리 접근이 필요하다.

 

이 때 사용할 것이 바로 무적의 O(1), hashMap이다.

key를 id로 하는 <id, index> 쌍을 hashMap에 저장하는 것이다.

즉 sendPacket()함수의 원형은 또 다음과 같이 변경될 것이다. (자료형은 편의상 int로 정의한다.)

 

before : bool sendPacket(int index, Packet p);
after   :bool sendPacket(int id, Packet p);

이제 유저가 접속하면 다음과 같은 순서로 초기화를 진행하게 된다.

 

1. 유저의 id를 할당한다.

2. freeQueue에서 사용할 index를 얻어온다.

3. <id, index> 를 hashMap에 저장한다.

4. players\[index\] 를 초기화한다.

    그리고 다음과 같은 순서로 유저 정보에 접근하게 된다.

5. 유저의 id로 get()함수를 호출한다. (ex. UserPool::getSocket(id) )

6. hashMap에서 id로 index를 얻는다.

6. players\[index\].socket을 리턴한다.

 

이렇게 구현하면 많은 문제를 해결할 수 있다.

 

 

TBB - 병렬 컨테이너 사용 (concurrent_hash_map) : 멀티쓰레드에서도 안전하게 식별하기

---

자. 지금까지 효율적이고 안정적인 유저 정보 관리에 대해서 알아보았다.

 

여기까지는 서론이고, 이제 진짜 이야기를 시작하려고 한다.

지금까지 적었던 이야기는, 모두 싱글 쓰레드에 해당되는 이야기다.

 

때문에 hashMap에서 얻을 수 있는 자연적인 병렬성에 대해서는 언급하지 않았던 것이다.

 

위에서 설계한 유저 관리 클래스는 게임 서버에서 사용할 수 없다. 

왜냐! 게임 서버는 성능을 위해 멀티쓰레드에서 돌아가기 때문에!

 

두 쓰레드에서 동시에 freeQueue.pop()을 요청하면, 일관성을 잃는다.

hashMap 또한 서로 다른 두 key에 대해 해시값이 같을 경우, 동시에 한 버킷에 들어가면 일관성을 잃는다.

 

결국, 공유 메모리를 사용하는 freeQueue와 hashMap(버킷) 을 Lock으로 보호해야 한다.

그리고 Lock은, 온갖 성능 저하의 주된 요인이다.

이 부분이 보틀넥이 된다면 어떻게 해야 할까?

 

Non-blocking 컨테이너를 직접 짜서 사용할 수도 있다. 

하지만 안타깝게도 내 생산성으론, 이런 컨테이너를 만든 후, 버그가 없다는 것을 증명해 내면 졸업작품을 기간 내에 끝낼 수 없다.

 

결론은, 바퀴를 다시 발명할 필욘 없으므로, Intel TBB의 병렬 컨테이너를 사용하면 된다.

 

사용법은 매우 간단하다. 다음은 intel TBB 홈페이지에 있는 

concurrent_hash_map 에 대한 유저 가이드를 일부 수정한 것이다.

 

 

typedef concurrent_hash_map<int,int> IntTable;
 
IntTable table;
 
void insertValue()( const pair<int, int>& value ) {
    IntTable::accessor a;
    table.insert( a, value );
    //삽입 성공 시
    //a->first == value.first,
    //a->second == value.second 
 
    a.release();
}