Understanding Git - Data Model

|-- objects
|   |-- 5d
|   |   |-- 92c127156d3d86b70ae41c73973434bf4bf341
|   |-- a6
|   |   |-- bdf05551541dc86b7a49212b62cfe1e9bb14fe
|   |-- cf
|   |   |-- 59e02c3d2a2413e2da9e535d3c116af1077906
|   |-- f8
|   |   |-- 9e64bdfcc08a8b371ee76a74775cfe096655ce
|   |-- info
|   |-- pack

              +-----------------+
              |     a6dbf0      |
              +-----------------+
              | tree     f89e64 |
              +-----------------+
                       |
                       v
              +-----------------+
              |     f89e64      |
              +-----------------+
              |cf59e0  README.md|
              |5d92c1  index.php|
              +-----------------+
                     |    |
         +-----------+    +-----------+
         |                            |
         v                            v
+-----------------+          +-----------------+
|     5d92c1      |          |     cf59e0      |
+-----------------+          +-----------------+
| <?php echo      |          | # Description   |
| "Hello World";  |          |This is my hello |
|                 |          |world project    |
+-----------------+          +-----------------+

2005년에 시작된 이래로 git은 오픈 소스 세계에서 대중적으로 인기를 얻고있다. 매우 유명한 VCS 도구들이 있지만 이와 성격은 조금 다르다. 최근에는 포스트에도 사용하고 있다. Edward Thomson이 강연 한 Deep Dive Into Git을 확인하는것이 크게 도움된다:

“The Git commands are just a leaky abstraction over the data storage.” Git commands는 data storage에 대한 leaky abstraction 이다.

git의 data model을 알아보자.

git init

시작하려면 프로젝트 디렉토리에서 git 저장소를 초기화한다:

git init

Git은 프로젝트 디렉토리에 .git 디렉토리를 생성한다:

$ tree .git/

.git/  
|-- HEAD  
|-- config  
|-- description  
|-- hooks  
|   |-- applypatch-msg.sample  
|   |-- commit-msg.sample  
|   |-- post-update.sample  
|   |-- pre-applypatch.sample  
|   |-- pre-commit.sample  
|   |-- pre-push.sample  
|   |-- pre-rebase.sample  
|   |-- pre-receive.sample  
|   |-- prepare-commit-msg.sample  
|   |-- update.sample  
|-- info  
|   |-- exclude  
|-- objects  
|   |-- info  
|   |-- pack  
|-- refs  
    |-- heads  
    |-- tags

8 directories, 14 files

이 파일들과 디렉토리 중 일부는 익숙한 모습이지만 (특히, HEAD), 우선 비어있는 .git/objects 디렉토리에 집중하여 보자.

  • index.php 파일 생성
touch index.php
  • 내용 추가
<?php  
echo "Hello World";
  • README.md 파일 생성
touch README.md
  • 내용 추가
# Description  
This is my hello world project
  • commit
git add .  
git commit -m "Initial Commit"

.git 디렉토리에서 다시 한번 살펴보면 .git/object 디렉토리에 몇개의 서브 디렉토리와 파일이 있음을 알 수 있다.

|-- objects  
|   |-- 5d  
│   │   |-- 92c127156d3d86b70ae41c73973434bf4bf341  
|   |-- a6  
│   │   |-- dbf05551541dc86b7a49212b62cfe1e9bb14f2  
|   |-- cf  
│   │   |-- 59e02c3d2a2413e2da9e535d3c116af1077906  
|   |-- f8  
│   │   |-- 9e64bdfcc08a8b371ee76a74775cfe096655ce  
|   |-- info  
|   |-- pack

.git/objects에 구성된 디렉토리 이름이 2문자 길이라는 것에 주목하여야 한다. Git은 모든 객체에 대해 40자 체크섬 (SHA-1) 해시를 생성하고 그 체크섬의 처음 두 문자를 디렉토리 이름으로 사용하고 다른 하나는 파일(object) 이름으로 사용합니다.

어떤 파일을 커밋 할 때 git이 생성하는 첫 번째 종류의 객체는 blob 객체이다. (생성 및 수정한 파일에 대한 객체)

