Microsoft MVP성태의 닷넷 이야기
닷넷: 2146. C# - ConcurrentDictionary 자료 구조의 동기화 방식 [링크 복사], [링크+제목 복사]
조회: 3020
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
 
(연관된 글이 1개 있습니다.)

C# - ConcurrentDictionary 자료 구조의 동기화 방식

이에 대해 묻는 질문이 있었는데... ^^; 제가 주말에 일이 있어 답변을 못했더니 그사이 삭제가 되었습니다.

암튼, 기존 DictionaryConcurrentDictionary의 구조를 잠시 살펴볼까요? ^^

우선 Dictionary는 동기화가 제공되지 않습니다. 따라서 당연히 다중 스레드에서의 접근이 안전하지 않으므로 반드시 lock을 걸어줘야 합니다.

재미있는 점이 하나 있다면, Dictionary의 경우 동기화는 제공하지 않지만 기초적인 수준에서의 "깨짐"을 예방하기 위한 수단은 제공한다는 점입니다. 일례로, 열거(enumeration)하는 동안 다른 스레드에서 Write 작업을 하게 되면 무조건 예외를 발생시키는 구조로 작성되었습니다.

이 현상을 간단하게 다음의 코드를 사용하면 재현할 수 있습니다.

namespace ConsoleApp2;

internal class Program
{
    static void Main(string[] args)
    {
        Dictionary<int, int> dict = new Dictionary<int, int>();

        Thread t = new Thread(EnumThreadProc);
        t.Start(dict);

        Thread.Sleep(1000);
        dict[7] = 7;

        t.Join();
    }

    private static void EnumThreadProc(object? obj)
    {
        Dictionary<int, int>? dict = obj! as Dictionary<int, int>;

        foreach (var item in dict!)
        {
            Console.WriteLine(item);
            Thread.Sleep(2000);
        }
    }
}

/* 출력 결과:
[5, 5]
Unhandled exception. System.InvalidOperationException: Collection was modified; enumeration operation may not execute.
   at System.Collections.Generic.Dictionary`2.Enumerator.MoveNext()
   at ConsoleApp2.Program.EnumThreadProc(Object obj)
*/

위의 코드는 EnumThreadProc에서 Dictionary를 열거하는 동안, 다른 스레드에서 "dict[7] = 7" 코드를 수행해 변경하므로 예외가 발생하는데요, 이렇게 할 수 있었던 것은 Dictionary 내에 _version 숫자 필드를 이용해 변경이 있을 때마다 매번 값을 증가시키기 때문입니다.

아래는 Add 메서드에서 호출하는 TryInsert에서 _version 필드의 값이 증가하는 것을 보여주는데,

namespace System.Collections.Generic
{
    // ...[생략]...
    public class Dictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback where TKey : notnull
    {
        // ...[생략]...

        private int _freeCount;
        private int _version;

        // ...[생략]...

        private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior)
        {
            // ...[생략]...

            ref Entry entry = ref entries![index];
            entry.hashCode = hashCode;
            entry.next = bucket - 1; // Value in _buckets is 1-based
            entry.key = key;
            entry.value = value;
            bucket = index + 1; // Value in _buckets is 1-based
            _version++;

            // ...[생략]...

            return true;
        }

        // ...[생략]...
    }
}

이와 함께 Dictionary의 Enumerator.MoveNext 호출 때마다 매번 _version이 바뀐 것은 아닌지 검사하는 코드가 있기 때문에,

public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>, IDictionaryEnumerator
{
    private readonly Dictionary<TKey, TValue> _dictionary;
    private readonly int _version;
    // ...[생략]...

    internal Enumerator(Dictionary<TKey, TValue> dictionary, int getEnumeratorRetType)
    {
        _dictionary = dictionary;
        _version = dictionary._version;
        _index = 0;
        _getEnumeratorRetType = getEnumeratorRetType;
        _current = default;
    }

    public bool MoveNext()
    {
        if (_version != _dictionary._version)
        {
            ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
        }

        // ...[생략]...
    }

    // ...[생략]...
}

예외가 발생할 수 있는 구조입니다. 간단하죠? ^^ 관련해서 아래의 글에서도 _version 필드에 대한 내용을 실었으니 참고하시고.

