네임스페이스

네임스페이스는 프로젝트와 관련 리소스의 컨테이너입니다. NamespaceGroup, ProjectNamespace, 그리고 UserNamespace의 서브클래스를 통해 인스턴스화됩니다.

graph TD Namespace -.- Group Namespace -.- ProjectNamespace Namespace -.- UserNamespace

User는 하나의 UserNamespace를 가지며, 여러 Namespaces의 멤버가 될 수 있습니다.

graph TD Namespace -.- Group Namespace -.- ProjectNamespace Namespace -.- UserNamespace User -- has one --- UserNamespace Namespace --- Member --- User

Group은 재귀적인 계층 관계에 있습니다. Groups는 많은 ProjectNamespaces를 가지며, 하나의 Project를 상위에 두고 있습니다.

graph TD Group -- has many --- ProjectNamespace -- has one --- Project Group -- has many --- Group

네임스페이스 조회

네임스페이스의 계층을 조회하기 위한 메서드가 제공됩니다. 이러한 메서드들은 일반적인 Rails ActiveRecord::Relation 객체를 생성합니다. 이러한 메서드들은 하나의 네임스페이스 개체에서 작동하는 메서드 집합과 계층 묶음 네임스페이스에 작동하는 메서드로 분리될 수 있습니다.

객체 메서드들은 본질적으로 하나의 Namespace 계층 내에서 작동할 것이며, 범위는 계층을 이을 수 있습니다.

다음은 Namespace 계층을 조회하기 위한 메서드 중 일부입니다.

루트 네임스페이스

루트는 계층에서 가장 높은 Namespace입니다. 루트는 nil parent_id를 가집니다.

graph TD classDef active fill:#f00,color:#fff classDef sel fill:#00f,color:#fff A --- A.A --- A.A.A A.A --- A.A.B A --- A.B --- A.B.A A.B --- A.B.B class A sel class A.A.B active
Namespace.where(...).roots

namespace_object.root_ancestor

자손 네임스페이스

네임스페이스의 자손은 해당 네임스페이스 자체와 그 자식들, 그 자식들의 자식들로 이어집니다.

graph TD classDef active fill:#f00,color:#fff classDef sel fill:#00f,color:#fff A --- A.A --- A.A.A A.A --- A.A.B A --- A.B --- A.B.A A.B --- A.B.B class A,A.A.A,A.A.B sel class A.A active

self_and_descendants를 통해 자신과 자손들을 반환할 수 있습니다.

Namespace.where(...).self_and_descendants

namespace_object.self_and_descendants

자신을 제외하고 자손들만 반환할 수 있습니다:

Namespace.where(...).self_and_descendants(include_self: false)

namespace_object.descendants

메서드 이름을 .descendants로 지정할 수 없었던 이유는 동일한 이름을 가진 Object 메서드와 충돌할 가능성이 있었기 때문입니다.

레코드 전체 대신 자손 ID를 반환하는 것이 더 효과적일 수 있습니다:

Namespace.where(...).self_and_descendant_ids
Namespace.where(...).self_and_descendant_ids(include_self: false)

namespace_object.self_and_descendant_ids
namespace_object.descendant_ids

조상 네임스페이스

네임스페이스의 조상은 해당 네임스페이스의 부모, 부모의 부모 등을 포함합니다.

graph TD classDef active fill:#f00,color:#fff classDef sel fill:#00f,color:#fff A --- A.A --- A.A.A A.A --- A.A.B A --- A.B --- A.B.A A.B --- A.B.B class A sel class A.A,A.A.A active

self_and_ancestors를 통해 자신과 조상들을 반환할 수 있습니다.

Namespace.where(...).self_and_ancestors

namespace_object.self_and_ancestors

자신을 제외하고 조상들만 반환할 수 있습니다:

Namespace.where(...).self_and_ancestors(include_self: false)

namespace_object.ancestors

메서드 이름을 .ancestors로 지정할 수 없었던 이유는 동일한 이름을 가진 Module의 메서드와 충돌할 가능성이 있었기 때문입니다.

레코드 전체 대신 조상 ID를 반환하는 것이 더 효과적일 수 있습니다:

Namespace.where(...).self_and_ancestor_ids
Namespace.where(...).self_and_ancestor_ids(include_self: false)

namespace_object.self_and_ancestor_ids
namespace_object.ancestor_ids

계층

네임스페이스 계층은 Namespace와 해당 계층의 조상과 자손을 의미합니다.

graph TD classDef active fill:#f00,color:#fff classDef sel fill:#00f,color:#fff A --- A.A --- A.A.A A.A --- A.A.B A --- A.B --- A.B.A A.B --- A.B.B class A,A.A.A,A sel class A.A active

네임스페이스 계층을 조회할 수 있습니다:

Namespace.where(...).self_and_hierarchy

namespace_object.self_and_hierarchy

재귀적 조회

위의 쿼리들은 표준 SQL 쿼리를 수행하기 위해 namespaces.traversal_ids 열을 사용하는 선형 쿼리라고 알려져 있습니다. 반면에, 재귀 CTE 쿼리 대신 더 효과적인 레거시 재귀 쿼리 또한 필요할 때 접근할 수 있습니다:

Namespace.where(...).recursive_self_and_descendants
Namespace.where(...).recursive_self_and_descendants(include_self: false)
Namespace.where(...).recursive_self_and_descendant_ids
Namespace.where(...).recursive_self_and_descendant_ids(include_self: false)
Namespace.where(...).recursive_self_and_ancestors
Namespace.where(...).recursive_self_and_ancestors(include_self: false)
Namespace.where(...).recursive_self_and_ancestor_ids
Namespace.where(...).recursive_self_and_ancestor_ids(include_self: false)
Namespace.where(...).recursive_self_and_hierarchy