+-----------------+          +-----------------+
|     5d92c1      |          |     cf59e0      |
+-----------------+          +-----------------+
| <?php echo      |          | # Description   |
| "Hello World";  |          |This is my hello |
|                 |          |world project    |
+-----------------+          +-----------------+
index.php 및 README.md 파일과 관련된 Blob 객체

여기는 파일의 스냅샷(커밋 당시의 파일 내용)과 체크섬 헤더가 있다.

tree objects

프로젝트에 있는 모든 파일의 목록을 포함하는 blob 객체에 대한 포인터가 들어가 있다. (git 이 파일을 blob 객체와 연관시키는 방법)

              +-----------------+
              |     f89e64      |
              +-----------------+
              |cf59e0  README.md|
              |5d92c1  index.php|
              +-----------------+
                     |    |
         +-----------+    +-----------+
         |                            |
         v                            v
+-----------------+          +-----------------+
|     5d92c1      |          |     cf59e0      |
+-----------------+          +-----------------+
| <?php echo      |          | # Description   |
| "Hello World";  |          |This is my hello |
|                 |          |world project    |
+-----------------+          +-----------------+
BLOB 객체를 가리키는 Tree 객체

자식 객체는 다른 정보와 함께 트리 객체에 대한 포인터를 가진 커밋 객체를 만든다:

              +-----------------+
              |     a6dbf0      |
              +-----------------+
              | tree     f89e64 |
              +-----------------+
                       |
                       v
              +-----------------+
              |     f89e64      |
              +-----------------+
              |cf59e0  README.md|
              |5d92c1  index.php|
              +-----------------+
                     |    |
         +-----------+    +-----------+
         |                            |
         v                            v
+-----------------+          +-----------------+
|     5d92c1      |          |     cf59e0      |
+-----------------+          +-----------------+
| <?php echo      |          | # Description   |
| "Hello World";  |          |This is my hello |
|                 |          |world project    |
+-----------------+          +-----------------+
객체 포인터가 트리 객체에 커밋 됨
  • .git/object 디렉토리는 아래와 같이 보일 것이다.
|-- objects  
|   |-- 5d  
│   │   |-- 92c127156d3d86b70ae41c73973434bf4bf341  
|   |-- a6  
│   │   |-- dbf05551541dc86b7a49212b62cfe1e9bb14f2  
|   |-- cf  
│   │   |-- 59e02c3d2a2413e2da9e535d3c116af1077906  
|   |-- f8  
│   │   |-- 9e64bdfcc08a8b371ee76a74775cfe096655ce  
|   |-- info  
|   |-- pack
  • git log를 사용하여 커밋 기록을 확인할 수 있다:
commit a6dbf05551541dc86b7a49212b62cfe1e9bb14f2   
Author: atom <[atom@gmail.com](mailto:atom@gmail.com)>  
Date:   Tue Jan 23 13:31:43 2018 +0100

Initial Commit
  • naming 규칙을 사용하면 .git/object에서 commit 객체를 찾을 수 있다:
|-- objects  
|   |-- a6  
│   │   |-- dbf05551541dc86b7a49212b62cfe1e9bb14f2
  • cat-file을 활용하여 파일을 보면:
git cat-file commit a6dbf05551541dc86b7a49212b62cfe1e9bb14f2
  • 커밋 객체의 내용을 가져오려면:
tree f89e64bdfcc08a8b371ee76a74775cfe096655ce  
author atom <[atom@gmail.com](mailto:atom@gmail.com)> 1516710703 +0100  
committer atom <[atom@gmail.com](mailto:atom@gmail.com)> 1516710703 +0100

Initial Commit
  • 여기에 커밋의 트리 객체에 대한 포인터가 있으며 git ls-tree 명령을 사용하여 내용을 검사:
git ls-tree f89e64bdfcc08a8b371ee76a74775cfe096655ce
  • 그리고 예상대로 그것은 blob 객체에 대한 포인터가있는 파일 목록을 포함:
