Chapter 9. Peer-To-Peer(P2P) Computing

들어가기전

p2p 사이트가 불법 음악/영화 공유로 유명한데, 그런 걸로만 쓰이는 것은 아니다.

중앙 집권 없이, 자원 공유를 가능케 하는 네크워크를 구축할 수 있게 해준다.

 

---

1. Client/Sever Architecture

• 서버에 데이터 있고, 클라이언트는 데이터를 서버에게 요청.
• 클라이언트 수 🔺 ⇒ 서버 demand 🔺

---

a. Client/Sever Architecture의 한계

1. 확장성 문제
2. SPoF
3. administration(관리) 필요
4. 네트워크 가장자리 → 사용되지 않는 리소스

⇒ 이런 문제를 해결 해줄 것이 바로 “P2P System”

---

2. P2P 정의

• P2P는 분산된 Resource(자원)을 활용하여 분산 방식으로 기능을 수행하는 시스템 및 응용 프로그램의 class
• resources :
  • computing power, data(storage and content), network and bandwidth , presence(computers, human, and other resources)
• 모든 네트워크 노드가 동일하게 작동하는 통신 모델!

P2P Computing

• 시스템 간의 직접 교환 → 컴퓨터 리소스 및 서비스의 공유

---

a. P2P란 무엇인가?

• 분산 시스템 아키텍처
  • 중앙 집권 ❌
  • Node 🔺(Scalability 👍), Reliable 👎, heterogeneous (이질성)
  • 노드들은 기능적으로 대칭!
  • Fault-tolerant, 자체 조직

---

b. P2P 네트워크 특성

• 클라이언트는 서버가 될 수도 있고, 라우터가 될 수도 있음.
  • 노드는 콘텐츠, 저장 공간, 메모리, CPU를 기여
• 노드는 자율적 (관리 권한 없음)
• 네트워크는 Dynamic : 노드가 네트워크에 자주 enter(join) & leave
• 노드는 서로 직접 협력!

---

c. P2P vs. 클라이언트/서버

• 순수한 P2P:
  • 중앙 서버 없음
  • 특정 요청의 경우 어떤 피어도 클라이언트, 라우터 또는 서버로 작동할 수 있음
  • 정보는 중앙 위치에 위치하지 않고 모든 피어 사이에 분산됨
  • 정보를 찾으려면 피어가 여러 피어와 통신해야 할 수도 있음

더 많은 피어가 추가될수록 네트워크의 수요 및 용량이 증가합니다!

---

d. P2P의 장점

1. 자원의 효율적인 이용
2. 확장성이 좋다.
3. 신뢰성이 높다. (Replication, 지리적 분포, SPoF ❌)
4. 관리 측면에서의 이점
   1. node들이 자체 조직 (관리가 분산됨)
   2. 서버 배치할 필요 x
   3. load balancing 분산

---

e. P2P의 단점

1. Decentralized coordination (분산된 조정이 필요하다)
   1. Global state consistent 유지 해야함!! → Hard
2. 노드 간의 성능, 속도 차이..
3. 프로그래밍이 어렵다.
   (decentralized coordination의 corollary(따름정리) 때문에…)

 

---

3. P2P Computing이 어디에 쓰일까!?

1. **File Sharing** // 이 친구가 원조이다. file sharing 목적으로 p2p 시스템이 개발됨
2. ****Process Sharing****
3. ****Collaborative Environments****

---

a. P2P File Sharing Application

• data availability 향상!
• 장애를 보상하기 위한 복제.
• 예: Napster(원조), Gnutella, Freenet, KaZaA (FastTrack)...

---

b. P2P Process Sharing Application

• 대규모 계산 용도!
• 예: SETI@Home, distributed.net, World-Wide Computer
  • SETI(Search for Extra-Terrestrial Intelligence) → CPU Power를 공유한다.

---

c. P2P Collaborative Environments Application

• 원격 실시간 협업을 위해 사용
• 예: talk, IRC, ICQ, AOL Messenger, Yahoo! Messenger, Jabber, MS Netmeeting, NCSA Habanero, 게임
  • Skype (VoIP P2P system)
  • SNS

---

4. P2P 가 보장해주는 특성들

• 대규모 확장성! (Massive Scalability)
• No SPoF
• Dos 공격으로부터 안전!
• 부하 분산

---

5. P2P가 기술적으로 극복해야 할 점들

• peer 발견 / 식별, Routing protocols, 보안, 미세한 자원 관리 등

