원문은 IPLD Github specs 에서 확인 가능하다. IPLD Graphsync

Graphsync

Status: Prescriptive - Draft

peer간에 그래프를 동기화하는 프로토콜이다.

ipld, IPLD Selectors 도 참조하여야 한다.

[Meta: Status of this doc]

  • 이 내용은 2018-10-16 경에 작성되었다. (video presentation)
  • 미완성 문서상태 임
  • 이미 비트맵을 구현한 사람이면 구현할 수 있는 충분한 정보를 제공
  • bitswap 에 크게 의존

1. Concepts and Glossary

  • peer-graphsync 프로토콜에 참여하는 프로그램 또는 프로세스. 다른 피어에 연결할 수 있음
  • graph-콘텐츠의 directed acyclic graph (DAG). IPLD dag. 다른 노드에 대한 해시 (content addressed, authenticated) 링크가 있는 노드로 구성. (\(G\))
  • dag-directed acyclic graph. DAG는 모두 IPLD (해시 링크, 인증, 컨텐트 주소 등으로 연결됨)
  • selector-그래프의 특정 subset을 식별하는 표현식. (\(S(G) \subset G\))
  • selector language-언어는 셀렉터 제품군을 정의
  • request-한 피어에서 다른 피어로 콘텐츠 요청. 이는 HTTP, RPC 또는 API 요청과 유사
  • response-responder에서 requester로 전송된 콘텐츠는 request를 수행
  • requester-request를 시작하는 피어 (콘텐츠를 원함)
  • responder-피어는 request을 받고, response에 콘텐츠를 제공
  • request process-요청 및 그 이행은 하위 프로세스로, 다음 단계 (상위 단계)의 피어를 통한 프로 시저 호출:
    • (1) requester는 원하는 콘텐츠와 다른 요청 매개 변수를 지정하면서 responder에게 요청 메시지 (req)를 보냄으로 시작
    • (2) 요청 메시지를 수신하면, responder는 요청을 활성 요청 집합에 추가하고 처리를 시작
    • (3) responder는 requester에게 내용을 전송하여 요청을 이행 (response)
    • (4) responder와requester는 언제든지 요청 프로세스를 종료 할 수 있음
    • Notes:
      • 명시적으로 requester와 responder가 다른 피어가 할 수 있는 “role”이고 웹의 two-sided client-server 모델에서 충만하지 않기 위해 client-server 용어를 피하고 있음.
      • requests는 short 또는 long-lived – 요청은 마이크로 초만큼 짧거나 무한정 지속될 수 있음
  • priority-요청에 대한 상대적 순서를 암시하는 request과 연관된 숫자 label. requester가 requests 충족이 되기를 원하는 순서를 requester's에게 표현하는 responder의 방식이다. responder는priority를 존중해야하지만, 어떤 순서로든 respondions를 반환 할 수도 있다.

2. Interfaces

이것은 그래프 동기화 프로토콜과 관련된 데이터 구조와 프로세스 인터페이스 목록이다. 간단히하기 위해, 우리는 Go 형식 표기법을 사용한다. 물론 graphsync는 언어에 구애받지 않는다.

type Graphsync interface {
	Request(req	Request) (Response, error)
}

type Request struct {
    Selector Selector
    Priority Priority      // optional
    Expires  time.Duration // optional
}

type GraphSyncNet interface {
    SendMessage(m Message)
    RecvMessage(m Message)
}

3. Network Messages

message GraphsyncMessage {

  message Request {
    int32 id = 1;       // unique id set on the requester side
    bytes selector = 2; // ipld selector to retrieve
    bytes extra = 3;    // aux information. useful for other protocols
    int32 priority = 4;	// the priority (normalized). default to 1
    bool  cancel = 5;   // whether this cancels a request
  }

  message Response {
    int32 id = 1;     // the request id
    int32 status = 2; // a status code.
    bytes extra = 3;
  }

  message Block {
  	bytes prefix = 1; // CID prefix (cid version, multicodec and multihash prefix (type + length)
  	bytes data = 2;
  }

  // the actual data included in this message
  bool completeRequestList    = 1; // This request list includes *all* requests, replacing outstanding requests.
  repeated Request  requests  = 2; // The list of requests.
  repeated Response responses = 3; // The list of responses.
  repeated Block    data      = 4; // Blocks related to the responses
}

3.1 Response Status Codes

# info - partial
10   Request Acknowledged. Working on it.
11   Additional Peers. PeerIDs in extra.
12   Not enough vespene gas ($)
13   Other Protocol - info in extra.
14   Partial Response w/ metadata, may include blocks, metadata in extra

# success - terminal
20   Request Completed, full content.
21   Request Completed, partial content.

# error - terminal
30   Request Rejected. NOT working on it.
31   Request failed, busy, try again later (getting dosed. backoff in extra).
32   Request failed, for unknown reason. Extra may have more info.
33   Request failed, for legal reasons.
34   Request failed, content not found.

4. Example Use Cases

4.1 Syncing a Blockchain

하고자하는 Requests:

  • <hash>/Parent, <hash>/Parent/Parent등을 N depth까지 부여
  • <hash1>에는 존재하지만 <hash2>에는 존재하지 않는 노드
    • 이 외에도 “Give me some range of (the above query) is very important”. 예를들면: “Give me the second 1/3 of the nodes that are children of <hash1> but not <hash2>”

4.2 Downloading Package Dependencies

  • <hash>/foo/v1.0.0의 모든것을 원함

4.3 Loading content from deep within a giant dataset

  • 경로 <hash>/a/b/c/d/e/f/g에 대한 노드를 원함

4.4 Loading a large video optimizing for playback and seek

  • First, 처음 몇개의 데이터 블록 <hash>/data/*
  • Second, <hash>/**/!를 제외한 모든 tree를 원함
  • Third, <hash>/**/* 나는 모든것을 원함

4.5 Looking up an entry in a sharded directory

might가 샤드된 디렉토리에 존재하는 디렉토리 엔트리가 있다고 가정할 때 아이템에 대한 경로를 지적하고 준재하는 경로의 많은 부분을 되찾을 수 있어야 한다. 예: “Give me <shardhash>/AB/F5/3E/B7/11/C3/B9”

만약 원하는 항목이 실제 /AB/F5/3E에 있다면 되돌려놓아야 한다.

5. Other notes

Cost to the responder. 그래프 동기화 프로토콜은 CPU와 메모리의 오버 헤드가 0이 아닌 추가 오버 헤드를 필요로한다. 이 비용은 매우 분명하게 표현되어야 하고, 계산되어야한다. 그렇지 않으면 DoS 벡터를 열게 될 것이다.