Kademlia: A Peer-to-peer Information SystemBased on the XOR Metric

원본 파일 https://www.scs.stanford.edu/~dm/home/papers/kpos.pdf

 

아래 내용은 해당 논문을 구글 번역을 통해서 번역한 내용의 일부입니다.

(3 Sketch of proof 부터 안 되어 있음.)

---

카뎀리아: XOR 매트릭스에 근거한 P2P 정보 시스템

초록

우리는 오류가 발생하기 쉬운 환경에서 일관성과 성능을 보장하는 P2P 시스템을 기술한다. 우리 시스템은 알고리즘은 단순화하고 우리의 증명을 가능하게 하는 새로운 XOR 기반 매트릭스 토폴로지를 사용하여 쿼리를 라우팅하고 노드를 찾는다. 그 토폴로지는 모든 메시지 교환을 운반 또는 유용한 연락처를 보충한다. 이 시스템은 이 정보를 이용하여 사용자에게 시간 초과 지연을 유발하지 않으면서 노드 장애를 허용하는 병렬 비동기 쿼리 메시지를 보낸다.

1 소개

이 논문은 p2p <키, 값> 저장소과 조회 시스템인 카뎀리아를 기술한다. 카뎀리아는 이전의 p2p 시스템에서는 동시에 제공하지 않은 여러 가지 바람직한 특징이 있다. 노드가 서로 등록하기 위해 보내야 하는 구성 메시지 수를 최소화한다. 구성 정보는 키 조회의 부가 효과로써 자동으로 전파된다. 노드가 지연 시간이 짧은 경로를 통해 쿼리를 라우팅할 수 있는 충분한 지식과 유연성을 가진다. 카뎀리아는 실패한 노드로부터 시간 초과 지연을 피하기 위해서 병렬 비동기 쿼리를 사용한다. 노드가 서로의 존재를 기록하는 이 알고리즘은 특정 기본 서비스 거부 공격(Dos)에 저장한다. 마지막으로 카뎀리아의 몇 가지 중요한 특징은 가동 시간 분포에 대한 약한 가정(weak assumptions on uptime distributions)으로 증명될 수 있다.

 

 카뎀리아는 다수의 p2p 시스템의 기본 접근 방식을 가진다. 키는 160비트로, 참여 컴퓨터들은 각각 노드 ID인 160비트의 키 공간이 있습니다. <키, 값> 쌍은 키에 “가까운” Id와 함께 노드에 저장된다. 마지막으로 노드 ID 기반 라우팅 알고리즘을 사용하면 누구나 대상 키 근처에서 서버를 찾을 수 있다.

카뎀리아의 많은 이점은 새로운 XOR 매트릭스를 키에 대한 거리 계산에 사용함으로써 발생한다. XOR은 대칭이므로 카뎀리아 참가자들은 그들의 라우팅 테이블에 포함된 정확히 동일한 노드 분포에서 조회 쿼리를 수신할 수 있다. 카뎀리아는 간격 내의 모든 노드에 쿼리를 보낼 수 있으므로 대기 시간에 따른 경로를 선택하거나 병렬 비동기화 쿼리를 보낼 수도 있다.

 

 특정 ID 근처에 위치한 노드를 찾기 위해서, 카뎀리아는 시작부터 끝까지 싱글 라우팅 알고리즘을 사용한다. 반대로 다른 시스템은 하나의 시스템을 사용하여 가까운 타겟 ID를 접근하고 다른 하나의 마지막 몇 홉에 접근한다. 기존 시스템 중에서 카뎀리아가 Pastry의 첫 번째 단계와 가장 비슷하다. 카뎀리아의 XOR 매트릭스에 의해 타겟 ID로부터 절반 정도 떨어진 노드를 연속적으로 찾는다. 그러나 두 번째 단계에서 Pastry는 거리 측정 항목을 ID 간의 숫자 차이로 전환한다.  또한 replication에서도 두 번째 단계로 숫자 차이를 사용한다. 불행하게도 두 번째 매트릭스에 가까운 노드는 첫 번째에 비래 상당히 멀어 특정 노드 ID 값에서 불연속성을 생성하여 성능을 저하시키며 최악의 동작에 대한 공식적인 분석 시도를 좌절시킨다.

