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

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

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

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

User -- has one --- UserNamespace Namespace --- Member --- User

Group은 재귀적인 계층 관계로 존재합니다. Group은 하나의 Project를 부모로 갖는 다수의 ProjectNamespace를 가집니다.

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

네임스페이스 쿼리#

네임스페이스 계층을 쿼리하기 위한 메서드 집합이 제공됩니다. 이 메서드들은 표준 Rails ActiveRecord::Relation 객체를 생성합니다. 메서드는 유사한 두 가지 그룹으로 나눌 수 있습니다. 한 그룹은 Namespace 객체에서 동작하고, 다른 그룹은 조합 가능한 Namespace 스코프로 동작합니다.

특성상 객체 메서드는 단일 Namespace 계층 내에서 동작하는 반면, 스코프는 여러 계층에 걸쳐 동작할 수 있습니다.

다음은 Namespace 계층을 쿼리하는 메서드의 비완전 목록입니다.

루트 네임스페이스#

루트는 계층에서 최상위 Namespace입니다. 루트는 nil 값의 parent_id를 가집니다.

%%{init: { "fontFamily": "GitLab Sans" }}%% graph TD accTitle: Root namespaces accDescr: Diagram showing a namespace hierarchy, starting with the root namespace at the top

classDef active stroke-width:3px classDef sel stroke-width:2px

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 class A sel

Namespace.where(...).roots

namespace_object.root_ancestor

하위 네임스페이스#

네임스페이스의 하위 항목은 자식, 자식의 자식 등으로 이어집니다.

%%{init: { "fontFamily": "GitLab Sans" }}%% graph TD accTitle: Descendent namespaces accDescr: Diagram showing namespace descendants, including children namespaces and their children namespaces

classDef active stroke-width:3px classDef sel stroke-width:2px

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 active class A.A.A,A.A.B sel

self_and_descendants를 통해 자신과 하위 항목을 반환할 수 있습니다.

Namespace.where(...).self_and_descendants

namespace_object.self_and_descendants

자신을 제외한 하위 항목만 반환할 수 있습니다:

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

namespace_object.descendants

같은 이름의 Object 메서드를 재정의하게 되므로 스코프 메서드에 .descendants라는 이름을 사용할 수 없었습니다.

전체 레코드 대신 하위 항목 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

상위 네임스페이스#

네임스페이스의 상위 항목은 부모, 부모의 부모 등으로 이어집니다.

%%{init: { "fontFamily": "GitLab Sans" }}%% graph TD accTitle: Ancestor namespaces accDescr: Diagram showing ancestors of a namespace, including its parent, its parent's parent, and so on

classDef active stroke-width:3px classDef sel stroke-width:2px

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 active class A sel

self_and_ancestors를 통해 자신과 상위 항목을 반환할 수 있습니다.

Namespace.where(...).self_and_ancestors

namespace_object.self_and_ancestors

자신을 제외한 상위 항목만 반환할 수 있습니다:

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

namespace_object.ancestors

같은 이름의 Module 메서드를 재정의하게 되므로 스코프 메서드에 .ancestors라는 이름을 사용할 수 없었습니다.

전체 레코드 대신 상위 항목 ID만 반환하는 것이 더 효율적일 수 있습니다:

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

namespace_object.self_and_ancestor_ids
namespace_object.ancestor_ids

계층#

Namespace 계층은 하나의 Namespace와 그 상위 항목 및 하위 항목으로 구성됩니다.

%%{init: { "fontFamily": "GitLab Sans" }}%% graph TD accTitle: Hierarchies accDescr: Diagram showing the namespace hierarchy, including the namespace, its ancestors, and its descendants

classDef active stroke-width:3px classDef sel stroke-width:2px

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 active class A,A.A.A,A.A.B sel

네임스페이스 계층을 쿼리할 수 있습니다:

Namespace.where(...).self_and_hierarchy

namespace_object.self_and_hierarchy

재귀 쿼리#

위의 쿼리들은 재귀 CTE 쿼리 대신 namespaces.traversal_ids 칼럼을 사용하여 표준 SQL 쿼리를 수행하기 때문에 선형 쿼리로 알려져 있습니다.

필요한 경우 레거시 재귀 쿼리 집합도 사용할 수 있습니다:

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_ancstor_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::TrieNode는 Namespace 집합에 대한 namespaces.traversal_ids 계층 내에서 효율적으로 검색하기 위한 트라이(trie) 자료구조를 구현합니다.

traversal_ids = [[9970, 123], [9970, 456]] # 예시: Namespace.where(...).map(&:traversal_ids)에서 도출

trie = Namespaces::Traversal::TrieNode.build(traversal_ids)

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

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

네임스페이스 쿼리 구현#

