원문은 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
}