[C++ 게임 서버] 1-17, 18, 19. Lock-Free Stack

Rookiss 님의 '[C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part4: 게임 서버' 를 들으며 배운 내용을 정리하고 있습니다. 관심이 있으신 분은 꼭 한 번 들어보시기를 추천합니다!

[C++ 게임 서버] 1-17, 18, 19. Lock-Free Stack

핵심 :

1. Lock-Free Stack 은 락을 사용하지 않고 여러 쓰레드가 Stack 에 어떻게 하면 제대로 Push/Pop 을 할 수 있는지를 보여준다. popCount 나 참조권/소유권 개념을 활용해 이를 구현할 수 있다.

2. Lock-Free Stack 은 실제로 활용하기에는 까다로우며, Lock 기반의 자료구조보다 더 빠르고 효율적이라고 장담할 수 없다. 결국 경합이 일어났을 때, 실질적으로 삭제를 하는 쓰레드는 1개이어야 하기 때문이다.

3. compare_exchange_weak 은 compare_exchange_strong 과 비교했을 때, spurious fail 이 일어날 수도 있다는 차이가 있다. 그 spurious fail 에 대한 비용이 크지 않을 때는, weak 버전을 사용하는 것이 일반적으로 더 빠르다!

---

이전에 우리는 Lock 을 기반으로 하여 데이터를 Push/Pop 을 할 때 락을 걸고 푸는 자료구조를 구현하였다(실제로는 구경하였다 😅).

그런데 사실 Lock 을 걸지 않고도 멀티 쓰레드 환경에서 같은 결과를 도출해낼 수 있는데, 그게 바로 Lock-Free 한 자료구조 되시겠다.

언뜻 들으면 Lock-Free 이니 더 빠르고 효율적일 것 같지만, 사실 디버깅이 어렵고 불안정하며 때로는 더 느린 경우도 있다고 하니, 주의해서 사용하는 것이 좋다고 한다 😂 (실제로 Lock-Free 구현 알고리즘 특허도 있다고 함)

 

그럼 가장 간단한 버전의 코드를 보자(자세한 내용은 주석에 잘 달려 있음).

template<typename T>
class LockFreeStack
{
	struct Node
	{
		Node(const T& value) : data(value)
		{

		}

		T data;
		Node* next;
	};

public:
	
	// 1) 새 노드를 만들고
	// 2) 새 노드의 next = head
	// 3) head = 새 노드

	// [ ][ ][ ][ ][ ][ ][ ]
	// [head]
	void Push(const T& value)
	{
		Node* node = new Node(value);
		node->next = _head;

		/*
		if (_head == node->next)
		{
			_head = node;
			return true;
		}
		else
		{
			node->next = _head;
			return false;
		}
		*/

		while (_head.compare_exchange_weak(node->next, node) == false)
		{
			//node->next = _head;
		}

		// 이 사이에 새치기 당하면?
		//_head = node;
	}
	
	// 1) head 읽기
	// 2) head->next 읽기
	// 3) head = head->next
	// 4) data 추출해서 반환
	// 5) 추출한 노드를 삭제

	// [ ][ ][ ][ ][ ][ ]
	// [head]
	bool TryPop(T& value)
	{
		Node* oldHead = _head;

		/*
		if (_head == oldHead)
		{
			_head = oldHead->next;
			return true;
		}
		else
		{
			oldHead = _head;
			return false;
		}
		*/

		while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)
		{
			//oldHead = _head;
		}

		if (oldHead == nullptr)
			return false;

		// Exception X
		value = oldHead->data;

		// 잠시 삭제 보류
		//delete oldHead;

		// C#, Java 같이 GC가 있으면 사실 여기서 끝

		return true;
	}

private:
	// [ ][ ][ ][ ][ ][ ]
	// [head]
	atomic<Node*> _head;
};

사실 위 코드에서의 핵심은, Push/Pop 을 할 때 head 를 다른 쓰레드에서 건드렸는지를 추가로 체크해 준다는 점이다.

해당 부분은 compare_exchange_weak 함수를 통해 구현되었다.

그런데.. 위에서처럼 정말 바로 삭제를 해도 되는 걸까..? 사실 삭제는 조금 더 주의해서 시도할 필요가 있다. 그래서 해당 부분을 보충해야 하는데...

 