선형 쿼리는 namespaces.traversal_ids 배열 칼럼을 사용하여 실행됩니다. 각 배열은 루트 Namespace부터 현재 Namespace까지 순서대로 정렬된 Namespace ID 집합을 나타냅니다.

다음 시나리오를 가정합니다:

%%{init: { "fontFamily": "GitLab Sans" }}%% graph TD accTitle: Namespace query implementation accDescr: Diagram showing how linear queries are executed using the namespaces traversal ids array column

classDef active stroke-width:3px classDef sel stroke-width:2px

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.B의 traversal_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로 표현됩니다.

• Namespace의 traversal_ids는 하위 항목의 traversal_ids의 부분 집합입니다. traversal_ids = [1,2,3]인 Namespace는 모두 [1,2,3,...]으로 시작하는 traversal_ids를 가진 하위 항목을 갖습니다.

• PostgreSQL 배열은 [1] < [1,1] < [2]와 같이 정렬됩니다.

이 속성들을 활용하면 root와 ancestors는 이미 traversal_ids에 의해 제공된다는 것을 알 수 있습니다.

객체 하위 항목 쿼리에서는 배열 내부에 다른 배열이 포함되어 있는지 테스트하는 @> 배열 연산자를 활용합니다. @> 연산자는 검색 공간이 커질수록 상당히 느려지는 것으로 확인되었습니다. 더 큰 검색 공간을 갖는 스코프 쿼리에는 다른 방법이 사용됩니다. 스코프 쿼리에서는 비교 연산자와 배열 정렬 속성을 조합합니다.

traversal_ids = [1,2,3]인 Namespace의 모든 하위 항목은 [1,2,3]보다 크고 [1,2,4]보다 작은 traversal_ids를 가집니다. 이 예시에서 [1,2,3]과 [1,2,4]는 형제 관계이며, [1,2,4]는 [1,2,3] 다음 형제입니다. traversal_ids의 다음 형제를 찾기 위해 next_traversal_ids_sibling이라는 SQL 함수가 제공됩니다.

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

슈퍼셋#

Namespace 쿼리는 중복 결과를 반환하는 경향이 있습니다. 예를 들어, A와 A.A의 하위 항목을 찾는 쿼리를 생각해 보겠습니다:

%%{init: { "fontFamily": "GitLab Sans" }}%% graph TD accTitle: Superset accDescr: Diagram showing how namespace queries can return duplicate results

classDef active stroke-width:3px classDef sel stroke-width:2px

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

A.A는 이미 A의 하위 항목이므로 A와 A.A 모두의 하위 항목을 검색할 필요가 없습니다. 극단적인 경우 이로 인해 과도한 I/O가 발생하여 성능이 저하될 수 있습니다.

traversal_ids 속성의 Namespace ID가 쿼리되는 Namespace 집합의 다른 Namespace에 속하는 ID와 일치하면 해당 Namespace는 쿼리에서 중복으로 제거됩니다. 이 조건이 일치하면 쿼리되는 Namespace 집합에 상위 항목이 존재한다는 것을 의미하며, 현재 Namespace는 따라서 중복입니다. 이 최적화는 그렇지 않으면 매우 느릴 수 있는 엣지 케이스의 성능을 크게 향상시킵니다.

네임스페이스 잠금#

네임스페이스 계층을 수정할 때(그룹 생성 또는 parent_id/traversal_ids 업데이트), GitLab은 데이터 무결성을 유지하기 위해 데이터베이스 잠금을 사용합니다.

GitLab은 상위 항목에 공유 잠금을, 수정된 노드에 독점 잠금을 사용하는 경량 잠금 시스템을 사용하여 동시 작업 중 잠금 경합을 줄입니다.

네임스페이스 생성 시:

• 상위 항목은 FOR SHARE(공유 잠금)로 잠깁니다

• 새 네임스페이스는 FOR NO KEY UPDATE(독점 잠금)로 잠깁니다

• Namespace::TraversalHierarchy.sync_traversal_ids!(node)를 사용하여 노드와 그 하위 항목만 업데이트됩니다

네임스페이스 업데이트 시(부모 변경):

• 기존 및 새 루트 상위 항목 모두 FOR NO KEY UPDATE로 잠깁니다

• Namespace::TraversalHierarchy.for_namespace(node).sync_traversal_ids!를 사용하여 루트에서부터 전체 계층이 업데이트됩니다

이점:

• 동일한 부모 아래의 동시 그룹 생성이 더 이상 직렬화되지 않습니다

• 데이터베이스 잠금 경합 감소

• 높은 동시성 시나리오에서의 성능 향상

구현:

잠금 로직은 Namespace::TraversalHierarchy.acquire_locks에 있으며, 다음을 수행합니다:

• 상위 항목에 공유 잠금 획득(노드에 부모가 있는 경우)

• 노드 자체에 독점 잠금 획득

• 무한 차단을 방지하기 위해 1000ms의 LOCK_TIMEOUT 사용