Kademlia like 와 Node Table

안녕하세요 이더리움 코드보는 Sigmoid 입니다.

이더리움 p2p에서는 "Kademlia-like" 라는 표현을 사용합니다. 카뎀리아면 카뎀리아지 like는 또 뭘까요?
오늘은 카뎀리아 라이크에대해 조금 자세히 알아보려고 합니다.

이더리움은 p2p레이어에서 UDP를 이용해서 노드를 탐색하고, TCP를 이용해서 데이터를 전송한다고 말씀드린적이 있는데요,
(링크참조: https://steemit.com/ethereum/@sigmoid/p2p)

이렇게 탐색된 노드를 관리하는 것이 node table입니다. 크게 2가지 경우 업데이트가 되죠

내가 특정 노드에 접속을 요청하고, 수락된 경우(Dial)
내 테이블상에 이미 등록된 노드에게 요청하여 해당노드의 이웃 정보를 얻어올 경우(Discovery)

여기서 2번째의 경우인 discovery에서 kademlia-like 라는 표현을 사용합니다.

일단 카뎀리아가 뭔지 간략히 알아보겠습니다.

카뎀리아(Kademlia)는 분산 P2P 컴퓨터 네트워크를 위한 분산 해시 테이블로 2002년 Petar Maymounkov와 David Mazières가 고안하였다. 논문[1]은 네트워크 구조 및 노드 탐색을 통한 정보 교환에 대한 명세를 기술하고 있다. 카뎀리아 노드는 UDP를 이용하여 서로 통신하며 참여 노드 간에 가상 또는 오버레이 네트워크를 형성한다.
https://ko.m.wikipedia.org/wiki/카뎀리아

https://ko.m.wikipedia.org/wiki/%EC%B9%B4%EB%8E%80%EB%A6%AC%EC%95%84#cite_note-kademlia-paper-1

우선 카뎀리아는 분산 해시 테이블을 구성하는 하나의 방식인데, 논문에서 중요한 표현이 나오네요 분산해시 테이블에서 XOR metric으로 거리를 사용함으로 인해 정확히 같은 분산의 룩업 요청을 받을수 있다. 즉, 모든 노드들이 동등하게 연결될 기회를 가지게 된다 정도로 해석하면 될 것 같습니다.

공정하고 다양한 노드와의 연결을 통해 내가 가진 체인의 데이터를 최대한 신뢰성있게 확보하는 것을 원했던 이더리움에 딱 맞는 방법인것 같습니다.

그럼, like인 이유는 무엇일까요? 논문을 다 읽진 않았지만, 아래 부분에서 답을 찾을수 있을것 같습니다.
(인터페이스가 카뎀리아 프로토콜의 모든 기능을 다구현하고 있지 않음)

사견이지만, 데이터를 저장하고, 찾는 프로토콜은 이더리움 프로토콜이니 당연히 구현을 안하는게 맞겠죠. 아니라도, 크게 중요한 부분은 아닌것 같으니 스리슬쩍!

그럼 노드 테이블이 어떻게 관리되는지 조금 자세하게 알아 보도록 하겠습니다

테이블의 구조는 먼저,
테이블당 버켓의 갯수는 17 ( 32*8 / 15) 이며 버켓당 크기는 16개 입니다.
첫번째 버켓의 최대 log거리는 239로서 나와 상대방의 거리를 계산하여 239보다 작으면
버켓[0]에 해당 노드가 기입되게 되는 구조입니다.
이후에는 거리에따라 버켓[n]에 저장이 됩니다.
16씩 17개의 버켓이니까 테이블이 최대로 관리할수 있는 노드의 갯수는 272개가 되겠네요.
참고로 노드의 ID는 512bit입니다. (카뎀리아 프로토콜에서는 160bit)
버켓을 채우는 방법은 이웃노드의 가까운 이웃을 물어보는 방식이지만 30분에 한번씩 추가로 refresh를 해서 나와 가까운 노드들을 랜덤하게 탐색하여 연결을 추가합니다. 카뎀리아는 최근 갱신된 노드를 검색해보고 업데이트하는 로직인데, geth의 경우 랜덤으로 몇번 돌리는 로직으로 대체한다고 하네요, 과연 이게 기존 카뎀리아 프로토콜의 균형성에 영향을 안줄지는 고민이 필요해 보입니다.
10초마다 랜덤하게 버켓의 상태를 validation합니다. 만약 노드가 응답하지 않는다면 삭제합니다. 30초마다 버켓의 노드정보를 DB에 저장합니다.
특정 노드를 탐색하는 Lookup함수가 재밌습니다. 내 테이블을 기준으로 특정노드와 가까운 n개의 노드를 선정하여 쿼리를 보냅니다.( 너 얘 아니?)

생각보다 글이 두서없네요. 카뎀리아 프로토콜을 차용하여 노드를 관리하기 위해 노드 테이블이 있고, 버켓의 형태로 최근까지 연결된 가까운 노드를 관리하는 식으로 운용된다 까지만 기억하시면 될 것 같습니다.

부족한글 읽어주셔서 늘 감사합니다.