조금 더 길어진 버전을 보자. 이 버전은 popCount 라는 변수를 활용하여, 실제 삭제를 바로 하지 않고 여러 쓰레드가 삭제 시도를 하는 경우를 고려하여 만들어졌다 😉

template<typename T>
class LockFreeStack
{
	struct Node
	{
		Node(const T& value) : data(value), next(nullptr)
		{

		}

		T data;
		Node* next;
	};

public:
	
	// 1) 새 노드를 만들고
	// 2) 새 노드의 next = head
	// 3) head = 새 노드
	void Push(const T& value)
	{
		Node* node = new Node(value);
		node->next = _head;

		while (_head.compare_exchange_weak(node->next, node) == false)
		{
		}
	}
	
	// 1) head 읽기
	// 2) head->next 읽기
	// 3) head = head->next
	// 4) data 추출해서 반환
	// 5) 추출한 노드를 삭제
	bool TryPop(T& value)
	{
		++_popCount;

		Node* oldHead = _head;

		while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)
		{
		}

		// oldHead 가 nullptr 면 이미 누군가 그 사이에 삭제를 해 버린 것
		if (oldHead == nullptr)
		{
			--_popCount;
			return false;
		}

		value = oldHead->data;
		TryDelete(oldHead);
		return true;
	}
	
	// 1) 데이터 분리
	// 2) Count 체크
	// 3) 나 혼자면 삭제
	void TryDelete(Node* oldHead)
	{
		// 나 외에 누가 있는가?
		if (_popCount == 1)
		{
			// 나 혼자네?

			// 이왕 혼자인거, 삭제 예약된 다른 데이터들도 삭제해보자
			// 기존 값을 리턴하면서, 인자값으로 변수 값을 변경하는 일이 원자적으로 일어난다.
			Node* node = _pendingList.exchange(nullptr);

			if (--_popCount == 0)
			{
				// 끼어든 애가 없음 -> 삭제 진행
				// 이제와서 끼어들어도, 어차피 데이터는 분리해둔 상태~!
				DeleteNodes(node);
			}
			else if (node)
			{
				// 누가 끼어들었으니 다시 갖다 놓자
				ChainPendingNodeList(node);
			}

			// 내 데이터는 삭제
			delete oldHead;
		}
		else
		{
			// 누가 있네? 그럼 지금 삭제하지 않고, 삭제 예약만
			// 삭제 예약을 한다는 것은, _pendingList 에 현재 oldHead 를 추가한다는 뜻이다.
			ChainPendingNode(oldHead);
			--_popCount;
		}
	}

	// 새롭게 제거될 List 의 마지막에 기존의 _pendingList 의 head 를 붙이고...
	// _pendingList 의 Head 가 다시 first 를 가리키도록 만든다
	void ChainPendingNodeList(Node* first, Node* last)
	{
		last->next = _pendingList;

		while (_pendingList.compare_exchange_weak(last->next, first) == false)
		{
		}
	}

	void ChainPendingNodeList(Node* node)
	{
		Node* last = node;
		while (last->next)
			last = last->next;

		ChainPendingNodeList(node, last);
	}

	void ChainPendingNode(Node* node)
	{
		ChainPendingNodeList(node, node);
	}

	static void DeleteNodes(Node* node)
	{
		while (node)
		{
			Node* next = node->next;
			delete node;
			node = next;
		}
	}

private:
	atomic<Node*> _head;

	atomic<uint32> _popCount = 0; // Pop을 실행중인 쓰레드 개수
	atomic<Node*> _pendingList; // 삭제 되어야 할 노드들 (첫번째 노드)
};

 

그런데 사실 C# 같은 언어에서는 메모리 관리를 자체적으로 해 주기 때문에, C++ 에서처럼 명시적으로 delete 를 호출해 주지 않아도 된다.

만약 smart pointer 를 활용하면 그런 언어에서 제공하는 것과 비슷한 느낌으로 구현할 수 있지 않을까...? 싶은데, 아래 코드는 shared_pointer 를 활용하여 자체적으로 메모리가 관리되도록 LockFreeStack 을 만드는 방법을 보여준다! 😁

template<typename T>
class LockFreeStack
{
	struct Node;

	struct CountedNodePtr
	{
		// 참조권
		int32 externalCount = 0;
		Node* ptr = nullptr;
	};

	struct Node
	{
		Node(const T& value) : data(make_shared<T>(value))
		{

		}

