[C# 동시성 프로그래밍] # 9 컬렉션

불변 컬렉션(immutable collection)은 절대 변경할 수 없는 컬렉션 인스턴스다.

불변 컬렉션은 단일 스레드, 비동시성 애플리케이션에서도 유용하다.

 

열거 같은 읽기 전용 연산은 직접 불변 인스턴스를 사용하고 항목 추가 같은 쓰기 연산은 기존 인스턴스를 변경하지 않고 새로운 불변 인스턴스를 반환한다.

낭비처럼 보여도 불변 컬렉션은 대부분 메모리를 공유하기 때문에 그렇게 낭비는 아니다. 또 불변 컬렉션은 여러 스레드에서 사용해도 절대 안전하다는 장점이 있다.

 

변경할 수 없으니 스레드로부터 안전하다.

 

 

스레드로부터 안전한 컬렉션

- 스레드로부터 안전한 가변 컬렉션 인스턴스는 여러 스레드가 동시에 변경할 수 있다. 스레드로부터 안전한 컬렉션은 정교한 잠금(fine-grained locks)과 무잠금(lock-free) 기법을 함께 사용해서 스레드의 차단 시간을 최소화한다.

대게 아예 차단하지 않는다. 스레드로부터 안전한 컬렉션의 상당수는 컬렉션을 열거하면 컬렉션의 스냅샷(snapshot)을 생성한 뒤에 스냅샷을 열거한다. 스레드로부터 안전한 컬렉션의 가장 큰 장점은 여러 스레드가 안전하게 사용할 수 있다는 점이다.

컬렉션의 연산이 코드를 차단하더라도 아주 잠깐 차단 할 뿐이다.

1️⃣ 스레드 안전한 가변 컬렉션

ConcurrentDictionary, ConcurrentQueue, ConcurrentBag 같은 스레드 안전 컬렉션은 여러 스레드가 동시에 데이터를 추가·삭제·수정할 수 있도록 설계돼 있다.
이런 컬렉션은 내부적으로 정교한 잠금(fine-grained locks)과 무잠금(lock-free) 알고리즘을 조합해, 스레드가 오랫동안 대기하지 않도록 구현돼 있다.

---

2️⃣ 열거(Enumeration) 방식

대부분의 스레드 안전 컬렉션은 컬렉션을 열거할 때 스냅샷(snapshot)을 만든다.
즉, 열거가 시작될 때의 상태를 별도로 복사해 두고, 그 스냅샷을 기준으로 foreach 등을 수행한다.
그래서 열거 중에 다른 스레드가 컬렉션을 변경해도 현재 열거는 영향을 받지 않는다(단, 스냅샷 이후의 변경 내용은 열거 결과에 반영되지 않는다).

---

3️⃣ 차단(Blocking) 여부

연산 중에 잠금이 필요한 경우가 있더라도 아주 짧게만 잠금이 걸리도록 설계돼 있다.
어떤 연산은 잠금을 전혀 사용하지 않는 lock-free 방식으로 동작하기도 한다.
즉, 스레드가 멈춰 서 있는 시간을 최소화하거나 아예 없애는 것이 목표다.

---

4️⃣ 가장 큰 장점

이런 컬렉션의 핵심 장점은 여러 스레드가 동시에 안전하게 데이터를 읽고 쓸 수 있다는 점이다.
별도의 동기화 코드를 직접 작성하지 않아도 컬렉션이 스레드 간 경쟁을 잘 처리해 준다.

---

➡️ 결론
스레드 안전 컬렉션은 멀티스레드 환경에서 데이터 무결성을 보장하면서도, 잠금으로 인한 병목을 최소화하도록 설계된 자료구조라고 이해하면 된다.

 

생산자/소비자 컬렉션

- 생산자/소비자 가변 컬렉션 인스턴스는 특별한 목적을 염두에 두고 만들어졌다. 즉 가능한 여러 생산자가 항목을 컬렉션에 밀어 넣을 수 있어야 하는 동시에 가능한 여러 소비자가 컬렉션에서 항목을 당겨 갈 수 있어야 한다.

따라서 생산자/소비자 컬렉션은 생산자 코드와 소비자 코드 사이의 다리 역할을 하며 컬렉션의 항목 수를 제한하는 옵션도 갖고 있다. 생산자/소비자 컬렉션은 블로킹 API 또는 비동기 API를 지닐 수 있다.

예를 들어, 컬렉션이 비어 있을 때 블로킹 생산자/소비자 컬렉션은 새로운 항목이 추가될 때까지 호출한 소비자 스레드를 차단한다. 하지만 비동기 생산자/소비자 컬렉션은 다른 항목이 추가될 때까지 호출한 소비자 스레드가 비동기적으로 기다릴 수 있다.

 

표 9-1 생산자/소비자 컬렉션

기능	채널	BlockingCollection<T>	BufferBlock<T>	AsyncProduceConsumerQueue<T>	AsyncCollection<T>
큐 역할	O	O	O	O	O
스택/백 역할	X	O	X	X	O
동기 API	O	O	O	O	O
비동기 API	O	X	O	O	O
가득 차면 항목 버림	O	X	X	X	X
MS의 검증	O	O	O	X	X

 

채널: System.Threading.Channels 누겟 패키지

BufferBlock<T>:  System.Threading.Tasks.Dataflow 누겟 패키지

AsyncProducerConsumerQueue<T>, AsyncCollection<T>: Nito.AsyncEx 누겟 패키지

 

9.1 불변 스택과 불변 큐

자주 바뀌지 않으며 여러 스레드에서 안전하게 사용할 수 있는 스택 또는 큐를 불변 스택과 불변 큐라 한다.

큐는 작업의 수행 순서로, 스택은 작업 취소(undo) 명령의 실행 순서로 사용 가능하다.

 

둘다 기본적인 Stack<T>, Queue<T>와 매우 비슷하게 동작한다.

성능 면에서 불변 스택, 불변 큐는 기본적인 스택, 큐와 동일한 시간 복잡도를 지닌다.

 

하지만, 컬렉션을 자주 업데이트해야 하는 상황이면 기본적인 스택, 큐가 더 빠르다.

 

스택은 선입후출(FILO, First In/Last Out) 방식의 데이터 구조다. 다음 코드는 빈 불변 스택을 만들고 항목 2개를 push하고 항목을 열거 한 뒤에 항목 1개를 pop한다.

 

using System.Collections.Immutable;
using System.Diagnostics;

ImmutableStack<int> stack = ImmutableStack<int>.Empty;
stack = stack.Push(13);
stack = stack.Push(7);

// "7" 다음에 "13"을 표시한다.
foreach(int item in stack)
{
    Trace.WriteLine(item);
}

int lastItem;
stack = stack.Pop(out lastItem);
// lastItem == 7

 

이 예제는 로컬 변수 stack을 계속 덮어쓰고 있다는 점에 주의한다.

불변 컬렉션은 업데이트 한 컬렉션을 반환하는 패턴을 따르기 때문에 원본 컬렉션의 참조는 바뀌지 않는다.

 

즉 한 번 불변 컬렉션 인스턴스의 참조를 얻고 나면, 이 참조는 절대 바뀌지 않는 다는 뜻이다.

 

using System.Collections.Immutable;
using System.Diagnostics;

ImmutableStack<int> stack = ImmutableStack<int>.Empty;
stack = stack.Push(13);
ImmutableStack<int> biggerStack = stack.Push(7);

// "7" 다음에 "13"을 표시한다.
foreach(int item in biggerStack)
{
    Trace.WriteLine(item);
}

//"13"만 표시한다.
foreach(int item in stack)
{
    Trace.WriteLine(item);
}

 

상키 코드에서 두 스택은 항목 13의 저장에 사용하는 메모리를 공유한다. 이런 구현은 매우 효율적인 동시에 현재 상태를 간단하게 스냅샷할 수 있다는 장점이 있다.

 

불변 컬렉션 인스턴스는 기본적으로 스레드로부터 안전하다는 특징이 있지만, 단일 스레드 애플리케이션에도 사용 가능하다.

 

개인적인 경험상 코드가 함수형에 가까울 때 또는 많은 수의 스냅샷을 저장해야 하고 최대한 많은 메모리를 공유하고 싶을 때 특히 불변 컬렉션이 유용했다.

 

큐는 선입 선출 방식의 데이터 구조라는 점만 빼면 스택과 비슷하다.

 

다음 코드는 빈 불변 큐를 만들고 항목 2개를 삽입(enqueue)하고 항목을 열거한 뒤 항목 1개를 삭제(dequeue)한다.

 

using System.Collections.Immutable;
using System.Diagnostics;

ImmutableQueue<int>queue = ImmutableQueue<int>.Empty;
queue = queue.Enqueue(13);
queue = queue.Enqueue(7);

//"13" 다음에 "7"을 표시한다.
foreach(int item in queue)
{
    Trace.WriteLine(item);
}

int nextItem;
queue = queue.Dequeue(out nextItem);
//"13"을 표시한다.
Trace.WriteLine(nextItem);

 

 

- 불변 컬렉션의 인스턴스는 절대 바뀌지 않는다.

- 절대 바뀌지 않기 때문에 당연 스레드로부터 안전하다.

- 불변 컬렉션을 변경하는 메서드를 호출하면 변경한 내용을 반영한 새로운 컬렉션을 반환한다.

 

불변 컬렉션은 스레드로부터 안전하지만, 불변 컬렉션의 참조는 스레드로부터 안전하지 않다. 불변 컬렉션을 참조하는 변수는 다른 변수와 마찬가지로 동기화 보호가 필요하다.

 

불변 컬렉션은 상태 공유에 이상적이나 통신 경로로는 적당치 않다. 특히 스레드 간 통신에 불변 큐를 사용하면 안된다. 이럴 땐 생산자/소비자 큐가 훨씬 더 적합하다.

 

불변 큐 (Immutable Queue)

• 정의
  • 한 번 생성하면 내용을 변경할 수 없는 큐다.
  • 요소를 추가(Enqueue)하거나 제거(Dequeue)할 때, 기존 인스턴스를 바꾸지 않고 새로운 큐 인스턴스를 반환한다.
• 특징
  • 참조가 공유돼도 안전 → 여러 스레드가 같은 큐 인스턴스를 읽어도 문제가 없다.
  • 함수형 프로그래밍 스타일에 적합하다.
  • System.Collections.Immutable.ImmutableQueue<T> 가 대표적인 구현체다.
• 용도
  • 상태 변화를 최소화해야 하는 코드(불변성 보장)
  • 스냅샷 기반 데이터 처리
  • 동시 읽기(read)가 많고, 수정은 드문 시나리오

---

2️⃣ 생산자/소비자 큐 (Producer/Consumer Queue)

• 정의
  • 여러 생산자(Producer) 가 항목을 추가하고, 여러 소비자(Consumer) 가 항목을 꺼내는 구조의 큐다.
  • 스레드 간 데이터를 안전하게 교환하도록 설계됐다.
• 특징
  • 스레드 안전(thread-safe)하며, 대개 잠금(fine-grained lock) 또는 lock-free 알고리즘을 사용한다.
  • 항목 수를 제한하는 bounded capacity 옵션을 가질 수 있다.
  • 블로킹(Blocking) API와 비동기(Async) API를 지원할 수 있다.
  • .NET에서는 BlockingCollection<T> 나 Channel<T>이 대표적이다.
• 용도
  • 생산자와 소비자가 동시에 동작하는 파이프라인
  • 데이터 버퍼, 작업 큐, 로그 처리, 스레드 풀 같은 시나리오

---

📌 비교 요약

구분	불면 큐(Immutable Queue)	생산자/소비자 큐(Produce/Consumer Queue)
데이터 변경	불가능 → 새 큐를 반환	가능 → 동일 인스턴스의 항목을 추가·제거
스레드 안전성	변경이 없으므로 자연스럽게 안전	동시 접근을 고려해 동기화 기법 사용
주요 목적	불변 상태 유지, 참조 공유	스레드 간 안전한 데이터 전달
대표 타입	ImmutableQueue<T>	BlockingCollection<T>, Channel<T>
적합한 시나리오	함수형 스타일, 읽기 위주	파이프라인, 백그라운드 작업 큐

---

➡️ 결론

• 불변 큐는 “데이터 자체가 변하지 않는 안정성” 에 초점이 맞춰진 컬렉션이다.
• 생산자/소비자 큐는 “여러 스레드가 데이터를 안전하게 주고받는 구조” 에 초점이 맞춰진 컬렉션이다.
  즉, 불변 큐는 값의 불변성, 생산자/소비자 큐는 스레드 간 동기화가 핵심 차이다.

 

9.2 불변 리스트

자주 바뀌지 않으며 여러 스레드가 안전하게 사용할 수 있으면서 인덱싱 할 수 있는 데이터 구조가 필요할 때 불변 리스트를 사용할 수 있다.

 

불변 리스트는 인덱싱을 지원하지만 인덱싱의 성능적 특징을 알아야하며, 단순히 List<T>의 대용품이 아니다.

다음 예제와 같이 ImmutableList<T>는 List<T>와 비슷한 메서드를 지원한다.

using System.Collections.Immutable;
using System.Diagnostics;

ImmutableList<int> list = ImmutableList<int>.Empty;
list = list.Insert(0, 13);
list = list.Insert(0, 7);

// "7"다음에 "13"을 표시
foreach (int item in list)
{
    Trace.WriteLine(item);
}

list = list.RemoveAt(1);

 

list.Insert의 첫번째 인자는 인덱스로 0번째 인덱스에 각 13, 7을 순차적으로 넣으니 최종 0번째 인덱스의 값은 7이다.

 

불변 리스트는 불변 리스트의 인스턴스끼리 최대한 많은 메모리를 공유할 수 있게 내부적으로 이진트리로 이뤄진다. 결과적으로 ImmutableList<T>와 List<T>의 공통적인 연산 중에 표 9-2처럼 성능에 차이가 나는 연산도 있다.

 

표 9-2 불변 리스트의 성능차이

 

연산	List<T>	ImmutableList<T>
Add	상각해서 O(1)	O(logN)
Insert	O(N)	O(logN)
RemoveAt	O(N)	O(logN)
item[index]	O(1)	O(logN)

 

 

ImmutableList<T>에 foreach 루프를 실행하면 O(N)의 시간이 걸린다. 같은 컬렉션에 for 루프를 실행하면 O(N * log N)의 시간이 걸린다.

// ImmutableList<T>를 반복하는 가장 좋은 방법이다.
using System.Diagnostics;

foreach (var item in list)
{
    Trace.WriteLine(item);
}

// 이렇게 할 수 있지만, 훨씬 느리다.
for(int idx = 0; idx != list.Count; ++idx)
{
    Trace.WriteLine(list[idx]);
}

 

ImmutableList<T>는 좋은 범용 데이터 구조이나 성능 차이로 인해 무작정 List<T>를 대체해서 사용할 수는 없다. 다만, ImmutableList<T>는 자주 사용하지 않으며 List<T>는 널리 쓰인다. 불변 컬렉션은 신중하게 따져 보고 상황에 맞게 컬렉션을 선택하자.

ImmutableList<T>는 System.Collections.Immutable 누겟 패키지에 있음.

 

9.3 불변 집합

불변 집합은 값을 중복해서 저장할 필요 없고 자주 바뀌지 않으며, 여러 스레드가 안전하게 사용할 수 있는 데이터 구조다.

파일의 단어 색인은 집합의 좋은 예다.

 

불변 집합 형식은 두 가지다. ImmutableHashSet<T>는 고유 항목의 컬렉션이고, ImmutableSortedSet<T>는 정렬된 고유 항목의 컬렉션이다. 두 형식의 인터페이스는 비슷하다.

using System.Collections.Immutable;
using System.Diagnostics;

ImmutableHashSet<int> hashSet = ImmutableHashSet<int>.Empty;
hashSet = hashSet.Add(13);
hashSet = hashSet.Add(7);

// "7"과 "13"을 임의의 순서로 표시.
foreach(int item in hashSet)
{
    Trace.WriteLine(item);
}

hashSet = hashSet.Remove(7);

foreach (int item in hashSet)
{
    Trace.WriteLine(item); // 13 출력
}

 

정렬된 집합만 리스트 처럼 인덱싱 할 수 있다.

using System.Collections.Immutable;
using System.Diagnostics;

ImmutableSortedSet<int> sortedSet = ImmutableSortedSet<int>.Empty;
sortedSet = sortedSet.Add(13);
sortedSet = sortedSet.Add(7);

// "7" 다음 "13"을  순서로 표시.
foreach(int item in sortedSet)
{
    Trace.WriteLine(item);
}

int smallestItem = sortedSet[0];
// smallestItem는 7

sortedSet = sortedSet.Remove(7);

foreach (int item in sortedSet)
{
    Trace.WriteLine(item);
}

 

표 9-3에서와 같이 정렬되지 않은 집합과 정렬된 집합의 성능은 비슷하다.

연산	ImmutableHashSet<T>	ImmutableSortedSet<T>
Add	O(log N)	O(log N)
Remove	O(log N)	O(log N)
Item[index]	해당 없음	O(log N)

ImmutableSortedSet<T> 

 

내부 구조

ImmutableSortedSet<T>는 정렬 상태를 유지하면서 요소를 추가하거나 제거할 수 있도록 균형 이진 탐색 트리(AVL 계열)로 구현돼 있다.
배열처럼 메모리가 연속적이지 않고, 각 노드가 값과 왼쪽/오른쪽 자식을 가지는 트리 형태다.

---

인덱싱 동작

Item[index]는 정렬 순서에서 index번째 요소를 반환하는 기능이다.
배열은 base + (index × size) 방식으로 한 번에 주소를 계산하므로 O(1)이지만,
트리는 이런 산술 계산이 불가능해 루트에서 시작해 서브트리의 크기를 참고하며 원하는 위치까지 내려가야 한다.
트리의 높이가 O(log N)이므로 탐색 비용도 O(log N)이다.

---

요약

자료구조	접근 방식	시간 복잡도
배열 / List<T>	주소 계산 후 바로 접근	O(1)
ImmutableSortedSet<T>	트리를 탐색하며 요소 찾기	O(log N)

➡️ 결론적으로 ImmutableSortedSet<T>에서 인덱스로 요소를 찾는 연산은
정렬 상태를 유지하는 트리 구조를 탐색해야 해서 O(log N) 이다.

 

정렬이 꼭 필요치 않으면 정렬되지 않은 집합을 사용하는 것을 추천한다.

기초적인 동등(equality) 비교만 지원하고 전체적인 비교를 지원하지 않는 형식이 많아 정렬되지 않은 집합은 정렬된 집합 보다 더 많은 형식을 대상으로 사용가능하기 때문이다.

 

불변 집합은 유용한 데이터 구조이나, 커다란 불변 집합을 채우려면 속도가 느려질 수 있다. 대부분 불변 컬렉션에는 가변  방식으로 빠르게 생성한 뒤에 불변 컬렉션으로 변환할 수 있는 특별한 빌더가 있다.

 

ImmutableHashSet<T>와 ImmutableSortedSet<T>는 System.Collections.Immutable 누겟 패키지에 있다.

 

9.4 불변 딕셔너리

자주 바뀌지 않으며 여러 스레드가 안전하게 사용할 수 있는 키/값 컬렉션이 필요할 때 불변 딕셔너리를 사용할 수 있다.

 

불변 딕셔너리 형식은 ImmutableDictionary<TKey, TValue>와 ImmutableSortedDictionary<TKey, TValue> 두가지다.

 

전자는 항목의 순서를 예측할 수없고, 후자는 항목이 정렬 돼 있다.

 

두 컬렉션 형식은 매우 비슷한 멤버를 지닌다.

using System.Collections.Immutable;
using System.Diagnostics;

ImmutableDictionary<int, string> dictionary =
    ImmutableDictionary<int, string>.Empty;

dictionary = dictionary.Add(10, "Ten");
dictionary = dictionary.Add(21, "Twenty-One");
dictionary = dictionary.SetItem(10, "Diez");

// "10Diez"와 "21Twenty-One"를 임의의 순서로 표시한다.
foreach(KeyValuePair<int, string> item in dictionary)
{
    Console.WriteLine($"{item.Key} : {item.Value}");
}


string ten = dictionary[10];  // ten == "Diez"
dictionary = dictionary.Remove(21); // "21Twenty-One" 제거
foreach (KeyValuePair<int, string> item in dictionary)
{
    Console.WriteLine($"{item.Key} : {item.Value}");
}

 

불변 딕셔너리는 업데이트 한 불변 딕셔너리를 반환해야하므로 SetItem 메서드를 사용한다. 결과적으로 키 10의 값은 "Ten"이 아닌 "Diez"로 변경됐다.

 

using System.Collections.Immutable;
using System.Diagnostics;

ImmutableSortedDictionary<int, string> sortedDictionary =
    ImmutableSortedDictionary<int, string>.Empty;

sortedDictionary = sortedDictionary.Add(10, "Ten");
sortedDictionary = sortedDictionary.Add(21, "Twenty-One");
sortedDictionary = sortedDictionary.SetItem(10, "Diez");

// "10Diez" 다음 "21Twenty-One" 순서로 표시한다.
foreach(KeyValuePair<int, string> item in sortedDictionary)
{
    Console.WriteLine($"{item.Key} : {item.Value}");
}


string ten = sortedDictionary[10];  // ten == "Diez"
sortedDictionary = sortedDictionary.Remove(21); // "21Twenty-One" 제거
foreach (KeyValuePair<int, string> item in sortedDictionary)
{
    Console.WriteLine($"{item.Key} : {item.Value}");
}

 

표 9-4 에서 보듯 정렬되지 않은 딕셔너리와 정렬된 딕셔너리의 성능은 비슷하나 정렬이 필요하지 않다면 정렬되지 않은 딕셔너리의 사용을 추천한다. 정렬되지 않은 딕셔너리가 전체적으로 조금 더 빠를 수 있으며, 모든 형식을 키로 사용할 수 있지만, 정렬된 딕셔너리는 완전히 비교할 수 있는 형식만 키로 사용할 수 있다.

 

 

표 9-4 불변 딕셔너리의 성능

연산	ImmutableDictionary<T>	ImmutableSortedDictionary<T>
Add	O(log N)	O(log N)
Remove	O(log N)	O(log N)
Item[key]	O(log N)	O(log N)
Remove	O(log N)	O(log N)