• 문제 설명
• 알고리즘

트리 계층 구조에서의 일괄 반복 (콘셉트 증명)

GitLab의 그룹 계층 구조는 루트 요소가 최상위 네임스페이스이고 하위 요소는 서브그룹 또는 최근에 도입된 Namespaces::ProjectNamespace 레코드인 트리로 표현됩니다.

이 트리는 namespaces 테이블에서 parent_id 열을 통해 구현됩니다. 이 열은 부모 네임스페이스 레코드를 가리킵니다. 최상위 네임스페이스는 parent_id가 없습니다.

gitlab-org의 부분적인 계층 구조:

그룹 계층 구조를 효율적으로 반복하는 것에는 여러 가지 잠재적인 사용 사례가 있습니다. 특히 안정적이고 안전한 실행이 빠른 런타임보다 중요한 백그라운드 작업에서 이것이 참되어집니다. 일괄 반복은 네트워크 왕복이 더 필요하지만 각 일괄은 유사한 성능 특성을 제공합니다.

일부 예시:

• 각 서브그룹에 대해 다른 작업 수행
• 계층 구조의 각 프로젝트에 대해 다른 작업 수행
• 계층 구조의 각 이슈에 대해 다른 작업 수행

문제 설명

그룹 계층은 너무 커져서 단일 쿼리로 시간 내에 로드할 수 없게 될 수 있습니다. 쿼리는 제한 시간 초과 오류로 실패할 수 있습니다.

매우 큰 그룹과 관련된 확장성 문제에 대한 대응은 동일한 데이터를 다른 형식으로 (비 정규화) 저장해야 한다는 것을 의미합니다. 그러나 그룹 계층을 로드할 수 없다면 비 정규화를 구현할 수 없을 것입니다.

비 정규화 기술 중 하나는 주어진 그룹의 모든 하위 그룹 ID를 저장하는 것입니다. 이렇게 하면 그룹과 그 하위 그룹을 로드해야 하는 쿼리를 가속화할 수 있습니다. 예시:

이러한 구조를 사용하면 데이터베이스에서 한 행만 읽으면 모든 하위 그룹을 결정할 수 있습니다. 1000개의 그룹 정도로 커다란 계층의 경우 이것은 큰 차이를 만들 수 있습니다.

계층 문제의 읽기는 이러한 비 정규화로 해결됩니다. 그러나 여전히 이러한 데이터를 테이블에 지속적으로 저장해야 하는 방법을 찾아야 합니다. 그룹과 해당 계층은 매우 커질 수 있으므로 여기서는 단일 쿼리를 기대할 수 없습니다.

SELECT id FROM namespaces WHERE traversal_ids && ARRAY[9970]

위의 쿼리는 대규모 그룹의 경우 시간 초과될 수 있으므로 데이터를 일괄적으로 처리해야 합니다.

트리에 일괄 논리를 구현하는 것은 이전에 본 적이 없고, 상당히 복잡하게 구현됩니다. EachBatch 또는 find_in_batches 기반 솔루션이 작동하지 않는 이유는 다음과 같습니다:

• 데이터 (그룹 ID)는 계층 구조에 정렬되어 있지 않습니다.
• 하위 그룹의 그룹은 최상위 그룹 ID에 대해 알지 못합니다.

알고리즘

일괄 쿼리는 재귀 CTE SQL 쿼리로 구현되며, 한 일괄은 최대 N개의 행을 읽을 수 있습니다. 트리 구조 때문에 N 개의 행을 읽는 것이 N개의 그룹 ID를 읽는 것을 의미하지 않을 수 있습니다. 트리가 비 최적적인 방식으로 구성되어 있으면 일괄은 더 적은 (그러나 더 많지는 않음) 그룹 ID를 반환할 수 있습니다.

이 쿼리는 깊이 우선 트리 순회 논리를 구현하며, DB는 트리의 첫 번째 가지를 잎 요소에 이르기까지 스캔합니다. 깊이 우선 알고리즘을 구현하는 이유는 일괄이 완료되면 쿼리가 다음 일괄(cusor)에 대한 충분한 정보를 반환해야 하기 때문입니다. GitLab에서는 트리의 깊이를 20으로 제한하므로 최악의 경우 쿼리는 19개의 요소가 있는 커서를 반환할 수 있습니다.