---

6. Unstructured P2P

a. Napster

Napster OverView

• P2P 시장의 막을 열었다.
• Central [ Indexing / Searching ] ⇒ Server!
  • 순수 P2P가 아닌 하이브리드 P2P (서버가 있긴함)
• Centralized Database:
  • Join: 시작 → client가 중앙 서버에 접근
  • Publish: 중앙 서버에 자신의 File list를 보고
    • Server가 각 client의 File List를 유지하고 있음
  • Search: query the server ⇒ 요청한 파일을 저장하고 있는 누군가를 return 해줌.
  • Fetch: 그 누군가에게 File을 peer-to-peer 방식으로 Directly하게 가져옴

---

Napster ; Hybrid p2p

• Central Napster Server
  • 장점
    • 올바른 결과를 보장할 수 있다!
  • 단점
    • Scalability에 대한 Bottleneck 가능성
    • SPoF
    • 서비스 거부에 취약함. → 외부에서 발생하는 공격에 취약하다
• Search = Centralized
• File Transfer = Direct (peer-to-peer)

---

Napster Refinement (세부 조정)

• 향상된 directory server는 client를 조사하고, 그들의 file list 상태를 추적하는 것으로 보인다.
• "Bad Sources”를 list에서 잘라내기 위해, 다운로드 문제가 있는 node를 자동으로 보고함.
  • → 왜냐하면, node(client) 하나 하나가, 파일 제공자 역할도 함.
    사용자들이 품질이 낮은 소스로부터 파일을 다운로드하는 것을 방지할 수 있음.
• Ranking Data Source에 대한 Incentive 제공
• 이러한 노드에게 더 좋은 점수를 부여! → 클라이언트 목록을 나열함
  • 오랫동안 가동 중
  • Fast Connections을 가진.
  • 다운로드를 수행하는 client와 가까움.
  • 병렬 다운로드 지원 (나눌 수 있음)
  • 비대칭 다운로드/업링크 속도 활용 ⇒ 대역폭을 나누어 upload / download 나눔.

---

b. Gnutella

Gnutella의 역사

→ Napster의 Centralized Server 없애고, 모든 것을 다 분산!

---

Gnutella: Overview

• Query Flooding: (BroadCasting)
  • Join: Client가 시작할 때 몇 개의 다른 노드에 연락 → 그 노드들이 이 client의 "neighbors(이웃)"이 됨.
  • // Publish: NO NEED
  • Search: 이웃에게 물어보고, 그 이웃들이 자신의 이웃들에게 물어보는 식으로 계속 전파.
                    Find! → 해당 정보를 요청자에게 응답
  • Fetch: File을 peer-to-peer 방식으로 Directly하게 가져옴

⇒ 파일 있냐고 쿼리문을 이웃에게 계속 전파시키는 방식

---

Gnutella의 장단점

• 장점:
  • Fully de-centralized (완전한 분산)
  • Search Cost가 분산된다. (모든 노드에게 보내지 않아도 되고, 각자의 이웃에게만 보냄)
• 단점:
  • Search scope = O(N)
  • Search time = O(???)
  • 노드가 자주 나가서 네트워크가 불안정
  • Flooding 기반의 검색은 Bandwidth에서 매우 낭비적이다… (중복 메시지 多)

---

c. KaZaA

KaZaA의 역사

• Gnutella와 Napster 사이의 Hierarchical Approach (계층적 구조)
  • Two-Layred Architecture
  • Powerful nodes (supernodes)는 로컬 인덱스 서버로 작동.
    client query들이 다른 supernodes에게 전파됨
  • 각 슈퍼노드는 약 100-150개의 하위 노드를 관리
  • 각 슈퍼노드는 30-50개의 다른 슈퍼노드에 연결
     ⇒ Gnutella보다 효율적인 조회 및 Napster보다 확장 가능성이 높음

---

KaZaA: Overview

• “Smart(Intelligent)” Query Flooding:
  • Join: client 시작 → supernode에 접근 (언제간 본인이 supernode가 될 수도 있음)
  • <마치 Napster가 중앙 서버에 접근 하듯이>*
  • Publish: supernode에게 file list를 보냄
  • Search: supernode에게 query를 보내고, supernode간에 query를 flooding함.
  • <마치 Gnutella가 neighbor에게 flooding 하듯이>*
  • Fetch: File을 peer-to-peer 방식으로 Directly하게 가져옴 + 여러 peer에서 동시에 fetch 가능

