반응형
들어가기전
p2p 사이트가 불법 음악/영화 공유로 유명한데, 그런 걸로만 쓰이는 것은 아니다.
중앙 집권 없이, 자원 공유를 가능케 하는 네크워크를 구축할 수 있게 해준다.
1. Client/Sever Architecture
- 서버에 데이터 있고, 클라이언트는 데이터를 서버에게 요청.
- 클라이언트 수 🔺 ⇒ 서버 demand 🔺
a. Client/Sever Architecture의 한계
- 확장성 문제
- SPoF
- administration(관리) 필요
- 네트워크 가장자리 → 사용되지 않는 리소스
⇒ 이런 문제를 해결 해줄 것이 바로 “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의 장점
- 자원의 효율적인 이용
- 확장성이 좋다.
- 신뢰성이 높다. (Replication, 지리적 분포, SPoF ❌)
- 관리 측면에서의 이점
- node들이 자체 조직 (관리가 분산됨)
- 서버 배치할 필요 x
- load balancing 분산
e. P2P의 단점
- Decentralized coordination (분산된 조정이 필요하다)
- Global state consistent 유지 해야함!! → Hard
- 노드 간의 성능, 속도 차이..
- 프로그래밍이 어렵다.
(decentralized coordination의 corollary(따름정리) 때문에…)
3. P2P Computing이 어디에 쓰일까!?
- **File Sharing** // 이 친구가 원조이다. file sharing 목적으로 p2p 시스템이 개발됨
- ****Process Sharing****
- ****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) 하나 하나가, 파일 제공자 역할도 함.
사용자들이 품질이 낮은 소스로부터 파일을 다운로드하는 것을 방지할 수 있음.
- → 왜냐하면, 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이 사용됨)
- KaZaA는 UUHash를 사용: 빠르지만 보안은 취약함
- How to fetch?
- A에서 [0..1000] 바이트 가져오고, B에서 [1001...2000] 바이트 가져옴
- 나누어 가져오기!!*
KaZaA의 장단점
- 장점:
- node heterogeneity을 고려하려는 시도를 함
- 대역폭
- 호스트 계산 리소스
- 호스트 가용성
- network locality을 고려함
- node heterogeneity을 고려하려는 시도를 함
- 단점:
- 여전히 검색 범위나 검색 시간에 대한 실질적인 보장이 없음
d. BitTorrent
BitTorrent의 역사
- 주된 동기:
- 인기 있는 콘텐츠는 temporal locality (시간적인 지역성)을 나타냄. (플래시 크라우드)
Spatial locality (X) - "Temporal locality (시간적인 지역성)"란 특정 콘텐츠가 특정 시간 동안 매우 인기가 있고, 그 후에는 관심이 급격하게 줄어드는 현상
- → 이러한 시간적 지역성을 기반으로 비트토렌트를 개발
즉, 한정된 시간 동안에만 필요한 콘텐츠에 대한 효율적인 다운로드 및 공유를 가능하게 하는 것
- 인기 있는 콘텐츠는 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 특정 콘텐츠가 있는 곳을 가르키도록) - 노드가 해당 콘텐츠를 원할 때,
가지거나 그 정보를 알고 있을 것으로 기대되는 노드로 이동!!
- 특정 node에 특정 콘텐츠를 보유하도록 지정
- 해결 과제:
- 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을 변경) - 항목을 여러 노드에 복제 → 견고성 증가
- Load Balancing : change the key-hash
- 목표 : 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) 노드만 알아야 함
- 키({key, value} 쌍)를 저장하는 노드를 검색
- 두 가지 프로토콜
- 단순 키 조회
- 보장된 방법
- 확장 가능한 키 조회
- 효율적인 방법
- 단순 키 조회
- 조회 쿼리는 후속자에게 전달됨.
- 일방향
- 원을 따라 쿼리를 전달
- 최악의 경우 O(N) 전달이 필요함
- 양방향으로는 O(N/2)
- 각 노드 n은 최대 m 항목 (피거 테이블finger table)을 포함하는 라우팅 테이블을 유지함
- 테이블의 ith 항목은 후속자의 위치 (n +2i-1)
- 주어진 식별자(key)에 대한 쿼리는 각 노드에서 m 항목 중에서 가장 가까운 노드로 전달됨(즉, key를 가장 즉시 선행하는 노드)
- 이 테이블은 O(log N) 개의 항목으로 구성되어 있고, 각 항목은 해당 노드의 이후의 노드를 가리키는데, 이를 이용하여 효율적인 조회를 가능케 합니다.
각 노드 n의 피거 테이블의 ith 항목은 n + 2^i의 위치에 있는 후속자 노드를 가리킵니다. 이것은 즉, 각 노드가 O(log N)만큼 떨어진 이웃 노드들을 추적하고 있음
- 새로운 노드 N은 후속자를 식별함
- 조회 수행 (N)
- 새 노드가 책임져야 하는 모든 후속자의 키를 가져감
- 그것의 선행자를 그의 후속자의 이전 선행자로 설정
- 그것의 후속자의 이전 선행자를 자신으로 설정
- 새로 가입한 노드가 피거 테이블을 작성함
- 조회 수행 (N + 2i-1) (i=0, 1, 2, ...I)
- I= 피거 테이블 항목 수
- 다른 노드의 피거 테이블을 업데이트함
- 노드 가입과 유사
- 노드가 책임져야 하는 모든 키를 후속자로 이동함
- 그것의 후속자의 선행자를 그의 선행자로 설정
- 그것의 선행자의 후속자를 그의 후속자로 설정
- 링크드 리스트 관리와 유사
- 피거 테이블은??
- 나가는 노드를 가리키는 다른 사람의 피거 테이블을 명시적으로 업데이트하는 방법이 없음
- 만약 링이 올바르다면, 루팅도 올바르고, 속도를 위해 손가락이 필요할 뿐
- 안정화
- 각 노드는 주기적으로 안정화 루틴을 실행함
- 각 노드는 모든 손가락을 주기적으로 새로 고쳐야 함
- 주기적인 비용은 손가락 새로 고침으로 인한 O(logN)임
- 실패한 노드는 다음과 같이 처리됨
- 복제: 후속자 하나 대신 r개의 후속자를 유지함
- 노드 실패 시 새로운 후속자를 찾을 수 있음
- 라우팅 중 경로 변경
- 피거가 응답하지 않으면 이전 피거를 취하거나, 충분히 가까우면 복제를 취함
- 복제: 후속자 하나 대신 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
- 구조는 이론적인 한계와 보장을 제공할 수 있다
반응형
