동시 해시 테이블

Concurrent hash table
동일한 해시 테이블에 대한 동시 액세스.

동시 해시 테이블(동시 해시 맵)은 해시 [1][2]함수를 사용하여 여러 스레드에 의한 동시 액세스를 허용하는 해시 테이블의 구현입니다.

따라서 동시 해시 테이블은 여러 스레드가 공유 [1]데이터 간의 연산을 위해 보다 효율적으로 협력할 수 있도록 하는 동시 컴퓨팅에 사용되는 주요 동시 데이터 구조를 나타냅니다.

동시접속, 즉 경합과 관련된 자연적 문제로 인해 구현에 따라 테이블에 동시에 액세스할 수 있는 방법 및 범위가 달라집니다.게다가 그 결과 발생하는 속도 향상은 경합을 해결할 필요가 있는 스레드 수와 선형적이지 않을 수 있으며, [1]이로 인해 처리 오버헤드가 발생합니다.경합 효과를 완화하기 위한 여러 솔루션이 있으며,[1][2][3][4] 각 솔루션은 테이블의 작업 정확성을 유지합니다.

순차적 해시 테이블과 마찬가지로 동시 해시 테이블은 더 복잡한 데이터 유형을 키와 값에 사용할 수 있도록 하는 등 더 광범위한 애플리케이션에 맞게 일반화하고 확장할 수 있습니다.그러나 이러한 일반화는 성능에 부정적인 영향을 미칠 수 있으므로 애플리케이션의 [1]요건에 따라 선택해야 합니다.

동시 해시

동시 해시 테이블을 생성할 때 선택한 해시 알고리즘으로 테이블에 액세스하는 함수는 충돌 해결 전략을 추가하여 동시성을 위해 조정해야 합니다.이러한 전략에서는 접근으로 인해 발생하는 충돌이 데이터 손상을 초래하지 않고 병렬로 사용할 때 효율성을 높이는 방식으로 접근 관리를 해야 합니다.Herlihy와 Shavit은[5] 이러한 전략이 없는 해시 테이블에 대한 액세스를 Cuckoo 해시 알고리즘의 기본 구현에 기초한 예에서 어떻게 동시에 사용할 수 있는지 설명합니다.Fan [6]등은 또한 동시적일 뿐만 아니라 캐시 인접성 및 삽입 처리량을 향상시키면서 해싱 기능의 공간 효율성을 유지하는 뻐꾸기 해싱을 기반으로 한 테이블 액세스 스킴을 설명한다.

해시 테이블의 크기가 제한되지 않아 필요에 따라 증가/축소가 허용되는 경우 해시 알고리즘을 조정하여 이 작업을 허용해야 합니다.여기에는 사용된 해시 함수를 수정하여 크기 조정된 테이블의 새 키 공간을 반영해야 합니다.동시 성장 알고리즘은 Maier [1]등에 의해 설명된다.

어디서 뻐꾸기 해시와 KV색인은 엄청나게 배치 모드에서 parallelized GPU에 의해 사용된다 Mega-KV[7]은 고성능 키-값 가게 시스템이다, GPU에 가속도 NVIDIA와 오크리지 국립 연구소에 의한 추가적인 최적화로, Mega-KV 처리량은 2018년에 다른 높은 기록한 키-값 operat의(까지 888수백만까지 밀려왔다이온s/초).[8]

경합 처리

경합을 일으키는 동시 액세스(빨간색으로 표시)

모든 동시 데이터 구조와 마찬가지로 동시 해시 테이블은 컨텐션의 [3]결과로 동시 컴퓨팅 분야에서 알려진 다양한 문제를 겪습니다.그 예로는 ABA 문제, 레이스 조건, 교착 상태 등이 있습니다.이러한 문제가 발생하는 정도는 동시 해시 테이블의 구현, 특히 테이블을 동시에 실행할 수 있는 조작 및 경합과 관련된 문제를 완화하기 위한 전략에 따라 달라집니다.경합을 처리할 때 주요 목표는 다른 동시 데이터 구조와 같은 것입니다. 즉, 테이블 상의 모든 작업에 대한 정확성을 확인하는 것입니다.동시에 동시에 사용할 경우 순차적 솔루션보다 효율이 높은 방법으로 자연스럽게 수행되어야 합니다.이는 동시성 제어라고도 합니다.

원자 명령

compare-and-swap이나 fetch-and-add 등의 원자적인 명령을 사용하면 다른 액세스가 간섭하기 전에 액세스가 완료되도록 함으로써 경합에 의한 문제를 줄일 수 있습니다.비교 및 스왑 등의 조작에서는 처리할 수 있는 데이터의 크기에 제한이 있는 경우가 많습니다.즉,[1] 테이블의 키와 값의 종류를 적절히 선택하거나 변환해야 합니다.

이른바 HTM(Hardware Transactional Memory)을 사용하면 테이블 조작을 데이터베이스 [3]트랜잭션과 유사하게 생각할 수 있어 원자성을 확보할 수 있습니다.실제 HTM의 예로는 트랜잭션 동기화 확장을 들 수 있습니다.

