GIT - Distributed GIT
distributed git
1. workflow in distributed environment
git은 매우 유연한 구조의 분산형 버전관리 시스템이다. 즉, git에서는 각 개발자의 저장소가 하나의 노드 (= 분산형) 또는 중앙집중형일 수 있다.
모든 개발자는 다른 개발자의 저장소에 작업 내용을 전송하거나, 다른 개발자들이 참여할 수 있도록 자신이 운영하는 저장소 위치를 공개할 수 있다. 이러한 특징은 프로젝트나 팀이 코드를 운영할 때 다양한 워크플로를 만들 수 있도록 해준다.
git은 매우 유연함을 가지고 있기 때문에 저장소를 운영하는 측면에서 다양한 방식을 가질 수 있다. 이는 운영자가 상황에 따라 잘 조합하여야 원하는 저장소를 만들 수 있다는 것을 의미한다.
1.1 중앙집중식 워크플로
중앙집중식 협업 모델은 한 가지밖에 없다. 중앙저장소는 딱 하나 있고 변경 사항은 모두 이 중앙저장소에 집중된다. 개발자는 이 중앙저장소를 중심으로 작업한다.
+---------------------------+
| shared repository |
+---------------------------+
^ ^ ^
| | |
+------+ + +------+
| | |
V V V
+-----------+ +-----------+ +-----------+
| developer | | developer | | developer |
+-----------+ +-----------+ +-----------+
중앙집중식 모델에서 개발자 두명이 중앙저장소를 Clone 하고 각자 수정을 한다고 가정하는 것을 예로들어 보자. A 개발자가 자신이 한 작업을 commit 하고, 서버에 push 한다. 다른 개발자 B 는 자신의 작업을 commit, push 하기전에 A 개발자가 한 일을 marge 해야 한다. A 개발자가 먼저 commit, push 한 내용을 덮어쓰지 않기 위함이다. 이러한 방식은 subversion 으로 대표되는 중앙집중식 버전 관리 시스템에서 자연스럽게 이용되는 방식이다.
소규모 프로젝트이거나 중앙집중화 방식에 완전히 적응한 상황이라면 중앙집중식 워크플로에 따라 git을 도입하여 사용할 수 있다. 중앙저장소를 하나 만들고 개발자 모두에게 push 권한을 주는 것이다. git은 한 개발자가 다른 개발자의 작업 내용을 덮어쓰도록 허용하지 않는다. 개발자 A, 개발자 B 가 동시에 같은 부분을 수정된다고 예를 들어보자. A 가 먼저 작업을 끝내고 수정한 내용을 서버로 push 한다. 동시에 B 도 작업을 끝내고 수정한 내용을 서버로 push 하려 하지만 서버는 이를 받지 않는다. 서버에는 A 가 수정한 내용이 추가되었기 때문에 push 하기 전에 fetch 로 받아서 merge 한 후 push 할 수 있다. 이는 개발자에게 이미 익숙한 개념이다.
소규모에서만 할 수 있는 것이 아니라 git이 제공하는 브렌치 관리 모델을 사용하면 대규모 프로젝트에서도 사용 가능하다.
1.2 Integration-Manager 워크플로
git에서는 리모트 저장소를 여러개 운영할 수 있다. 다른 개발자는 읽기만 가능하고 자신은 쓰기도 가능한 공개 저장소를 만드는 워크플로를 만들 수 있다. 이 워크플로에는 보통 프로젝트를 대표하는 공식저장소가 있다. 기여자는 우선 공식저장소를 하나 clone 하고 수정(자신의 작업)하고 자신의 저장소에 push 한다. 그 다음에 프로젝트 Integration-Manager 에게 새 저장소에서 pull 하라고 요청한다. 그러면 Integration-Manager 는 기여자의 저장소를 리모트 저장소로 등록하고, 로컬에서 기여물을 테스트하고, 프로젝트 메인 브렌치에 merge 하고, 그 내용을 다시 프로젝트 메인 저장소에 push 한다. 이런 과정은 아래와 같다.
- 프로젝트 Integration-Manager는 프로젝트 메인 저장소에 push 한다.
- 프로젝트 기여자는 메인 저장소를 clone 하고 수정한다.
- 기여자는 자신의 저장소에 push 하고 Integration-Manager 가 접근할 수 있도록 공개한다.
- 기여자는 Integration-Manager 에게 변경사항을 적용해 줄 것을 메일로 요청한다.
- Integration-Manager 는 기여자의 저장소를 리모트 저장소로 등록하고 수정사항을 merge 하여 테스트한다.
- Integration-Manager 는 merge 한 사항을 메인 저장소에 push 한다.
+-----------+ +---------+ +---------+
| blessed | |developer| |developer|
|repository | ----+ | public | +---- | public |
+-----------+ | +---------+ | +---------+
^ \ | | ^ | ^
| \ +------|-----|------|-------+ |
| +----\-----------+ | | | |
| | +-----------+ | | | |
| | +------|----|------+ | |
| V | V | V |
+-----------+ <----+ +---------+ +---------+
|integration| |developer| |developer|
| manager | | private | | private |
+-----------+ +---------+ +---------+
이 방식은 github 나 gitlab 같은 사이트를 통해 주로 사용하는 방식으로 프로젝트를 fork 하고 수정사항을 반영하여 다시 모두에게 공개하기 좋은 구조로 되어있다. 이 방식의 장점은 기여자와 Integration-Manager가 각자의 사정에 맞춰 프로젝트를 유지할 수 있다는 점이다. 기여자는 자신의 저장소와 브랜치에서 수정 작업을 계속해 나갈 수 있고 수정사항이 프로젝트에 반영되도록 기다릴 필요가 없다. 관리자는 여유를 가지고 기여자가 push 한 commit 을 적절한 시점에 merge 한다.
1.3 Dictator and Lieutenants 워크플로
저장소를 여러개 운영하는 방식을 변형한 구조이다. 수백 명의 개발자가 참여하는 아주 큰 프로젝트를 운영할 때 사용하는 방식으로 Linux 커널 프로젝트가 대표적이다. 여러 명의 Integration-Manager가 저장소에서 자신이 맡은 부분만을 담당하는데 이들을 Lieutenants 라고 한다. 모든 Lieutenant는 최종 관리자 아래에 있으며 이 최종 관리자를 Benevolent Dictator 라고 부른다. Benevolent Dictator는 Lieutenant의 저장소를 가져와 공식 저장소에 push 하고 모든 프로젝트 참여자는 이 공식 저장소에서 반드시 pull 해야 한다. 이러한 워크플로는 아래와 같다.
- 개발자는 코드를 수정하고
master브랜치를 기준으로 자신의 토픽 브랜치를 rebase 한다. 여기서master브랜치란 공식 저장소의 브랜치를 말한다. - Lieutenant들은 개발자들의 수정사항을 자신이 관리하는
master브랜치에 merge 한다. - Dictator는 Lieutenant의
master브랜치를 자신의master브랜치로 merge 한다. - Dictator는 자신의
master브랜치를 push 하며 다른 모든 개발자는 Dictator의master브랜치를 기준으로 rebase 한다.
+----------+ ------------------------------> +-----------+
| dictator | +------------------------- |blessed |
+----------+ | +------------ | repository|
^ ^ | | +-----------+
| | | | | | |
| +--------|------+ | +--------+ | |
| | | V | | |
+----------+ <----+ +----------+ | | |
|lieutenant| |lieutenant| <----|-----+ | |
+----------+ +----------+ | | | |
^ ^ +---------------------+ | | |
| | | +--------------|----+ |
| +--------|-----+ | | |
| | | V | V
+----------+ <----+ +----------+ +----------+
|developer | |developer | |developer |
| public | | public | | public |
+----------+ +----------+ +----------+
일반적이지 않지만 깊은 계층 구조를 가지는 환경이나 규모가 큰 프로젝트에서는 매우 쓸모 있다. 프로젝트 리더가 모든 코드를 통합하기 전에 코드를 부분부분 통합하도록 여러 명의 Lieutenant에게 위임한다.
GIT - Data Model
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을 알아보자.
1. 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 객체
여기는 파일의 스냅샷(커밋 당시의 파일 내용)과 체크섬 헤더가 있다.
2. 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!"
3. 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 객체는 트리를 가리키며 부모 커밋 객체에 대한 포인터를 가지고 있음
또한 부모 커밋 객체에 대한 포인터이다. (첫번째 커밋을 제외한 모든 커밋은 적어도 하나의 부모를 가진다).
4. 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.php 와 app_dev.php)
Git은 blob 객체를 사용하여 주어진 시점 (커밋) 및 프로젝트의 폴더 구조를 재현 할 수있는 트리 객체에서 파일 내용을 재생성한다.
IPLD - Specification: IPLD Paths
원문은 IPLD Github specs 에서 확인 가능하다. IPLD Paths
Specification: IPLD Paths
Status: Descriptive - Draft
1. Summary
IPLD “Path(경로)”는 IPLD 그래프에 대한 deep references에 사용되는 string 식별자이다. 경로는 URI 경로와 유사한 escape 및 segmentation rules을 따른다.
IPLD 경로는 IPLD 그래프에 대한 deep references에 사용되는 string 식별자이다.
IPLD 경로는 다음과 같은 제약 조건에 따라 생성된다. URI Paths.
비슷하게 문자열?는 나중에 쿼리 분리 자로 사용하기 위해 예약되어 있다.
2. Path Resolution
경로 분석은 전체 경로 분석과 블록 수준 분석의 두 부분으로 나뉜다.
블록 레벨 경로 분석은 개별 코덱에 의해 정의된다.
전체 경로 분석은 각 블록을 통해 블록 수준의 해상도를 사용해야한다. 블록 레벨 리졸버가 IPLD Link를 리턴 할 때, 전체 경로 해상도는 그 블록을 조사하고, 코덱을 로딩하고, 전체 경로가 해결 될 때까지 추가적인 블록 레벨 해결을 계속해야한다. 마지막으로 경로 결정은 주어진 경로에 대한 값의 representation 을 반환해야 한다.
IPLD - Graphsync
원문은 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 – 요청은 마이크로 초만큼 짧거나 무한정 지속될 수 있음
- 명시적으로
- (1)
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등을Ndepth까지 부여<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>”
- 이 외에도 “Give me some range of (the above query) is very important”. 예를들면: “Give me the second 1/3 of the nodes that are children of
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 벡터를 열게 될 것이다.
IPLD - Specification: IPLD Selectors
원문은 IPLD Github specs 에서 확인 가능하다. IPLD Selectors
Specification: IPLD Selectors
이 문서는 IPLD Selector를 위한 document 이다. 또한 미완성이다.
1. 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 등이 있다.
2. Prior Work
IPFS 및 IPLD 프로젝트의 역사에서 selector에 관해 많은 논의가 있었다. Selector에 대한 모든 종류의 유스 케이스를 나타내는 많은 문서가 존재한다.
- Designing IPLD Selectors (2017)
- IPLD Selector Thoughts (2017)
- exprimental js-ipld-selector (2017)
- Designing IPLD Selectors - Workshop (2016) (+ notes)
- IPLD Selector (original issue) (2015)
2.1 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 루트로 경로를 지원해야 한다.
3. IPLD Selector System
3.1 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)
문제의 범주가 줄어들면 문제를 해결하는 것에 집중할 수 있다.
3.2 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-인간이 읽을 수 있는 구문은 직관적이고 익숙함
3. 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을 구현하는데 권장
4. Selector types
4.1 CID Selector
Selects 는 single CID 이다.
4.2 Path Selector
Selects 는 single path segment 이다.
4.3 Array Selector
항목 배열의 조각 또는 단일 항목을 선택한다.
4.4 Recursive Selector
다른 Selector를 사용하여 재귀적으로 항목을 선택한다. 또한 재귀가 얼마나 자주 발생해야 하는지에 대한 제한이 있다 (limit가 “infinity”로 설정되어 일치하는 경로가 남아 있지 않을 때까지 계속 이동).
재귀는 주어진 CID에 의해 중지 될 수도 있다.
4.5 CID Rooted Selector
CID Rooted Selector는 Root Selector CID와 순회를 지정하는 Selector 목록으로 구성된다.
5. Use cases
5.1 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"}
]
}
}
5.2 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
}}
]
}
}
5.3 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"
}}
]
}
}
5.4 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"}
]
}}
]
}
}
6. 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
}