		shared_ptr<T> data;
		// 소유권
		atomic<int32> internalCount = 0;
		CountedNodePtr next;
	};

public:
	// [][][][][][][]
	// [head]
	void Push(const T& value)
	{
		CountedNodePtr node;
		node.ptr = new Node(value);
		node.externalCount = 1;
		// [!]
		node.ptr->next = _head;
		while (_head.compare_exchange_weak(node.ptr->next, node) == false)
		{
		}
	}
	
	// [][][][][][][]
	// [head]
	shared_ptr<T> TryPop()
	{
		CountedNodePtr oldHead = _head;
		while (true)
		{
			// 참조권 획득 (externalCount를 현 시점 기준 +1 한 애가 이김)
			IncreaseHeadCount(oldHead);
			// 최소한 externalCount >= 2 일테니 삭제X (안전하게 접근할 수 있는)
			Node* ptr = oldHead.ptr;

			// 데이터 없음
			if (ptr == nullptr)
				return shared_ptr<T>();

			// 소유권 획득 (ptr->next로 head를 바꿔치기 한 애가 이김)
			if (_head.compare_exchange_strong(oldHead, ptr->next))
			{
				shared_ptr<T> res;
				res.swap(ptr->data);

				// external : 1 -> 2(나+1) -> 4(나+1 남+2)
				// internal : 1 -> 0
				const int32 countIncrease = oldHead.externalCount - 2;

				// fetch_add 는 더하기 이전의 값을 리턴한다!
				// 즉, internalCount 의 원래 값이 -countIncrease 라면... ptr 를 삭제해도 된다.
				// 소유권을 얻기 실패한 녀석들의 갯수만큼 internalCount 가 fetch_sub 되었기 때문이다.
				if (ptr->internalCount.fetch_add(countIncrease) == -countIncrease)
					delete ptr;

				return res;
			}
			// 즉, internalCount 가 1 인 녀석... 마지막에 사용하는 녀석이 ptr 를 삭제해준다!
			else if (ptr->internalCount.fetch_sub(1) == 1)
			{
				// 참조권은 얻었으나, 소유권은 실패 -> 뒷수습은 내가 한다
				delete ptr;
			}
		}
	}

private:
	void IncreaseHeadCount(CountedNodePtr& oldCounter)
	{
		while (true)
		{
			CountedNodePtr newCounter = oldCounter;
			newCounter.externalCount++;

			// 만약 내가 헤드를 잡을 수 있으면...
			if (_head.compare_exchange_strong(oldCounter, newCounter))
			{
				oldCounter.externalCount = newCounter.externalCount;
				break;
			}
		}
	}

private:
	atomic<CountedNodePtr> _head;
};

위에서는 참조권과 소유권에 대한 개념을 각각 externalCount 와 internalCount 로 분리하여 사용하고 있다.

참조에 대한 개념은 값을 체크하는 느낌으로, 소유에 대한 개념은 값을 실제로 사용(swap) 하고 메모리를 해제하는 용도로 사용하고 있다.

해당 코드는 이해하기 조금 어려울 수 있으니, 일단 참고로 알아두자 😅

 

+ 위의 코드에서 compare_exchange_strong 과 compare_exchange_weak 을 혼용하여 사용하고 있는데... 그 차이는 무엇일까?

compare_exchange_weak 의 경우, 'spuriously fail' 할 수 있다고 한다. 그 말은, object.compare_exchange_weak(expected, desired) 라는 코드에서, object == expected 인 경우에도, 결과를 false 로 리턴할 수 있다는 것을 의미한다(atomic 하게 체크를 하지 않아서 그런 현상이 생긴 것으로 보인다).

그렇다면 compare_exchange_weak 은 어떤 상황에서 사용하면 좋은 것일까..? 🤔

만약 spurious fail 에 대한 비용이 낮거나(즉, loop 안에서 돌아가니까 그냥 loop 한번만 더 돌면 spurious fail 을 다음 트라이에서 넘길 수 있는 경우), 그러한 fail 이 fatal 하지 않은 경우, weak 버전을 사용하는 것이 더 빠르다고 한다! 😉

물론 loop 이 아닌 경우에는 strong 버전을 써야 하겠다 (참고 설명) 😅

두 녀석의 차이에 대한 자세한 내용은 이 링크를 참고하자! 😁