2 시스템 설명

각 카뎀리아 노드는 160 비트의 노드 ID를 가진다. 노드 ID는 Chord와 같이 구성되어 있지만, 이 논문을 단순화하기 위해 시스템에 참여할 때, 임의의 160 비트 식별자를 선택한다고 가정한다. 모든 노드의 메시지는 그 노드의 ID를 포함하고 있고, 필요한 경우 수신자가 발신자의 정보를 기록할 수 있다. 키는 160 비트 식별자다. <키, 값>쌍을 게시하고 찾으면, 카뎀리아는 두 식별자 사이의 거리 개념을 사용한다. 주어진 두 160 비트의 식별자 x와 y를 카뎀리아는 이들 사이의 거리를 비트 배타적 또는 XOR (d(x, y) = x ⊕ y)로 해석한다.

 

 우리는 먼저 XOR이 nonEuclidean가 아닌 매트릭스에서만 유효하다는 것을 주목해야 한다. d(x, x) = 0, d(x, y) > 0 if x ≠ y, and ∀x, y : d(x, y) = d(y, x) 임이 명백하다. XOR은 또한 삼각형 속성 d(x, y) + d(y, z) ≥ d(x, z)를 제공한다. 삼각형 속성은 d(x, z) = d(x, y) ⊕ d(y, z) 및 ∀a ≥ 0, b ≥ 0 : a + b ≥ a ⊕ b이다.

 

 Chord의 시계 방향 원 매트릭스와 마찬가지로 XOR은 단방향이다. 주어진 점 x와 거리 ∆ > 0에 대해 d(x, y) = ∆와 같은 점 y가 정확히 하나 있다. 단방향성은 원래 노드에 관계없이 동일한 키에 대한 모든 조회가 동일한 경로를 수렴되도록 한다. 그러므로 조회 경로를 따라 <키, 값> 쌍을 caching하면 핫스팟이 완화된다. Pastry와 마찬가지로 Chord와 달리 XOR 토폴로지는 대칭이다. (d(x, y) = d(y, x) for all x and y)

2.1 노드 상태

 카뎀리아 노드는 서로의 연락 정보를 저장하여 쿼리 메시지를 라우팅한다. 각 0 ≤ i < 160에 대한 모든 노드는 2i 와 2i+1 사이의 거리에 있는 노드에 대해 <IP 주소, UDP 포트, Node ID> 세 가지 정보의 목록을 유지하고 있다. 우리는 이 목록을 k-bucket이라고 부른다. 각 k-bucker은 가장 최근에 본 노드(least-recently seen node at the head, most-recently seen at the tail)를 기준으로 정렬된다. 작은 값의 i의 경우, k-bucket은 생성될 때 비워져 있다(적절한 노드가 없기 때문에). 큰 값의 i의 경우, 목록은 최대 크기 k까지 커질 수 있다. 여기서 k는 시스템 전체의 replication 매개변수이다. k는 임의로 주어진 k 노드들이 서로 1시간 내에 실패할 가능성이 거의 없도록 선택된다(예를 들어 k = 20).

 

 카뎀리아 노드가 다른 노드로부터 어떤 메시지(요청이나 응답)를 받을 때, 발신자 ID를 적당한 k-bucket에 업데이트한다. 만약 발신 노드가 이미 수신자 k-bucket에 존재하는 경우, 수신자는 그것을 목록의 tail로 이동한다. 만약 노드가 아직 k-bucket에 있지 않고 k-bucket에 k 미만의 항목이 있는 경우, 수신자는 새 발신자를 목록의 tail에 삽입하면 된다. 그러나 k-bucket에 가득 찬 경우, 수신자는 k-bucket의 가장 최근에 본 노드를 ping하여 수행할 작업을 결정한다. 가장 최근에 본 노드가 응답하지 않으면 k 버킷에서 제거되고 새 발신자가 tail에 삽입된다. 만약 가장 최근에 본 노드가 응답하면 목록의 맨 위로 이동하고 새 발신자의 연락처가 삭제된다.

 

 k-bucket은 실행중인 노드가 목록에서 제거되지 않는 것을 제외하고 least-recently seen 제거 정책으로 효과적인 도구다. 오래된 접속에 대한 우선권은 Saroiu 등이 수집한 Gnutella trace 데이터 분석에 의해 이루어진다. 그림 1은 현재 가동 시간의 함수로 온라인 상태를 유지하는 Gnutella 노드의 비율을 보여준다. 노드가 길어질수록 한 시간 더 남아있을 가능성이 높다. K-bucket은 가장 오래된 연결을 유지함으로써 노드가 온라인 상태를 유지할 가능성을 최대화합니다.

 

 k-bucket의 두 번째 장점은 특정 DoS 공격에 대한 내성을 제공한다는 것이다. 카뎀리아의 노드는 오래된 노드가 시스템을 떠날 때만 k-bucket에 새 노드를 삽입한다. 그래서 새로운 노드로 시스템을 공격할 수 없다.