100644 blob cf59e02c3d2a2413e2da9e535d3c116af1077906 README.md  
100644 blob 5d92c127156d3d86b70ae41c73973434bf4bf341 index.php
  • cat-file 명령을 사용하여 (예를 들어) index.php를 나타내는 blob 객체를 볼 수 있음:
git cat-file blob 5d92c127156d3d86b70ae41c73973434bf4bf341
  • index.php 파일의 내용이 포함 된 것을 볼 수 있다.
<?  
echo "Hello World!"

commit

              +-----------------+
              |     a6dbf0      |
              +-----------------+
              | tree     f89e64 |
              +-----------------+
                       |
                       v
              +-----------------+
              |     f89e64      |
              +-----------------+
              |cf59e0  README.md|
              |5d92c1  index.php|
              +-----------------+
                     |    |
         +-----------+    +-----------+
         |                            |
         v                            v
+-----------------+          +-----------------+          +-----------------+
|     5d92c1      |          |     cf59e0      |          |     6d725d      |
+-----------------+          +-----------------+          +-----------------+
| <?php echo      |          | # Description   |          | <?php echo      |
| "Hello World";  |          |This is my hello |          | "Hello World";  |
|                 |          |world project    |          |//some code magic|
+-----------------+          +-----------------+          +-----------------+
git은 변경된 파일에 대한 새 BLOB 개체를 생성

index.php의 새로운 스냅샷으로 신규 blob 객체를 만들었다. README.md는 변경되지 않았기 때문에, 새로운 blob 객체가 생성되지 않는다. git은 대신 기존의 객체를 재사용한다.

git이 트리 객체를 만들면index.php에 할당 된 blob 포인터가 업데이트되고 README.md에 할당 된 blob 포인터는 이전 커밋의 트리와 동일하게 유지된다.

              +-----------------+
              |     a6dbf0      |
              +-----------------+
              | tree     f89e64 |
              +-----------------+
                       |
                       v
              +-----------------+               +-----------------+
              |     f89e64      |               |     6f2109      |
              +-----------------+               +-----------------+
              |cf59e0  README.md|               |cf59e0  README.md|
              |5d92c1  index.php|               |6d725d  index.php|
              +-----------------+               +-----------------+
                     |    |                            |    |
         +-----------+    +-----------+    +-----------+    +-----------+
         |                            |    |                            |
         v                            v    v                            v
+-----------------+          +-----------------+          +-----------------+
|     5d92c1      |          |     cf59e0      |          |     6d725d      |
+-----------------+          +-----------------+          +-----------------+
| <?php echo      |          | # Description   |          | <?php echo      |
| "Hello World";  |          |This is my hello |          | "Hello World";  |
|                 |          |world project    |          |//some code magic|
+-----------------+          +-----------------+          +-----------------+
index.php BLOB에 대한 포인터가 업데이트되고 README.md BLOB에 대한 포인터는 그대로 유지

그리고 결국 git은 트리 객체에 대한 포인터를 가진 commit 객체를 생성한다.

              +-----------------+               +-----------------+
              |     a6dbf0      |               |     5ebdb4      |
              +-----------------+ <------------ +-----------------+
              | tree     f89e64 |               | tree     6f2109 |
              +-----------------+               | parent   a6dbf0 |
                       |                        +-----------------+
                       |                                 |
                       v                                 v
              +-----------------+               +-----------------+
              |     f89e64      |               |     6f2109      |
              +-----------------+               +-----------------+
              |cf59e0  README.md|               |cf59e0  README.md|
              |5d92c1  index.php|               |6d725d  index.php|
              +-----------------+               +-----------------+
                     |    |                            |    |
         +-----------+    +-----------+    +-----------+    +-----------+
         |                            |    |                            |
         v                            v    v                            v
+-----------------+          +-----------------+          +-----------------+
|     5d92c1      |          |     cf59e0      |          |     6d725d      |
+-----------------+          +-----------------+          +-----------------+
| <?php echo      |          | # Description   |          | <?php echo      |
| "Hello World";  |          |This is my hello |          | "Hello World";  |
|                 |          |world project    |          |//some code magic|
+-----------------+          +-----------------+          +-----------------+
Commit 객체는 트리를 가리키며 부모 커밋 객체에 대한 포인터를 가지고 있음