IEnumerator는 언제나 읽기 전용일까?
; https://www.sysnet.pe.kr/2/0/1308




그렇다면 ConcurrentDictionary는 어떻게 저걸 개선했을까요? 이름에서 알리고 싶은 것처럼, 이것은 다중 스레드에서의 접근을 허용합니다.

따라서, 당연히 다른 스레드에서의 읽기/쓰기가 가능합니다. 실제로 위의 예제 코드에서 Dictionary 타입을 그대로 ConcurrentDictionary로 바꾸기만 한 다음 실행하면 이번엔 InvalidOperationException 예외가 발생하지 않습니다. 이를 위해 _version 필드는 제거되었고, lock을 써서 업데이트에 따른 자료 구조가 깨지는 것을 방지합니다.

관련 코드를 간단하게 살펴볼까요? ^^

우선 열거의 경우, 중간에 목록이 추가되거나 삭제되어도 이를 반영하지 못합니다.

private sealed class Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
{
    private readonly ConcurrentDictionary<TKey, TValue> _dictionary;

    // ...[생략]...

    public bool MoveNext()
    {
        switch (_state)
        {
            // ...[생략]...

            case StateOuterloop: // bucket을 순회
                ConcurrentDictionary<TKey, TValue>.Node?[]? buckets = _buckets;
                Debug.Assert(buckets != null);

                int i = ++_i;
                if ((uint)i < (uint)buckets.Length)
                {
                    // The Volatile.Read ensures that we have a copy of the reference to buckets[i]:
                    // this protects us from reading fields ('_key', '_value' and '_next') of different instances.
                    _node = Volatile.Read(ref buckets[i]);
                    _state = StateInnerLoop;
                    goto case StateInnerLoop;
                }
                goto default;

            case StateInnerLoop: // bucket의 연결 리스트를 순회
                Node? node = _node;
                if (node != null)
                {
                    Current = new KeyValuePair<TKey, TValue>(node._key, node._value);
                    _node = node._next;
                    return true;
                }
                goto case StateOuterloop;

            // ...[생략]...
        }
    }
}

bucket의 경우 현재 배열에 있는 것을 그대로 가져오고, 일단 한번 hash code에 해당하는 슬롯이 비어 있어 지나가면(순회하면) 그걸로 끝입니다. 이전 슬롯에 새로운 hash code에 해당하는 값이 업데이트(추가/삭제) 되었어도 그걸 다시 찾아가서 순회하지는 않습니다.

또한, bucket 내의 연결 리스트도 마찬가지입니다. Current에 해당하는 노드가 삭제되었어도 (atomic하게 업데이트 가능한 포인터 크기만큼의) _next가 null이면 다음 bucket으로 넘어가고, 값이 있으면 계속 열거하게 되어 있습니다.

그럼 Add/Update/Delete 작업에 lock이 어떻게 걸리는지 한번 볼까요? ^^

public TValue AddOrUpdate(TKey key, Func<TKey, TValue> addValueFactory, Func<TKey, TValue, TValue> updateValueFactory)
{
    // ...[생략]...

    IEqualityComparer<TKey>? comparer = _comparer;
    int hashcode = comparer is null ? key.GetHashCode() : comparer.GetHashCode(key);

    while (true)
    {
        if (TryGetValueInternal(key, hashcode, out TValue? oldValue))
        {
            // key exists, try to update
            TValue newValue = updateValueFactory(key, oldValue);
            if (TryUpdateInternal(key, hashcode, newValue, oldValue))
            {
                return newValue;
            }
        }
        else
        {
            // key doesn't exist, try to add
            if (TryAddInternal(key, hashcode, addValueFactory(key), updateIfExists: false, acquireLock: true, out TValue resultingValue))
            {
                return resultingValue;
            }
        }
    }
}