너비 우선 트리 순회 알고리즘을 구현하는 것은 비실용적입니다. 왜냐하면 그룹은 무제한의 후손을 가질 수 있기 때문에 엄청난 크기의 커서가 나올 수 있기 때문입니다.

1. 다음 항목을 포함하는 초기화된 행 생성:
   1. 현재 처리 중인 그룹 ID (최상위 그룹 ID)
   2. 두 개의 배열 (트리 깊이 및 수집된 ID)
   3. 쿼리에서 행을 추적하는 카운터
2. 행을 재귀적으로 처리하고 다음 중 하나를 수행합니다 (조건에 부합하는 경우):
   • 맨 아래 노드가 아닌 경우 첫 번째 자식 네임스페이스를 로드하고 현재 처리 중인 네임스페이스 ID를 업데이트합니다. (가지 아래로 이동)
   • 현재 깊이에서 나머지 행을 로드합니다 (행이 남아 있는 경우)
   • 하나의 노드를 올라가고 더 높은 수준의 행을 처리합니다.
3. 쿼리 수행 횟수가 LIMIT(일괄 크기)에 도달할 때까지 처리를 계속합니다.
4. 커서를 사용하여 마지막으로 처리된 행을 찾고 수집된 레코드 ID를 모두 반환합니다.

WITH RECURSIVE result AS (
  (
    SELECT
      9970 AS current_id, /* 우리가 처리하고 있는 현재 네임스페이스 ID */
      ARRAY[9970]::int[] AS depth, /* 커서 */
      ARRAY[9970]::int[] AS ids,  /* 수집된 ID */
      1::bigint AS reads,
      'initialize' AS action
    ) UNION ALL
    (
    WITH cte AS ( /* result CTE를 여러 번 참조하기 위한 트릭 */
        select * FROM result
    )
    SELECT * FROM (
      (
        SELECT /* 가지 아래로 이동 */
          namespaces.id,
          cte.depth || namespaces.id,
          cte.ids || namespaces.id,
          cte.reads + 1,
          'walkdown'
        FROM namespaces, cte
        WHERE
        namespaces.parent_id = cte.current_id
        ORDER BY namespaces.id ASC
        LIMIT 1
      ) UNION ALL
      (
        SELECT /* 같은 수준에서 다음 요소 찾기 */
          namespaces.id,
          cte.depth[:array_length(cte.depth, 1) - 1] || namespaces.id,
          cte.ids || namespaces.id,
          cte.reads + 1,
          'next'
        FROM namespaces, cte
        WHERE
        namespaces.parent_id = cte.depth[array_length(cte.depth, 1) - 1] AND
        namespaces.id > cte.depth[array_length(cte.depth, 1)]
        ORDER BY namespaces.id ASC
        LIMIT 1
      ) UNION ALL
      (
        SELECT /* 현재 레벨에서 완료되었을 때 하나의 노드 올라가기 */
          cte.current_id,
          cte.depth[:array_length(cte.depth, 1) - 1],
          cte.ids,
          cte.reads + 1,
          'jump'
        FROM cte
        WHERE cte.depth <> ARRAY[]::int[]
        LIMIT 1
      )
    ) next_row LIMIT 1
    )
)
SELECT current_id, depth, ids, action
FROM result

 current_id |    depth     |        ids         |  action
------------+--------------+-------------------+-----------
         24 | {24}         | {24}              | initialize
         25 | {24,25}      | {24,25}           | walkdown
         26 | {24,26}      | {24,25,26}        | next
        112 | {24,112}     | {24,25,26,112}    | next
        113 | {24,113}     | {24,25,26,112,113}| next
        114 |{24,113,114}  |{24,25,26,112,113,114}| walkdown
        114 | {24,113}     | {24,25,26,112,113,114} | jump
        114 | {24}         | {24,25,26,112,113,114} | jump
        114 | {}           | {24,25,26,112,113,114} | jump