그래프 건너뛰기

스킵 그래프는 스킵 리스트를 기반으로 한 분산 데이터 구조의 일종이다.그들은 제임스 아스프네스와 가우리 샤에 의해 2003년에 발명되었다.스킵넷이라고 불리는 거의 동일한 데이터 구조는 니콜라스 하비, 마이클 존스, 스테판 사로이우, 마빈 테이머, 알렉 울만에 의해 2003년에 독립적으로 발명되었다.^[1]

스킵 그래프는 분산 시스템에서 균형 잡힌 트리의 전체 기능을 가지고 있다.그래프 건너뛰기는 대부분 피어 투 피어 네트워크를 검색하는 데 사용된다.키 순서에 의해 쿼리할 수 있는 기능을 제공하기 때문에 해시 테이블 기능만 기반으로 검색 툴에 비해 개선된다.스킵 리스트와 다른 트리 데이터 구조와는 대조적으로, 그것들은 매우 탄력적이며 많은 노드 실패를 허용할 수 있다.또한 노드 장애로 인해 방해를 받은 스킵 그래프를 구성, 삽입, 검색 및 복구하는 작업은 간단한 알고리즘으로 수행할 수 있다.^[2]

설명

스킵 그래프는 균형 잡힌 검색 트리를 닮도록 설계된 스킵 리스트를 기반으로 한 분산 데이터 구조다.이들은 분산 해시 테이블을 구현하는 몇 가지 방법 중 하나로, 리소스의 이름(또는 키)이 주어진 경우 네트워크를 통해 서로 다른 위치에 저장된 리소스를 찾는 데 사용된다.스킵 그래프는 코드(peer-to-peer) 및 태피스트리(DHT)와 같은 다른 분산 해시 테이블 방식보다 기대 로그 시간에 추가 및 삭제, 인덱스 정보를 저장하기 위한 리소스당 로그 공간, 집합의 노드 수에 대한 필수 지식 없음 및 복잡한 범위 쿼리 지원 등 여러 가지 이점을 제공한다.코드 및 태피스트리와의 주요 차이점은 리소스의 검색 키가 해싱되지 않아 관련 리소스가 스킵 그래프에서 서로 가까이 있을 수 있다는 것이다. 이 속성은 주어진 범위 내의 값을 검색 가능하게 한다.스킵 그래프의 또 다른 강점은 무작위 및 대립적 실패 모델 모두에서 노드 실패를 복원하는 것이다.

이행내역

스킵 리스트와 마찬가지로, 노드는 여러 레벨에서 증가하는 순서로 배열된다. 레벨 i의 각 노드는 어느 정도 확률 p(조절 가능한 파라미터)와 함께 레벨 i+1에 포함된다.레벨 0은 세트의 모든 노드를 포함하는 하나의 이중으로 연결된 목록으로 구성된다.목록이 한 개의 노드로 구성될 때까지 목록이 더 높은 수준에서 점점 더 희박해진다.건너뛰기 그래프가 건너뛰기 목록과 다른 경우 각 수준 i11은 여러 개의 목록을 포함하며, 목록에서 키 x의 멤버십은 멤버십 벡터 $m(x)$ ( x $m(x)$ ) $m(x)$ 에 의해 정의된다 $m(x)$ 멤버십 벡터는 고정 알파벳을 통한 무한 무작위 단어로 정의되며, 스킵 그래프의 각 목록은 동일한 알파벳의 유한 단어 w로 식별된다. 만약 그 단어가 $m(x)$ ( x $){\displaystyle m(x)}$ 의 접두사라면 노드 $m(x)$ x는 목록의 멤버다.^[2]

운영

그래프 건너뛰기는 검색, 삽입 및 삭제의 기본 작업을 지원한다.그래프 건너뛰기는 또한 더 복잡한 범위 검색 작업을 지원할 것이다.

검색

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

목록의 각 노드에는 다음 필드가 있다.

