분산시스템) 시스템 아키텍쳐(2) - 비중앙 집중식

Decentralized architectures

중앙집중식 방식에서 중요한 것은 client-server 관점에서 컴포넌트를 어디에 둘지 수직적인 관점이었고 이와 반대로 수평적인 관점에서도 생각해 볼 수 있다.
Decentralized architectures는 서버와 클라이언트의 구분이 없다. 모든 노드들이 동일한 기능을 수행한다. 따라서 client-server 대신 peer라는 용어를 사용한다. 소위 말하는 P2P 시스템이 Decentralized architectures이다.

장점

앞서 말했듯이 중앙집중식 방식은 single point of failure, bottleneck, 확장성 등의 문제가 있을 수 있다. 이를 해결하기 위해 나온 것이 Decentralized 방식이다. 한 지점이 문제가 생겼을 때 일부는 마비될 수 있겠지만 전체가 마비되지 않으므로 single point of failure 문제를 해결할 수 있고, 특정 서버가 없기 때문에 peer가 계속 증가할 수 있어 client-server에 비해 확장성이 크다.

단점

서버가 없으므로 데이터를 어디서 관리할지에 대한 문제도 있다. 관리 측면에서 client-server에 비해 더 복잡해졌다. peer들끼리 역할 분담을 어떻게 할지에 대해 고민해야 한다. 오늘날 p2p 시스템들은 대부분 관리가 어렵기 때문에 순수한 p2p 시스템은 없다. 서버가 어딘가에 있고 처음에 필요한 데이터를 서버에서 받아오고 실제 돌아갈 때 서로 데이터를 주고받는 것은 p2p 방식으로 사용한다.
오늘날에는 블록체인이 나오면서 순수하게 p2p 방식으로 운영하는 것에 대해 고민하고 있다.

overlay network

p2p system에서 가장 주요한 문제는 peer들 간에 overlay network를 어떻게 구성할지 이다. overlay network는 채널간의 물리적인 underline computer network가 아닌 논리적인 process들 사이의 연결이 맺어진 상태를 말한다. 논리적인 레벨로 볼 때 두 peer간에 직접 연결이 되어있는 것처럼 그리지만 사실 물리적인 레벨로 보면 여러 라우터를 거쳐서 연결된다. 이처럼 직접 연결되어 있는것 처럼 나타내는 것을 overlay network라 한다.

peer들 간에 overlay network를 어떻게 연결할지에 따라 다양한 종류의 p2p 알고리즘이 존재한다. 연결 방식을 크게 두 가지로 구분해서 생각해볼 수 있다.

Structured P2P

Structured P2P는 overlay network를 어떤식으로 연결할지 특정 규칙에 따라 하는 방식인 deterministic procedure이다. 주로 Distributed hash table(DHT)를 이용하여 룰을 만들고 관리해야하는 데이터를 처리한다. 해쉬테이블은 key와 value의 pair로 이루어져있고 대량의 데이터를 빨리 찾고자 할 때 사용하는 자료구조이다. DHT는 해시테이블이 분산되어 있는 것을 말한다. 서버 없이 peer들이 데이터를 나누어서 담당하는 것이다.

(1) DHT-based system

관리해야하는 각각의 데이터에 키를 할당한다. hash function 같은 룰을 적용해서 키를 할당하여 동일한 데이터에 대해서 동일한 키를 가진다. 키는 128 or 160-bit의 긴 숫자이다. 데이터뿐만아니라 peer에 대해서도 어떤 키 값, 즉 id가 존재한다. 이를 바탕으로 어떤 키를 가진 peer가 어떤 데이터를 관리할지 결정한다. 데이터를 찾는 과정을 looking up이라 한다.

(2) Chord system

Chord system은 overlay를 원 형태로 구성한다. 한 peer는 다음 노드인 successor와 이전 노드인 predecessor 이렇게 최대 연결된 노드가 두 개 있을 수 있다. 노드가 새로 추가되었을 때에도 특정한 규칙이 있다. k라는 키값을 가진 데이터 아이템이 있을 때 이 노드는 id >= k인 노드 중 가장 작은 것이 관리한다. k를 담당하는 노드를 k의 successor라 하고 succ(k)로 나타낸다. Chord system을 이용하면 peer 위에 애플리케이션을 돌리면 되고 peer들 간 overly network 연결은 chord system에서 해준다.

(3) LOOKUP(k) function

이 함수는 succk(k)의 네트워크 주소를 반환해준다. 즉 찾고자 하는 데이터의 키값인 k를 주면 그 데이터를 관리하는 노드의 네트워크 주소를 알려준다.

 

chord system

 

그림 상에서 굵은 선으로 된 노드가 온라인인 상태이고 점선은 오프라인인 상태이다. 예를 들어 12 번이 관리하는 데이터는 12 번보다 작거나 같은 데이터 중 온라인인 7번 이후의 데이터인 8, 9, 10, 11, 12 이다. 시스템의 상황에 따라 어떤 데이터를 누가 관리할지는 달라진다. 만일 4번이 나가면 4번이 관리하던 데이터를 7번이 관리한다. 따라서 데이터를 찾는 LOOKUP 과정이 복잡해진다.

(4) Membership management