또한 부모 커밋 객체에 대한 포인터이다. (첫번째 커밋을 제외한 모든 커밋은 적어도 하나의 부모를 가진다).

file delete

              +-----------------+               +-----------------+
              |     5ebdb4      |               |     379cb3      |
              +-----------------+ <------------ +-----------------+
              | tree     6f2109 |               | tree     69d524 |
              | parent   a6dbf0 |               | parent   5ebdb4 |
              +-----------------+               +-----------------+
                       |                                 |
                       v                                 v
              +-----------------+               +-----------------+
              |     6f2109      |               |     69d524      |
              +-----------------+               +-----------------+
              |cf59e0  README.md|               |cf59e0  README.md|
              |6d725d  index.php|               |                 |
              +-----------------+               +-----------------+
                     |    |                            |
         +-----------+    +-----------+    +-----------+
         |                            |    |
         v                            v    v                            
+-----------------+          +-----------------+
|     5d92c1      |          |     cf59e0      |
+-----------------+          +-----------------+
| <?php echo      |          | # Description   |
| "Hello World";  |          |This is my hello |
|//some code magic|          |world project    |
+-----------------+          +-----------------+
자식은 트리 객체에서 index.php에 대한 엔트리를 삭제

git은 tree 객체에서 파일 항목 (BLOB 객체에 대한 포인터로 파일 이름)을 삭제한다. 이 경우 커밋에서index.php를 삭제 했으므로 더 이상 커밋의 트리 객체에index.php 엔트리가 없다. (즉, 커밋의 트리 객체에는 더 이상index.php를 나타내는 blob 객체에 대한 포인터가 없다.)

데이터 모델에는 트리 객체를 중첩 할 수 있는 추가 기능이 한 가지 더 있다. (다른 트리 개체를 가리킬 수 있음). 모든 BLOB 객체는 파일을 나타내고 모든 트리 객체는 디렉토리를 나타내므로 중첩 된 디렉토리가 있으면 중첩 된 트리 객체를 갖게된다.

  • 예제
           +-----------------+
           |      bf4513     |
           +-----------------+
           | tree     6f1183 |
           +-----------------+
                    |
                    v
           +-----------------+
           |      6f1183     |
           +-----------------+
           | cb31c9 README.md|
           | eabb42      app |
           +-----------------+
                   |  |
         +---------+  +-----------+
         |                        |
         v                        v
+----------------+     +-------------------+
|     cb31c9     |     |     eabb42        |
+----------------+     +-------------------+
| # Description  |     | cb31c9     app.php|
|example project |     | 0bdda9 app_dev.php|
+----------------+     +-------------------+
                               |  |
                +--------------+  +----------+
                |                            |
                v                            v
        +----------------+    +----------------------+
        |     cb31c9     |    |     0bdda9           |
        +----------------+    +----------------------+
        | <?php          |    | <?php                |
        |// our app      |    |// our app in dev env |
        +----------------+    +----------------------+
트리 객체는 다른 트리 객체를 가리킬 수 있다

하나의README.md 파일과 두 개의 파일을 가진 하나의 app 디렉토리를 가진다. (app.phpapp_dev.php)

Git은 blob 객체를 사용하여 주어진 시점 (커밋) 및 프로젝트의 폴더 구조를 재현 할 수있는 트리 객체에서 파일 내용을 재생성한다.


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

Specification: IPLD Paths

Status: Descriptive - Draft

Summary

IPLD “Path(경로)”는 IPLD 그래프에 대한 deep references에 사용되는 string 식별자이다. 경로는 URI 경로와 유사한 escape 및 segmentation rules을 따른다.

IPLD 경로는 IPLD 그래프에 대한 deep references에 사용되는 string 식별자이다.

IPLD 경로는 다음과 같은 제약 조건에 따라 생성된다. URI Paths.

비슷하게 문자열?는 나중에 쿼리 분리 자로 사용하기 위해 예약되어 있다.

Path Resolution

경로 분석은 전체 경로 분석과 블록 수준 분석의 두 부분으로 나뉜다.