private bool TryAddInternal(TKey key, int? nullableHashcode, TValue value, bool updateIfExists, bool acquireLock, out TValue resultingValue)
{
    IEqualityComparer<TKey>? comparer = _comparer;

    // ...[생략]...

    int hashcode =
        nullableHashcode ??
        (comparer is null ? key.GetHashCode() : comparer.GetHashCode(key));

    while (true)
    {
        Tables tables = _tables;
        object[] locks = tables._locks;
        ref Node? bucket = ref tables.GetBucketAndLock(hashcode, out uint lockNo);

        bool resizeDesired = false;
        bool lockTaken = false;
        try
        {
            if (acquireLock)
            {
                Monitor.Enter(locks[lockNo], ref lockTaken);
            }

            // ...[생략]...

            Node? prev = null;
            for (Node? node = bucket; node != null; node = node._next)
            {
                // ...[생략]...
                if (hashcode == node._hashcode && (comparer is null ? _defaultComparer.Equals(node._key, key) : comparer.Equals(node._key, key)))
                {
                    if (updateIfExists)
                    {
                        if (s_isValueWriteAtomic)
                        {
                            node._value = value;
                        }
                        else
                        {
                            var newNode = new Node(node._key, value, hashcode, node._next);
                            if (prev is null)
                            {
                                Volatile.Write(ref bucket, newNode);
                            }
                            else
                            {
                                prev._next = newNode;
                            }
                        }
                        resultingValue = value;
                    }
                    else
                    {
                        resultingValue = node._value;
                    }
                    return false;
                }
                prev = node;
            }

            var resultNode = new Node(key, value, hashcode, bucket);
            Volatile.Write(ref bucket, resultNode);

            // ...[생략]...
        }
        finally
        {
            if (lockTaken)
            {
                Monitor.Exit(locks[lockNo]);
            }
        }

        // ...[생략]...
    }
}

성능을 위해 lock을 전체적으로 걸지 않고 bucket 요소 단위로 걸고 있기 때문에 hash code가 같지 않다면 동시에 업데이트가 가능하게 작성했습니다.

이 상황을 Visual Studio의 디버깅 기능을 이용하면 실제로 테스트하는 것도 가능합니다. 일례로 다음과 같이 예제를 구성하고,

using System.Collections.Concurrent;

namespace ConsoleApp3;

internal class Program
{
    static void Main(string[] args)
    {
        ConcurrentDictionary<int, int> dict = new ConcurrentDictionary<int, int>();

        Thread t = new Thread(UpdateThreadProc);
        t.Start(dict);

        while (true)
        {
            Console.ReadLine();
            dict[2] = 8;
        }
    }

    private static void UpdateThreadProc(object? obj)
    {
        ConcurrentDictionary<int, int>? dict = obj! as ConcurrentDictionary<int, int>;

        dict![2] = 7;
    }
}

이후, ConcurrentDictionary의 Source Code에 TryAddInternal 메서드의 Monitor.Enter 위치에 앞/뒤로 각각 BP를 걸어둬 F5 키를 눌러 실행합니다. 테스트의 의도가 대충 그려지시죠? ^^

UpdateThreadProc에 의해 TryAddInternal 내부의 Monitor.Enter 뒤에 있는 BP까지 실행한 다음, 해당 스레드를 Visual Studio 스레드 창(Ctrl+Alt+H)을 이용해 "Freeze" 시킵니다.

이제 프로세스 실행을 재개하면 Monitor.Lock은 점유된 상태가 되고, 콘솔에 아무 키나 누르면 "dict[2] = 8;"가 실행돼 다시 Monitor.Enter 위치의 앞에 있는 BP에서 멈추게 될 것입니다. 당연히 hash code가 같기 때문에 bucket의 위치도, 그것에 대한 lock도 같아 이런 경우 Monitor.Enter 실행 시 블록킹이 걸리게 됩니다.

concurrent_lock_1.png

반면, hash code가 다르도록 코드를 바꾸면,

while (true)
{
    Console.ReadLine();
    dict[3] = 8;
}

같은 bucket을 공유하지 않기 때문에 lock도 달라져 blocking이 걸리지 않습니다.




잘 이해가 되지 않아도 상관없습니다. ^^; 대충 ConcurrentDictionary는 다중 스레드에서 안전하게 사용할 수 있도록 마이크로소프트가 잘 만들어 놨다고만 여겨도 무리가 없을 것입니다.

참고로, python의 경우에도 Dictionary는 스레드에 안전하지 않아 유사한 현상이 발생합니다.




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[연관 글]






