Concurrent Skip List

Concurrent Skip List는 Skip List 자료구조를 기반으로 하여 멀티스레드 환경에서 동시에 삽입, 삭제, 검색 작업을 수행할 수 있도록 구현된 동시성 자료구조이다.
Skip List는 여러 계층의 연결 리스트로 구성된 정렬된 데이터 구조인데, ConcurrentSkipList는 이를 멀티스레드 환경에서 안전하게 사용할 수 있도록 구현한 것이다.

이 자료구조는 락-프리(lock-free) 또는 세밀한 동기화 메커니즘을 사용하여 높은 동시성을 제공한다.

특징

  1. 동시성 지원: 여러 스레드가 동시에 자료구조에 접근하고 수정할 수 있다.
  2. 락-프리 구현: 대부분의 연산에서 락을 사용하지 않고 Compare-and-Swap(CAS) 연산을 활용한다.
  3. 확장성: 멀티코어 시스템에서 높은 확장성을 제공한다.
  4. 로그 시간 복잡도: 평균적으로 O(log n) 시간 복잡도로 검색, 삽입, 삭제 연산을 수행한다.
  5. 확률적 균형: 재조정 작업 없이 확률적으로 균형을 유지한다.

구현 방식

  1. 레벨별 락-프리 리스트: 각 레벨의 리스트를 락-프리 연결 리스트로 취급한다.
  2. CAS 연산 사용: 노드 삽입 시 CAS 연산을 사용하여 동시성을 제어한다.
  3. 마킹 기법: 노드 삭제 시 다음 참조를 마킹하여 논리적 삭제를 수행한다.
  4. 도움 메커니즘: find() 메서드가 마킹된 노드를 정리하는 역할을 수행한다.

장점

  1. 높은 동시성: 여러 스레드가 동시에 작업을 수행할 수 있어 성능이 향상된다.
  2. 확장성: 스레드 수가 증가해도 성능 저하가 적다.
  3. 간단한 구현: 동시성 트리 구조에 비해 구현이 상대적으로 간단하다.
  4. 메모리 효율성: 일부 트리 구조보다 메모리 효율적일 수 있다.

응용

  1. 동시성 우선순위 큐: 멀티스레드 환경에서 효율적인 우선순위 큐 구현에 사용된다.
  2. 데이터베이스 시스템: 동시성 인덱싱 구조로 활용된다.
  3. 분산 시스템: 분산 환경에서의 정렬된 데이터 관리에 사용된다.
  4. 캐시 시스템: 동시성 캐시 구현에 활용될 수 있다.

동작 원리

Concurrent Skip List는 여러 레벨의 연결 리스트로 구성되며, 각 레벨은 이전 레벨의 “빠른 경로"로 작용한다.
검색, 삽입, 삭제 작업은 상위 레벨에서 시작하여 하위 레벨로 이동하면서 수행된다.

구성 요소

  1. 노드: 키-값 쌍과 여러 레벨의 다음 노드 포인터를 포함한다.
  2. 레벨: 각 노드는 여러 레벨에 존재할 수 있으며, 레벨 수는 확률적으로 결정된다.
  3. 센티널 노드: 리스트의 시작과 끝을 나타내는 특별한 노드이다.

예시 코드 (Java)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public class ConcurrentSkipListSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable {
    // 구현 생략
    
    public boolean add(E e) {
        // CAS 연산을 사용한 동시성 제어 구현
    }
    
    public boolean remove(Object o) {
        // 마킹 기법을 사용한 동시성 제어 구현
    }
    
    public boolean contains(Object o) {
        // 락-프리 검색 구현
    }
}

이 예시는 Java의 ConcurrentSkipListSet 클래스의 기본 구조를 보여준다.
실제 구현에서는 CAS 연산, 마킹 기법, 락-프리 알고리즘 등이 사용된다.

참고 및 출처