씨트리

Ctrie
C-트리엇과 혼동하지 말자.

동시 해시 트리 또는 Ctrie는[1][2] 해시 어레이 매핑된 트라이의 동시 스레드-세이프 잠금 없는 구현이다.동시 지도 추상화를 구현하기 위해 사용된다.특히 확장성이 뛰어난 동시 삽입 및 제거 작업을 가지고 있으며 메모리 효율적이다.[3]O(1), 원자성, 잠금 없는 스냅샷을 지원하는 최초의 동시 데이터 구조다.[2][4]

작전

Ctrie 데이터 구조는 공유 메모리 시스템에서 단일 단어 비교 및 스왑 지침을 기반으로 하는 비차단 동시 해시 어레이 매핑 trie이다.동시 조회, 삽입 및 제거 작업을 지원한다.해시 어레이 맵핑 트라이처럼 해시 값에 전체 32비트 공간을 사용하므로 해시코드 충돌 위험이 낮다.각 노드는 최대 32번의 서브 시도까지 분기할 수 있다.메모리를 보존하기 위해 각 노드는 32비트맵을 포함하고, 각 비트는 분기의 존재를 표시하고 비트맵의 해밍 중량과 동일한 길이의 배열이 뒤따른다.

키는 수정해야 할 노드에서 원자 비교-스왑 작업을 수행하여 삽입된다.업데이트가 독립적으로 적절한 순서로 수행되도록 하기 위해, 각 일반 노드와 하위 노드 사이에 특별한 양방향 노드(I-노드)를 삽입한다.

Ctrie 삽입 작업

위 그림은 Ctrie 삽입 작업을 보여준다.Trie A가 비어 있음 - 이전 노드 C1을 새 키 k1이 있는 새 버전의 C1과 바꾸기 위해 원자 CAS 명령이 사용된다.CAS가 성공하지 못하면 작업이 재시작된다.만약 CAS가 성공한다면, 우리는 Trie B를 얻는다.이 절차는 새 키 k2가 추가될 때 반복된다(트리엇 C).k2와 k3의 경우와 마찬가지로 Ctrie에 있는 키의 두 해시코드가 충돌하는 경우, Ctrie를 적어도 한 수준 더 확장해야 한다 - trie D에는 충돌 키를 모두 보유하는 새로운 노드 C2와 함께 새로운 양방향 노드 I2가 있다.추가 CAS 지침은 양방향 노드 I1 및 I2의 내용에 대해 수행되며, 이러한 CAS 지침은 서로 독립적으로 수행될 수 있으므로 경합이 적은 동시 업데이트가 가능하다.

Ctrie는 루트 리디렉션 노드(또는 루트 I-노드)에 대한 포인터에 의해 정의된다.Ctrie에 대해 다음과 같은 유형의 노드가 정의된다.

구조 INode { main: CNode } 구조 CNode {bmp: 정수 배열: 분기[2^W] } 분기: INode SNode 구조 SNode { k: KeyType v: ValueType }

C-노드는 분기 노드다.일반적으로 32개 지점까지 포함하므로 위의 W는 5개 지점이다.각 분기는 키 값 쌍(S-노드로 표시됨) 또는 다른 I-노드가 될 수 있다.일부 분기가 비어 있을 때 분기 배열에서 32개의 항목이 낭비되는 것을 방지하기 위해 정수 비트맵을 사용하여 어떤 비트가 가득 차 있고 어떤 비트가 비어 있는지 표시한다.도우미 메서드 플래그포스는 특정 레벨의 관련 해시코드 비트를 검사하고 비트맵의 비트 값을 추출하여 비트맵의 설정된 비트 값을 추출하여 해당 위치에 분기가 있는지 여부를 표시한다.비트가 있으면 분기 배열에서 위치도 계산한다.이를 위해 사용되는 공식은 다음과 같다.

비트 = bmp & (1<< ((해시코드 > 레벨) & 0x1F)) pos = 비트카운트(비트 - 1) & bmp)

이 작업은 I-노드만 변이 가능한 노드로 처리하며 다른 모든 노드는 Ctrie에 생성 및 추가된 후 변경되지 않는다는 점에 유의하십시오.