---

KaZaA: Fetching

• 하나 이상의 node가 requested file을 가지고 있을 수 있음.
• How to tell ?
  • 동일한 파일을 구별할 수 있어야 함
  • 동일한 파일 이름일 필요는 X
  • 역으로, 동일한 파일 이름이라고 해서 반드시 동일한 파일은 아님...
• Use Hase of File
  • KaZaA는 UUHash를 사용: 빠르지만 보안은 취약함
    (대체로 MD5, SHA-1이 사용됨)
• How to fetch?
  • A에서 [0..1000] 바이트 가져오고, B에서 [1001...2000] 바이트 가져옴
  • 나누어 가져오기!!*

---

KaZaA의 장단점

• 장점:
  • node heterogeneity을 고려하려는 시도를 함
    • 대역폭
    • 호스트 계산 리소스
    • 호스트 가용성
  • network locality을 고려함
• 단점:
  • 여전히 검색 범위나 검색 시간에 대한 실질적인 보장이 없음

---

d. BitTorrent

BitTorrent의 역사

• 주된 동기:
  • 인기 있는 콘텐츠는 temporal locality (시간적인 지역성)을 나타냄. (플래시 크라우드)
    Spatial locality (X)
  • "Temporal locality (시간적인 지역성)"란 특정 콘텐츠가 특정 시간 동안 매우 인기가 있고, 그 후에는 관심이 급격하게 줄어드는 현상
  • → 이러한 시간적 지역성을 기반으로 비트토렌트를 개발
    즉, 한정된 시간 동안에만 필요한 콘텐츠에 대한 효율적인 다운로드 및 공유를 가능하게 하는 것
• Focused on Efficient Fetching, not Searching:
  • same file을 all peers에게 배포
  • Single publisher, Multiple Downloaders

---

BitTorrent

• File Swarming 을 사용한 효율적인 콘텐츠 배포 시스템.
• 전형적인 p2p 시스템의 모든 기능(4단계) 수행 X
  Searching 수행 X
• "Pull-based" “Swarming” 의 작동방식
  • 각 file은 더 작은 pieces으로 분할됨
  • nodes는 neighbors에서 원하는 pieces을 요청
  • pieces은 순차적으로 다운로드되지 않음
• 모든 node가 기여하도록 장려함

---

용어

• Seed(seeder): 전체 파일을 가진 피어
  • Original Seed: 첫 번째 시드
• Leech(leecher)(=downloader) : 파일을 다운로드하는 peer
• Sub-piece: piece의 더 작은 하위 분할
  • Request의 단위
  • peer는 완전한 조각을 조립한 후에만 업로드함

---

기본 아이디어

• Leecher가 파일의 piece를 다운로드하면 해당 조각의 Replica가 생성됨.
• 더 많은 다운로드는 더 많은 복제본을 의미함
• Leecher가 완전한 조각을 가지면 잠재적으로 다른 downloader와 공유할 수 있음.
• 최종적으로 각 Leecher는 모든 조각을 얻어 파일을 조립함.

---

BitTorrent: 개요

• Swarming:
  파일의 각 조각은 여러 peer에게 분산된다. 이러한 peer들은 함께 협력하여 파일을 공유하고 다운로드!!
  • Join: 중앙 집중식 "Tracker Server" 서버에 연락 → peer list를 가져옴
  • Publish: Tracker Server를 실행
  • Search: Out-of-band (File을 Serching은 우리 영역이 아니다.)
                  검색엔진에서 Tracker을 찾아라.
  • Fetch: client는 여러 peer로부터 조각을 받아온다. (Download chunk)
                 내가 가지고 있는 Chunk (조각)를 peer에 업로드함

---

BitTorrent: 공유 전략

• "Tit-for-tat" 공유 전략 사용 (눈에는 눈 이에는 이)
  • "당신이 나에게 공유하면, 나도 다른 사용자들에게 공유할 것” 약속.
    • 희망편 : downloader가 많아지면, 효율적으로, 무료로 다운로드 가능!
    • 절망편 : 아무도 공유를 시작하지 않음 (Download 끝나면 바로 공유 없이 삭제)
• Pareto Efficiency에 근사하게 된다.
  • "다른 사람들에게 해를 끼치지 않고는 누구도 좋아질 수 없다"

---

BitTorrent의 장단점

• 장점:
  • "인기 있는 콘텐츠"에 대해서는 아주 잘 작동!
  • peer에게 자원을 공유하도록 동기 부여; freeloaders 방지