[최초 등록일: ]
[최종 수정일: 9/25/2023]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 




1  2  [3]  4  5  6  7  8  9  10  11  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
13522정성태1/11/20241368닷넷: 2200. C# - HttpClient.PostAsJsonAsync 호출 시 "Transfer-Encoding: chunked" 대신 "Content-Length" 헤더 처리
13521정성태1/11/20241475닷넷: 2199. C# - 한국투자증권 KIS Developers OpenAPI의 WebSocket Ping, Pong 처리
13520정성태1/10/20241302오류 유형: 888. C# - Unable to resolve service for type 'Microsoft.Extensions.ObjectPool.ObjectPool`....'
13519정성태1/10/20241359닷넷: 2198. C# - Reflection을 이용한 ClientWebSocket의 Ping 호출파일 다운로드1
13518정성태1/9/20241484닷넷: 2197. C# - ClientWebSocket의 Ping, Pong 처리
13517정성태1/8/20241413스크립트: 63. Python - 공개 패키지를 이용한 위성 이미지 생성 (pystac_client, odc.stac)
13516정성태1/7/20241515닷넷: 2196. IIS - AppPool의 "Disable Overlapped Recycle" 옵션의 부작용
13515정성태1/6/20241773닷넷: 2195. async 메서드 내에서 C# 7의 discard 구문 활용 사례 [1]
13514정성태1/5/20241518개발 환경 구성: 702. IIS - AppPool의 "Disable Overlapped Recycle" 옵션
13513정성태1/5/20241439닷넷: 2194. C# - WebActivatorEx / System.Web의 PreApplicationStartMethod 특성
13512정성태1/4/20241442개발 환경 구성: 701. IIS - w3wp.exe 프로세스의 ASP.NET 런타임을 항상 Warmup 모드로 유지하는 preload Enabled 설정
13511정성태1/4/20241421닷넷: 2193. C# - ASP.NET Web Application + OpenAPI(Swashbuckle) 스펙 제공
13510정성태1/3/20241371닷넷: 2192. C# - 특정 실행 파일이 있는지 확인하는 방법 (Linux)
13509정성태1/3/20241412오류 유형: 887. .NET Core 2 이하의 프로젝트에서 System.Runtime.CompilerServices.Unsafe doesn't support netcoreapp2.0.
13508정성태1/3/20241467오류 유형: 886. ORA-28000: the account is locked
13507정성태1/2/20242186닷넷: 2191. C# - IPGlobalProperties를 이용해 netstat처럼 사용 중인 Socket 목록 구하는 방법파일 다운로드1
13506정성태12/29/20231624닷넷: 2190. C# - 닷넷 코어/5+에서 달라지는 System.Text.Encoding 지원
13505정성태12/27/20231799닷넷: 2189. C# - WebSocket 클라이언트를 닷넷으로 구현하는 예제 (System.Net.WebSockets)파일 다운로드1
13504정성태12/27/20231674닷넷: 2188. C# - ASP.NET Core SignalR로 구현하는 채팅 서비스 예제파일 다운로드1
13503정성태12/27/20231582Linux: 67. WSL 환경 + mlocate(locate) 도구의 /mnt 디렉터리 검색 문제
13502정성태12/26/20231667닷넷: 2187. C# - 다른 프로세스의 환경변수 읽는 예제파일 다운로드1
13501정성태12/25/20231509개발 환경 구성: 700. WSL + uwsgi - IPv6로 바인딩하는 방법
13500정성태12/24/20231551디버깅 기술: 194. Windbg - x64 가상 주소를 물리 주소로 변환
13498정성태12/23/20231836닷넷: 2186. 한국투자증권 KIS Developers OpenAPI의 C# 래퍼 버전 - eFriendOpenAPI NuGet 패키지
13497정성태12/22/20231654오류 유형: 885. Visual Studiio - error : Could not connect to the remote system. Please verify your connection settings, and that your machine is on the network and reachable.
13496정성태12/21/20231590Linux: 66. 리눅스 - 실행 중인 프로세스 내부의 환경변수 설정을 구하는 방법 (gdb)
1  2  [3]  4  5  6  7  8  9  10  11  12  13  14  15  ...