블록 레벨 경로 분석은 개별 코덱에 의해 정의된다.

전체 경로 분석은 각 블록을 통해 블록 수준의 해상도를 사용해야한다. 블록 레벨 리졸버가 IPLD Link를 리턴 할 때, 전체 경로 해상도는 그 블록을 조사하고, 코덱을 로딩하고, 전체 경로가 해결 될 때까지 추가적인 블록 레벨 해결을 계속해야한다. 마지막으로 경로 결정은 주어진 경로에 대한 값의 representation을 반환해야 한다.


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

Graphsync

Status: Prescriptive - Draft

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

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

[Meta: Status of this doc]

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

Concepts and Glossary

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

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)
}

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
}

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.

Example Use Cases

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>

Downloading Package Dependencies

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

Loading content from deep within a giant dataset

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

Loading a large video optimizing for playback and seek

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

Looking up an entry in a sharded directory

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

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

Other notes

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


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

Specification: IPLD Selectors

이 문서는 IPLD Selector를 위한 document 이다. 또한 미완성이다.

Motivation - what are Selectors?

전제조건: IPLD, IPLD data model, CID.

IPLD Selectors는 IPLD dag에서 노드의 subset을 식별(“select”)하는 표현식이다.

이것은 다음과 함께 사용할 수있는 유용한 기본 요소이다: (a) DAG (IPFS, Filecoin, bitswap, graphsync, ipfs-cluster)를 분산하거나 고정해야하는 시스템, (b) 특정 주문 또는 특정 시간 (비디오 플레이어, 데이터 세트 뷰어, 파일 시스템)의 데이터 subsets 가져 오기가 필요한 응용 프로그램, (c) 그래프를 다른 그래프(데이터 변환, ETL 등)로 변환하는 프로그램

즉, IPL 및 IPFS 생태계에서 대부분의 시스템 및 응용 프로그램에서 필요로하는 근본적인 기본 요소이며 multihash, CIDs, IPLD Formats 등이 있다.

Prior Work

IPFS 및 IPLD 프로젝트의 역사에서 selector에 관해 많은 논의가 있었다. Selector에 대한 모든 종류의 유스 케이스를 나타내는 많은 문서가 존재한다.

Important Design Notes

Learn from the best. 지난 수십 년 동안 수십 개의 그래프 Selector 시스템이 구현되었다. 하지만 성공적이고 생산적이었던 소수만 남았다. unix globs, regular expressions, XPath, css selectors 등을 알아야한다.

Selectors include paths to the root. 대부분의 경우 IPLD Selector를 사용하여 프로그램은 인증된 데이터 구조를 검증 할 수 있어야 한다 (루트의 모든 노드를 경로에 해시해야한다). 따라서 분산되고 인증된 유스 케이스의 경우 검증 가능(루트 – 원래 쿼리와 대조하여 확인 가능)한 결과를 산출하는 Selector를 믿을 수 있다.

Self-describe and use multiple types. 지금까지 수많은 선행기술이 있었다. self-describe 와 업그레이드 가능성이 기능으로 필요하다는 것을 알고 있습니다. 다양한 유형의 selector가 있어야 하며 응용 프로그램은 자신의 필요에 맞는 유형을 사용해야 합니다. 다양한 유즈케이스를 볼 때 하나의 완벽한 구문을 가지는 것이 어렵다는 것을 알게된다. IPLD는 인증된 코드를 실행할 수 있는 기능을 가지고 있기 때문에 시간이 지남에 따라 쉽게 해결될 것이다.

Aim for succinct, intuitive, human-readable, expressive power. 가장 성공적인 selector 시스템 (unix globs, regular expressions, css selectors, etc.)은 매우 강력하고 간결한 표현을 작성하여 인간 친화적이고 매우 효율적이다. 이해하기 쉽고, 직관적이며, 표현할 수 있고, 친숙하며, 유사한 자질이 인간이 읽을 수있는 구문에서 바람직하다. Self-description과 유형을 사용하면 훨씬 쉽고 편리하게 구문을 발견 할 수 있고, 익숙한 기존 구문을 포팅 할 수 있어 시간이 지남에 따라 완전히 새로운 유형을 만들 수 있다.