2.2 카뎀리아 프로토콜

 카뎀리아 프로토콜은 4 개의 RPC로 구성된다. PING, STORE, FIND_NODE, FIND_VALUE. PING RPC는 노드를 검사하여 온라인 상태인지 확인한다. STORE는 나중에 검색할 수 있도록 <키, 값> 쌍을 저장하도록 노드에 지시한다.

 

  FIND_NODE는 160 비트의 ID를 인수로 가진다. RPC 수신자는 대한 ID에 대해 가장 가까운 k 개의 노드에 대한 <IP 주소, UDP 포트, 노드 ID>를 반환한다. 이 세개의 정보는 단일 k-bucket에서 가져오거나 가장 가까운 k-bucket이 가득 차지 않은 경우, 여러 k-bucket에서 나올 수 있다. 어쨌든 RPC 수신자는 k 개의 항목을 반환해야 한다(모든 k-bucket에서 k개 미만의 노드가 결합되어 있지 않는 경우 아는 모든 노드가 반환됨).

 

 FIND_VALUE는 하나의 예외를 제외하고 FIND_NODE처럼 동작한다(<IP 주소, UDP 포트, 노드 ID> 세 개의 정보). 만약 RPC 수신자가 STORE RPC를 수신한 경우 저장된 값만 반환한다.

 

 모든 RPC에서는 수신자가 160 비트의 랜덤 RPC ID를 echo 해야 하는데, 이는 위조 주소에 대한 저항은 제공한다. 발신자의 네트워크 주소의 추가 보증을 얻기 위해 RPC 수신자의 RPC 응답을 PING을 piggy-back할 수 있다.

 

 카뎀리아 참가자가 수행해야 하는 가장 중요한 절차는 특정 노드의 ID에 가장 가까운 k개의 노드를 찾는 것이다. 이 절차를 노드 조회라고 한다. 카뎀리아는 노드 조회에 재귀 알고리즘을 사용한다. 조회는 비어 있지 않은 가장 가까운 k-bucket에서 α 노드를 선택하는 것으로 시작한다. (또는 해당 k-becket에 α 항목 미만인 경우, 알고 있는 가장 가까운 α 노드를 사용한다) 그런 다음 초기자는 선택한 비동기 노드를 병렬 비동기 FIND_NODE RPC를 보낸다. α는 시스템 전체의 동시성 매개 변수다(예를 들어 α = 3)

 

 재귀 단계에서 초기자는 FIND_NODE를 이전 RPC에서 배운 노드로 다시 보낸다. (이 재귀는 이전 PRC의 모든 α가 반환되기 전에 시작할 수 있다) 초기자가 대상에 가장 가까운 것으로 알고 있는 k 개의 노드 중에서 아직 쿼리하지 않은 α를 선택하고 FIND_NODE RPC를 다시 보낸다. 빠르게 응답하지 않는 노드는 응답할 때까지 응답하지 않는 고려 대상에서 제거됩니다. FIND_NODE의 라운드가 이미 가장 가까운 노드보다 가까운 노드를 반환하지 못하면 초기자는 아직 쿼리하지 않은 모든 k개의 가장 가까운 노드에 FIND_NODE를 다시 보냅니다. 초기자가 조회한 k개의 가장 가까운 노드에서 쿼리하고 응답을 받으면 조회가 종료된다. α = 1인 경우, 조회 알고리즘은 메시지 비용 및 실패한 노드 감지 대기 시간 측면에서 Chord와 유사하다. 하지만 카뎀리아는 k 개의 노드 중 하나를 선택하여 요청을 전달할 수 있는 유연성을 가지고 있기 때문에 대기 시간을 단축할 수 있다.

 

 대부분의 작업은 위의 조회 절차에 따라 구현된다. <키, 값> 쌍을 저장하기 위해 참가자는 k에 가장 가까운 k 개의 노드를 찾아 STORE RPC로 보낸다. 또한 각 노드는 매시간마다 보유하고 있는 <키, 값> 쌍을 다시 공개한다. 이것은 매우 높은 확률로 <키, 값> 쌍의 지속성을 보장한다. 일반적으로 24시간마다 republish하려면 <키, 값> 쌍의 원래 게시자도 필요하다. 그렇지 않으면 모든 <키, 값> 쌍이 시스템에서 오래된 정보를 제한하기 위해 게시 후 24시간 후에 만료된다.

 

 마지막으로 <키, 값> 쌍의 게시-검색 수명 주기의 일관성을 유지하려면, 우리는 노드 w가 <키, 값> 쌍 중 일부에 더 가까운 새로운 노드 u를 관찰할 때마다 그 <키, 값> 쌍을 자신의 데이터베이스에서 제거하지 않고 u에 replicate 해야 한다.

 

 <키, 값> 쌍을 찾기 위해 노드는 조회를 수행하여 키에 가장 가까운 ID를 가진 k 개의 노드를 찾는다. 그러나 값 조회는 FIND_NODE RPC 대신 FIND_VALUE를 사용한다. 또한 노드가 값을 반환하면 절차가 즉시 중지된다. caching을 위해 조회가 성공하면 요청 노드는 값을 반환하지 않은 가장 가까운 노드의 키에 대해 관찰하고 <키, 값> 쌍을 저장한다.

 

 토폴로지의 단방향성 때문에 가장 가까운 노드를 쿼리하기 전에 동일한 키에 대한 향후 검색이 캐시된 항목에 도달할 수 있다. 특정 키에 대한 인기가 높은 시간동안 시스템은 많은 노드에서 키를 caching하게 된다. “over-caching(과도한 캐싱)”을 피하기 위해 모든 노드 데이터베이스의 <키, 값> 쌍의 만료 시간을 현재 노드와 키가 ID가 가장 가까운 노드 사이의 노드 수에 지수적으로 반비례한다. 간단한 LRU 제거는 수명 분포와 비슷하지만 노드가 시스템에 저장할 값의 수에 대한 사전 지식이 없기 때문에 캐시 크기를 선택하는 자연스러운 방법은 없다.

 

 Bucket은 일반적으로 노드를 통과하는 요청 트래픽으로 인해 지속적으로 최신 상태로 유지된다. 트래픽이 없는 경우, 병리학적 사례를 피하기 위해 각 노드는 1시간 이내에 노드 조회를 수행하지 않은 범위의 bucket을 refresh합니다. Refreshing이란 버킷 범위에서 임의의 ID를 선택하고 해당 ID에 대한 노드 검색을 수행함을 의미합니다.

 

 네트워크에 참여하려면 노드 u가 이미 참여중인 노드 w에 연락해야 한다. U는 적절한 k-bucket에 w를 삽입한다. 그런 다음 u는 자체 노드 ID에 대한 노드 검색을 수행한다. 마지막으로 u는 가장 가까운 이웃보다 먼 모든 k-bucket을 refresh한다. Refresh하는 동안, u는 자체 k-bucket을 채우고 필요에 따라 다른 노드의 k-bucket에 삽입한다.