• 단점:
  • swarming을 bootstrap하기 위해 Central Tracker Server 필요
  • Central Tracker에 대한 SPoF

 

 

---

7. Structured P2P

• Unstructured P2P networks는 리소스를 어떤 노드에든 배치할 수 있다. // 지금까지 본 것들이 Unstructured P2P
  • network topology는 Arbitrary(임의적). Growth는 Spontaneous(자발적).
• Structured P2P networks는 리소스 위치와 부하 분산을 간소화하기 위해. // 아래 볼 사례들이 Structured P2P
• topology를 정의하고 리소스 배치를 위한 규칙을 정의!*
  • object를 효율적으로 검색하는 것을 보장
  • 분산 해시 테이블(Distributed Hash Tables, DHT) 규칙에 따른다.
• = 노드들 간의 물리적 또는 논리적인 배치 방법, 그리고 노드들 간의 통신 규칙을 명시

---

a. DHT(Distributed Hash Tables)

• 동기:
  • 어설픈 P2P들의 인기에 어이가 없음 → 더 나은 P2P 서비스를 제공하고자 함

DHT 개요: Directed Lookup

• 아이디어:
  • 특정 node에 특정 콘텐츠를 보유하도록 지정
    (or 특정 콘텐츠가 있는 곳을 가르키도록)
  • 노드가 해당 콘텐츠를 원할 때,
    가지거나 그 정보를 알고 있을 것으로 기대되는 노드로 이동!!
• 해결 과제:
  • Distributed: 기존 노드들 사이에 책임을 분산해야 함.
  • Adaptive: 노드가 P2P overlay를 join & leave
    • 참여하는 노드에게 지식 책임을 분배
    • 떠나는 노드에서 지식 책임을 재분배

---

Hash Table

• 임의의 key & 인접한 데이타(value) 저장.
  • put (key, value)
  • value = get(key)
• 조회가 빨라야 함
  • 키에 대한 해시 함수 h()를 계산하여 저장 셀 반환
  • Chained Hash Table : key 저장

 

---

분산 해시 테이블(Distributed Hash Table, DHT)

• P2P 네트워크에서의 해시 테이블의 기능 : keys로 index된 데이터를 빠르게 조회
• Key-hash → node mapping
  • 고유한 라이브 노드를 키에 할당
  • 오버레이 네트워크에서 빠르고 저렴하게 이 노드를 찾음
• DHT의 유지 관리 / 최적화 방법은?
  • Load Balancing : change the key-hash
    (부하 많이 받으면, runtime에 동적으로 노드에 대한 mapping을 변경)
  • 항목을 여러 노드에 복제 → 견고성 증가
• 목표 : key - value Mapping
• 분산되어 있으며, 이웃의 수가 제한됨

 

• 검색에 대한 성능을 보장
  • 콘텐츠가 네트워크에 있으면 찾을 수 있음
  • 검색에 필요한 메시지 수는 제한됨
• 참여/떠나기에 대한 성능을 보장
  • 영향을 받는 노드의 최소한의 수
• 보장된 성능이 필요한 파일 시스템과 같은 응용 프로그램에 적합

---

DHT의 장단점

• 장점:
  • 조회 보장!
  • 노드 당 상태 및 검색 범위에 대한 O(log N)
• 단점:
  • 비정확한 일치 검색을 지원하는 것이 어려움
  • 아무도 사용하지 않는다...

---

b. Structured P2P Systems 로직 구현 ; Chord

노드들 간의 물리적 또는 논리적인 배치 방법, 그리고 노드들 간의 통신 규칙을 명시 → 어떤 방식/구조로 할 것인지?
DHT? CAN? Chord?

• Chord (DHT의 일종)
  • 링 구조를 사용하여 노드 간의 일관된 해싱을 구현!
  • 각 노드는 링 상의 특정 위치에 매핑되어 있으며, 이는 효율적인 Key-Value 검색을 가능하게 한다.
• Pastry, CAN, Kademlia 등 이 있다.

---

Chord

• 중요한 건 : orderd ring overlay를 기반으로 한 일관된 해싱

여기 아래 부분은 추가적으로만 보세용…