Aim for succinct, efficient, self-describing binary representations. IPLD Selectors를 사용하는 다양한 시스템은 수많은 selector를 분산하고 store 할 수 있다. 표현의 간결함이 중요하다. Self-description 및 type을 사용하면 구문을 쉽게 작성할 수 있어 시간이 지남에 따라 완전히 새로운 유형을 만들 수 있다.

Blocks have CIDs. IPLD Nodes have Paths. 다음 두 문장을 맞추는 것은 매우 중요하다. (1) Block은 CID를 가지고 있다. (2) IPLD 노드에는 경로(path)가 있지만 CID는 없다. 이는 IPLD 노드가 블록 중간에서 시작될 수 있으며 CID에서 직접 주소 지정할 수 없기 때문에 중요하다. Selectors는 CID뿐 아니라 항상 DAG 루트로 경로를 지원해야 한다.

IPLD Selector System

Narrowing down the problem

IPLD Selectors 문제는 매우 구체적이고 간단한 문제로 좁혀있다:

  • 어떻게 루트에 연결된 dag subset을 같결하게 식별할 수 있는가?

이러한 다른 질문은 다른 시스템, IPLD Selectors 위 또는 아래에서 해결된다:

  • dag에서 임의의 데이터 구조 나 파일을 어떻게 표현할 수 있는가? (IPLD data model, user code)
  • dag subset을 간결하게 식별할 수 있는 방법이 있는가? 루트에 연결되지 않은 (IPLD Selector 맨 위에 있는 사용자 코드)
  • dag subset을 탐색할 수 있는가? (IPLD 라이브러리 구현, IPLD Selector 사용)
  • subset을 효율적으로 선택할 수 있는가? (IPLD 라이브러리 구현)
  • selector 조합을 효율적으로 만들 수 있는가? (IPLD 라이브러리 구현)
  • subset에 없는 객체에 대한 링크에서 dag subset을 제거하는 방안이 있는가? (IPLD 변환, 사용자 코드)
  • 하나의 dag 표현을 다른 표현으로 변환 할 수 있는 방안이 있는가? (IPLD 변환, 사용자 코드)
  • dag의 subset을 고정하거나 보내는 여러 다른 파트와 합의하는 방안이 있는가? (ipfs-cluster, graphsync)

문제의 범주가 줄어들면 문제를 해결하는 것에 집중할 수 있다.

Selector Requirements

  • P0-Selector는 유효한 dag subset (루트에 연결됨)을 표현할 수 있음
  • P0-Selector는 IPLD 경로를 기반으로 선택할 수 있음
  • P1-Selector는 값에 따라 선택할 수 있음
  • P2-Selector는 시드 된 의사 난수(pseudorandomness)를 선택하여 선택할 수 있음
  • P3-Selector는 형제 노드 (css3에서와 같이)와 그 자손 (css4에서와 같이)을 기반으로 선택할 수 있음
  • P1-Selector를 구성할 수 있음
  • P0-작성되면 Selector가 영구적으로 작동 (Selector 코드는 사용자에 따라 변경될 수 없음)
  • P1-Selector 언어는 시간이 지남에 따라 발전하고 향상될 수 있음 (다른 select 시스템보다 빠름)
  • P3-이전 버전과 호환되는 구문을 사용하지 않고 실허믈 허용 (globs 및 css와는 다름)
  • P0-사람이 읽을 수 있는 구문과 binary syntaxes 사이에 1:1 매핑
  • P0-binary syntax는 self-described, 간결하고, 효율적임
  • P0-인간이 읽을 수 있는 구문은 강력하고 표현력이 뛰어남
  • P1-인간이 읽을 수 있는 구문은 직관적이고 익숙함

Approach: Selector Types

시스템 핵심 요소를 세가지 구성요소로 축소하면 다음과 같다.

  • (1) selector type system으로, selector 언어와 구문을 새로 만들 수 있으며 이를 구성할 수 있음
  • (2) selector type을 IPLD 라이브러리 및 IPLD selector의 다른 소비자에 연결하기 위한 쉬운 경로
  • (3) 새로운 selector 유형을 테스트하고 표준 IPLD 라이브러리에 허용하기 위한 가벼운 프로세스

