스킵 그래프

스킵 그래프(영어: Skip graph)는 스킵 리스트를 기반으로 하는 일종의 분산 자료 구조이다. 이것은 2003년 제임스 아스프네스(James Aspnes)와 가우리 샤(Gauri Shah)가 발명했다. 거의 동일한 자료 구조인 스킵넷(SkipNet)은 2003년에 니콜라스 하비(Nicholas Harvey), 마이클 존스(Michael Jones), 스테판 사로이우(Stefan Saroiu), 마빈 타임머(Marvin Theimer), 알렉 울먼(Alec Wolman)이 독자적으로 발명했다.^[1]

스킵 그래프는 분산 시스템에서 균형 잡힌 트리의 모든 기능을 수행한다. 스킵 그래프는 주로 P2P 네트워크 검색에 사용된다. 키 정렬을 통해 쿼리 기능을 제공하므로 해시 테이블 기능에만 의존하는 검색 도구보다 개선되었다. 스킵 리스트 및 다른 트리 자료 구조와 달리 매우 탄력적이며 많은 노드 실패를 허용할 수 있다. 또한 노드 실패로 인해 방해받는 스킵 그래프를 구성하고, 삽입하고, 검색하고, 복구하는 것은 간단한 알고리즘으로 수행할 수 있다.^[2]

설명

스킵 그래프는 스킵 리스트를 기반으로 하는 분산 자료 구조로, 균형 잡힌 탐색 트리를 닮도록 설계되었다. 스킵 그래프는 네트워크 전반에 걸쳐 다른 위치에 저장된 리소스를 리소스의 이름(또는 키)을 기반으로 찾아내는 데 사용되는 분산 해시 테이블을 구현하는 여러 방법 중 하나이다.

스킵 그래프는 Chord 및 Tapestry와 같은 다른 분산 해시 테이블 방식에 비해 여러 이점을 제공한다. 예상 로그 시간 내에 추가 및 삭제가 가능하며, 인덱싱 정보 저장에 리소스당 로그 공간이 필요하고, 세트에 있는 노드 수를 알 필요가 없으며, 복잡한 범위 쿼리를 지원한다. Chord 및 Tapestry와의 주요 차이점은 리소스의 검색 키를 해싱하지 않아 관련 리소스가 스킵 그래프에서 서로 가까이 있을 수 있다는 점이다. 이 속성 덕분에 주어진 범위 내의 값을 검색하는 것이 가능하다. 스킵 그래프의 또 다른 장점은 무작위 및 적대적 실패 모델 모두에서 노드 실패에 대한 탄력성이다.

구현 세부 사항

스킵 리스트와 마찬가지로, 노드는 여러 레벨에 걸쳐 증가하는 순서로 배열된다. 레벨 i의 각 노드는 확률 p(조정 가능한 매개변수)로 레벨 i+1에 포함된다. 레벨 0은 세트의 모든 노드를 포함하는 하나의 이중 연결 리스트로 구성된다. 리스트는 상위 레벨로 갈수록 점점 희소해져, 결국 하나의 노드만으로 구성된 리스트가 된다. 스킵 그래프가 스킵 리스트와 다른 점은 각 레벨 i≥1에 여러 개의 리스트가 포함된다는 것이다. 리스트에 키 x가 포함되는지 여부는 멤버십 벡터 ${\displaystyle m(x)}$에 의해 정의된다. 멤버십 벡터는 고정된 알파벳에 대한 무한 임의 단어로 정의되며, 스킵 그래프의 각 리스트는 동일한 알파벳의 유한 단어 w로 식별된다. 이 단어가 ${\displaystyle m(x)}$의 접두사이면 노드 x는 해당 리스트의 멤버이다.^[2]

작업

스킵 그래프는 검색, 삽입 및 삭제의 기본 작업을 지원한다. 스킵 그래프는 더 복잡한 범위 검색 작업도 지원한다.

검색

스킵 그래프의 검색 알고리즘은 스킵 리스트의 검색 알고리즘과 거의 동일하지만, 분산 시스템에서 실행되도록 수정되었다. 검색은 최상위 레벨에서 시작하여 구조를 통과한다. 각 레벨에서 검색은 다음 노드가 더 큰 키를 포함할 때까지 리스트를 통과한다. 더 큰 키가 발견되면 검색은 다음 레벨로 내려가 키를 찾거나 키가 노드 집합에 포함되어 있지 않다고 판단될 때까지 계속된다. 키가 노드 집합에 포함되어 있지 않으면 검색 키보다 작은 가장 큰 값이 반환된다.

리스트의 각 노드에는 다음 필드가 있다.

key

노드의 값.

neighbor[R/L][level]

레벨 i에서 노드의 이중 연결 리스트에 있는 오른쪽 및 왼쪽 이웃에 대한 포인터를 포함하는 배열.

search(searchOp, startNode, searchKey, level)
    if (v.key = searchKey) then
        send(foundOp, v) to startNode
    if (v.key < searchKey) then
        while level ≥ 0
            if (v.neighbor[R][level].key ≤ searchKey) then
                send(searchOp, startNode, searchKey, level) to v.neighbor[R][level]
                break
            else
                level = level - 1
    else
        while level ≥ 0
            if ((v.neighbor[L][level]).key ≥ searchKey) then
                send(searchOp, startNode, searchKey, level) to v.neighbor[L][level]
                break
            else
                level = level - 1
    if (level < 0) then
        send(notFoundOp, v) to startNode