• Chord
  • 일관된 해싱
    • 무작위성
      • 모든 노드가 대략적으로 동일한 부하를 받음
    • 지역성
      • 노드 추가 또는 제거에는 키의 O(1/N) 분수가 새 위치를 얻는 데 관여됨
  • 실제 조회
    • 조회를 위해 후속자 및 전송자 외에 O(log N) 노드만 알아야 함
  Chord : 조회 작업
  • 키({key, value} 쌍)를 저장하는 노드를 검색
  • 두 가지 프로토콜
    • 단순 키 조회
      • 보장된 방법
    • 확장 가능한 키 조회
      • 효율적인 방법
  Chord : 기본 조회
  • 조회 쿼리는 후속자에게 전달됨.
    • 일방향
  • 원을 따라 쿼리를 전달
  • 최악의 경우 O(N) 전달이 필요함
    • 양방향으로는 O(N/2)
  Chord : 확장 가능한 조회
  • 각 노드 n은 최대 m 항목 (피거 테이블finger table)을 포함하는 라우팅 테이블을 유지함
  • 테이블의 ith 항목은 후속자의 위치 (n +2i-1)
  • 주어진 식별자(key)에 대한 쿼리는 각 노드에서 m 항목 중에서 가장 가까운 노드로 전달됨(즉, key를 가장 즉시 선행하는 노드)
  • 이 테이블은 O(log N) 개의 항목으로 구성되어 있고, 각 항목은 해당 노드의 이후의 노드를 가리키는데, 이를 이용하여 효율적인 조회를 가능케 합니다.
    각 노드 n의 피거 테이블의 ith 항목은 n + 2^i의 위치에 있는 후속자 노드를 가리킵니다. 이것은 즉, 각 노드가 O(log N)만큼 떨어진 이웃 노드들을 추적하고 있음
  Chord : 노드 가입
  • 새로운 노드 N은 후속자를 식별함
    • 조회 수행 (N)
  • 새 노드가 책임져야 하는 모든 후속자의 키를 가져감
  • 그것의 선행자를 그의 후속자의 이전 선행자로 설정
  • 그것의 후속자의 이전 선행자를 자신으로 설정
  • 새로 가입한 노드가 피거 테이블을 작성함
    • 조회 수행 (N + 2i-1) (i=0, 1, 2, ...I)
    • I= 피거 테이블 항목 수
  • 다른 노드의 피거 테이블을 업데이트함
  Chord : 노드 나가기
  • 노드 가입과 유사
  • 노드가 책임져야 하는 모든 키를 후속자로 이동함
  • 그것의 후속자의 선행자를 그의 선행자로 설정
  • 그것의 선행자의 후속자를 그의 후속자로 설정
    • 링크드 리스트 관리와 유사
  • 피거 테이블은??
    • 나가는 노드를 가리키는 다른 사람의 피거 테이블을 명시적으로 업데이트하는 방법이 없음
  Chord : 안정화
  • 만약 링이 올바르다면, 루팅도 올바르고, 속도를 위해 손가락이 필요할 뿐
  • 안정화
    • 각 노드는 주기적으로 안정화 루틴을 실행함
    • 각 노드는 모든 손가락을 주기적으로 새로 고쳐야 함
    • 주기적인 비용은 손가락 새로 고침으로 인한 O(logN)임
  Chord : 장애 처리
  • 실패한 노드는 다음과 같이 처리됨
    • 복제: 후속자 하나 대신 r개의 후속자를 유지함
      • 노드 실패 시 새로운 후속자를 찾을 수 있음
    • 라우팅 중 경로 변경
      • 피거가 응답하지 않으면 이전 피거를 취하거나, 충분히 가까우면 복제를 취함
  • DHT 수준에서는 키를 r개의 후속자 노드에 복제할 수 있음
    • 저장된 데이터는 더욱 견고해짐
• 노드가 오버레이에 참여하거나 나가면 객체가 노드 간으로 이동하는 데 O(K/N)의 복잡성이 발생함.
• Chord : 해싱 속성

---

P2P vs. Google

• Google이 수행하는 복잡한 검색 쿼리와 랭킹 시스템이 대규모 클러스터와 고대역폭 네트워크를 필요로 함.

 

 

 

---

---

P2P: 요약

• 각각의 장단점을 기억하라
  • centralized, flooding, swarming, unstructured and structured routing
• 배운 교훈:
  • SPoF 나빠!
  • Flooding messages to everyone 나빠!
  • Underlying(기본) network topology 중요!
  • Not all nodes are equal
  • Need incentives to discourage freeloading (Ranking)
  • Privacy and security are important
  • 구조는 이론적인 한계와 보장을 제공할 수 있다