이러한 구성 요소는 다음과 같은 것을 의미한다:

  • 잘 정의된 바이너리 및 사람이 읽을 수 있는 유형의 self-description (multicodec의 코드)
  • selector 유형에 관계없이 selector 대부분을 사용하기 위한 Selector 인터페이스
  • IPLD 라이브러리에 selector type 유형 구현을 추가하는 방법
  • 추상적인 Selector 유형을 사용하는 IPLD 라이브러리로서 구체적인 유형을 연결할 수 있음
  • 가장 일반적인 사례 (cid, path, glob, …)를 처리하는 selector type
  • selector를 구성할 수 있는 selector type (MultiSelector)
  • selector 구현 (parsers, execution 등)에 대해 언어 독립적인 구현을 목표로 함
  • selector 의 언어별 구현을 허용 (parsers, execution 등)
  • IPLD selector의 다양한 유스 케이스를 나타내는 테스트 벡터의 잘 설계된 set
  • 사용하기 쉬운 테스트 스위트와 함께 selector type을 구현하는데 권장

Selector types

CID Selector

Selects 는 single CID 이다.

Path Selector

Selects 는 single path segment 이다.

Array Selector

항목 배열의 조각 또는 단일 항목을 선택한다.

Recursive Selector

다른 Selector를 사용하여 재귀적으로 항목을 선택한다. 또한 재귀가 얼마나 자주 발생해야 하는지에 대한 제한이 있다 (limit가 “infinity”로 설정되어 일치하는 경로가 남아 있지 않을 때까지 계속 이동).

재귀는 주어진 CID에 의해 중지 될 수도 있다.

CID Rooted Selector

CID Rooted Selector는 Root Selector CID와 순회를 지정하는 Selector 목록으로 구성된다.

Use cases

Deeply nested path

일부 DAG에서는 경로를 알고있는 특정값 하나를 얻고 싶은 경우가 있다. 특정 쇼의 특정 캐릭터의 탄생 연도를 원한다고 가정 해 봅시다.

CID cidabcdef 를 사용하는 예제 데이터 (JSON). 단순하게 유지하기 위해 단일 JSON 구조로 표시되지만 예를 들어 문자는 CID로 연결된다.

{
  "show": "start-trek-voyager",
  "characters": {
    "kathryn-janeway": {
      "birthday": {
        "day": 20,
        "month": 5,
        "year": 2328
      },
      "rank": "vice admiral"
    }
  }
}

최종 Selector는 다음과 같다.

{
  "cidRootedSelector": {
    "root": "cidabcdef",
    "selectors": [
      {"selectPath": "characters"},
      {"selectPath": "kathryn-janeway"},
      {"selectPath": "birthday"},
      {"selectPath": "year"}
    ]
  }
}

Getting a certain number of parent blocks in a blockchain

특정 블록에서 특정 수의 부모를 얻고 싶은 경우가 있다.

블록의 모양은 JSON에서 다음과 같이 보일 수 있다:

{
  "parent": "parentcid",
  "time": 1549641260,
  "none": 3423545
}

5명의 부모가 필요하다는 것을 알고 있다면 Path Selectors를 사용할 수 있다.

{
  "cidRootedSelector": {
    "root": "cidabcdef",
    "selectors": [
      {"selectPath": "parent"},
      {"selectPath": "parent"},
      {"selectPath": "parent"},
      {"selectPath": "parent"},
      {"selectPath": "parent"}
    ]
  }
}

그러나 제한적인 Recursive Selector를 사용하는 것이 더 좋다:

{
  "cidRootedSelector": {
    "root": "cidabcdef",
    "selectors": [
      {"selectRecursive": {
        "follow": [
          {"selectPath": "parent"}
        ],
        "depthLimit": 5
      }}
    ]
  }
}

Getting changes up to a certain one