key: 노드의 값.
neighbor[R/L][level]: 노드의 두 배로 연결된 레벨 i에서 오른쪽과 왼쪽 인접 영역에 대한 포인터를 포함하는 배열.

검색(v.key = searchKey)인 경우 searchOp, startNode, searchKey, level)를 startNode로 전송(foundOp, v)한 다음(v.key <검색키)인 경우 레벨 ≥ 0(v.neighbor[R][level]).그런 다음 키 search searchKey)를 v.neighbor[R][level]/break other level = level - 1인 반면 (v.neighbor[L][level]인 경우 0 0인 경우)로 전송(searchOp, startNode, searchKey, level)하십시오.키 ≥ searchKey) 그런 다음 v.neighbor[L][level]로 전송(searchOp, startNode, searchKey, level)하고 다른 레벨 = 레벨 1이면 레벨 1로 전송(레벨 < 0)한 후 startNode로 전송(notFoundOp, v)

분석 윌리엄 퓨에 의해 수행되고 평균적으로, 스킵 리스트와 확장에서 스킵 그래프)}O(로그⁡와 로그 ⁡(1/p)){O\left({\frac{\log n}{\log(1/p)\displaystyle}}\right p.[3]의 고정된 값에 대한 수준을 감안할 때 포함한다는 가장 11− p{\displaystyle{\frac{1}{1-p}에}}노드 ave.에 검색을 보여 주넝마e per level, the total expected number of messages sent is $O\left({\frac {\log n}{(1-p)\log(1-p)}}\right)$ and the expected time for the search is $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$ 를 반환할 것으로 예상된다.2단계에서 $u$ 는 상위 레벨의 리스트에 있는 유일한 요소가 될 때까지 각 레벨에 자신을 삽입한다.^[2]각 수준에서 삽입은 표준 이중 연계 목록 연산을 사용하여 수행되며, 왼쪽 이웃의 다음 포인터는 새 노드를 가리키도록 변경되고 오른쪽 이웃의 이전 포인터는 노드를 가리키도록 변경된다.

에 대한 검색을 삽입하다.s L= 참 삽입 중 0u로부터 레벨 L로s전체 레벨 스캔L찾기 위해서.s'멤버십 벡터 매칭 멤버십 벡터를 가진u우선L+1자(없을 경우)s'다른 종료가 있음         s=s'         L=L+ 1

검색과 마찬가지로 삽입 작업에는 예상 O(log n) 메시지와 O(log n) 시간이 소요된다.고정값 p인 경우, 1단계에서 검색 작업에는 O(log n) 시간과 메시지가 소요될 것으로 예상된다.각 레벨 L ≥ 0의 2단계에서 $u$ 는 평균 1/p 다른 노드와 통신하여 $s$ '를 찾는데, 여기에는 O(1/p) 시간 및 메시지를 유도하는 메시지가 2단계의 각 단계에 대해 필요하다.^[2]

삭제

O(1) 시간 및 O(log n) 메시지에서 각 단계에서 노드를 병렬로 삭제할 수 있다.^[2]노드가 그래프를 떠나려고 할 때, 노드는 바로 이웃에게 메시지를 보내 다음 포인터와 이전 포인터를 다시 정렬해야 한다.^[2]

delete() L = 1 ~ max 레벨의 경우, 각 레벨에서 u를 병렬로 삭제. u를 레벨 0에서 삭제

스킵 그래프에는 평균 O(log n) 레벨이 포함되어 있으며, 각 레벨에서 2개의 메시지를 전송하여 이중으로 연결된 목록에서 삭제 작업을 완료해야 한다.각 레벨의 작업은 병렬로 수행될 수 있으므로 O(1) 시간과 예상 O(log n) 메시지를 사용하여 삭제 작업을 완료할 수 있다.

내결함성

스킵 그래프에서 내결함성은 다른 노드의 장애에 의해 스킵 그래프에서 분리될 수 있는 노드 수를 설명한다.^[2]무작위적 고장 및 대립적 고장이라는 두 가지 고장 모델을 검사했다.무작위 고장 모델에서 어떤 노드는 어느 정도의 확률로 다른 노드와 독립적으로 고장날 수 있다.적대적 모형은 각 단계에서 최악의 고장이 달성되고 전체 스킵 그래프 구조를 알 수 있으며 노드 분리를 극대화하기 위해 장애를 선택하도록 노드 고장이 계획되어 있다고 가정한다.스킵 그래프의 단점은 복구 메커니즘이 없다는 것이다. 현재 스킵 그래프를 제거하고 복구하는 유일한 방법은 살아남은 노드로 스킵 그래프를 새로 만드는 것이다.

무작위 고장

그래프 건너뛰기는 무작위 고장에 대한 내성이 강하다.이웃의 상태에 대한 정보를 유지하고, 실패한 이웃을 피하기 위해 중복 링크를 사용함으로써, 다수의 노드 장애가 발생하더라도 정상적인 운영을 계속할 수 있다.실패한 노드 수가 $O\left({\frac {1}{\log n}}\right)$ 1 $O\left({\frac {1}{\log n}}\right)$ ) ${\$ 보다 적지만, 건너뛰기 $O\left({\frac {1}{\log n}}\right)$ 그래프는 정상적으로 작동할 수 있다.^[2]제임스 애스프네스에 의해 수행된 시뮬레이션은 131072개 노드가 있는 스킵 그래프가 생존 노드가 분리되기 전에 노드의 최대 60%가 고장나는 것을 용인할 수 있었다는 것을 보여준다.^[2]다른 분산 데이터 구조는 더 높은 수준의 복원력을 달성할 수 있지만 훨씬 더 복잡한 경향이 있다.

대립적 실패

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

참조

^ Nicholas J.A. Harvey, Michael B. Jones, Stefan Saroiu, Marvin Theimer, Alec Wolman. "SkipNet: A Scalable Overlay Network with Practical Locality Properties" (PDF). https://www.usenix.org/legacy/events/usits03/tech/harvey/harvey.pdf. {{cite web}}:외부 링크 위치 location=(도움말)CS1 maint: 위치(링크) CS1 maint: 여러 이름: 작성자 목록(링크)
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m James Aspnes; Gauri Shah. "Skip Graphs" (PDF). http://www.cs.yale.edu/: Computer Science – Yale University. Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes that may fail at any time. They are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. Unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. In addition, simple and straightforward algorithms can be used to construct a skip graph, insert new nodes into it, search it, and detect and repair errors in a skip graph introduced due to node failures. {{cite web}}:외부 링크 위치 location=(도움말)
^ William Pugh. "Skip Lists: A probabilistic Alternative to Balanced Trees" (PDF). https://web.stanford.edu/class/cs161/skiplists.pdf. {{cite web}}:외부 링크 위치 location=(도움말)CS1 maint: 위치(링크)

[SkipNet-1] Nicholas J.A. Harvey, Michael B. Jones, Stefan Saroiu, Marvin Theimer, Alec Wolman. "SkipNet: A Scalable Overlay Network with Practical Locality Properties" (PDF). https://www.usenix.org/legacy/events/usits03/tech/harvey/harvey.pdf. {{cite web}}:외부 링크 위치 location=(도움말)CS1 maint: 위치(링크) CS1 maint: 여러 이름: 작성자 목록(링크)

[SG-2] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m James Aspnes; Gauri Shah. "Skip Graphs" (PDF). http://www.cs.yale.edu/: Computer Science – Yale University. Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes that may fail at any time. They are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. Unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. In addition, simple and straightforward algorithms can be used to construct a skip graph, insert new nodes into it, search it, and detect and repair errors in a skip graph introduced due to node failures. {{cite web}}:외부 링크 위치 location=(도움말)

[Pugh-3] William Pugh. "Skip Lists: A probabilistic Alternative to Balanced Trees" (PDF). https://web.stanford.edu/class/cs161/skiplists.pdf. {{cite web}}:외부 링크 위치 location=(도움말)CS1 maint: 위치(링크)

[1]

[2]

Search