윌리엄 퍼그(William Pugh)의 분석에 따르면, 평균적으로 스킵 리스트는 고정된 p 값에 대해 ${\displaystyle O\left({\frac {\log n}{\log(1/p)}}\right)}$ 레벨을 포함하며, 이는 스킵 그래프에도 확장된다.^[3] 각 레벨당 평균 ${\displaystyle {\frac {1}{1-p}}}$ 노드만 검색된다고 가정하면, 전송되는 총 메시지 수는 ${\displaystyle O\left({\frac {\log n}{(1-p)\log(1-p)}}\right)}$이며, 검색 예상 시간은 ${\displaystyle O\left({\frac {\log n}{(1-p)\log(1-p)}}\right)}$이다.^[2] 따라서 고정된 p 값에 대해, 검색 작업은 O(log n) 메시지를 사용하여 O(log n) 시간이 걸릴 것으로 예상된다.^[2]

삽입

삽입은 두 단계로 이루어지며, 새로운 노드 u가 소개 노드 v를 알고 있어야 한다. 소개 노드는 현재 스킵 그래프에 있는 다른 어떤 노드라도 될 수 있다. 첫 번째 단계에서 새로운 노드 u는 소개 노드 v를 사용하여 자신의 키를 검색한다. 이 검색은 실패하고 u보다 작은 가장 큰 키를 가진 노드 s를 반환할 것으로 예상된다. 두 번째 단계에서 u는 최상위 레벨의 리스트에서 유일한 요소가 될 때까지 각 레벨에 자신을 삽입한다.^[2] 각 레벨에서의 삽입은 표준 이중 연결 리스트 연산을 사용하여 수행된다. 왼쪽 이웃의 다음 포인터는 새 노드를 가리키도록 변경되고, 오른쪽 이웃의 이전 포인터는 새 노드를 가리키도록 변경된다.

insert()
search for s
L = 0
while true
    insert u into level L from s
    Scan through level L to find s' such which has membership vector matching membership vector of u for first L+1 characters
    if no s' exists
        exit
    else
        s = s'
        L = L + 1

검색과 유사하게, 삽입 작업은 예상 O(log n) 메시지와 O(log n) 시간을 소비한다. 고정된 p 값으로, 1단계의 검색 작업은 O(log n) 시간과 메시지를 소비할 것으로 예상된다. 2단계에서 각 레벨 L ≥ 0에서, u는 평균적으로 1/p의 다른 노드와 통신하여 s'를 찾는데, 이는 O(1/p) 시간과 메시지를 필요로 하며, 2단계의 각 단계마다 O(1) 시간과 메시지로 이어진다.^[2]

삭제

노드는 각 레벨에서 병렬로 O(1) 시간과 O(log n) 메시지로 삭제될 수 있다.^[2] 노드가 그래프를 떠나기를 원할 때, 즉시 이웃에게 메시지를 보내 다음 및 이전 포인터를 재배열해야 한다.^[2]

delete()
for L = 1 to max level, in parallel
    delete u from each level.
delete u from level 0

스킵 그래프는 평균 O(log n) 레벨을 포함한다. 각 레벨에서 u는 이중 연결 리스트에서 삭제 작업을 완료하기 위해 2개의 메시지를 보내야 한다. 각 레벨의 작업은 병렬로 수행될 수 있으므로, 삭제 작업은 O(1) 시간과 예상 O(log n) 메시지를 사용하여 완료될 수 있다.

결함 허용

스킵 그래프에서 결함 허용은 다른 노드의 실패로 인해 스킵 그래프에서 연결이 끊어질 수 있는 노드의 수를 의미한다.^[2] 무작위 실패와 적대적 실패의 두 가지 실패 모델이 조사되었다. 무작위 실패 모델에서는 어떤 노드든지 다른 노드와 독립적으로 어떤 확률로든 실패할 수 있다. 적대적 모델은 노드 실패가 각 단계에서 최악의 실패를 달성하도록 계획되며, 전체 스킵 그래프 구조가 알려져 있고 노드 단절을 최대화하도록 실패가 선택된다고 가정한다. 스킵 그래프의 단점은 복구 메커니즘이 없다는 것이다. 현재 스킵 그래프를 제거하고 복구하는 유일한 방법은 살아남은 노드로 새로운 스킵 그래프를 구축하는 것이다.

무작위 실패

스킵 그래프는 무작위 오류에 매우 강하다. 이웃 노드의 상태 정보를 유지하고, 실패한 이웃을 피하기 위해 중복 링크를 사용함으로써 많은 노드 오류에도 불구하고 정상적인 작업을 계속할 수 있다. 실패한 노드의 수가 ${\displaystyle O\left({\frac {1}{\log n}}\right)}$ 미만인 동안 스킵 그래프는 정상적으로 계속 작동할 수 있다.^[2] 제임스 아스프네스가 수행한 시뮬레이션에 따르면, 131072개의 노드를 가진 스킵 그래프는 살아남은 노드들이 고립되기 전까지 최대 60%의 노드 오류를 견딜 수 있었다.^[2] 다른 분산 데이터 구조들이 더 높은 수준의 탄력성을 달성할 수도 있지만, 그들은 훨씬 더 복잡한 경향이 있다.

적대적 실패

적대적 실패는 최악의 실패 패턴을 찾기 어렵기 때문에 대규모 네트워크에서 시뮬레이션하기 어렵다.^[2] 이론적 분석에 따르면, 탄력성은 그래프의 정점 확장 비율에 따라 달라지며, 이는 다음과 같이 정의된다. 그래프 G에서 노드 집합 A에 대해, 확장 요소는 A에 속하지 않지만 A의 노드에 인접한 노드의 수를 A의 노드 수로 나눈 값이다. 스킵 그래프가 ${\displaystyle \Omega \left({\frac {1}{\log n}}\right)}$의 충분히 큰 확장 비율을 가진다면, f개의 실패가 특별히 목표로 설정되더라도 최대 ${\displaystyle O(f\log n)}$개의 노드만 분리될 수 있다.^[2]