이 유스케이스는 변경 사항 체인이있는 CRDT에서 영감을 얻었다. 새로운 변화를 관찰하고 이미 관찰 한 변화까지 모든 이전의 변화를 얻길 원한다. 중지 조건으로 CID가 있는 재귀 쿼리이다.

변경된 모양은 JSON에서 다음과 같이 보일 수 있다:

{
  "prev": "prevcid",
  "timestamp": 1549641260,
  "value": "abc"
}

그것은 긴 특정 필드 (이 경우 prev) 다음에 오는 재귀 선택자이다:

{
  "cidRootedSelector": {
    "root": "cidabcdef",
    "selectors": [
      {"selectRecursive": {
        "follow": [
          {"selectPath": "prev"}
        ],
        "cidLimit": "somecid"
      }}
    ]
  }
}

Getting a full sub-DAG

UnixFSv1에서 전체 파일을 얻으려면 전체 sub-DAG를 검색해야한다.

특정 CID를 기반으로하는 전체 sub-DAG를 가져 오는 example selector:

{
  "cidRootedSelector": {
    "root": "cidabcdef",
    "selectors": [
      {"selectRecursive": {
        "follow": [
          {"selectPath": "Links"},
          {"selectArrayAll": null},
          {"selectPath": "multihash"}
        ]
      }}
    ]
  }
}

그것이 어떤 디렉토리의 파일이라면, 더 깊은 레벨에서 시작할 수도 있다:

{
  "cidRootedSelector": {
    "root": "cidabcdef",
    "selectors": [
      {"selectPath": "with"},
      {"selectPath": "some"},
      {"selectPath": "subdirectory"},
      {"selectRecursive": {
        "follow": [
          {"selectPath": "Links"},
          {"selectArrayAll": null},
          {"selectPath": "multihash"}
        ]
      }}
    ]
  }
}

IPLD Schema

# This is the main entry point for the current selectors
type CidRootedSelector struct {
  root Cid
  # Each element matches a path segement (or several, in some cases)
  selectors [Selector]
}

# A catch all for all types of selectors. They are split between recursive and
# non-recursive ones as a recursive selector can't have another recursive
# selector embedded
type Selector union {
  | SelectPath "selectPath"
  | SelectArrayAll "selectArrayAll"
  | SelectArrayPosition "selectArrayPosition"
  | SelectArraySlice "selectArraySlice"
  | SelectMapAll "selectMapAll"
  | SelectRecursive "selectRecursive"
} representation keyed

# This is a subset of the selectors that can be used within a recursive selector
type SelectorNonRecursive union {
  | SelectPath "selectPath"
  | SelectArrayAll "selectArrayAll"
  | SelectArrayPosition "selectArrayPosition"
  | SelectArraySlice "selectArraySlice"
  | SelectMapAll "selectMapAll"
} representation keyed

# Paths are split into their individual segments
type PathSegment String

# Selects a specific path segment
type SelectPath PathSegment

# Selects all elements of an array, it's similar to a `/*`
type SelectArrayAll Null

# Selects a specific item from an array
type SelectArrayPosition Int

# Selects a slice of items out of an array
type SelectArraySlice struct {
  start optional Int
  end optional Int
}

# Selects all keys one level deep, it's similar to a `/*`
type SelectMapAll Null

# Follow a selector recursively
type SelectRecursive struct {
  # Can be used to follow a more complex path, e.g. for UnixFSv1
  follow [SelectorNonRecursive]
  # Stop recursing after a certain amount of iterations
  depthLimit optional Int
  # Stop recursing once a specific CID is visited
  cidLimit optional Cid
}

원문은 IPLD Github specs 에서 확인 가능하다. IPLD DAG-JSON

Specification: DAG-JSON

DAG-JSON은 전체 IPLD 데이터 모델을 지원한다.

Format

Simple Types

바이너리를 제외한 모든 간단한 유형은 기본적으로 JSON에서 지원된다.

JSON은 Big Integers를 지원한다. 즉, dag-json의 JS 구현은 기본 JSON 파서 및 직렬기를 사용할 수 없다는 것을 의미한다.

Binary Type

{"/": { "base64": String }}
{"/": String /* base encoded CID */}