멀티 스테이지 데이터 파이프라인의 Latency 최적화 경로 설계 (예제 문제 포함)

# 1. 멀티 스테이지 데이터 파이프라인

데이터 파이프라인을 보게 되면, 사용자의 요청을 처리하기 위해 총 $N$개의 레이어(단계)를 거치는 분산 처리 시스템을 운영하고 있다.

예를 들어 아래와 같이 기본적으로 4단계의 단계를 자주 볼 수 있다.

• 1단계: API 게이트웨이
• 2단계: 인증/인가 서버군
• 3단계: 메인 비즈니스 로직 서버군
• 4단계: 데이터베이스 분산

여기서 나오는 현실적 문제점은 양과 질이다. 결과적으로 시스템의 확장성(Scalability) 구조 때문에, 하위 레이어로 갈수록 선택할 수 있는 서버 인스턴스의 개수가 가용 영역(AZ) 제한으로 인해 하나씩 늘어난다. (1단계는 1대, 2단계는 2대, 3단계는 3대...) 그렇다 보니, 가용 경로 제약 조건네트워크 토폴로지 제한 상, 현재 $i$번째 인덱스에 있는 서버는 다음 레이어의 $i$번째 혹은 $i+1$번째 서버로만 패킷을 보낼 수 있다. 다른 서버로 보내면 가용 영역을 벗어나 오버헤드가 발생하고 입력 데이터 형식 (Input)이 각 서버 인스턴스의 현재 처리 지연 시간(단위: ms)이 레이어별 배열로 input 된다.

 

그래서 결과적으로 다단계, 즉 멀티 스테이지라고 불리는 데이터 파이프라인에서의 Latency 최적화를 어떻게 설계할 것인가가 중요한데, 이러한 개념을 이해하고 있는지를 물어보는 문제로 아래와 같은 최적화 경로를 찾는 문제가 나오곤 한다.

---

앞서 4단계를 예시로 들었으니 아래 피라미드 구조에 대입해 보면 이해가 훨씬 쉽다.

# triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
server_latency_matrix = [
       [2],              # Layer 1 (API Gateway)
      [3, 4],            # Layer 2 (Auth Servers)
     [6, 5, 7],          # Layer 3 (Worker Nodes)
    [4, 1, 8, 3]         # Layer 4 (DB Shards)
]

---

위와 같은 형태의 문제를 보거나 아니면 내용 안에서 멀티 스테이지에 대한 Latency 최적화에 대해서 언급이 되었다면 해당 문제에 대한 핵심 요구사항만을 파악하면 된다.

 

첫 번째로 사용자 요청이 1단계부터 마지막 단계까지 통과할 때, 전체 처리 지연 시간(Latency의 총합)이 '최소'가 되는 라우팅 경로를 찾고, 그 최소 지연 시간(ms)을 반환하는 알고리즘을 구현하면 된다. 이때 메모리 제약이 있다면, 라우팅 계산은 요청이 들어올 때마다 초경량 라우터(로드 밸런서)의 메모리 위에서 실시간으로 돌아가야 하고 전체 레이어 히스토리를 다 저장하는 큰 임시 배열을 만들면 안 되며, 현재 레이어 크기만큼의 공간($O(n)$ extra space)만 사용하거나 기존 매트릭스를 인플레이스(In-place)로 업데이트해야 한다. 따라서 아래와 같은 형태의 예제코드를 통해서 최적 경로 설계가 가능하다.

---

from typing import List

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        """
        멀티 스테이지 데이터 파이프라인 최저 지연 시간(Latency) 경로 설계
        - Approach: Bottom-up Dynamic Programming (In-place)
        - Time Complexity: O(N^2) - 삼각형 내부 모든 원소 방문
        - Space Complexity: O(1) Extra Space - 입력 배열을 그대로 재사용
        """
        # 변수명을 실무적으로 매핑 (블로그 설명용)
        latency_matrix = triangle
        
        # 전체 레이어(행)의 개수
        total_layers = len(latency_matrix)
        
        # 맨 아래에서 두 번째 레이어(행)부터 시작해서 꼭대기(0번째)까지 역순으로 올라감
        for layer in range(total_layers - 2, -1, -1):
            # 현재 레이어의 각 노드(인스턴스)를 순회
            for idx in range(len(latency_matrix[layer])):
                
                # 내 바로 아래 레이어에서 연결된 두 개의 노드 값 확인
                next_layer_left = latency_matrix[layer + 1][idx]
                next_layer_right = latency_matrix[layer + 1][idx + 1]
                
                # 두 하위 경로 중 '더 지연 시간이 짧은(최솟값)' 쪽을 선택하여 현재 노드에 누적
                latency_matrix[layer][idx] += min(next_layer_left, next_layer_right)
        
        # 모든 최적화 연산이 끝나면 꼭대기[0][0]에 최종 누적 최솟값이 저장됨
        return latency_matrix[0][0]

---

위의 예제코드에서 눈여겨봐야 할 두 가지는 O(N^2) Time Complexity를 설정한 거와 Space Complexity를 O(1) Extra Space로 설정해 두는 것이다. 이렇게 설정을 함으로써 모든 노드를 정확히 한 번씩만 방문하여 하위 노드 2개를 비교하는 상수 연산을 minium으로 수행하면서도 input으로 들어온 연산을 재사용 (메모리 공간을 그대로 활용)하는 in-place 통해 효율성을 높인다. 다만 이 경우 원본 데이터의 구조, 즉 여기서는 삼각형 모양의 배열 구조를 임의로 최적화에 맞춰 바꾼다는 특징이 있다. 그래서 만일 데이터 구조 자체를 유지하면서 최적화 경로 latency를 원한다면 dp = triangle [-1][:]를 통해서 아래 행의 크기를 만큼만 선언한 뒤에 새로고침에서 올라가는 방식을 사용하면 된다. 그래도 해당 Space Complexity가 O(n)이 되기 때문에 최적화 경로가 가능하다.

---