안녕하세요. 플라네타리움 개발팀의 고찬혁입니다. 이번에는 분산 P2P 네트워크를 효율적으로 구성하기 위한 분산 해시 테이블 기법 중 하나인 Kademlia가 무엇인지 간단하게 설명드리고, 왜 이를 저희 프로젝트인 Libplanet에 적용하게 되었는지에 대해서 간단히 말해보는 시간을 가지려고 합니다.
Kademlia가 무엇인가요?
분산 해시 테이블은 데이터를 네트워크 상의 노드들에 분산하여 저장하여 관리하는 기술입니다. 네트워크 상에서 데이터를 찾을 때 그 데이터를 갖고 있는 노드를 찾아 값을 요청하여 각 노드가 받는 부하를 줄이는데 큰 역할을 합니다.
분산형 해시 테이블을 구현하는 여러 종류의 구현체들은 네트워크 상의 노드들을 각각 다른 방법으로 자신의 라우팅 테이블에 저장합니다. 그렇다면 그 중 Kademlia는 분산 해시 테이블을 어떻게 구현하고 있을까요? 이에 대해 설명하기 앞서서 쉽게 이해하실 수 있게 간단한 예시를 들어보겠습니다. 2008년에 미국에 LA에 거주했던 재미 교포인 김씨의 얘기를 해보죠. 그는 오랜만에 한국에 있는 친구를 만나기 위해 한국을 방문했고, 이제 막 인천 국제 공항에 내렸습니다.
친구 집으로 가고 싶은데, 주소만 보고는 어디인지 잘 모르겠는걸.
저런, 김씨가 길을 잃은 것 같네요. 2019년이었다면 스마트폰을 꺼내 주소를 입력해 찾아갔겠지만, 아쉽게도 2008년에는 스마트폰이 많이 보급되지 않아 김씨는 스마트폰을 갖고 있지 않았습니다. 김씨는 가지고 유일한 정보인 주소를 다시 유심히 살펴봅니다.
서울특별시 종로구 세종로 1-91번지
딱히 특별한 수가 없던 김씨는 우선 서울특별시를 찾아갔습니다. 그리고 그 곳에서 사람들을 잡고 길을 물어보지만, 위 주소를 정확히 알고 있는 사람은 많지 않군요. 김씨는 전략을 바꿔 종로구를 가려면 어떻게 해야 하는지 물어보기 시작합니다. 종로구를 아는 사람은 꽤 많았고, 우여곡절 끝에 종로구에 도착했습니다. 이제 세종로에 대해서 물어볼 차례군요!
김씨는 이처럼 정확한 위치를 알지 못했지만 점점 범위를 좁혀가며 친구의 집에 도착했는데요, Kademlia를 적용한 네트워크의 각 피어도 이렇게 피어들의 정보를 유지하고, 탐색합니다.
네트워크 상의 피어들은 가상의 주소를 갖습니다. *“서울특별시 종로구 세종로 1-91번지”*와 같은 지리적 주소가 아닌 임의로, 혹은 정해진 규칙에 따라 배정된 일련의 바이트들이죠. 거리 개념 역시 실제 피어간에 물리적인 거리가 아닌, 두 피어의 주소값의 배타적 논리합으로 정의합니다.
Kademlia 프로토콜을 적용한 피어는 자신의 라우팅 테이블에 네트워크 상의 다른 모든 피어들의 정보를 담는 대신, 그 피어들을 위에서 정의한 거리에 따라 분류해 각 거리 범위당 제한된 개수의 피어만 저장합니다. 거리가 최소 2i에서 최대 2i+1 사이의 피어들은 라우팅 테이블의 i번째 행에 저장하는 식으로요. 이렇게 선택적으로 피어들의 정보를 라우팅 테이블에 저장하게 되면 어떤 피어 A의 라우팅 테이블에 피어 B가 포함되어 있지 않더라도, 자신이 알고있는 피어들 중 피어 B와 가장 가까운 피어에 정보를 요청하고, 그 피어는 다시 자신의 라우팅 테이블 내의 피어들 중 가장 근접한 피어에 요청을 하는 작업을 반복하다보면 결국 피어 B를 찾아낼 수 있을 것입니다.
Kademlia를 적용한 이유가 무엇인가요?
서버가 없이 통신하는 P2P 네트워크를 구성하기 위해서는 모든 피어간에 통신이 보장되어야 합니다. 그러나 모든 피어가 서로 직접적으로 연결되어 있어야 하는 것은 아니죠. 여기 세 개의 피어 A, B 그리고 C가 있습니다.
기존 Libplanet에서는 다음과 같이 네트워크를 구성했죠. 모든 피어가 서로 연결되어 있는 구성이었습니다.
모든 피어가 서로 연결되어 있다.
그러나 이렇게 네트워크를 구성한다면 네트워크의 규모가 작을 때는 큰 문제가 되지 않지만, 피어의 수가 1000개, 아니면 10000개라면 그 만큼의 업로드를 매 메시지를 네트워크에 전파할 때마다 해야 하기에 많은 부하가 걸리게 됩니다.
과도한 송신량에 과부하가 걸린 피어.
Kademlia를 이용하여 노드를 탐색해 만든 라우팅 테이블의 각 행에는 자신으로부터 거리가 같은 범위 내에 있는 피어들로 구성될 것입니다. 데이터를 전파할 때 라우팅 테이블의 각 행에서 피어들을 선택하여 메시지를 보내고, 메시지를 받은 피어가 그 메시지를 다시 자신의 라우팅 테이블의 각 행에서 선택한 피어에 보낸다면, 결과적으로 네트워크 상의 모든 피어들은 메시지를 받게 될 것입니다. 이렇게 하면 n개의 피어가 네트워크 상에 존재할 때 한 피어는 log(n)번만 메시지를 보내게 될 것이고, 네트워크 부하가 하나의 피어에 집중되는 것을 막을 수 있겠죠.
메시지를 전파하는 네트워크.
마치며
게임을 운영하는 데 있어 유저들이 실행하는 액션이 빠르게 실행된다는 느낌을 주기 위해서는 그 액션이 포함된 트랜잭션을 담는 블록을 자주 생성해야겠죠. 블록을 자주 생성할수록 마이너가 받는 네트워크 부하량도 커질 것입니다. 그런 만큼 네트워크가 커질 것을 대비해 분산 해시 테이블의 적용이 필요했고, 실제로 규모를 올려서 테스트를 진행했을 때 하나의 피어에 걸리는 네트워크 부하가 감소하는 수확이 있었습니다.
Kademlia 분산 해시 테이블이나 Libplanet에 대해 더 궁금한 점이 있으시다면 언제든 저희 팀이 상주해 있는 디스코드 대화방에 놀러 오세요!