새로운 노드가 코드 네트워크에 참여하고 싶을 때 먼저 ID를 얻어야 한다. ID는 코드 시스템 상에서 사용할 수 있는 것이고 hash function을 통해 얻어진다. hash function은 input의 개수에 비해 output의 개수가 적기 때문에 중복된 ID가 나올 수도 있다. 따라서 key를 나타내는 bit 수를 크게한다. (보통 160 bits) 내가 할당받은 ID를 가지고 코드 시스템에 LOOKUP 서비스를 요청한다. 예를 들어 새로 들어온 노드의 ID가 13일 때 LOOKUP 서비스를 통해 자신의 successor 15를 알게된다. 그 다음 13이 15와 통신해서 15의 predecessor를 자신의 predecessor로 하고 15의 predecessor는 13인 자신으로 바꾼다. 그 다음 predecessor인 12와 통신하여 비슷한 형태로 변경한다. 나갈 때도 비슷한 식으로 변경한다. 중간에 그냥 나가버리는 경우가 생길 수도 있으므로 지속적으로 자신의 successor와 predecessor가 잘 연결되어 있는지 확인해야한다.

Unstructured P2P

(1) Randomized algorithms

오버레이를 구축하고 데이터를 관리하는 측면에서 특별한 룰 없이 randomized algorithms을 주로 사용한다. structured P2P에서 각각의 노드는 이웃 노드만 연결할 수 있었는데, Unstructured P2P에서는 어느 노드든 연결할 수 있다. 따라서 각 peer마다 이웃 노드에 대한 리스트가 존재하고 데이터를 관리하는 노드도 랜덤하게 결정한다.

(2) LOOKUP

찾고자 하는 데이터가 어디에 있는지 찾기 위해서 flooding(broadcast)해야한다. 브로드캐스트는 네트워크를 혼잡하게 만들 수 있기 때문에 좋지 않다.

Unstructed P2P

(3) Membership management

주기적으로 각자 가지고있는 이웃 정보를 교환하여 업데이트하여 관리한다. 새로운 노드가 들어왔을 때 모든 노드에 정보를 뿌리고 반응이 오는 노드와 맨 처음 연결을 하면 그때부터 이웃 노드 정보를 업데이트 하면서 연결을 해나갈 수 있다. 사실 내 옆에 연결할 수 있는 노드가 더 있을 수 있는데 알지 못하는 것일 뿐이니 자신의 이웃 정보는 Partial view이다. 어떤식으로 Partial view를 노드들 사이에서 교환할지에 따라 Unstructured 방식도 여러가지가 있을 수 있다.

Superpeers

P2P, 특히 Unstructured P2P에서는 문제가 많다. 이를 해결하기 위해 나온 개념이 Superpeers이다. 순수한 p2p가 아닌 다른 peer보다 강력한 정보와 파워를 가진 peer이다. Superpeers는 어떻게 정할까? distributed한 방법으로 peer들끼리의 합의를 통해 Superpeers를 정한다.

(1) Overlay

Superpeer는 data items의 인덱스를 가지고 있어서 누구에게 해당 데이터가 있는지 알고있다. 이전에는 임의의 peer가 어떤 peer에게 연결해야할지도 애매했는데 이제는 가까운 superpeer에 일단 연결하면 된다. 따라서 오버레이 네트워크 구축하고 데이터를 찾는 것에 대해 이전보다 관리가 쉬워졌다.

superpeers

(2) Leader-selection

Superpeer는 서버같은 역할을 해야하기 때문에 high availability를 가지고 안정적으로 오랫동안 돌아갈 수 있는 long-lived processes를 선택해야한다. 만일 superpeer역할을 하는 peer가 나가게 되면 새로운 superpeer를 선정해야 한다. 그리고 superpeer는 고정적인 것이 아니다. 만일 어떤 peer가 특정 superpeer에 연결되었는데 다른 superpeer에 연결되는 것이 좋다면 자신과 연결된 superpeer를 바꿀 수 있다.

Hybrid architecture

Client-server와 P2P를 혼합한 형태이다. 각각의 장점을 함께 사용하기 위함이다. peer들끼리 서로 직접적으로 연결하는 것은 P2P방식으로 하고 서버는 필요할 때에 이용한다. 서버에게는 데이터를 주고받을 상대를 물어본다. Hybrid architecture를 사용하는 시스템은 Edge-server systems과 Collaborative distributed systems이 있다.

(1) BitTorrent

Hybrid architecture방식을 사용하는 파일 공유 시스템이다. tit-for-tat 정책을 사용한다. 일단 도움을 필요로하는 노드들에게 많이 업로드할 수록 다운로드 속도를 빠르게 해준다.

 

hybrid architecture

 

클라이언트 노드는 자신이 원하는 파일을 찾기 위해 bitTorrent를 사용하고자 한다면 찾고자하는 파일의 torrent 파일을 찾아야한다. 이를 위해선 우선 해당 정보를 가진 bitTorrent 웹서버를 찾아서 토렌타파일 서버에서 .torrent file을 받아온다. .torrent file을 통해서 tracker를 알아낸다. tracker안에 이 파일에 대한 정보를 어떤 노드에서 가지고 있는지에 대한 정보가 있다. tracker가 알려준 정보를 토대로 해당 노드들로부터 동시에 파일 조각들을 받을 수 있다. 이 전까지는 서버가 개입한 클라이언트-서버 구조이고 노드들과 파일을 주고 받는것은 직접적으로 하는 p2p 방식을 사용한다.