잠금

잠금을 사용하면 테이블 또는 테이블 내의 값에 동시에 액세스하려는 작업을 올바른 동작을 보장하는 방식으로 처리할 수 있습니다.단, 이는 퍼포먼스에 부정적인 영향을 미칠 [1][6]수 있습니다.특히 사용되는 잠금이 너무 제한적인 경우에는 그렇지 않으면 경합할 수 없고 문제를 일으키지 않고 실행될 수 있는 접근을 차단합니다.라이브록, 교착 상태 또는 [3]기아와 같이 정확성을 위협하는 더 심각한 문제를 피하기 위해 추가 검토가 이루어져야 합니다.

위상 동시성

동시접속은 다른 단계로 그룹화 됩니다.

페이즈 동시 해시 테이블은, 1 종류의 조작만이 허가되는 페이즈(순수 기입 페이즈)를 작성하고, 이어서 모든 스레드에 걸친 테이블 상태의 동기화를 작성함으로써, 액세스를 그룹화한다.이에 대한 공식 증명된 알고리즘은 Shun과 Belloch에 [2]의해 제시되었습니다.

읽기-복사-업데이트

Linux [3]커널 내에서 널리 사용되는 RCU(Read-Copy-Update)는 읽기 수가 [4]쓰기 수를 훨씬 초과하는 경우에 특히 유용합니다.

적용들

당연히 동시 해시 테이블은 순차 해시 테이블이 유용한 곳이라면 어디서든 응용 프로그램을 찾을 수 있습니다.여기서 동시성이 제공하는 이점은 이러한 사용 사례의 잠재적 속도 향상과 확장성 [1]향상에 있습니다.멀티코어 프로세서와 같은 하드웨어가 점점 더 동시연산을 가능하게 되는 것을 고려하면, 이러한 애플리케이션에서의 동시 데이터 구조의 중요성은 [3]꾸준히 증가하고 있습니다.

퍼포먼스 분석

Maier [1]등은 다양한 동시 해시 테이블 구현에 대한 철저한 분석을 수행하여 실제 사용 사례에서 발생할 가능성이 있는 다양한 상황에서 각각의 효과를 파악합니다.가장 중요한 결과는 다음과 같이 요약할 수 있습니다.

작동 컨텐션 메모들
낮다 높은
find 매우 높은 경합에도 불구하고 고유 검색에 성공하거나 실패했을 때 모두 매우 빠른 속도 향상
insert 고속화에 도달하면 키가 여러 값을 유지할 수 있는 경우 높은 경합에 문제가 생깁니다(그렇지 않으면 키가 이미 존재하는 경우 삽입이 폐기됩니다).
update 경합이 낮게 유지되면 기존 값의 덮어쓰기 및 수정이 모두 고속으로 진행됩니다.경합이 낮은 상태일 경우 순차보다 성능이 저하됩니다.
delete 단계 동시성이 최고의 scalability에 도달했습니다.완전 동시 실장에서는,delete사용하다update더미코트가 바짝 뒤쫓고 있었다.

예상대로 낮은 경합은 모든 작업에 걸쳐 긍정적인 동작으로 이어지는 반면 높은 경합은 쓰기에 문제가 있습니다.그러나 후자는 일반적으로 경합이 심한 문제이며, 동시 계산의 이점은 경합 액세스를 제한하는 동시 제어의 자연적 요구 때문에 무효화된다.결과적으로 발생하는 오버헤드는 이상적인 순차 버전보다 성능이 저하됩니다.그럼에도 불구하고 동시 해시 테이블은 적절하게 설계된 구현이 동시에 데이터를 읽는 동시성 이점을 활용함으로써 여전히 매우 빠른 속도를 달성할 수 있다는 것을 관찰할 때 이러한 높은 경합 시나리오에서도 매우 귀중한 것으로 입증됩니다.

그러나 동시 해시 테이블의 실제 사용 사례는 종종 단순히 동일한 연산의 시퀀스가 아니라 여러 유형의 혼합입니다.이와 같이, 이 혼합물이insert그리고.find연산은 특히 관찰할 때 동시 해시 테이블의 속도 향상과 결과적 유용성이 더욱 명확해집니다.find부하가 높은 작업량

궁극적으로 동시 해시 테이블의 성능은 원하는 애플리케이션에 따라 다양한 요소에 따라 달라집니다.구현을 선택할 때는 필요한 일반성, 경합 처리 전략 및 원하는 테이블의 크기를 미리 결정할 수 있는지 또는 그 대신 확장 접근방식을 사용해야 하는지에 대한 몇 가지 생각을 결정하는 것이 중요합니다.