다음은 삽입 작업의 유사 코드를 나타낸 그림이다.

  반항하다 삽입하다(k, v)     r = 읽다(뿌리를 내리다)     만일 아이삽입(r, k, v, 0, 무효의) = 다시 시작 삽입하다(k, v)    반항하다 아이삽입(i, k, v, 부담시키다, 부모)     cn = 읽다(i.본래의)     깃발을 꽂다, 양치류 = 깃발.(k.hc, 부담시키다, cn.bmp)     만일 cn.bmp & 깃발을 꽂다 = 0 {       ncn = cn.삽입된(양치류, 깃발을 꽂다, 스노데(k, v))       만일 CAS(i.본래의, cn, ncn) 돌아오다 네 알겠습니다       다른 돌아오다 다시 시작     }     cn.배열하다(양치류) 짝을 맞추다 {       케이스 죄를 짓다: 이노데 => {         돌아오다 아이삽입(죄를 짓다, k, v, 부담시키다 + W, i)       케이스 코를 풀다: 스노데 =>         만일 코를 풀다.k ≠ k {           nsn = 스노데(k, v)           닌 = 이노데(씨노데(코를 풀다, nsn, 부담시키다 + W))           ncn = cn.갱신된(양치류, 닌)           만일 CAS(i.본래의, cn, ncn) 돌아오다 네 알겠습니다           다른 돌아오다 다시 시작         } 다른 {           ncn = cn.갱신된(양치류, 스노데(k, v))           만일 CAS(i.본래의, cn, ncn) 돌아오다 네 알겠습니다           다른 돌아오다 다시 시작         }     }

노드에 삽입된 방법과 업데이트된 방법은 각각 지정된 위치에 삽입되거나 업데이트된 값을 사용하여 새로운 버전의 C-노드를 반환한다.위의 삽입 작업은 꼬리가 반복되므로 잠시 루프로서 다시 작성할 수 있다는 점에 유의하십시오.다른 수술은 Ctries에 관한 원본 논문에서 더 자세히 설명되어 있다.[1][5]

데이터 구조는 정확하다는[1] 것이 입증되었다 - Ctrie 운영은 원자성, 선형성 및 잠금 자유 특성을 가지고 있는 것으로 나타났다.조회 작업은 대기 자유가 보장되도록 수정할 수 있다.

Ctries의 장점

ctries는 동시 스킵 리스트,[2][4] 동시 해시 테이블 및 유사한 데이터 구조와 룩업 작업 측면에서 유사한 성능을 보이며, 해시 테이블보다 약간 느리고, 진입도가 낮아 스킵 리스트보다 빠른 것으로 나타났다.그러나 삽입과 관련된 대부분의 동시 해시 테이블보다 확장성이 훨씬 높다.[1]대부분의 동시 해시 테이블은 메모리를 보존하는데 서툴다 - 키를 해시 테이블에서 제거해도 기본 배열이 줄어들지 않는다.ctries는 할당된 메모리가 항상 데이터 구조에서 현재 키 수만으로 기능한다는 속성을 가지고 있다.[1]

ctri는 분지 수준(보통 32)이 높아 상수 인자가 낮지만 기본 연산의 로그 복잡성 한계를 가진다.

Ctries는 영구적인 데이터 구조에서 얻은 통찰력에 기반하여 잠금 없는 선형 가능한 일정한 시간 스냅샷 작업을 지원한다.[2]이는 기존의 동시 데이터 구조는 스냅샷을 지원하지 않기 때문에 동시 데이터 구조 설계의 획기적인 발전이다.스냅샷 연산을 통해 잠금 없는 선형 가능한 반복기, 크기 및 명확한 운영을 구현할 수 있다 - 기존의 동시 데이터 구조는 글로벌 잠금을 사용하거나 데이터 구조에 동시 수정 사항이 없을 때만 올바른 구현을 한다.특히 Ctries는 O(1) 반복기 생성 작업, O(1) 클리어 작업, O(1) 중복 작업, 상각된 O(logn) 크기 검색 작업이 있다.

Ctries 문제

대부분의 동시 데이터 구조는 동적 메모리 할당이 필요하며, 잠금 없는 동시 데이터 구조는 대부분의 플랫폼에서 가비지 수집에 의존한다.Ctrie의 현재 구현은[4] JVM을 위해 작성되었으며, 여기서 가비지 수집은 플랫폼 자체에 의해 제공된다.Ctries의 모든 인스턴스가 공유한 노드에 대한 동시 메모리 풀을 애플리케이션에서 유지하거나 노드를 적절히 할당 해제하기 위해 참조 카운트를 사용할 수 있지만, 지금까지 Ctries에서 사용되는 노드의 수동 메모리 관리를 처리할 수 있는 유일한 구현은 여러 개의 중지 및 복사 기능을 구현하는 공통 구성 구현 cl-ctrie이다.지속적인 메모리 저장소를 위한 y 및 표시 및 표시/표시/표시 가비지 수집 기술.위험 포인터는 제거된 노드의 정확한 수동 관리를 위한 또 다른 가능한 해결책이다.이러한 기법은 GC에 대한 압력을 낮출 수 있기 때문에 관리되는 환경에서도 사용할 수 있다.러스트에서 Ctrie 구현은 이러한 목적을 위해 위험 포인터를 사용한다.[6]

구현

Scala 2.9.x에 대한 Ctrie 구현은[4] GitHub에서 이용할 수 있다.이것은 진행 상황을 보장하고 잠금, 선형화, O(1) 스냅샷을 지원하는 변형 가능한 스레드 세이프 구현이다.

  • Ctries와 유사한 데이터 구조가 Scala에서 사용됨STM,[7] JVM용 소프트웨어 트랜잭션 메모리 라이브러리.
  • 스칼라 표준 라이브러리(2.13.x 기준)는 2012년 2월부터 Ctries 구현을 포함한다.[8]
  • Haskell 구현은 패키지로[9] GitHub에서 이용할 수 있다.[10]
  • 독립 실행형 Java 구현은 Java 8, Java[11] 11뿐만 아니라 Java 6의 GitHub에서도 이용할 수 있다.[12]
  • CL-CTRIE는 GitHub에서 사용할 수 있는 공통 Lisp 구현이다.[13]
  • Prolog 프로그램에서 탭링에는 삽입 전용 Ctrie 변종이 사용되어 왔다.[14]
  • Go 구현을 독립 실행형 패키지로 사용 가능
  • 러스트 구현은 잠금 없는 동기화를 달성하기 위해 구현 시 위험 포인터를 사용한다.
  • Ctrie의 관리형 C+++ 버전과 관리되지 않는 Ctrie는 모두 Managed Ctrie 관리되지 않는 Ctrie를 구현했다.
  • Clojure 구현은 Clojure Ctrie도 이용할 수 있다.

역사

ctries는 알렉산다르 프로코펙에 의해 2011년에 처음 설명되었다.[1]작성자의 말을 인용하려면:

Ctrie는 단일 단어 비교 및 스왑 지침을 기반으로 하는 비차단 동시 공유 메모리 해시 트라이어이다.해시 트리의 서로 다른 부분을 수정하는 삽입, 조회 및 제거 작업은 서로 독립적으로 실행될 수 있으며 다투지 않는다.제거 작업을 통해 불필요한 메모리가 해제되고 트리(Trie)가 압축되어 있는지 확인하십시오.

2012년에는 Ctrie 데이터 구조의 개정판이 발행되어 데이터 구조를 단순화하고 고정 시간, 잠금 없는 선택적 원자 스냅샷 연산을 도입하였다.[2]

참조

  1. ^ a b c d e f Prokopec, A. 외 (2011) 캐시 인식 잠금-무료 동시 해시 시도.기술 보고서, 2011.
  2. ^ a b c d e 효율적인 비차단 스냅샷을 사용한 Prokopec, A, Bronson N, Bagwell P, Odersky M.(2012) 동시 시도
  3. ^ Prokopec, A. 외 (2011) 잠금 없는 크기 조정 가능 동시 시도.제24회 병렬 컴퓨팅용 언어 및 컴파일러 국제 워크숍, 2011.
  4. ^ a b c d Prokopec, GitHub에 대한 A. JVM 구현
  5. ^ https://axel22.github.io/resources/docs/lcpc-ctries.ppt
  6. ^ a b GitHub에서 Rust Ctrie 구현
  7. ^ N. 브론슨 스칼라STM
  8. ^ 트라이맵.스칼라
  9. ^ 하스켈 ctrie 패키지
  10. ^ 하스켈 CTRI의 GitHub repo
  11. ^ 자바 8과 11 Ctrie를 위한 GitHub repo
  12. ^ 자바 6 Ctrie를 위한 GitHub repo
  13. ^ Common Lisp Ctrie에 대한 GitHub repo
  14. ^ 동시 Table 로직 프로그램을 위한 잠금 없는 해시 트라이 디자인 미겔 아리아스와 리카르도 로차
  15. ^ Go Ctrie 패키지