namespace_object.recursive_root_ancestor
namespace_object.recursive_self_and_descendants
namespace_object.recursive_descendants
namespace_object.recursive_self_and_descendant_ids
namespace_object.recursive_descendant_ids
namespace_object.recursive_self_and_ancestors
namespace_object.recursive_ancestors
namespace_object.recursive_self_and_ancestor_ids
namespace_object.recursive_ancestor_ids
namespace_object.recursive_self_and_hierarchy

트라이 데이터 구조를 사용한 검색

Namespaces::Traversal::TrieNodenamespaces.traveral_ids 계층 내에서 효율적으로 검색하기 위한 트라이 데이터 구조를 구현합니다.

traversal_ids = Namespace.where(...).map(&:traversal_ids)

# contains [9970, 123] and [9970, 456]
trie = Namespaces::Traversal::TrieNode.build(traversal_ids)

trie.prefix_search([9970]) # [[9970, 123], [9970, 456]] 반환

trie.covered?([9970]) # false 반환
trie.covered?([9970, 123]) # true 반환
trie.covered?([9970, 123, 789]) # true 반환

Namespace Query Implementation

namespaces.traversal_ids 배열 열을 사용하여 선형 쿼리를 실행합니다. 각 배열은 루트 Namespace에서 현재 Namespace까지의 정렬된 Namespace ID 세트를 나타냅니다.

시나리오가 주어진 경우:

graph TD classDef active fill:#f00,color:#fff classDef sel fill:#00f,color:#fff A --- A.A --- A.A.A A.A --- A.A.B A --- A.B --- A.B.A A.B --- A.B.B class A.A.B active

Namespace A.A.Btraversal_ids[A, A.A, A.A.B]가 됩니다.

traversal_ids에는이 영역에서 작업하는 경우 주의해야하는 몇 가지 유용한 속성이 있습니다.

  • 모든 Namespace의 루트는 traversal_ids[1]로 제공됩니다. PostgreSQL 배열 인덱스는 1에서 시작한다는 점에 유의하십시오.
  • 현재 Namespace의 ID는 traversal_ids[array_length(traversal_ids, 1)]로 제공됩니다.
  • Namespace 조상은 traversal_ids에 의해 나타납니다.
  • Namespacetraversal_ids는 자손의 traversal_ids의 하위 집합입니다. traversal_ids = [1,2,3]Namespace의 자손은 모두 [1,2,3,...]으로 시작합니다.
  • PostgreSQL 배열은 [1] < [1,1] < [2]와 같이 정렬됩니다.

이러한 속성을 사용하여 rootancestors가 이미 traversal_ids에 의해 제공되는 것을 찾을 수 있습니다.

객체 자손 쿼리에서는 배열 연산자 @>를 활용하는데, 이는 배열 내부의 배열 포함 여부를 테스트합니다. 검색 공간이 커질수록 @> 연산자는 다소 느리다는 것이 밝혀졌습니다. 검색 공간이 큰 범위 쿼리에는 다른 방법이 사용됩니다. 범위 쿼리에서는 배열 정렬 속성과 비교 연산자를 결합하여 사용합니다.

traversal_ids = [1,2,3]Namespace의 모든 자손은 [1,2,3]보다 크고 [1,2,4]보다 작습니다. 이 예에서 [1,2,3][1,2,4]는 형제이며, [1,2,4][1,2,3] 다음 형제입니다. next_traversal_ids_sibling이라는 SQL 함수가 traversal_ids의 다음 형제를 찾는 데 제공됩니다.

gitlabhq_development=# select next_traversal_ids_sibling(ARRAY[1,2,3]);
 next_traversal_ids_sibling
----------------------------
 {1,2,4}
(1 row)

그런 다음 비교 연산자를 사용하여 자손 선형 쿼리 범위를 구축합니다.

WHERE namespaces.traversal_ids > ARRAY[1,2,3]
  AND namespaces.traversal_ids < next_traversal_ids_sibling(ARRAY[1,2,3])

Superset

Namespace 쿼리는 중복된 결과를 반환하기 쉽습니다. 예를 들어 AA.A의 자손을 찾는 쿼리를 고려해보십시오.

graph TD classDef active fill:#f00,color:#fff classDef sel fill:#00f,color:#fff A --- A.A --- A.A.A A.A --- A.A.B A --- A.B --- A.B.A A.B --- A.B.B class A,A.A active class A.A.A,A.A.B,A.B,A.B.A,A.B.B sel
namespaces = Namespace.where(name: ['A', 'A.A'])

namespaces.self_and_descendants

=> A.A, A.A.A, A.A.B, A.B, A.B.A, A.B.B

AA.A의 자손을 모두 찾는 것은 불필요합니다. 왜냐하면 A.A는 이미 A의 자손이기 때문입니다. 극단적인 경우 이는 성능이 저하되는 과도한 I/O를 초래할 수 있습니다.

중복된 Namespacestraversal_ids 속성의 ID가 질의 중인 Namespaces 집합에 속하는 다른 NamespaceID와 일치하면 쿼리에서 제거됩니다. 이 조건의 일치는 질의 중인 Namespaces 집합에 조상이 존재하며 따라서 현재 Namespace가 중복되었음을 나타냅니다. 이 최적화는 그렇지 않으면 매우 느릴 수있는 극단적인 경우의 성능을 훨씬 더 향상시킵니다.