실장

  • Java 1.5 이후 동시 해시 맵은 동시 맵인터페이스를 [9]기반으로 제공됩니다.
  • libcuckoo는 C/C++용 동시 해시 테이블을 제공하여 동시 읽기 및 쓰기를 허용합니다.라이브러리는 GitHub에서 [10]사용할 수 있습니다.
  • 스레드화 빌딩 블록은 C++에 동시에 삽입 및 트래버설이 가능하며 C++11과 유사한 스타일로 유지되는 C++용 비순서 동시 맵을 제공합니다. std::unordered_map인터페이스입니다.에는 동시 비순서 멀티맵이 포함되어 있습니다.이러한 멀티맵을 사용하면 동시 비순서 [11]맵에서 동일한 키에 대해 여러 개의 값이 존재할 수 있습니다.또한 동시 비순서 맵을 기반으로 하여 동시 삭제를 가능하게 하고 내장된 잠금을 포함하는 동시 해시 맵이 제공된다.[12]
  • growt는 소위 민속 구현에 기반하여 C++에 동시에 증가하는 해시 테이블을 제공합니다.이 비성장 구현을 기반으로 다양한 성장 해시 테이블이 제공됩니다.이러한 구현을 통해 읽기, 삽입, 업데이트(키에 있는 현재 값에 따라 값을 업데이트) 및 삭제(묘석을 사용한 업데이트에 기반)를 동시에 수행할 수 있습니다.그 밖에도, 인텔 TSX 를 베이스로 한 변종이 준비되어 있습니다.라이브러리는 GitHub에서 [1][13]사용할 수 있습니다.
  • folly는 C++14 이후를 위해[14] 동시 해시 테이블을 제공합니다.대기 없는 리더와 잠금 기반의 샤드화된 라이터를 보증합니다.GitHub 페이지에 기재된 바와 같이, 이 라이브러리는 Facebook에 [15]유용한 기능을 제공합니다.
  • Junction은 테이블의 특정 멤버 함수에 대한 스레드 안전성을 보장하기 위해 원자 연산을 기반으로 C++에 대한 여러 동시 해시 테이블의 구현을 제공합니다.라이브러리는 GitHub에서 [16]사용할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d e f g h i j k Maier, Tobias; Sanders, Peter; Dementiev, Roman (March 2019). "Concurrent Hash Tables: Fast and General(?)!". ACM Transactions on Parallel Computing. New York, NY, USA: ACM. 5 (4). Article 16. doi:10.1145/3309206. ISSN 2329-4949.
  2. ^ a b c Shun, Julian; Blelloch, Guy E. (2014). "Phase-concurrent Hash Tables for Determinism". SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures. New York: ACM. pp. 96–107. doi:10.1145/2612669.2612687. ISBN 978-1-4503-2821-0.
  3. ^ a b c d e f Li, Xiaozhou; Andersen, David G.; Kaminsky, Michael; Freedman, Michael J. (2014). "Algorithmic Improvements for Fast Concurrent Cuckoo Hashing". Proceedings of the Ninth European Conference on Computer Systems. EuroSys '14. New York: ACM. Article No. 27. doi:10.1145/2592798.2592820. ISBN 978-1-4503-2704-6.
  4. ^ a b Triplett, Josh; McKenney, Paul E.; Walpole, Jonathan (2011). "Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming". USENIXATC'11: Proceedings of the 2011 USENIX conference on USENIX annual technical conference. Berkeley, CA: USENIX Association. p. 11.
  5. ^ Herlihy, Maurice; Shavit, Nir (2008). "Chapter 13: Concurrent Hashing and Natural Parallelism". The Art of Multiprocessor Programming. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. pp. 316–325. ISBN 978-0-12-370591-4.
  6. ^ a b Fan, Bin; Andersen, David G.; Kaminsky, Michael (2013). "MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing". nsdi'13: Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association. pp. 371–384.
  7. ^ 장, 카이; 왕, 카이보; 위안, 위안, 궈, 레이; 리, 루바오; 장, 샤오둥 (2015년)"메가 KV: GPU가 메모리 내 키밸류 저장소의 throughput을 최대화하는 케이스"2015년 제8권 제11호 VLDB 기금의 절차
  8. ^ Chu, Ching-Hing, Potluri, Sreeram, Goswami, Anshuman, Venkata, Manjunath Gorentla, Imam, Neenand, Newburn, (2018) "지속적인 GPU를 통한 메모리에서의 고성능 핵심 작업 설계" 및 "개방"
  9. ^ Java ConcurrentHashMap 매뉴얼
  10. ^ libcuckoo용 GitHub 저장소
  11. ^ 스레딩 빌딩 블록 concurrent_unordered_map 및 concurrent_unordered_multimap 문서
  12. ^ 스레딩 빌딩 블록 concurrent_hash_map 문서
  13. ^ growt용 GitHub 저장소
  14. ^ 동시 해시 맵을 어리석게 구현하기 위한 GitHub 페이지
  15. ^ 어리석음을 위한 GitHub 저장소
  16. ^ Junction의 GitHub 저장소

추가 정보

  • Herlihy, Maurice; Shavit, Nir (2008). "Chapter 13: Concurrent Hashing and Natural Parallelism". The Art of Multiprocessor Programming. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. pp. 299–328. ISBN 978-0-12-370591-4.