[C#] ConcurrentDictionary<TKey,TValue>란 무엇인가?

System.Collections.Generic.ConcurrentDictionary<TKey,TValue>에 대해 공부하다가 알게된 정보를 정리한 글입니다.
주로 어떤 원리로 작동되는 지 공부해 정리하였습니다.

ConcurrentDictionary<TKey,TValue>란?

• Dictionary의 쓰레드 세이프 버전이다. (Dictionary에 대해 먼저 공부하고 오면 도움이 된다)
• 사용법은 Dictionary와 비슷하다고 생각하면 된다
• Tables 라는 클래스를 통해 데이터를 가지고 있는다

Node

• Key와 Value를 저장하는 타입
• 데이터를 보관할 때 단일 연결 리스트처럼 구조가 되어 있다
• 내부 데이터
  • _key : Key값
  • _value : Value값
  • _next : 다음 Node (volatile)
  • _hash : hash값

VolatileNode

• 데이터는 Node 하나뿐인 Struct타입
• Node는 volatile으로 설정되었다
  • Node을 그대로 배열로 사용할 경우 배열에서 안전하게 읽으려면 Volatile.Read()를 수행해야한다
  • 그러나 이는 불필요한 ldelema 를 트리거하여 CastHelpers.LdelemaRef 를 호출한다
  • Node를 감싸는 VolatileNode을 사용하면 인라인되지 않은 호출은 사라진다

Tables

• ConcurrentDictionary의 내부 상태를 보관하는 테이블이다
• 중요 내부 데이터
  • IEqualityComparer<TKey>? _comparer : 테이블에서 조회에 사용할 Comparer
  • VolatileNode[] _buckets : VolatileNode 배열, 데이터 저장 배일임
  • object[] _locks : 상호배제를 위한 lock 객체 배열
  • int[] _countPerLock : 각 lock으로부터 보호되는 요소 수, _locks 각 인덱스마다 몇 개씩 요소가 보호되는지 확인할 수 있다

생성자

• 모든 생성자가 객체를 할당할 때 배열도 할당한다
• _locks과 _countPerLock은 길이가 같다
  • _countPerLock[0]의 의미는 _locks[0]이 보호하는 요소의 개수이기 때문에 서로 길이가 같다
• _buckets는 capacity 크기의 배열이 할당된다
• _buckets.Length / _locks.Length 는 lock 객체마다 최대로 보호할 수 있는 요소 수입니다

동작

요소 추가

• Lock 부분
  • Hash를 통해 _buckets[index] 접근한다
  • index % _locks.Lenght 해서 나온 정수를 LockIndex라고 한다
  • 멀티스레드 환경에서 같은 요소에 동시 엑세스를 막기 위해서 _locks[LockIndex]를 lock한다
  • 같은 Hash 요소는 LockIndex도 같기 때문에 같은 요소에 대한 동시 엑세스를 막을 수 있다
• bucket._next 를 순회하면서 찾지 못하면 buckets에 추가한다
  • 만약 기존에 이미 연결되어 있었다면 추가된 bucket._next로 참조된다
  • 단일 연결 리스트처럼 된다
• 요소가 추가되면서 _countPerLock[LockIndex] 도 증가한다
• lock 객체가 보호하는 요소 개수가 최대 개수를 초과하면 resize된다
• Hash충돌이 일정 횟수 이상 발생하면 resize된다

요소 갱신

• 요소 추가의 Lock 부분은 동일하고 이후 bucket._next를 순회하면서 같은 요소가 이미 있는 경우에만 _value를 갱신한다
• 요소가 추가되는 것이 아니므로 _countPerLock이 증가되지 않고 resize되지 않는다

요소 제거

• 요소 추가의 Lock 부분은 동일하고 이후 bucket._next를 순회하면서 같은 요소가 이미 있는 경우에만 요소를 제거한다
• 요소가 제거되어 _countPerLock이 감소한다
• resize되지 않는다

Resize

• _locks 모두 lock 상태로 만들어 수정이 이루어 지지 않도록 만든다
• _buckets의 크기의 2배보다 큰 소수만큼의 배열을 할당한다
• 기존 _buckets에 있던 모든 요소를 새 배열에 전부 복사한다
• 복사 후 _locks 모두 lock 상태를 푼다

출처

• Microsoft 공식 문서
• Microsoft Reference Source

---

💻 열심히 공부해서 작성 중이니 오류나 틀린 부분이 있을 경우 
  언제든지 댓글 혹은 메일로 알려주시면 감사하겠습니다! 😸

맨 위로 이동하기

CSharp 카테고리 내 다른 글 보러가기