Content-based publish/subscribe systems provide a useful alternative to traditional address-based communication due to their ability to decouple communication between participants. Removing the dependency between the interacting peers makes it well adapted to large scale distributed applications such as news delivery, stock quoting, traffic control, on-line games, and dissemination of multimedia contents. It has remained a challenge to design a scalable overlay supporting the complexity of content-based networks, while satisfying the desirable properties large distributed systems should have. This dissertation presents the design of Mirinae, a new structured peer-to-peer overlay mesh based on the interests of peers. Due to the flexibility of virtual hypercube topology, Mirinae provides efficient event dissemination trees minimizing the participation of non-matching nodes. I also present a novel ID space transformation mechanism for balancing routing load of peers even with highly skewed data, which is typical of the real world. The evaluation demonstrates that Mirinae is able to achieve its goals of scalability, efficiency, and near-uniform load balancing. Mirinae can be used as a substrate for content-search and range query in other important distributed applications.
기존의 주소 기반의 통신 방법에 동기식인데 반해 컨텐트 기반 Publihs/Subscribe 시스템은 주어진 패킷을 받아야 하는 노드들의 존재를 알 필요가 없는 비동기식 통신 방법이다. 송신자와 수신자를 이렇게 분리할 수 있는 특성으로 인해 Publish/Subscribe는 뉴스 전달, 주식 시세, 온라인 게임, 트래픽 모니터링과 같은 대규모 분산 어플리케이션을 구현하는데 점차 중요한 통신 패러다임이 되고 있다.
기존의 컨텐트 기반 Publish/Subscribe 시스템은 이벤트 브로커라 불리는 특별한 프락시 서버를 인터넷상에 둠으로써 구현하였다. 하지만, 이러한 브로커 기반 시스템은 브로커 노드가 저장하고 처리해야 하는 정보가 선형적으로 증가하여 확장성에 큰 문제를 가지고 있다. 또한 여러개의 브로커로 구성된 오버레이 네트웍은 각 브로커에 저장된 정보들이 거의 flooding되어 많은 트래픽을 유발할 뿐만 아니라 브로커들의 토폴로지가 정적인 경우를 가정하여 동적으로 오버레이 네트웍을 재구성하는 데 많은 어려움이 있다.
이러한 문제점을 해결하기 위해 본 논문에서는 이벤트 브로커 서버없이 가입자(subscriber)들이 자신이 설정한 이벤트 메시지를 받기위한 가입조건(subscription predicate)에 따라 스스로 네트웍을 구성하고이벤트 메시지들을 주고 받을 수 있는 피어-투-피어 오버레이 네트웍인 미리내(Mirinae)를 제안한다. 미리내는 가상적인 하이퍼큐브(hypercube) 토폴로지를 기반으로 하는데, 이 토폴로지는 각 노드의 ID가 이웃한 노드의 ID와 해밍 거리(hamming distance)가 1인 특성을 가지고 있으며, N개의 노드로 이루어진 네트웍에 대해 $2^N$개의 트리가 내장된(embedded) 메쉬구조이다. 가입조건을 피어-투-피어 네트웍의 ID space로 맵핑시키는 함수(ID function)에 의해 각 노드는 ID를 가지게 되고, 하이퍼큐브의 특성으로 인해 관심사가 비슷한 노드들은 네트웍상에 이웃하게 배치되게 된다. 이러한 토폴로지 상에서 한 노드에서 이벤트가 발생하게 되면, 같은 ID function에 의해 이벤트는 event ID space (eID) 로 맵핑되어 이벤트를 전달하는 과정은 피어-투-피어 네트웍상에서 주어진 ID space에 포함된 ID를 가지는 모든 노드들에게 메시지를 전달할 수 있는 멀티캐스트 트리를 동적으로 만드는 문제로 바뀌게 된다.
이벤트가 발생한 노드는 eID space에 매칭되는, 즉 이벤트 메시지를 받아야 하는, 노드에게 메시지를 라우팅을 통해 전달하고, 첫 매칭노드를 기준으로 멀티캐스트 트리를 구성한다. 이 첫번째 노드는 이벤트 메시지를 받아야 하는 모든 노드에 대한 정보를 가지고 있지 못하므로 자신이 알고 있는 이웃노드들중 매칭되는 노드들에게 eID space를 이항적으로(binomially) 쪼개서 나누어 주게 되고, 이 과정에서 가장 가까운 노드에게 가장 큰 eID space 부분을 줌으로써 멀티캐스트 과정에서 더 많은 노드에게 메시지를 전달하는 역할을 하도록 한다. 이 결과로 이벤트 메시지는 proximity-aware binomial tree를 따라서 멀티캐스팅되고, 주어진 eID space에 포함된 ID를 가지는 모든 노드는 이벤트 메시지를 받는 것이 보장된다. 이러한 메커니즘이 가능한 이유는 하이퍼큐브 메쉬 토폴로지의 유연성때문이라고 할 수 있다.
피어-투-피어 네트웍의 ID space에 비해 노드의 숫자가 일반적으로 굉장히 작기 때문에 각 노드들은 ID이외에도 자신이 담당해야할 영역, ID Cover를 가지게 된다. 이러한 ID Cover를 가지고 하이퍼 큐브 형태의 가상 토폴로지를 유지하기 위한 피어-투-피어 알고리즘을 설계하였고, 이를 통해 노드가 동적으로 join/leave 할 수 있다. 각 노드가 가져야 할 정보의 수와 라우팅 길이, 이벤트 전달과정에서 오버헤드가 모두 O(logN)이 된다.
앞서 설명한 알고리즘은 발생되는 트래픽(subscriptions and events)이 uniform한 분포를 가지는 경우 이상적인 성능을 보여주지만, 실제 어플리케이션의 트래픽을 분석해 보면 인기있는 컨텐트에 집중되는 zipf-like 분포를 가지고 있다. 따라서 각 노드들이 가지는 ID space가 몰리는 왜곡(skew)현상이 발생하게 되고, 각 노드의 부하가 서로 비슷하지 않은 문제가 발생하게 된다. 하이퍼 큐브 오버레이에서 join과 leave한 순서에 따라 ID Cover가 바뀌는 점에 착안하여 큰 ID Cover를 가지는 노드는 leave/join과정을 에뮬레이션하여 주변 노드와 같은 크기의 ID Cover를 가지는 방법을 제안한다. 또한, 이벤트 전달과정에서 관심이 없는 노드에게 메시지가 전달되는 불필요한 트래픽을 최소화하기 위해 ID Cover를 인기있는 이벤트들이 가지는 방향(dimension)으로 맞추는(align) 과정 역시 비슷한 방법으로 가능하게 된다.
실험결과는 미리내 알고리즘은 O(log N)의 확장성을 가지며, 이벤트 전달과정이 약 2%의 오버헤드만으로 가능하다는 것을 보여준다. 이벤트가 전달되는 과정에서 생기는 딜레이 패널티 역시 4 ∼ 5정도로 만족할 만한 수준이다. 또한 zipf 분포를 가지는 트래픽에 대해서도 노드들의 부하 수준을 거의 비슷하게 조절할 수 있었다. 노드들의 갑작스런 failure에 대해서도 하이퍼 큐브의 유연성으로 인해 성능상의 손실은 적다는 것을 확인할 수 있다.
본 논문에서 제안한 미리내 프로토콜은 브로커없이 효율적으로 Publish/Subscribe 서비스를 가능하다는 것을 보여주며, 이는 피어-투-피어 네트웍상에서 많은 다른 고수준 서비스를 제공하는데 사용될 수 있다.
