트리가 주어졌을 때, u와 v 두 노드의 조상이면서 가장 깊은 노드를 찾는 알고리즘이다.

예를 들어, 아래와 같은 트리가 존재한다고 가정하자. 4번 노드와 6번 노드의 공통 조상은 1번 노드, 2번 노드가 존재한다. 1번 노드는 루트 노드로, 깊이가 0이고 2번 노드는 깊이가 1이다. 따라서 가장 깊은 2번 노드가 최소 공통 조상이다.

어떻게 찾을까?

기본적인 아이디어는 다음과 같다.

1. 높이 맞추기: 낮은 깊이를 기준으로, u와 v의 깊이가 같아지도록 한다.
2. 최소 공통 조상 찾기: u와 v가 같아질 때까지 각각의 부모 노드로 이동한다. (= 높이를 올린다.)
3. u와 v가 같아지는 첫 노드가 최소 공통 조상이다.

위에서 사용한 트리를 기준으로 8번 노드와 15번 노드의 최소 공통 조상을 찾아보자.

1. 15 → 11 → 5
   • 8번 노드의 깊이는 2, 15번 노드의 깊이는 4이다. 따라서 15번 노드의의 깊이를 2가 되도록 맞춰야 한다.
   • 따라서 부모 노드로 2번 이동한다.
2. 5 → 2 → 1 / 8 → 3 → 1
   1. 5 ≠ 8 → 각각의 부모 노드로 이동 u = 2 / v = 3
   2. 2 ≠ 3 → 각각의 부모 노드로 이동 u = 1 / v = 1
   3. 1 = 1
3. u와 v가 1로 같아졌다. 8번 노드와 15번 노드의 최소 공통 조상은 1이다.

시간복잡도 문제

위 방식에서는 1번과 2번 과정에서 모두 부모 노드로 한 번씩 이동한다. 이는 O(n)의 시간복잡도를 갖게 된다. 아래의 트리에서 1번 노드와 5번 노드의 최소 공통 조상을 찾는 것을 예로 생각해보자.

1번 노드와 5번 노드의 깊이를 맞추기 위해 5번 노드를 부모 노드로 4번 이동해야 한다. 이는 n-1번의 연산이 필요함을 의미한다. 따라서 한 번씩 부모 노드로 이동하는 것은 상당히 느리다.

최적화

희소 테이블의 개념을 사용해서 이를 O(log n)의 시간복잡도로 최적화할 수 있다.

다시 위의 트리를 가져와서 8번 노드와 16번 노드의 최소 공통 조상을 찾아보자.

높이 맞추기

8번 노드와 16번 노드의 깊이 차이는 3이다. 차이를 이진수로 나타내면 11(2)이다. 우리는 이진수로 표현한 깊이 차이를 통해 한 번에 한 칸씩 이동하는 게 아니라, 2^k칸씩 이동할 것이다.

11(2)라는 깊이 차이가 주어졌을 때, 하나의 비트씩 확인하며 이동하는 것이다. 높은 자리의 비트부터 확인한다고 하면 2^1칸 이동, 2^0칸 이동하여 총 2번의 이동으로 3칸을 이동한다.

이렇게 O(n)의 시간복잡도로 높이를 맞추던 과정을 O(log n)으로 최적화했다.

최소 공통 조상 찾기

이제 16은 높이를 맞추며 5가 되었고, 5와 8이 같아질 때까지 부모 노드로 이동해야 한다. 이때도 우리는 비트를 통해 O(log n)의 시간복잡도로 최소 공통 조상을 찾을 수 있다.

최소 공통 조상이 1이라는 결과를 먼저 알고 있는 상태에서 보면 두 노드와 최소 공통 조상의 높이 차이는 2이므로, 2번 이동해야 한다. 이를 이진수로 나타내면 10(2)이다. 따라서 1칸씩 2번이 아니라 2칸씩 1번 이동하면 된다. 이는 높이 맞추기에서 최적화한 희소 테이블의 원리와 같다.

• 최소 공통 조상까지의 높이 차이가 10이라면 1010(2)이다. 따라서 8칸 1번, 2칸 1번 이동한다.
• 최소 공통 조상까지의 높이 차이가 512라면 1000000000(2)이다. 따라서 512칸 1번 이동한다.

즉, 최소 공통 조상과의 높이 차이만큼 2^k 꼴로 이동하며 O(log n)의 시간복잡도로 이동할 수 있다. 다만 우리는 최소 공통 조상과의 높이 차이를 모른다. 따라서 가능한 최대 자리의 비트부터 확인하며 최소 공통 조상을 찾는다.

예를 들어, 노드가 총 50,000개 있다고 가정하자. 이떄 가능한 트리의 최대 높이 또한 50,000이다. 이는 16개의 비트를 사용해서 표현할 수 있다. (50,000 ≤ 2^k - 1을 만족하는 가장 작은 수가 16이다.) 그러면 우리는 2^15 자리부터 2^0자리까지 확인하며 최소 공통 조상을 찾을 것이다. 과정은 다음과 같다.

1. k = 15 ; k ≥ 0; k—

2. u와 v에서 2^k번째 부모로 이동할 수 있는지 확인한다.

   만약 u와 v의 깊이가 2라면 4,8,16,…,2^15번째 부모는 존재하지 않기 때문에 이동할 수 없다.

3. u와 v의 2^k번째 부모가 같지 않은지 확인한다.

   부모가 같다는 것은 공통 조상임을 의미하지만, 최소 공통 조상은 아닐 수 있다. 우리는 높은 자리의 비트부터 확인하기 때문에 깊이가 낮은 조상으로 이동하게 되는 문제가 생길 수 있다. u와 v의 1023번째 조상이 최소 공통 조상이라면, 2^10 자리 이상의 비트를 사용하는 순간 1023보다 커지기 때문에 최소 공통 조상을 넘어가게 된다.

4. 1번, 2번 조건을 만족한다면 각각 2^k번째 부모로 이동한다.

5. 2~4번 과정을 반복한다.

이 과정을 반복하면 u와 v의 부모는 각각 같은 노드를 가리키고 있으며, 그 노드가 곧 최소 공통 조상이 된다.

노드가 총 50,000개 있다고 가정했을 때 16개의 비트를 사용해서 표현할 수 있다고 했다. 이는 곧, 최대 16번의 연산으로 최소 공통 조상을 찾을 수 있음을 의미한다.

희소 테이블?

높이를 맞추는 과정과 최소 공통 조상을 찾는 과정에서 모두 O(n)의 시간복잡도를 갖는 과정을 희소 테이블의 개념을 사용하여 O(log n)의 시간복잡도로 최적화했다. 다시 정리하자면, 한 번씩 이동하는 게 아니라 2^k번 꼴로 이동함으로써 연산 횟수를 줄인 것이다.

하지만 문제에서 u의 2^k번째 부모가 무엇인지 알려줄 리는 없기 때문에 특정 노드의 2^k번째 부모가 무엇인지 미리 찾아 놓는 전처리 과정이 필요하다. 이 과정이 희소 테이블을 만드는 것이다. 전처리 과정은 바텀업 DP를 통해 가능하다.

parent[i][j] = i 노드의 2^j번째 부모

1. 문제에서 주어진 간선과 루트 노드 번호를 통해 각 노드의 첫 번째 부모를 알 수 있다. (= parent[i][0])

2. 노드 u의 두 번째 부모는 곧 u의 첫 번째 부모의 첫 번째 부모이다.

   → parent[u][1] = parent[parent[u]][0]

3. 노드 u의 네 번째 부모는 곧 u의 두 번째 부모의 두 번째 부모이다.

   → parent[u][2] = parent[parent[u]][1]

4. 노드 u의 2^k번째 부모는 곧 u의 2^(k-1)번째 부모의 2^(k-1)번째 부모이다.

   → parent[u][k] = parent[parent[u]][k - 1]

일반화하는 과정을 보면 알 수 있듯이 2^k = 2^(k-1) * 2^(k-1)임을 활용한 전처리 과정이다.

노드의 개수가 n이고 n의 범위를 커버할 수 있는 가장 작은 비트 수가 k개라고 할 때, 전처리 과정 시간복잡도는 O(nk)이다. 이때 k는 n을 이진수로 나타냈을 때의 비트 수와 같기 때문에 log n으로 치환이 가능하다. 따라서 O(n logn)의 시간복잡도를 갖는다.

위에서 언급한 희소테이블은 2^k번째 부모를 저장하는 방식이다. 만약 2^k 꼴이 아니라 첫 번째 부모, 두 번째 부모, …, n번째 부모를 모두 저장하는 방식으로 전처리를 구성한다면 최소 공통 조상을 찾는 과정이 O(1)으로 해결될 것이다. 하지만 이는 전처리 과정의 시간복잡도가 O(n^2)이 될 뿐 아니라 메모리까지 그만큼 많이 사용하게 된다.

관련 문제 (BOJ 11438)

백준 온라인 저지의 11438번 문제(LCA 2)를 예제로 풀었다.

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

const int MAX = 100000;
const int MAX_D = 17;

int n, m;
vector< vector<int> > graph;
int depth[MAX];
int parent[MAX][MAX_D];

void makeTreeByDFS(int cur) {
    for (int next : graph[cur]) {
        if (depth[next] == -1) {
            parent[next][0] = cur;
            depth[next] = depth[cur] + 1;
            makeTreeByDFS(next);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);

    cin >> n;

    graph = vector< vector<int> >(n, vector<int>());
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    memset(parent, -1, sizeof(parent));
    memset(depth, -1, sizeof(depth));
    depth[0] = 0;
    // 트리 생성
    makeTreeByDFS(0);

    // parent 배열 채우기
    for (int j = 0; j < MAX_D - 1; ++j) {
        for (int i = 1; i < n; ++i) {
            if (parent[i][j] != -1)
                parent[i][j + 1] = parent[parent[i][j]][j];
        }
    }

    cin >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (depth[a] < depth[b]) swap(a, b);
        int diff = depth[a] - depth[b];

        for (int j = 0; diff; ++j) {
            if (diff % 2) a = parent[a][j];
            diff /= 2;
        }

        if (a != b) {
            for (int j = MAX_D - 1; j >= 0; --j) {
                if (parent[a][j] != -1 && parent[a][j] != parent[b][j]) {
                    a = parent[a][j];
                    b = parent[b][j];
                }
            }
            a = parent[a][0];
        }

        cout << a + 1 << '\n';
    }

    return 0;
}

References

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220820773477&categoryNo=299&parentCategoryNo=0&viewDate=&currentPage=2&postListTopCurrentPage=1&from=postList&userTopListOpen=true&userTopListCount=15&userTopListManageOpen=false&userTopListCurrentPage=2

한 회사의 기술 면접(라이브 코딩 세션)에서 특정 자료구조를 구현한 적이 있다. 자료구조의 자세한 요구사항은 차치하고 간단하게 설명하자면 Queue와 같은 구조로, offer(삽입) 연산과 poll(최상위 요소 제거 및 반환) 연산을 할 수 있다. 이때 offer 연산은 항상 상수 비용이 소요되고, poll 연산은 일반적으로는 상수 비용이 소요되지만, 최악의 경우 O(n)의 시간복잡도를 갖는다.

구현을 마치고, 최악의 경우에 대한 시간복잡도 분석까지 마친 뒤 다음과 같은 질문을 받았다.

무작위로 offer, poll을 n번 했을 때의 시간복잡도는 어떤가요?

한참을 고민하다가 결국 올바른 답을 하지 못 했다. poll과 offer를 각각 n/2번 수행했을 때를 생각했고, 최악의 경우를 기준으로 계산하여 결국 O(n^2)이 되겠다고 생각했다. 하지만 답이 아니였고, 면접이 끝난 뒤에 면접관님께 정답이 무엇이었는지 여쭤봤다. 이는 분할 상환 분석과 관련된 내용이었다.

분할 상환 분석이란

일련의 연산을 수행하는 알고리즘의 평균적인 시간복잡도를 분석하는 데 사용되는 기술이다. 최악의 경우를 분석하는 것이 아니라, 평균적인 시간복잡도를 분석하는 이유는 무엇일까?

2개 이상의 연산을 하는 어떠한 자료구조가 있다고 하자. 자료구조의 어떤 연산은 상당한 비용을 소모할 수 있지만, 다른 연산은 비교적 적은 비용을 소모할 수 있다. 그리고 두 연산은 각각 실행되는 빈도 역시 다를 것이다. 예를 들어, element가 추가되거나 제거됨에 따라 크기가 달라지는 동적 데이터 구조가 이에 해당한다. element가 추가됨에 따라 삽입 연산에 resizing이 동반될 수 있는데, 이때는 동적 데이터 구조의 크기에 따라 상당한 비용이 발생할 수 있다. 그렇지만, resizing은 삽입 연산 시에 매번 발생하지 않는다. 즉, 최악의 경우만 놓고 봤을 때는 상당한 비용이 발생하지만 평균적으로는 그렇지 않다는 것이다.

그럼에도 시간복잡도를 분석할 때 각각의 연산마다 최악의 경우를 따지는 것은 실제 성능보다 매우 낮은 결과로 분석될 수 있기 때문에 완벽한 분석 방법이 아니다.

분할 상환 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려하여 위와 같은 맹점을 해결하는 분석 기법이다.

분석 방법

분할 상환 분석의 핵심 아이디어는 비용이 많이 드는 작업의 비용을 비용이 적게 드는 여러 작업에 분산하는 것이다. 이름에서 알 수 있듯이 비용이 많이 드는 작업의 비용을 분할하여, 비용이 적게 드는 여러 작업에 상환한다.

하나의 예를 들어보자. 동적 배열이 존재한다고 했을 때, 배열에 element를 삽입하는 비용은 1이다. 하지만 배열의 capacity를 넘기는 순간에는 배열의 크기를 조정하는 동작이 발생한다. 배열의 크기를 조정할 때의 시간복잡도는 O(n)이라고 하자. (새로운 크기의 배열을 생성한 뒤, 기존 element n개를 복사한다.) 따라서 삽입 연산의 시간복잡도를 최악의 경우로 분석한다면 O(n)이라고 할 수 있다. 그렇다면 이러한 삽입 연산을 n번 했을 때의 시간복잡도는 어떨까? 앞서 언급한대로 간단하게 최악의 경우로 분석한다면 O(n)의 작업을 n번 수행하므로 O(n^2)일 것이다.

하지만 분할 상환 분석은 이를 다르게 분석한다. 결론부터 말하자면, 삽입을 n번 하더라도 상수 비용이 발생한다. 삽입 연산에서는 배열 크기 재조정이라는 고비용의 연산이 발생하긴 하지만 가끔 발생할 뿐이므로, 전체적으로는 그 비용이 높지 않다는 것이다.

위 그림을 참고하자. 초기 크기가 1인 동적 테이블(배열)에 element를 10개 넣으면서 발생하는 비용을 분석한 것이다. 즉, n = 10일 때 삽입 연산을 n번 하는 것이다.

우선 n개의 데이터를 넣기 때문에 1*n 의 비용이 발생한다.

그리고 Amortized Cost(상각 비용) 부분을 확인하면 재조정 비용을 2n으로 계산하는 것을 확인할 수 있다. 2n은 재조정에서 발생하는 비용을 정확하게 계산한 값은 아니고, n을 기준으로 그 비용의 상한선을 정한 것이다. 왜 그런지 확인해보자.

배열의 크기를 2배씩 늘리며 재조정한다는 가정 하에, 배열의 크기는 2의 거듭제곱 즉, 2^k의 크기를 갖는다. (1 -> 2 -> 4 -> 8 -> ...) 이때 2^k는 n개의 element를 충분히 담을 수 있는 크기여야 한다. 즉, n <= 2^k가 성립한다. 예를 들어, 8개의 element를 담기 위해서는 2^3의 크기면 충분하고, 9개의 element를 담기 위해서는 2^4의 크기가 필요하다.

즉, n개의 element를 담기 위해서는 배열의 크기가 2^k로 재조정돼야 한다. 이때 발생하는 재조정 비용은 다음과 같다.

• 2^0 + 2^1 + 2^2 + ... + 2^(k-1) = 2^k - 1

2^k는 위에서 설명했듯이 n개의 데이터를 담을 수 있으면서 제일 작은 2의 거듭제곱이다. 즉 n 이상의 크기이며, 최대 2n개의 데이터를 담을 수 있는 크기인 것이다. 2n+1개의 데이터를 담기 위해서는 2^(k+1)의 크기가 필요하다. 따라서 다음과 2^k는 같은 범위를 갖는다.

• n <= 2^k <= 2n

이제 우리는 2^k가 n개의 데이터를 담기 위한 동적 배열의 크기라는 것을 알고 있고, 2^k의 상한값이 2n이라는 것을 알 수 있다.

따라서 element를 n번 추가하는 비용 n, 그 과정에서 배열의 크기를 재조정하는 비용 2n이 발생한다. n번의 연산 속에서 총 3n의 비용이 발생하는 것이므로 평균적인 비용은 3이라는 상수 비용이 발생하는 것이다.

Java의 ArrayList는?

이러한 개념은 역시 Java의 동적 데이터 구조인 ArrayList에서도 적용된다.

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. ...

위 설명은 ArrayList의 Javadoc 내용을 가져온 것이다. element를 삽입하는 add 연산이 상각된 상수 시간으로 실행된다는 것을 확인할 수 있다.

정리

분할 상환 분석은 고비용 연산(현재 예시에선 배열 크기 재조정)의 비용을 단순히 최악의 경우로 분석하지 않고, 전체 주어진 시간 내에서 적절한 상한을 찾는다. 위에서 들었던 예시에 따르면, n번의 삽입 연산을 최악의 경우로 분석했을 때도 O(n^2)이라는 상한이 주어진다. 하지만 분할 상환 분석의 목적은 고비용 연산과 저비용 연산의 집합이 주어졌을 때, 평균적인 성능을 계산함으로써 실제 성능보다 매우 낮은 결과로 분석되는 것을 막는 것이다. 그런 이유에서 상한을 보다 엄격하게 잡고, 엄격한 상한을 통해 성능을 분석하는 것이다.

서론에서 내가 잘못 계산한 O(n^2)은 O(1)의 연산과 O(n)의 연산이 각각 n/2번씩 실행된다는 가정을 전제로 한 평균의 경우 분석을 통해 나온 결과였다. 이는 분할 상환 분석과 비교했을 때, O(n)의 연산이 드물게 발생한다는 것을 고려하지 않은 분석이다.

실생활을 예시로 한 자세한 설명 및 분석은 가젤 님의 블로그를 통해 확인해 볼 수 있다.

References

https://www.geeksforgeeks.org/introduction-to-amortized-analysis/

https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%83%81%ED%99%98_%EB%B6%84%EC%84%9D

https://gazelle-and-cs.tistory.com/87

https://www.acmicpc.net/problem/12850

접근 방식

입력으로 받는 D 값의 범위가 1부터 10억까지 가능하다. 1초의 시간 제한 내에 풀기 위해서는 시간복잡도 O(log N)으로 해결해야 한다.

우리가 최종적으로 구해야 하는 것은 주어진 경로(그래프) 내에서 D분 동안 산책하고 정보과학관으로 돌아오는 경우의 수이다. 즉, 특정 비용을 지불했을 때 0번 노드에서 0번 노드까지 갈 수 있는 경우의 수다.

여기서 인접 행렬을 통해 경로 수를 구하는 아이디어를 떠올릴 수 있다. (난 떠올리지 못 했다.) 이 문제는 모든 산책 경로가 1분만 소요되는, 즉, 가중치가 없는 그래프를 전제로 한다. 가중치가 없는 그래프에서는 인접행렬의 원소가 0 또는 1로 구성되어 간선 유무를 나타낸다. 그리고 우리는 인접행렬의 제곱을 활용해서 경로의 수를 파악할 수 있다.

문제에서 주어진 그래프를 인접행렬 M으로 만들었다고 가정하자. 인접행렬 M의 값은 다음과 같을 것이다.

• 정보과학관과 전산관은 연결되어 있다. -> M[정보과학관][전산관] = 1
• 정보과학관과 신양관은 연결되어 있지 않다. -> M[정보과학관][신양관] = 0

위와 같은 값을 갖는 이유는 인접행렬 M은 "i에서 j로 갈 수 있는지 여부"를 나타내고 있기 때문이다.

당연하게도 한 번의 이동만으로는 정보과학관에서 신양관으로 이동할 수 없음을 알 수 있다. 하지만 두 번의 이동으로는 어떨까? 가능한 것은 물론이거니와 두 가지 경로가 존재한다.

1. 정보과학관 -> 전산관 -> 신양관
2. 정보과학관 -> 미래관 -> 신양관

위에서 확인한 내용을 인접행렬의 거듭제곱을 통해 똑같이 확인할 수 있다. 처음으로 주어진 그래프를 인접행렬로 나타낸 것을 M이라고 했을 때, 행렬 M의 제곱 역시 i에서 j로 갈 수 있는지 여부를 나타낸다. 그렇다면 M과 M^2는 어떻게 다를까? 결론은 M^2는 (2번의 이동으로) i에서 j로 갈 수 있는 경우의 수를 나타낸다. 행렬 M을 직접 거듭제곱해보며 알아보자.

위에서 예시를 들었듯이 정보과학관(0), 전산관(1), 미래관(2), 신양관(3) 4개의 건물만 존재한다고 가정했을 때의 인접행렬 M은 다음과 같다.

0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

행렬 M을 제곱한 결과는 다음과 같다.

2 1 1 2
1 3 2 1
1 2 3 1
2 1 1 2

이제 이 행렬이 어떤 의미를 갖는지 알기 위해 M^2의 (0, 0) 계산 과정을 뜯어보자. M^2(0, 0)은 행렬 곱셈식에 의해 M(0, 0) * M(0, 0) + M(0, 1) * M(1, 0) + M(0, 2) * M(2, 0) + M(0, 3) * M(3, 0)의 값을 갖게 된다. 이를 하나씩 놓고 보면 다음과 같이 구성됨을 알 수 있다.

• M(0, 0) * M(0, 0) - 정보과학관 -> 정보과학관 -> 정보과학관
• M(0, 1) * M(1, 0) - 정보과학관 -> 전산관 -> 정보과학관
• M(0, 2) * M(2, 0) - 정보과학관 -> 미래관 -> 정보과학관
• M(0, 3) * M(3, 0) - 정보과학관 -> 신양관 -> 정보과학관

결과적으로 두 번의 이동을 통해 정보과학관에서 정보과학관으로 가는 경로는 전산관과 미래관을 거치는 총 2가지의 경우의 수가 있다.

즉, 인접행렬의 거듭제곱을 통해 i에서 j까지 가는 경우의 수를 구할 수 있다. 따라서 인접행렬 M의 거듭제곱을 다음과 같이 일반화할 수 있다. 인접행렬 M의 n제곱은, n번의 이동으로 i에서 j까지 가는 경우의 수를 의미한다.

이를 문제에 적용하면, 우리는 입력으로 주어진 D번의 이동을 했을 때, 정보과학관에서 정보과학관으로 가는 경우의 수를 구하면 되는 것이다. 풀이는 다음과 같을 것이다.

1. 주어진 그래프를 인접행렬(M)로 나타낸다.
2. 인접행렬을 D만큼 제곱한다. -> M^D
3. M^D의 (0, 0) 값을 출력한다. (MOD 연산자 신경쓰기)

정답 코드(Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    /*
    0. 정보과학관
    1. 전산관
    2. 미래관
    3. 신양관
    4. 한경직기념관
    5. 진리관
    6. 형남공학관
    7. 학생회관
     */

    private static final int MOD = 1_000_000_007;
    static long[][] matrix = {
            {0, 1, 1, 0, 0, 0, 0, 0},
            {1, 0, 1, 1, 0, 0, 0, 0},
            {1, 1, 0, 1, 1, 0, 0, 0},
            {0, 1, 1, 0, 1, 1, 0, 0},
            {0, 0, 1, 1, 0, 1, 1, 0},
            {0, 0, 0, 1, 1, 0, 0, 1},
            {0, 0, 0, 0, 1, 0, 0, 1},
            {0, 0, 0, 0, 0, 1, 1, 0},
    };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long[][] res = doPow(n);
        System.out.println(res[0][0] % MOD);
    }

    private static long[][] doPow(int n) {
        if (n == 1) {
            return matrix;
        }

        long[][] temp = doPow(n / 2);
        temp = multiply(temp, temp);

        if (n % 2 == 1) {
            temp = multiply(temp, matrix);
        }

        return temp;
    }

    private static long[][] multiply(long[][] a, long[][] b) {
        long[][] temp = new long[8][8];

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                for (int k = 0; k < 8; k++) {
                    temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % MOD;
                }
            }
        }

        return temp;
    }
}

회고

• 가중치가 없는 그래프가 주어졌을 때, 인접행렬을 활용하여 경로 수를 얻을 수 있다는 것을 알게 됐다. 사실 이를 잊지 않기 위해 기록한 것이기도 하다.
• 우리 학교 동아리에서 출제된 문제였다. 문제를 보자마자 아는 내용이어서 반가웠다.

‘201 CREATED’ 어플리케이션은 스터디원 모집 및 스터디 진행을 돕는 서비스이다.

스터디 진행을 돕는 기능 중 스터디가 현재 몇 주차인지, X요일까지 어떤 과제를 해야 하는지 확인할 수 있는 기능이 있다. 이를 위해서는 매일 변하는 날짜를 어플리케이션의 서버에도 동기화해야 한다.

이 과정에서 매우 많은 양의 쿼리가 실행되는 문제가 있었고, 이를 개선하고자 한다.

도메인 이해

도메인 상에서 최상위 계층에 있는 스터디라는 개념이 있다. 각각의 스터디에는 회차가 존재한다. 회차는 스터디원들이 스터디를 진행하는 날이라고 생각하면 된다. 예시는 다음과 같다.

• A 스터디: 주 3회, 월/수/금 요일
• B 스터디: 주 1회, 화요일

스터디를 진행하면서 회차는 계속해서 쌓일 것이다. 이미 끝난 회차도 중요하지만, 우리 어플리케이션에서는 ‘현재 회차’를 중심으로 사용자에게 기능을 제공한다. 날짜가 변경됨에 따라 회차가 변경되고, 사용자에게 보여지는 ‘현재 회차’도 달라져야 한다.

위의 B 스터디를 예로, 2주차 화요일이 12월 5일이라고 가정하자. 유저는 12월 5일까지 2주차 회차를 진행한다. 그리고 회차를 마치고 12월 6일이 되면, 3주차의 회차를 보게 될 것이다.

우리 팀은 이를 스케줄링으로 구현했다. 매일 자정(00시), 전날에 진행한 회차를 종료 처리하고 새로운 회차를 현재 회차로 업데이트한다.

소스코드 및 구현 내용

Spring의 @Scheduled 어노테이션을 활용하여 매일 0시 0분 0초에 RoundService.proceedRound() 메서드를 호출한다. (위에서 설명한 회차를 Round라고 칭한다.)

RoundService.proceedRound()의 구현 내용은 다음과 같다.

매우 긴 라인의 메서드이다. 이를 보기 쉽게 나눠서 설명하면,

1. 현재 진행 중(IN_PROGRESS)이면서, 어제 진행한 Round를 모두 가져온다.

   이렇게 찾아온 Round들은 날짜가 변경됨에 따라, 오늘 업데이트해줘야 하는 대상인 것이다.

2. Round가 속해 있는 Study의 Id와 weekNumber를 기반으로 다음 Round가 될 수 있는 후보 Round들을 조회한다.

   후보를 조회할 때, 현재 주차와 다음 주차의 Round들을 조회하고 있다. 이는 도메인 규칙에 근거한다.

   • 다음 주차까지의 회차만 조회할 수 있다는 규칙
   • → 기존에 n주차를 진행하고 있을 때는 n+1주차까지의 회차들이 존재한다.
   • 즉, 다음 Round가 될 수 있는 후보는 현재 주차 또는 다음 주차 안에 무조건 속한다.

3. 후보 Round들 중, 다음 Round가 무엇인지 찾아낸다.
   1. 현재 주차의 시작되지 않은 Round들을 필터링한다.
   2. 필터링한 Round들 중, 요일(DayOfWeek)의 값이 가장 작은 Round를 찾는다. 이는 월/수/금 진행하는 스터디의 월요일 Round가 끝났을 때, 다음 Round를 금요일이 아닌 수요일로 설정하기 위함이다.
   3. (1), (2) 과정을 통해 찾은 Round가 존재하지 않는다면 다음 주차를 기준으로 (1), (2) 과정을 반복한다. 월/수/금 진행하는 스터디의 1주차 금요일 Round가 끝났다면, 2주차 월요일이 다음 Round가 되어야 하기 때문이다.

4. 기존의 Round를 끝내고, 다음 Round를 진행한다.

   이 과정에서 기존의 Round는 상태가 FINISHED로 변경되며, nextRound의 상태는 IN_PROGRESS로 변경된다. 즉, 두 개의 Round 객체에 대해 상태 변경이 발생한다.

5. 다음 Round가 다음 주차에 속해 있다면, 다다음주차의 Round를 모두 생성해서 저장한다.

   2번 로직에서 설명한 도메인 규칙에 근거하여, 스터디의 현재 주차가 n+1주차로 넘어가면서 n+2주차의 Round들을 모두 생성하는 과정이다.

여기까지가 Study에 날짜를 반영하는 스케줄링 기능의 기존 코드이다.

이 기능의 흐름을 이해했다면, 여기서 어떤 문제가 발생했는지 살펴보자.

대량의 쿼리 실행

매우 많은 양의 쿼리를 실행하는 문제에 대해서 알아볼 것이다. 이때 쿼리의 수는 우리 어플리케이션에 존재하는 데이터 양에 따라 변경된다.

현재 글에서는 다음과 같은 환경이라고 가정하고 설명하겠다.

• 진행 중인 스터디 100개
• 각 스터디는 주 2회 수/일 요일 진행
• 한 스터디에 6명의 인원이 참여 → StudyMember 6명
• n주차 일요일 → n+1주차 월요일로 날짜가 변경되며 스케줄링 실행

위에서 설명한 1~5번 과정을 기반으로, 각 과정에서의 쿼리 횟수를 정리해보자.

1. 현재 진행 중(IN_PROGRESS)이면서, 어제 진행한 Round를 모두 가져온다. → 1회

2. Round가 속해 있는 Study와 weekNumber를 기반으로 다음 Round가 될 수 있는 후보 Round들을 조회한다. → 1회

3. 후보 Round들 중, 다음 Round가 무엇인지 찾아낸다. → 0회

   한 번에 조회해온 후보 Round들을 Stream으로 필터링하기 때문에 쿼리는 발생하지 않는다.

4. 기존의 Round를 끝내고, 다음 Round를 진행한다. → 1회

   기존 Round의 상태 변화 1회 + 다음 Round의 상태 변화 1회로, 두 번의 update가 이뤄진다.

   하지만, JPA의 쓰기 지연 저장소를 통해 Batch Update하므로, 실제로는 1회의 쿼리만 발생한다.

5. 다음 Round가 다음 주차라면, 다다음주차의 Round를 모두 생성해서 저장한다. → 16회

   Round.createNextWeekRound()의 구현은 다음과 같다.

   

   기존 Round의 내용을 복사하고, 주차 정보만 다음 주차로 변경한다. 이때 Round 내부에 있던 RoundOfMembers도 복사하게 되는데, 해당 필드는 OneToMany 관계의 RoundOfMember 리스트이다.

   • RoundOfMember는 Round와 Member를 매핑하는 엔티티이다.

     한 주에 2번 진행하는 스터디이기 때문에 Round를 2번 저장한다. 그리고 Round를 한 번 저장할 때 발생하는 쿼리는,

   • Round가 RoundOfMember를 Lazy Loading하는 쿼리 1회

   • 스터디에 참여한 인원은 6명이기 때문에 각각의 RoundOfMember를 저장하는 쿼리 6회

   • Round insert 쿼리 1회

     즉, 1+6+1회의 쿼리가 발생하는 Round를 2번 생성한다. 8*2=16회의 쿼리가 발생

정리

2~5번의 과정은 1번 과정에서 찾아온 Rounds를 반복하면서 진행하기 때문에, 100이 곱해진 수의 쿼리가 발생한다. 정리하자면 다음과 같다.

1. 현재 진행 중(IN_PROGRESS)이면서, 어제 진행한 Round(100개)를 모두 가져온다. → 1회
2. Round가 속해 있는 Study와 weekNumber를 기반으로 다음 Round가 될 수 있는 후보 Round들을 조회한다. → 1 * 100 = 100회
3. 후보 Round들 중, 다음 Round가 무엇인지 찾아낸다. → 0회
4. 기존의 Round를 끝내고, 다음 Round를 진행한다. → 1 * 100 = 100회
5. 다음 Round가 다음 주차라면, 다다음주차의 Round를 모두 생성해서 저장한다. → 16 * 100 = 1600회

총 1801회의 쿼리가 발생한다.

// proceedRound() 메서드 실행 시간
// Java의 System.currentTimeMillis()를 이용하여 계산

time spent to proceed Round 
study size: 100
total time spent: 360
The JVM is using 150 MB of memory.

쿼리 최적화

Batch Insert

먼저 1801회의 쿼리 중 무려 1600회의 쿼리를 발생시키는 Round 생성을 개선해보자.

Round를 저장할 때 쿼리가 발생하는 지점을 다시 짚어보면, 다음과 같다.

n = 업데이트하는 Round의 수, m = 스터디에 참여한 Member의 수라고 하겠다.

• Round 저장 → n회의 쿼리
  • Round의 Lazy Loading(RoundOfMember) → n회의 쿼리
  • Round 저장 시에 함께 저장되는 RoundOfMember 저장 → n * m회의 쿼리

여기서 가장 쉽고 빠르게, 많은 쿼리를 줄이는 방법은 Round와 RoundOfMember를 Batch Insert하는 것이라고 생각했다. 단순 저장을 매우 많은 양의 쿼리로 처리하고 있기 때문이다.

Round의 내부, 즉 객체 그래프 중 깊은 곳에 위치한 RoundOfMember를 먼저 Batch Insert 해보자.

근데 Batch Insert를 하기 전에 고려해야 할 부분이 있었다. 그것은 Round와 RoundOfMember의 연관관계였다. 두 엔티티는 1:N의 관계를 가진다. 즉 DB에서는 RoundOfMemeber 테이블이 외래키를 가지게 된다.

그렇기 때문에 RoundOfMember를 저장하기 위해서는 Round의 PK가 필요하다. Round의 PK 생성 전략은 AUTO_GENERATED이기 때문에 Round를 미리 저장해야 한다. 그리고 미리 저장한 Round의 id를 각각 가지고 있어야 한다.

위와 같은 제한 사항에 따라, 기존의 방식으로 Round를 저장하고 나온 id를 통해 RoundOfMember를 Batch Insert하는 방향으로 개선해보자.

먼저, Round를 저장할 때 RoundOfMember도 곧바로 함께 저장하지 않기 위해 기존의 Cascade Persist 전략을 제거한다.

RoundOfMember는 원래 Cascade 전략을 통해 저장했다. 하지만 이제 Round와 따로 저장할 것이기 때문에 BatchRepository를 통해 저장한다. 원래 n*m회의 쿼리로 저장하던 RoundOfMember를 이제 1회의 쿼리로 저장 가능하다.

RoundOfMember Batch Insert는 JdbcTemplate을 통해 구현했다.

• 소스 코드

이제 Round 저장 시에 401개의 쿼리가 나간다. Round 저장 로직의 성능을 최적화하는 가장 이상적인 방법은 n회의 Round 저장과, n*m회의 RoundOfMember 저장을 모두 Batch로 처리하여 각각 1회의 쿼리로 해결하는 것이다. 이제 Round 저장 역시 개선해보자.

위에서 언급했듯이 RoundOfMember를 저장하기 위해서는 Round를 먼저 저장하고, 그 id들 역시 가지고 있어야 한다. 하지만, RoundOfMember를 개선했듯이 JdbcTemplate을 통해 Batch Insert를 할 수는 없었다. 왜냐하면 AUTO_GENERATED PK 생성 전략을 쓰고 있는 Round는 Batch Insert 후에 저장된 Round들의 id를 알 수 없기 때문이다.

팀에서 고려한 다른 방법은 다음과 같다.

• DB에서 채번하는 PK 대신 UUID를 식별자로 사용한다. → 이는 index의 크기가 커지면서 DB 성능 저하를 야기할 수도 있다고 생각했다.
• PK 생성 전략 변경을 Sequence로 변경한다. → 우리 팀은 MySQL을 사용하고 있는데, MySQL은 Sequence 전략을 지원하지 않는다.
• PK 생성 전략 변경을 Table로 변경한다.

세 가지 방법 중 위 2가지 방법은 제한되는 부분이 있다고 느껴져서 결국 Table PK 생성 전략을 사용하는 것으로 결정했다.

PK 생성 전략을 Table로 변경한다. Table 전략은 id를 관리하는 하나의 테이블이 존재한다. 해당 테이블은 시퀀스 테이블과 같은 동작을 하고, 이를 조회함으로써 다음 id 값을 알 수 있다. 그렇다고 Round를 삽입할 때 마다 id를 알아내기 위해 매번 시퀀스 테이블을 조회하는 것은 성능 저하가 이어질 것이다.

이를 해결하기 위해 allocationSize를 설정할 수 있다. allocationSize는 시퀀스 테이블에 한 번 접근할 때 가져올 값의 크기이자, 시퀀스 테이블의 값을 얼마나 증가시켜줄지를 의미하기도 한다.

allocationSize가 500이라면, 시퀀스 테이블에 접근할 때 1부터 500까지의 값을 한 번에 가져오고 메모리에서 관리한다. 그리고 Round를 삽입할 때 순서대로 id를 부여한다. 동시에 시퀀스 테이블의 다음 시퀀스 값은 501으로 업데이트된다. 즉 시퀀스 테이블로부터 id를 채번해 올 때, 시퀀스를 조회하는 쿼리 1번, 업데이트하는 쿼리 1번으로 총 2번의 쿼리가 발생한다. 이를 알고 넘어가자.

우리 팀은 JDBC batch size를 500으로 설정했고, 이에 맞춰 allocationSize를 설정했다.

이제 200개의 Round를 Batch Insert 한 번으로 저장한다. 대신 시퀀스를 채번해오면서 발생하는 쿼리 2번이 추가된다.

• 의문점: 메서드 최하단에 entityManager.flush()를 호출하고 있다. 이를 호출하지 않으면 proceedRound()가 두 번 호출되면서 에러가 발생하는데, 아직 원인을 파악하지 못 한 상태이다.

마지막으로 Round 정보를 복사할 때 발생하는 Lazy Loading(RoundOfMember)을 EntityGraph로 해결한다. 이제 N개의 Round를 저장할 때 따라왔던 N개의 Lazy Loading이 발생하지 않는다.

이로써 1600번의 쿼리가 발생하던 Round 저장 로직을 Batch Insert와 @EntityGraph를 통해 2+@번의 쿼리로 개선했다.

• @: allocationSIze에 따라 시퀀스 채번 쿼리가 발생한다.

쓰기 지연 저장소를 활용한 효율적인 Batch Update

이제 4번 과정에 해당하는, 기존 Round 종료 및 다음 Round 시작에서 발생하는 N(100)번의 업데이트 쿼리를 개선하자.

현재는 2번의 round update 쿼리를 쓰기 지연 저장소에서 모아서 쿼리 1번으로 실행하고 있다. 그리고 이를 100번의 for문 내에서 반복하여 총 100번의 쿼리가 실행된다. 즉 2번의 쿼리를 1번으로 줄여서 100번 반복다.

쓰기 지연 저장소를 더 잘 활용한다면 200번의 쿼리를 1번으로 줄여서 실행할 수 있을 것이라고 생각했다.

for문 밖에 리스트를 선언하고, 기존에 for문 내에서 update하던 두 라운드를 리스트에 넣는다. 그리고 for문이 끝난 뒤에 일괄적으로 update함으로써 100개의 쿼리가 한 번에 나가도록 수정했다.

도메인 규칙 활용 및 조회 순서 변경

이제 2번에 해당하는, 다음 Round가 될 수 있는 후보 Round 조회 로직을 개선해보자.

현재는 다음과 같은 흐름이다.

1. 어제 끝나는 Round들을 모두 조회
2. 조회한 Round들에 대해서 반복문을 돌면서, Round가 가지고 있는 studyId와 weekNumber를 기반으로 다음 Round 후보 조회 → 1번에서 조회한 Round 개수 만큼 쿼리 발생!

Round 각각의 studyId와 weekNumber를 활용하기 위해 반복문에서 조회를 하는 게 문제인 상황이다. 그러므로 반복문 안에서 매번 쿼리를 실행하는 게 아니라, 반복문 밖에서 전체 조회를 한 뒤에 for문 안에서는 Java API만을 활용하여 처리하는 것이 좋아 보인다.

2번 과정에서 필요한 studyId는 1번 과정에서 조회한 Round들로부터 얻어낼 수 있다. 이제 weekNumber까지 밖으로 빼내고, studyId와 weekNumber를 매핑하면 된다. 하지만 문제가 있다.

• 3주차 회차가 끝난 1번 스터디 → studyId = 1, weekNumber = 3
• 6주차 회차가 끝난 2번 스터디 → studyId = 2, weekNumber = 6
• 5주차 회차가 끝난 3번 스터디 → studyId = 3, weekNumber = 5
• … → studyId = 5, weekNumber = 10

위와 같이 studyId와 weekNumber 쌍은 스터디마다 제각각일 수 있다. 반복문 내부에서 한 번씩 실행하던 쿼리를 외부에서 한 번에 처리하려면 IN 쿼리를 사용하게 될 텐데, studyId와 weekNumber에 대해 IN 쿼리를 사용한다면 어마어마한 양의 레코드를 조회하게 될 수도 있다.

우리 팀은 이를 도메인 규칙을 활용해서 해결했다. 조회의 목표는 ‘라운드가 끝난 특정 스터디의 다음 Round 후보를 조회하는 것’이다. 그리고 위에서 언급했듯이, 우리 팀에는 다음과 같은 도메인 규칙이 있다.

• 기존에 n주차를 진행하고 있을 때는 n+1주차까지의 회차들이 존재한다.

즉, 현재까지 진행한 Round는 모두 누적되어 DB에 쌓이지만 아직 진행하지 않은 Round는 아무리 많아봤자 다음주까지만 존재한다는 것이다. 아직 진행되지 않은 Round는 RoundStatus라는 컬럼을 통해 쉽게 알 수 있었다.

그러므로 studyId와 RoundStatus라는 컬럼을 통해 조회한다면 weekNumber 컬럼으로 IN 쿼리를 사용하지 않아도 된다.

studyId와 RoundStatus를 통해 조회한 Round를 studyId로 grouping한다. 그리고 기존의 반복문 내에서는 쿼리를 실행하는 대신 grouping한 Map에서 studyId를 통해 후보 Round들을 조회한다.

이제 후보 Round 조회도 한 번의 쿼리로 처리하면서 성능 최적화가 끝났다.

최적화 결과

// before
time spent to proceed Round 
study size: 100
total time spent: 360
The JVM is using 150 MB of memory.

// after
time spent to proceed Round 
study size: 100
total time spent: 85
The JVM is using 153 MB of memory.

스케줄링 시에 실행되는 쿼리의 수가 1,801개에서 5개로 줄었고, proceedRound() 메서드의 실행 시간을 4배 이상 개선했다.

최적화가 완료된 최종 코드는 위와 같다. 이제 리팩터링이 필요해 보인다.

느낀 점

• JPA를 사용하면서 쓰기 지연 저장소, flush 시점 등에 대해 제대로 이해하지 못하고 있었다는 걸 느꼈다.
• 특정 기술을 사용할 때, 필요한 기능을 구현하는 것은 생각보다 쉽다. 하지만 문제가 발생했을 때 빠르게 트러블슈팅을 하는 것은 그 기술의 동작 원리를 잘 이해하고 있을 때 가능한 것 같다. 핵심에 집중하자.

2편에서는 CloudWatch를 적용하며 가지게 된 고민에 대해서 작성한다.

CloudWatch는 기본적으로 많은 지표를 제공한다.

하지만 201에서 모니터링 하고자 했던 지표를 모두 제공하지는 않는 것을 확인했다.

201의 모니터링 툴로 CloudWatch를 적용하고, 추가적으로 우리가 원하는 지표를 추가하며 경험한 내용에 대해 작성한다.

문제 상황

우리가 모니터링하고자 했던 지표는 다음과 같다.

• CPU 사용량
• 메모리 사용량
• 각 엔드포인트 HTTP Request 횟수, 처리 시간

하지만, CloudWatch에서는 기본적으로 메모리 사용량에 대한 지표를 제공하지 않는다.

레퍼런스에 의하면, 메모리 사용량을 기본 메트릭으로 제공하지 않는 이유는 사이클 수를 기반으로 계산할 수 있는 CPU에 비해 메모리는 계산하는 것이 어렵기 때문이다. 운영 체제에서 사용하는 메모리, 애플리케이션에서 사용하는 메모리 등 여러 요인에 따라 메모리 사용량이 달라지기 때문이다.

그리고 HTTP Request 횟수 또한 제공하지 않는다. 다른 팀들의 대시보드를 살펴 보니 네트워크 패킷을 모니터링 하고 있는 팀도 꽤 있었다. 네트워크 패킷을 통해서 요청 횟수를 알 수도 있겠지만, 우리 팀이 원했던 것은 ‘각 엔드포인트마다의 요청 횟수 및 처리시간’ 이었다.

CloudWatch에서 제공하는 네트워크 패킷만으로는 우리가 원하는 디테일한 정보를 알 수는 없었다.

• 이렇게 디테일한 정보를 원한 이유는 엔드포인트마다의 요청 정보를 확인하고, 어떤 API에 대한 성능 개선이 우선시돼야 할지 판단하기 위함이다.

메모리 사용량

먼저 메모리 지표를 추가한다.

전체적인 과정은 다음과 같다.

1. EC2 인스턴스에 IAM 역할 연결
2. EC2 인스턴스에 CloudWatch Agent 설치
3. CloudWatch Agent 설정

핵심은 기본적으로 제공하지 않는 지표를 사용하기 위해, 모니터링 하려는 EC2 인스턴스 내에 CloudWatch Agent를 설치해야 한다는 것이다.

1번 과정인 ‘IAM 역할 연결’ 또한 CloudWatch Agent를 사용하기 위한 과정이다.

CloudWatch Agent를 설치한 뒤에는 설정 파일 마법사를 통해 가이드라인을 제공받을 수 있다. 윈도우 사용 시절 설치 마법사 이후에 매우 오랜만에 들은 마법사다..

이 모든 과정을 하나하나 보여주고 있는 좋은 블로그들이 많아서 참고한 블로그를 올리는 것으로 대신한다.

HTTP Request

다음으로 HTTP Request 관련 지표를 추가한다.

Spring Boot Actuator

201은 스프링 부트 프레임워크를 사용한다. 그리고 스프링 부트는 Actuator를 통해서 많은 메트릭을 엔드포인트로 제공한다.

예를 들어, /actuator/metrics/disk.total 엔드포인트에서는 다음과 같이 총 디스크 용량에 대한 지표를 제공한다.

{
    name: "disk.total",
    description: "Total space for path",
    baseUnit: "bytes",
  measurements: [
        {
            statistic: "VALUE",
            value: 494384795648
        }
    ],
    availableTags: [
        {
            tag: "path",
            values: [
                    "/Users/aaa/Desktop/workspace/wooteco/2023-yigongil/backend/."
                ]
        }
    ]
}

Actuator는 이 외에도 수많은 엔드포인트를 제공하는데 그중에 metrics/http.server.requests라는 엔드포인트도 제공한다.

• 참고: http.server.requests 엔드포인트를 사용하고 싶다면 HttpTraceRepository 의 구현체를 빈으로 등록해야 한다.

해당 엔드포인트가 제공하는 데이터를 살펴보면 다음과 같다. (대부분의 availableTags 생략)

{
    name: "http.server.requests",
    description: "Duration of HTTP server request handling",
    baseUnit: "seconds",
    measurements: [
        {
            statistic: "COUNT",
            value: 4
        },
        {
            statistic: "TOTAL_TIME",
            value: 0.076952749
        },
        {
            statistic: "MAX",
            value: 0.049487458
        }
    ],
    availableTags: [
        {
            tag: "uri",
            values: [
                "/actuator/metrics",
                "/actuator",
                "/actuator/metrics/{requiredMetricName}"
            ]
        }
    ]
}

애플리케이션의 (1) HTTP 요청 누적 횟수, (2) 누적 요청 처리 시간, (3) 요청 처리 최대 시간을 확인할 수 있다.

그리고 availableTags로 uri가 제공된다. 태그를 통해 더 자세한 정보를 확인할 수 있는데, uri 태그는 특정 uri로 온 HTTP 요청 정보만 확인할 수 있게 해준다.

즉, /actuator 라는 URI로 전달된 요청 정보만 확인할 수 있게 해준다.

문제 상황에서 우리는 엔드포인트마다의 요청 정보를 확인하고 싶다고 했다. 그리고 마침 Actuator를 통해 원하는 정보를 얻을 수 있기 때문에, 이 메트릭을 CloudWatch에서 확인할 것이다.

CloudWatch + Actuator 연동

우리의 목적은 Actuator에서 제공하는 메트릭을 CloudWatch에서도 확인하는 것이다. 그렇기 때문에 Actuator의 데이터 를 CloudWatch에 심어줘야 한다.

이때 AWS의 SDK를 사용하여 자바 코드를 통해 EC2 내의 CloudWatch Agent에 데이터를 넣어줄 것이다.

AWS 공식 문서를 확인하면 많은 언어로 SDK를 지원하는 것을 알 수 있다. 자바도 당연히 포함된다.

• SDK for Java Guide
• SDK Code Example

위 문서와 예제 코드를 참고하여 바로 실제 코드를 작성해보자.

실습

(gradle 빌드 기준)

AWS SDK를 사용하기 위해 다음 의존성을 추가한다.

implementation platform('software.amazon.awssdk:bom:2.20.56')
implementation 'software.amazon.awssdk:cloudwatch'

그리고 CloudWatch Agent에 메트릭 데이터를 넣어주는 코드를 작성한다.

import org.springframework.boot.actuate.metrics.MetricsEndpoint;
import org.springframework.context.annotation.Profile;
import org.springframework.scheduling.annotation.Scheduled;
import org.springframework.stereotype.Service;
import software.amazon.awssdk.regions.Region;
import software.amazon.awssdk.services.cloudwatch.CloudWatchClient;
import software.amazon.awssdk.services.cloudwatch.model.Dimension;
import software.amazon.awssdk.services.cloudwatch.model.MetricDatum;
import software.amazon.awssdk.services.cloudwatch.model.PutMetricDataRequest;
import software.amazon.awssdk.services.cloudwatch.model.StandardUnit;

import java.util.List;

import static org.springframework.boot.actuate.metrics.MetricsEndpoint.MetricResponse;
import static org.springframework.boot.actuate.metrics.MetricsEndpoint.Sample;

@Profile(value = {"prod"}) // (1)
@Service
public class CloudWatchMetricsService {

    private static final CloudWatchClient CLOUD_WATCH_CLIENT = CloudWatchClient.builder()
            .region(Region.AP_NORTHEAST_2)
            .build(); // (2)
    private final MetricsEndpoint metricsEndpoint; // (3)

    public CloudWatchMetricsService(MetricsEndpoint metricsEndpoint) {
        this.metricsEndpoint = metricsEndpoint;
    }

    @Scheduled(fixedDelay = 60_000) // (4)
    public void pushMetricsToCloudWatch() {
        MetricResponse metrics = metricsEndpoint.metric("http.server.requests", null); // (5)

        for (Sample sample : metrics.getMeasurements()) { // (6)
            List<String> uris = metrics.getAvailableTags().stream() // (7)
                    .filter(tag -> "uri".equals(tag.getTag()))
                    .flatMap(tag -> tag.getValues().stream())
                    .toList();

            for (String uri : uris) { // (8)
                MetricDatum datum = MetricDatum.builder()
                        .metricName("http.server.requests." + sample.getStatistic())
                        .value(sample.getValue())
                        .unit(StandardUnit.COUNT)
                        .dimensions(Dimension.builder().name("URI").value(uri).build())
                        .build();

                PutMetricDataRequest request = PutMetricDataRequest.builder() // (9)
                        .namespace("yigongil-prod")
                        .metricData(datum)
                        .build();

                CLOUD_WATCH_CLIENT.putMetricData(request); // (10)
            }
        }
    }
}

코드를 하나씩 이해해보자. 위에 첨부한 http.server.requests 엔드포인트에서 제공하는 데이터 포맷을 함께 보면 좋다. 해당 엔드포인트를 requests 엔드포인트라고 칭하겠다.

• (1): 모니터링 하고자 하는 환경은 실제 서비스가 돌아가는 프로덕션 환경이다. 즉, 이 코드는 CloudWatch Agent가 설치되어 있는 환경에서만 돌아가면 되기 때문에 프로필을 설정한다.
• (2): CloudWatch 서비스에 접근하기 위해 사용되는 객체를 생성한다. 해당 객체는 하나만 존재하기 때문에 상수로 관리한다.
• (3): Actuator에서 제공하는 메트릭의 모든 엔드포인트를 가지는 객체다. @Autowired를 통해 주입 가능하다.
• (4): pushMetricsToCloudWatch 메서드를 1분 간격으로 실행한다. 1분마다 메트릭을 CloudWatch Agent로 보내준다고 생각하면 된다.
• (5): 메트릭 중에서 requests 엔드포인트를 가져온다.
• (6): requests 엔드포인트의 Measurements를 가져와 반복문을 실행한다. 이때 Measurements란, 위에서 본 Actuator requests 엔드포인트 응답값에 포함된 Key다. 배열로 COUNT, TOTAL_TIME, MAX에 해당하는 값들을 가지고 있다.
• (7): availableTags를 돌면서 “uri” 태그에 해당하는 값들을 List로 가져온다. 위의 예시에선 다음 값들을 가져온다.
  • "/actuator/metrics"
  • "/actuator"
  • "/actuator/metrics/{requiredMetricName}"
• (8): uri 태그에 속하는 value들을 돌면서 메트릭 데이터를 캡슐화한 객체로 만든다.
  • ex) sample.getStatistic() = “COUNT” / sample.getValue() = 4
  • dimension은 일종의 지표 그룹이라고 생각하면 된다. 현재 예시에선 URI라는 dimension 내에 지표들이 속하게 된다.
• (9): 8번에서 만든 MetricDatum 객체를 CloudWatch Agent에 넘기기 위해 Request 객체로 변환하는 과정이다. namespace를 지정해줘야 한다.
• (10): Request 객체를 CloudWatch Agent에 전달한다.

이로써 자바 코드를 통해 우리가 원하는 지표를 뽑아낸 뒤, CloudWatch Agent가 원하는 형태로 만들어서 최종적으로 전달까지 하는 과정이 끝났다.

이렇게 완성한 코드를 모니터링 하고 있는 EC2 서버에서 빌드 및 실행을 한다면

서버에서 제공하는 엔드포인트(URI)마다 요청과 관련하여 3개의 지표를 가지고 생성된 것을 확인할 수 있다.

이제 이 지표들을 팀에서 원하는 형태로 모니터링 하면 된다.

의문점

우리는 스프링에서 제공하는 스케쥴 기능을 통해 일정 시간마다 지표를 CloudWatch Agent에게 전달하고 있다.

하지만 블로그를 작성하던 중에 MetricDatum 객체가 storageResolution()이라는 메서드를 가지고 있는 것을 확인했다.

해당 메서드의 JavaDoc 설명에선 다음과 같이 설명한다.

Valid values are 1 and 60. Setting this to 1 specifies this metric as a high-resolution metric, so that CloudWatch stores the metric with sub-minute resolution down to one second. Setting this to 60 specifies this metric as a regular-resolution metric, which CloudWatch stores at 1-minute resolution. Currently, high resolution is available only for custom metrics. For more information about high-resolution metrics, see High-Resolution Metrics in the Amazon CloudWatch User Guide. This field is optional, if you do not specify it the default of 60 is used.

원하는 해상도에 따라 1~60 사이의 값을 설정할 수 있다는 것이다. 여기서 해상도란 데이터를 얼마나 촘촘하게 수집할지를 말한다. 데이터를 짧은 주기로 정확하게 수집하고 싶다면 1초 단위로 수집할 것이고, 1분 간격의 추세만 봐도 괜찮다면 60초 단위로 수집하도록 설정할 것이다.

아무튼 이러한 값을 설정하지 않았을 떄의 기본값은 60초라는 것인데, 그렇다면 스케쥴러를 따로 구현하지 않아도 알아서 60초마다 CloudWatch Agent에 지표를 전달할 수 있는 것일까?

AWS에서 제공한 예제 코드를 확인해도 스케쥴러를 따로 구현하지 않은 것을 확인할 수 있다.

현재 짐작하기로는 스케쥴러가 필요 없을 것 같다. 추후에 테스트를 해보며 해당 내용을 확인해보고, 글 내용을 추가해야겠다.

References

CloudWatch 개념

• https://nearhome.tistory.com/134
• https://youtu.be/0vg9nxohKzo 1~3편

AWS 공식 레퍼런스

• https://docs.aws.amazon.com/ko_kr/sdk-for-java/latest/developer-guide/home.html
• https://github.com/awsdocs/aws-doc-sdk-examples

CloudWatch Agent 설치 및 설정

• https://dev.classmethod.jp/articles/try-installing-cloudwatch-agent-on-ec2-instances/

Spring Boot Actuator

• https://www.inflearn.com/course/스프링부트-핵심원리-활용/dashboard

서비스를 개발하며 팀 내 코드 리뷰를 필수로 진행하였고, QA를 거치며 예외 상황에 대비했다. 하지만 실제 유저가 존재하는 환경에서는 예상치 못한 문제가 발생할 수 있다. 그렇기 때문에 몇가지 지표에 대해서 모니터링을 하고자 하였다.

모니터링 툴을 선택하고 적용하며 가졌던 고민들을 두 편에 나눠서 작성할 예정이다. 이번 편에서는 모니터링을 하는 이유, 지표를 선택하는 기준, CloudWatch 선택의 이유에 대해서 알아본다.

모니터링을 왜 할까?

결론부터 말하자면, 오류 발생 원인을 빠르게 찾아내기 위해서다.

모니터링 과정은 간단하게 다음과 같다.

1. 애플리케이션/서버가 실행되며, 몇몇 지표가 생성된다.
   • 이때의 ‘지표’는 CPU 사용량, 메모리 사용량, 디스크 사용량, 서버 상태 등에 해당한다.
2. 생성된 지표를 수집한다.
3. 수집한 지표를 그래프와 같이 보기 편한 형태로 시각화하여 확인한다.

즉, 확인하고자 하는 데이터를 지표로 심고, 해당 지표의 상태 변화를 확인하며 애플리케이션의 상태를 진단하는 것이다.

이러한 모니터링의 필요성을 알아보기 위해, 특정 상황을 상상해보자. EC2 서버에서 스프링 서버를 실행하고 있다고 가정한다.

어느 날, 우리 서비스의 ‘TODO 완료 인증’ 기능이 동작하지 않게 됐다는 제보를 받게 됐다. 이 기능이 동작하지 않는다면 사용자에게 나쁜 경험을 제공하게 될 수도 있다!

재빨리 컴퓨터를 키고, 원인을 파악하기 위해 에러 로그를 확인해 보지만 도저히 원인을 확인할 수가 없다. 결국에는 TODO 완료 인증 기능과 관련된 모든 부분을 점검해 본다..

생각만 해도 답답해진다.

이때 만약 모니터링을 하고 있었다면 어땠을까? CPU 사용량, 메모리 사용량, 디스크 사용량에 대한 지표를 모니터링하고 있었다고 가정하자.

문제 상황을 제보받은 뒤, 에러 로그를 확인한다. 하지만 에러 로그에서 원인을 파악할 수 없게 되자, 모니터링하고 있던 지표를 확인한다.

지표를 확인하던 중, 디스크 사용량에 문제가 발생한 것을 확인하게 된다. 디스크 사용량이 임계 값에 도달하여 더 이상 사용자가 전송하는 이미지 파일을 저장할 수 없게 된 것이다. (TODO 완료 인증 기능은 사용자가 이미지를 업로드한다고 가정)

디스크 여유 공간을 만들었더니 TODO 완료 인증 기능이 다시 정상적으로 동작하는 것을 확인했다.

여기서 핵심은 모니터링을 통해 문제 발생 범위를 좁혔다는 것이다. 모니터링을 하지 않았다면, 모든 범위를 대상으로 문제의 원인을 찾아야 했다. 하지만 모니터링을 하면 기존에 심어 놓았던 지표를 통해 문제가 발생한 부분을 빠르게 확인할 수 있었다.

문제 발생 시점에 원인을 빠르게 파악할 수 있다는 이유 뿐 아니라, 경보(Alarm)를 통해 특정 지표를 기준으로 알람 이벤트를 발생할 수 있다. 이는 문제가 실제로 발생하기 전에 미리 조치를 취할 수 있도록 한다.

• ex) CPU 사용량이 50% 이상이 되면 슬랙 메시지를 전송한다 / 메모리 사용량이 70% 이상이 되면 메일을 보낸다

어떤 데이터를 모니터링 할까?

위에서 봤듯이 문제 발생 범위를 좁히기 위해서는, 문제가 발생할 여지가 있는 데이터를 주시해야 한다.

즉, 의미 있는 데이터를 모니터링 해야 한다는 것이다. 예를 들어 디스크에서 읽기/쓰기 작업이 일어나지 않는 서비스라면 굳이 디스크의 사용량 또는 I/O 성능을 확인할 필요가 없다.

물론 의미 없는 값도 ‘혹시혹시혹시나 나중에 문제 발생할 수 있으니 모니터링 하고 있어야지’ 생각할 수도 있다. 당연히 다양한 지표를 모니터링 할수록 안정성이 높아질 수도 있다.

하지만 첫 번째 문제는 돈이다. AWS에서 제공하는 모니터링 서비스 CloudWatch의 경우, 모니터링하고 있는 지표 수에 따라 요금이 청구된다. 돈까지 내면서 의미 없는 값을 모니터링 하는 것은 굳이…라고 생각한다

개인적인 생각으로는 많은 지표를 수집할수록, 해당하는 데이터를 보내주는 애플리케이션에 부하가 올 것이라고 생각한다. 지표 수집 주기가 너무 짧으면 애플리케이션 성능에 부하가 올 수도 있다는 내용을 들었는데, 이와 비슷한 맥락이지 않을까 싶다.

우리 프로젝트에선..

팀 내에서 어떤 지표를 수집할지 상의한 결과, 필요에 따라 다음 데이터들을 모니터링 하기로 했다.

• CPU 사용량

• 메모리 사용량

  현재 인프라 구조 상, 한 EC2 서버에서 개발 서버와 프로덕션 서버를 동시에 실행하고 있다. 서버에 부하가 커져 CPU 및 메모리 사용량이 급증하고, 서버에 영향을 미치는 문제가 생기는 것을 막고자 함

• HTTP Request 횟수, 처리 시간

  요청이 자주 발생하거나, 긴 처리시간을 가지는 API를 확인하고, 이에 대해 성능 개선을 고려하고자 함

현재는 이정도의 모니터링 계획을 가지고 있지만, 서버 및 사용자의 규모 그리고 새롭게 추가되는 기능 등에 따라 새로운 지표를 모니터링 하게 될 수도 있다.

어떤 툴을 사용할까?

모니터링 툴을 선택하기 위해 조사한 결과, 세상에는 정말 다양한 모니터링 툴이 존재한다는 것을 알 수 있었다.

그 많은 툴 중에서 어떤 것이 우리에게 최선의 선택지인지 판단하는 것은 정말 어려운 일이었다.

일단은 레퍼런스를 쉽게 찾을 수 있는 프로메테우스와 그라파나를 사용하는 방향으로 생각했지만, 문제점을 한 가지 발견했다.

프로메테우스 + 그라파나의 문제점

프로메테우스에서 수집하는 CPU 사용량은 실제값과 차이가 있다.

문제의 원인은 서버가 EC2, 즉, 가상 서버 상에서 존재하다는 것이었다. 가상 서버는 물리 서버의 자원을 가져다 쓰는 CPU 구조를 가진다. 이러한 구조에서 정확한 CPU 사용량을 알기 위해서는 가상화 컨텍스트를 알고 있어야 한다.

다시 프로메테우스로 돌아가면, 프로메테우스는 Spring Boot Actuator를 통해 지표를 수집한다. 하지만 Actuator는 가상화 컨텍스트에 대해 알지 못하기 때문에 가상 서버에서 실제로 자원을 어떻게 할당받고, 얼마나 사용하고 있는지 정확히 알 수 없는 것이다.

즉, 정확한 CPU 사용량을 알기 위해서는 프로메테우스가 아닌 방식을 사용해야 한다.

(더욱 자세한 원리를 알고 싶다면 Stolen CPU, vCPU 라는 키워드로 공부하면 될 것 같다)

CloudWatch

결국 가상 서버의 CPU 사용량을 정확하게 알 수 있는 CloudWatch를 모니터링 툴로 사용하기로 결정했다. CloudWatch는 AWS에서 제공하는 모니터링 서비스로, 이 서비스를 선택한 이유는 다음과 같다.

• EC2 인스턴스가 실행되는 가상화 컨텍스트를 알고 있다. 그렇기 때문에 가상화 환경 내에서 다양한 리소스 사용량을 측정하는 데에 유리하다는 장점을 가지고 있다.
• CloudWatch는 메트릭 수집에 더불어 자체적으로 대시보드를 제공한다. 시각화를 목적으로 그라파나를 따로 사용하지 않아도 된다.

References

CloudWatch 요금

• https://aws.amazon.com/ko/cloudwatch/pricing/

vCpu 관련

• https://yjiwony.tistory.com/10
• https://serverfault.com/questions/420122/why-does-top-report-a-different-cpu-usage-than-cloudwatch

@Override
public Object resolveArgument(
    final MethodParameter parameter,
    final ModelAndViewContainer mavContainer, 
    final NativeWebRequest webRequest, 
    final WebDataBinderFactory binderFactory
)    throws Exception {
  return memberRepository.save(
          Member.builder()
                  .nickname("유민트")
                  .tier(2)
                  .githubId("yujamint")
                  .profileImageUrl("www.yujamint.site")
                  .introduction("자기소개입니다")
                  .build()
  );
}

위와 같이 ArgumentResolver에서 Member 엔티티를 영속화하며 컨트롤러에 전달하고 있다.

그리고 해당 엔티티는 Controller → Service로 전달된다. 그리고 서비스에서는 해당 엔티티의 정보를 수정하고, 수정된 정보를 DB에 반영하려 한다.(UPDATE)

내가 알기론 트랜잭션이 시작되는 시점에 영속성 컨텍스트가 DB 커넥션을 가져오고, 트랜잭션이 끝나는 시점에 DB 커넥션을 반납하고 영속성 컨텍스트도 반환된다.

그렇기 때문에 트랜잭션 내에서 동작하지 않는 ArgumentResolver가 반환한 Member 엔티티는 영속성 컨텍스트 내에서 관리되지 않으며, 변경 감지가 일어나지 않을 것이라고 예상했다.

하지만, 서비스 메서드 내에서 정상적으로 변경감지가 일어나는 것을 확인했다.

OSIV

Open Session In View - Session(EntityManager)을 View까지 열어두겠다.

즉, 원래 트랜잭션이 끝나는 시점에 닫혀야 되는 DB 커넥션, 영속성 컨텍스트를 더욱 오래 열어두겠다는 것이다.

OSIV를 켜놓으면 위와 같이 요청이 들어오고 최종 Response가 나갈 때까지 영속성 컨텍스트, 커넥션이 살아 있는다.

OSIV의 장단점

OSIV를 켜놓았을 때의 장점

• 영속성 컨텍스트를 오래 유지 → 지연 로딩이 가능해진다.

  조회하는 시점에 연관된 모든 엔티티를 불러오지 않고 프록시 객체로 가지고 있다가, 해당 엔티티가 사용되는 시점에 실제 객체를 불러온다. 이는 OSIV를 통해 커넥션을 가지고 있을 때 더 자유롭게 활용할 수 있다.

  만약 OSIV가 꺼져 있다면, 트랜잭션을 선언하는 서비스 내에서 모든 연관 엔티티를 로딩한 채로 컨트롤러에 반환해야 할 것이다.

단점

• OSIV를 키지 않았을 때와 비교하면, 오랜 시간동안 커넥션 리소스를 사용하는 것이기 때문에 리소스 낭비가 발생할 수 있다.

결론

spring.jpa.open-in-view:true 와 같이 OSIV 여부를 설정할 수 있는데, 스프링의 기본 설정은 OSIV를 켜놓는 것이다.

그렇기 때문에 ArgumentResolver에서 가져온 Member 엔티티는 영속성 컨텍스트에 의해 관리될 수 있고, 변경 감지 또한 가능했던 것

+) 이렇듯, OSIV의 사용여부에 따라 ArgumentResolver에서 반환하는 엔티티는 영속 상태일 수도 있고, 준영속 상태일 수도 있다. 그렇기 때문에 이는 실수를 유발하기 매우 쉬운 형태이다. 그렇기 때문에 JPA를 사용한다면, ArgumentResolver에서 엔티티를 반환하지 않는 것이 권장된다.

• 추가로, ArgumentResolver가 Repository를 의존하지 않게 된다.

+) 이 모든 것은 결국 Member의 정보를 수정하기 위한 과정에서 발생한 것이다. 하지만, 멤버 정보 수정은 애플리케이션 내에서 호출 빈도가 큰 비중을 차지하지 않는 기능이다. 그렇기 때문에 해당 기능에서의 더티 체킹만을 위해 OSIV를 켜놓는 것 보다는, 차라리 서비스 내에서 엔티티를 한 번 더 조회하는 것이 좋을 수도 있다.

• 많이 호출되지 않는 기능의 쿼리를 한 번 줄이는 것은 사실상 성능 변화가 미미할 것이다.

References

https://tecoble.techcourse.co.kr/post/2020-11-03-osiv_with_interceptor/

https://kth990303.tistory.com/427 👍

서비스 계층에서 어떤 타입의 객체를 반환해야 할지 따지려면, 서비스 계층 내에서의 의존을 허용할 것인가를 먼저 정의해야 될 것 같다.

서비스 계층 내에서의 의존을 허용하는지 여부에 따라서 다음 두 가지로 구분할 수 있을 것이다.

OrderService 가 존재하고, 외부 서비스에서 주문 관련 기능이 수행되어야 한다고 가정하자.

1. 외부 서비스에서 OrderRepository을 참조한다.
2. 외부 서비스에서 OrderService를 참조한다.

1. Repository를 참조

서비스간의 참조는 없고, 한 서비스 클래스에서 여러 Repository를 참조하는 구조가 될 것이다.

만약 외부 서비스에서 주문이 이뤄진다면, 주문 생성과 관련된 비즈니스 규칙을 모두 검증하는 과정이 외부 서비스에 필요할 것이다. OrderService에 해당 로직이 이미 존재하지만, 서비스는 다른 서비스를 참조하지 않기 때문에 중복코드를 작성하게 되는 것이다.

이는 곧 응집도가 낮아짐을 의미하기도 한다.

위의 예시처럼 외부 서비스에서 주문 관련 로직을 구현하고 있다면, 주문 관련 로직은 한 곳에 모여 있지 않고 여기저기 흩어져 있는 상태가 될 것이다. 만약 주문 도메인 규칙이 변경된다면, 이를 구현하고 있는 모든 서비스 클래스를 수정해야 될 것이다.

💡 복잡한 비즈니스 규칙이 없는, DB 내용을 단순 조회하는 로직이라면?

주문 생성 같은 경우, 비즈니스 규칙이 많이 개입되는 복잡한 로직이다. 그렇다면 단순 조회 작업은 어떨까?

이때는 Repository를 참조해도 괜찮다고 생각한다. 단순 조회이기 때문에 어차피 OrderService에서도 Repository를 단순 호출하는 구조일 것이다. 이는 오히려 서비스간의 순환 참조를 방지할 수 있는 좋은 방법일 것이다.

2. Service를 참조

위의 예시로 돌아와서, 외부 서비스에서 주문을 생성한다면 OrderService의 주문 생성 메서드를 호출할 것이다. 관련 비즈니스 로직은 이미 구현되어 있기 때문에, 호출만 하면 된다. 즉, 서비스 클래스를 재사용할 수 있다.

Repository를 참조할 때 생긴 2가지 문제를 해결할 수 있다.

1. 도메인 로직을 재구현하느라 생기는 중복 코드 X
2. 주문관련 로직은 모두 OrderService를 통해서 이뤄진다 → 응집도 높아짐

이렇게 서비스간의 의존 관계를 가지면서 주의해야 할 점은, 더이상 서비스 계층의 클라이언트는 표현 계층만 존재하지 않는다는 것이다. (순환 참조 관련 문제도 있지만, 이에 대해 중점적으로 다루지는 않는다.)

이와 관련하여, 서비스가 어떤 타입의 객체를 반환하면 좋을지 생각해보자.

서비스 계층에선 어떤 타입의 객체를 반환해야 할까?

DTO를 반환한다면..

서비스 계층 내에서 서비스 클래스를 의존하지 않고, Repository만 의존하는 상황을 생각해보자.

Layered Architecture의 단방향 의존이 잘 지켜진다는 가정 하에, 서비스 계층의 클라이언트는 오직 표현 계층으로 한정된다.

그렇기 때문에 표현 계층이 원하는 형태의 반환값, 즉, DTO를 서비스 계층에서 만들어서 반환해도 괜찮았을 것이다.

(여기서의 DTO는 컨트롤러가 뷰에 응답할 ViewModel일 수도 있고, 도메인 객체를 감싼 DTO일 수도 있다.)

만약 서비스간 의존을 하는 상황이라면? B 서비스는 DTO를 반환하고, A 서비스가 B 서비스를 의존한다고 가정하자.

• A 서비스는 B 서비스의 메서드를 호출하고, DTO를 반환받는다.
• A 서비스는 로직을 수행하기 위해 DTO를 도메인 객체로 변환하는 과정이 필요하다.
• B 서비스를 의존하는 모든 서비스 클래스가 변환 로직이 필요하다 → 중복 코드 발생

DTO를 반환하기 위해 필요한 과정을 각 클래스 입장에서 보면, 다음과 같이 정리할 수 있다.

• B 서비스: 도메인 객체 → DTO 변환
• A 서비스: B 서비스로부터 반환받은 DTO → 도메인 객체로의 변환

DTO를 관리하는 과정에서 상당한 비용이 발생한다고 볼 수 있다.

도메인 객체를 반환한다면..

그렇다면, 서비스가 DTO를 반환하지 않고 도메인 객체를 반환하도록 해보자.

DTO ↔ 엔티티 변환과정이 사라지지만, 도메인 객체가 서비스를 의존하는 표현 계층까지 자연스럽게 전달될 것이다. 이로 인해 생기는 문제는 다음과 같다.

비즈니스 로직을 담고 있는 도메인 객체가 전달됨으로써, 표현 계층에서 비즈니스 로직이 호출될 수 있다. 이는 예상치 못한 결과를 초래한다.

즉, 도메인이 보호받지 못하고, 이를 오용할 여지가 생기는 것이다. 근데 .. 지금 시점에서 나의 생각은 다음과 같다.

1. 컨트롤러가 도메인 객체를 알고 있는 것은 의존 방향에 어긋나지 않는다. 도메인 객체를 View 요구사항에 맞게 변환하는 것은 컨트롤러의 책임으로 봐도 합리적이다.
2. 과연 이러한 일이 쉽게 일어날 수 있을지 의문이 생긴다.

각 계층의 역할에 대해 이해하고 있는 구성원과 함께 작업한다면, 도메인 객체를 오용하는 상황이 쉽게 찾아오지 않을 것 같다. 최악의 경우를 고려하면 충분히 일어날 수 있는 일이지만, 개발의 편의성을 내려놓으면서까지 경계해야 할지는 모르겠다.

(현실에서 보기 힘든 최악의 동료 개발자를 상상하며 쉐도우 복싱을 한다는 느낌을 받았다.)

하지만 DTO를 사용하는 데에도 비용이 발생한다는 것은 누구나 알고 있다. 그럼에도 사용하는 데에는 이유가 있을 것이다.

결론

결국 DTO 관리 비용을 감수하면서도 DTO를 사용할 가치가 있는지를 따져봐야 한다.

DTO의 필요성에 대해 작성한 아티클을 참고해보니, 프로젝트의 주기가 길거나, 팀의 규모가 크다면 DTO를 쓰는 것이 바람직하다고 말한다.

그렇지만 나는 아직 큰 규모의 프로젝트를 경험해보지 않았고, 막 와닿지 않는다. 내가 납득할 수 있는 DTO의 필요성은 도메인 객체를 흘려보내지 않을 수 있다는 것이다. 근데 이 마저도 개발 비용과 비교했을 때에는 의문이 생긴다.

‘도메인 객체를 흘려 보내지 않기 위해 DTO로 전달해야 돼!!’ vs ‘오용될 가능성이 적은데, 관리 비용을 들이면서까지 DTO를 써야 돼?’

너무나도 뻔한 말이지만 두 생각 사이에서 딱 답을 내리기 보다는, 프로젝트 규모와 팀 컨벤션 그리고 도메인에 따라 선택할 수 있는 기준을 만드는 것이 중요하다고 생각한다.

References

https://stackoverflow.com/questions/21554977/should-services-always-return-dtos-or-can-they-also-return-domain-models

http://guntherpopp.blogspot.com/2010/09/to-dto-or-not-to-dto.html

https://martinfowler.com/bliki/LocalDTO.html

우테코 장바구니 협업 미션을 진행하며 외부 서버에 존재하는 MySql에 접근해야 했다.

추가로, 로컬 환경에서 DB 서버로 직접 접근할 수 없는 환경이다.

개발의 편의성을 위해 로컬에서 DB 서버에 직접 접근할 수 있도록 하는 과정에서 많은 삽질을 했다. 같은 삽질을 반복하지 않기 위해 이를 기록하고자 한다.

개발 환경

• 총 3개의 서버 존재

  1. 개발을 진행하는 로컬 서버
  2. 스프링 서버를 띄우는 APP 서버 (AWS EC2)
  3. MySql 서버를 띄우는 DB 서버 (AWS EC2)

• EC2 인스턴스의 보안 그룹 설정으로 인해, DB 서버는 APP 서버에서만 접속할 수 있다.

  즉, 로컬 서버에서는 DB 서버에 다이렉트로 접근할 수 없다.

SSH 터널링이 무엇일까? 왜 필요할까?

(편한 이해를 위해 테스트 DB는 배제하고, 프로덕션에 사용되는 MySql DB만을 언급)

개발의 편의성을 위해 로컬 서버에서도 DB에 접근할 수 있도록 하자.

하지만 보안 설정상, 로컬 서버에서의 접근은 막혀 있다. DB 서버에 접근하는 방법을 모색해야 한다.

이때 ssh 터널링을 이용할 수 있다. ssh 터널링을 간단하게 설명하자면, “출발지에서 목적지로 한 번에 이동할 수 없을 때, 목적지로 이동 가능한 지점을 거쳐서 이동하는 우회 접근 방법”이다.

지하철 노선도를 예로 생각해보자. 우리는 잠실새내역(2호선)에서 석촌역(8호선)으로 이동하고 싶다. 두 역은 노선이 다르기 때문에 바로 이동할 방법이 없다. 이때 석촌역과 같은 노선에 속한 잠실역(2호선, 8호선)을 거쳐서 이동하는 방법, 즉, ssh 터널링을 선택할 수 있다.

이를 현재의 개발환경에 적용해보자.

로컬 서버에서 DB 서버에 접근하고 싶지만, 바로 이동할 수 없다. 그렇기 때문에 DB 서버에 접근 가능한 APP 서버를 우회해서 접근한다.

즉, 로컬 서버 → APP 서버 → DB 서버의 형태로 접근할 것이다.

SSH 터널링 설정

DBeaver, MySql Workbench, DataGrip 등 많은 툴에서 DB 연결 시에 SSH 터널링을 지원한다.

이 글에서는 DataGrip을 기준으로 설명한다. 위 3개의 툴 모두 사용해 본 결과, 설정 방법은 비슷하다.

설정 방법

• Host: DB 서버에 접근하기 위해 우회할 APP 서버의 주소를 입력한다.
  • 우회할 서버, 현재의 APP 서버를 점프 호스트라고도 부른다.
• Port: ssh 연결을 할 것이기 때문에 22번 포트를 사용한다.
• Username: 점프 호스트의 Username을 적는다.
  • 터미널에서 ssh 연결을 할 때, ubuntu@43.~ 를 입력하며 연결했을 것이다. @ 앞 부분이 Username, 뒷 부분이 Host라고 생각하면 된다.
• Private key file: 로컬에서 점프 호스트로 접속할 때 사용하는 key file 경로를 입력한다.

이렇게 설정을 마친 뒤 Test Connection을 해보면, 다음과 같이 SSH 연결에 성공했다는 것을 확인할 수 있다.

삽질의 시작 - root 계정

SSH 터널링은 준비됐다. 이제 로컬에서 DB 서버에 접속되는지 확인만 하면 된다.

접속할 DB 서버의 정보를 입력하자.

• Host: 접속할 DB 서버의 ip를 입력한다. (EC2로 띄운 DB 서버)
• Port: 연결할 DB가 사용하고 있는 포트 번호를 입력한다. MySql은 3306번 포트를 사용한다.
• Authentication: 인증 방법을 선택한다. MySql 계정명 & 비밀번호를 통해 인증한다.
  • User: MySql 계정명
  • Password: 계정의 비밀번호
• Database: 연결할 database를 입력한다. (ex. chess, subway, shopping-order 등.. *생략가능)

모든 정보를 입력했으니 MySql의 root 계정으로 Test Connection해보자.

실패했다.

이유를 찾아보니 root 계정은 많은 권한을 갖고 있기 때문에 기본적으로 localhost에서만 접근이 가능하도록 설정되어 있다.

즉, 보안상의 이유로 DB 서버의 localhost에서만 접근할 수 있는 것이고 나의 로컬 서버에서는 접근이 불가능한 상태다.

root 계정에서 외부 접근을 허용하도록 설정할 수도 있지만, MySql에서 제안하는대로 새로운 계정을 만들어서 외부 접근을 허용하도록 하자.

외부 접근을 허용하는 계정 생성

yuja 계정을 생성했다.

user 조회 결과에서 볼 수 있듯이, yuja 계정은 43.~ ip의 접근을 허용하고 있다.

• 43.~는 APP 서버의 Public ip다.

우리는 ssh 터널링 설정을 했고, 결국 APP 서버를 통해 DB 서버에 접근할 것이다. 그리고 APP 서버의 Public ip 접근을 허용했으니 로컬에서 DB 서버에 접근할 수 있을 것이다!

얼른 접속해보자.

실패했다.

왜 실패했을까? 다시 한 번 짚어보자.

우리는 ssh 터널링을 통해 로컬 서버 → APP 서버 → DB 서버의 흐름으로 접근할 것이다.

첫 번째로, ssh 터널링 설정이 잘 되어 있는 것을 확인했기 때문에 로컬 서버 → APP 서버의 연결은 정상적으로 이뤄졌다.

그리고, DB 서버의 MySql에는 yuja라는 계정을 생성해줬다. 이 계정은 APP 서버의 접근을 허용하고 있다. 그러면 APP 서버 → DB 서버의 연결도 잘 돼야 할텐데..?

진실은 Private IP에..

우리가 간과하고 있는 사실이 있다.

APP 서버와 DB 서버간의 통신은 EC2 인스턴스의 Private IP를 통해서 이뤄진다는 것이다.

두 서버는 같은 VPC 내부에 존재하고, 같은 VPC 내의 통신은 기본적으로 Public IP가 아닌 Private IP를 통해 이뤄진다.

Public ip를 통해 APP 서버에 ssh 연결을 했다. 그렇기 때문에 당연히 MySql에서도 APP 서버의 Public ip 접근을 허용하면 통신이 가능할 것이라고 생각했다.

하지만 실제로는, APP - DB 서버는 서로 Private ip를 통해 통신한다는 것이다!

이제 이 사실을 알게 되었으니 MySql에서도 Private ip의 접근을 허용하도록 하자.

해치웠나…

mint 계정을 생성했다.

mint 계정은 192.~ ip 대역에서의 접속을 허용한다.

APP 서버의 Public ip와는 다르게, Private ip는 192.~ 대역에 속한다. 그렇기 때문에 이제 DB 서버의 MySql 접속에 성공할 수 있을 것이다.

접속해보자!

실패했다.

bind-address 설정

현재처럼 다른 서버의 DB에 접근하려고 하는 경우, 즉 외부에서 접근하는 경우에는 MySql에서 외부 접근을 허용하도록 설정해야 한다.

(OS마다 기본 설정이 다르지만, ubuntu에서의 MySql기본 설정은 로컬호스트 접근만 허용하고 있다.)

외부 접근을 허용하기 위해서는 bind-address를 설정해주면 된다.

MySql 8.0.33 버전, 우분투 환경 기준으로 설정 파일의 경로는 /etc/mysql/mysql.confg.d/mysqld.cnf이다.

해당 파일을 확인해보면 bind-address가 127.0.0.1(localhost)로 설정되어 있는 것을 확인할 수 있습니다. 해당 설정값을 0.0.0.0으로 변경해주면 모든 IP에 대해서 외부 접근을 허용한다.

값을 바꾼 뒤, mysql을 restart하면 다음과 같이 MySql 접속에 성공한다.

마침내 로컬에서 DB 서버로 접근할 수 있게 되었다.

마치며

처음에는 ssh 터널링에 대해서 모른다고 생각했다. 하지만 생각해보니 ssh 연결은 처음부터 잘 되었고, 정말 몰랐던 부분은 다음 2가지였다.

1. MySql의 외부 접근 관련 설정
2. VPC에서의 통신(Private ip를 통한 통신)

누군가에겐 당연한 지식일 수 있지만, 여러 번의 삽질을 하며 몰랐던 정보를 많이 알게 되어 뿌듯하다.

스프링 공식문서를 참고하면, 다음과 같이 설명합니다.

86.3 Initialize a Database Spring Boot can automatically create the schema (DDL scripts) of your DataSource and initialize it (DML scripts). It loads SQL from the standard root classpath locations: schema.sql and data.sql

스프링 부트는 기본적으로 classpath 내에 있는 scehma.sql과 data.sql 파일에 작성된 DDL, DML을 읽습니다. 그리고 해당 스크립트를 통해 데이터베이스를 초기화할 수 있습니다.

이어서, 아래와 같이 설명합니다.

Spring Boot processes the schema-${platform}.sql and data-${platform}.sql files (if present), where platform is the value of spring.datasource.platform. This allows you to switch to database-specific scripts if necessary …

스프링 부트는 schema-${platform}.sql 또는 data-${platform}.sql 파일 또한 처리할 수 있습니다. 이때 ${platform} 값은 application.properties를 통해 각 데이터베이스 벤더사(h2, oracle, mysql)로 설정할 수 있습니다. 이를 통해 사용하는 DB 시스템이 바뀌어도 다른 sql 파일로 갈아끼워줄 수 있습니다.

load할 파일 설정

data-oracle.sql

CREATE TABLE user (
  id NUMBER CONSTRAINT pk_user PRIMARY KEY,
  name VARCHAR2(50) NOT NULL,
  age NUMBER
);

data-mysql.sql

CREATE TABLE your_table_name (
  id INT PRIMARY KEY,
  name VARCHAR(50) NOT NULL,
  age INT
);

같은 내용의 쿼리문을 각각 oracle과 mysql 문법에 맞게 작성한 파일입니다.

application.properties

#spring.datasource.platform=mysql -> deprecated
spring.sql.init.platform=mysql

공식문서에서는 spring.datasource.platform에 platform을 명시해주면 된다고 하지만, 이는 deprecate됐기 때문에 spring.sql.init.platform을 사용하면 됩니다. (IntelliJ가 추천해줌)

application.properties 파일에서 spring.sql.init.platform값을 통해 어떤 파일을 읽을지 선택할 수 있습니다. 현재는 값을 mysql로 설정했기 때문에 data-mysql.sql 파일의 내용을 읽고 데이터베이스를 초기화합니다. DB를 오라클로 바꾸게 되었다면 해당 설정값만 바꿈으로써 그에 맞는 DDL을 실행할 수 있습니다.

참고로, 설정해주는 값은 실제로 존재하는 벤더사가 아니어도 됩니다.

• ex) spring.sql.init.platform=yujamint로 설정 시, data-yujamint.sql 파일 load

+) spring.sql.init.platform=mysql로 설정되어 있을 때, data.sql 파일도 존재하고 data-mysql.sql 파일도 존재한다면 두 파일 모두 적용됩니다.

스크립트를 실행하고 싶지 않다면?

application.properties

#spring.datasource.initialization-mode=always -> deprecated
spring.sql.init.mode=always

마찬가지로, 공식문서에서 설명하는 spring.datasource.initialization-mode는 deprecate됐기 때문에 spring.sql.init.mode를 사용하면 됩니다.

spring.sql.init.mode 설정을 통해 초기화 모드를 설정할 수 있습니다.

• always: 말 그대로 서버를 킬 때마다 작성한 sql 파일을 통해 초기화합니다.
• never: 초기화를 하지 않습니다.

테스트를 위한 In-Memory DB가 아닌, 실제 프로덕션에 쓰일 DB라면 always로 설정을 하여 테이블과 데이터를 세팅하고, 그 뒤로는 never로 설정을 하여 초기화되지 않도록 하는 방법도 고려할 수 있을 것 같습니다.

4주간의 프리코스

최종 코딩 테스트 회고에 앞서, 4주간의 프리코스를 돌아보려고 한다.

프리코스 방식

프리코스 과정에 대해 간단하게 설명하자면, 한 주에 하나의 과제를 진행한 뒤 제출하는 과정을 4주간, 총 4번 진행한다. 과제의 형식은 하나의 프로그램을 만드는 것이다. (숫자 야구 게임, 다리 건너기 게임, 로또 게임 등등...)

피어 리뷰 스터디

나는 위 과정에 추가로 피어 리뷰 스터디를 따로 진행했다. 스터디의 진행 방식은 한 주간 진행한 과제에 대해서 서로의 코드를 리뷰하고, 스터디 시간에는 본인에게 남겨진 코드 리뷰를 함께 보며 이야기를 나누는 시간을 가졌다.

4주간의 과정이기 때문에 코드 리뷰 역시 4번을 진행했는데 코드 리뷰를 진행할 때마다 자신감이 점점 줄어드는 것을 느끼게 되었다.

스터디 팀원 분들의 코드를 보면 클린 코드와 디자인 패턴을 잘 적용하셔서 내 코드와는 비교가 됐고, 내 자신이 팀원 분들에 비해 부족한 실력으로 느껴졌다.

팀원 분들은 이론적으로나, 코드로 구현에 있어서나 지식이 빠삭하다고 느껴졌다. 코드 리뷰를 진행할 때와 스터디 시간이 되어 각자의 코드에 대한 생각을 이야기할 때면 각자의 코드에 대한 근거가 있었고, 깔끔한 코드를 구현하기 위해 고민했다는 것을 느낄 수 있었다.

나는 코딩을 공부하면서 알고리즘 문제를 푸는 데에 대부분의 시간을 썼기 때문에 돌아가기만 하는 코드를 작성했고, 깔끔한 코드를 작성해야겠다는 생각을 해본 적이 없었다.

그러다보니 스터디 팀원 분들이 주관을 갖고 코드에 대한 의견을 나눌 때에도, 피어 리뷰를 남길 때에도 의견을 내기 어려웠고 이야기를 듣는 것이 대부분이었다.

실제로, 내 코드에는 아래와 같이 팀원 분들이 아래와 같은 친절하고 자세한 리뷰를 달아주셨지만, 나는 대부분의 리뷰가 이 코드는 어떤 의미로 작성하신 걸까요?, 와.. 이렇게 구현할 수 있군요.. 아이디어 너무 좋네요!와 같이 질문,칭찬의 리뷰가 대부분이었다. 팀원 분들에게 양질의 리뷰를 제공하여 유익한 정보를 드리지 못한 거 같아 죄송한 마음도 들었다.

이렇게 내 자신이 작아지는 기분과 괜히 죄송한 마음이 점점 쌓여가며 '오늘은 스터디 빠질까..' 하는 생각도 하곤 했지만, 좋은 팀원 분들 덕분에 공부 자극을 받고, 성장을 하고 있다는 느낌을 받았기 때문에 열심히 듣기라도 해야겠다는 생각을 가지고 임했다.

엥?? 1차 합격??

위에서 말했듯이 코딩에 대한 자신감이 많이 떨어져 있었고, '열심히 공부하고 실력 좋은 사람들은 역시나 너무 많구나' 라는 생각을 하며 합격에 대한 기대가 많이 떨어져 있던 나는 1차 합격 여부 통보 메일을 기다리지도 않고 있었다.

그렇게 합격 통보날이 되었고, 아무 생각 없이 휴대폰을 본 나는 메일 어플의 알림에서 축하라는 단어를 볼 수 있었고, 화들짝 놀라 메일을 확인해봤다.

나보다 뛰어난 사람이 너무나도 많다고 느꼈기 때문에 합격 통보는 놀랍지 않을 수 없었다..!

최종 코딩 테스트

최종 코딩 테스트는 합격 통보날의 4일 뒤였고, 합격을 기대하지 않고 있던 나는 그 날 일정이 있었다. 취소하기 힘든 일정이었는데 운 좋게 일정이 취소되면서 맘 편하게 테스트에 응시하러 갔다.

시험장에는 물과 다과(ABC 초콜릿, 칙촉, 화이트하임 등등 엄청 종류가 많았다..!)가 준비되어 있었고, 인당 1개의 펜과 노트까지 주어졌다.

좋은 기업일수록 채용 과정에서 지원자를 배려하고, 편한 환경을 만들어준다는 이야기를 본 적 있는데 어떤 느낌인지 알 것만 같았다.

최종 코딩 테스트는 프리코스와 같은 방식으로, 하나의 프로그램을 5시간 내에 구현하는 것이었다.

하나의 프로그램을 5시간 내에 구현하는 것은 너무 힘들지 않을까 걱정되었는데, 다행히 기존에 프리코스에서 받았던 과제에 비해 볼륨이 작은 느낌이었고 할만하다고 느껴졌다.

시험장 분위기는 내가 생각한 분위기에 비해 자유로웠다. 다른 지원자에게 피해를 주지 않는 선에서 화장실, 다과 이용 모두 아무때나 자유롭게 할 수 있었고, 휴식도 개인의 템포에 맞춰 할 수 있었다. 무엇보다, 이어폰/헤드폰 착용 또한 개인의 자유라는 것이 신기했다.

그렇게 자유로운 분위기였음에도 키보드 타자 소리가 계속해서 들리는 경쟁의 분위기 속에서 코딩을 5시간동안 열심히 진행하고 나오니 진이 빠졌고, 엄청난 해방감 또한 느껴졌다. 시험장을 나오고 나서야 1차 합격이 실감났다. 최종 합격은 우테코를 수료할 때쯤 실감할 수 있으려나?

마치며

나름 열심히 했다고 생각했지만, 타인과 비교하며 내 자신이 작게 느껴지는 경험을 했다. 하지만, 1차 합격이라는 결과를 보자마자 사라졌던 자신감이 돌아오는듯 했다. 역시나 당장에 중요한 것은 결과지만, 당장의 결과에 크게 연연하지 않고 5년,10년 뒤의 미래를 바라보며 과정이 결과를 만든다는 것을 잊지 말자.

현재 기대를 하게 되고 마음이 붕 뜨는 것은 사실이지만, 내 프로그래밍 인생의 최종 목표는 우테코 수료가 아니다. 그러니까, 혹시나 최종 테스트에 불합격하더라도 그에 맞게 계획을 설정하고, 내 길을 묵묵히 걸어가도록 하자.

문제풀이 핵심

왼쪽부터 오른쪽 방향으로 1,2,3번 탑 / 작은 원판부터 큰 원판 순서대로 1,2,...,N번 원판이라고 했을 때,

• N개의 원판을 옮기는 방법은?

    1. N-1개의 원판을 2번 탑에 쌓기
    2. N번 원판 3번 탑에 쌓기
    3. N-1개의 원판 3번 탑에 쌓기

• N개의 원판을 옮기기 위해 N-1개의 원판이 어떻게 옮겨지는지 알아야 한다 -> 재귀를 떠올린다.

    - N = 7일 때, N = 6 호출
    - N = 6일 때, N = 5 호출
    - ...
    - N = 1일 때, 이동

즉, N-1개의 원판을 2번 탑에 쌓아놔야 된다.

N-1개의 원판을 2번 탑에 쌓아놓는 방법은 N-1개의 원판을 3번 탑에 쌓아놓는 방법과 과정이 같다. 이동하는 탑만 다를 뿐.

즉, 같은 로직에서 시작 탑 / 목표 탑이 어딘지만 바꿔주면 된다.

시작 탑 : 이동 전에 위치하고 있는 탑 목표 탑 : 이동 후에 위치하게 될 탑

예를 들어, N=3일 때, 2개의 원판을 2번 탑에 쌓아놔야 한다.

N=2일 때의 답을 구하면 2개의 원판을 3번 탑에 쌓고 끝이겠지만, 현재 N=3일 때의 답을 구하기 위한 것이므로 이를 2번 탑에 쌓는 것으로 목표 탑을 바꾸는 것이다.

그 후에, 3번 원판을 3번 탑에 옮긴 뒤, 다시 2번 탑에 있는 2개의 원판을 3번 탑으로 옮긴다. 2개의 원판을 2번 -> 3번으로 옮기는 것 역시 같은 로직이고 원래 있던 탑, 목표 탑만 바뀌는 것이다.

이를 코드로 옮겨보자.

hanoi(int N, int start, int mid, int to) 함수가 원판을 옮기며 이동 결과를 출력하는 함수라고 했을 때, 내용은 다음과 같다.

N : 옮기려고 하는 원판의 총 개수 start : 시작 탑 - N개의 원판이 처음에 위치하고 있는 탑 mid : 중간 탑 - 시작/중간 탑을 제외하고 남는 탑이라고 생각하면 된다. to : 목표 탑 - 최종적으로 N개의 원판을 위치시킬 탑

N = 1일 때, 원판이 하나뿐이므로 바로 start에서 to로 이동시키며 이동결과를 출력한다.

N != 1일 때,

• N-1개의 원판을 mid로 옮긴다.
• N번 원판을 to로 옮긴다.
• mid에 있던 N-1개의 원판을 to로 옮긴다.

이를 코드로 보면,

• hanoi(N-1, start, to, mid) : N-1개의 원판을 시작 탑에서 중간 탑으로 옮겨 놓는다.
• System.out.println(start + " " + to) : N-1개의 원판을 옮기고 남은 가장 큰 N번 원판을 시작 탑에서 목표 탑으로 옮긴다.
• hanoi(N-1, mid, start, to) : 중간 탑으로 옮겨 놓았던 N-1개의 탑을 목표 탑에 쌓는다.

참고 : N개의 원판을 옮기는 최소 이동 수는 2^N - 1 이다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n;
    static StringBuilder sb;

    public static void hanoi(int N, int start, int mid, int to) {
        if (N == 1) {
            sb.append(start).append(' ').append(to).append('\n');
            return;
        }

        hanoi(N - 1, start, to, mid);

        sb.append(start).append(' ').append(to).append('\n');

        hanoi(N - 1, mid, start, to);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());

        sb.append((int) Math.pow(2, n) - 1).append('\n');
        hanoi(n, 1, 2, 3);

        System.out.println(sb);
    }
}

References

https://st-lab.tistory.com/96 결국엔 해당 블로그 코드를 보고나서야 문제를 해결했다..

하노이 탑 게임 문제 규칙을 찾아내겠다고 시작햇다가 재밌어서 1시간 가까이 했다..

https://secstart.tistory.com/246

가장 인접한 두 공유기 사이의 최대 거리를 출력해야 하는 문제다. 즉, 최소 거리가 최대가 될 때의 거리를 구해야 한다. (가장 약한 놈이 그나마 제일 강할 때를 구하라)

잘못된 첫 접근법

n개의 집에 c개의 공유기를 설치할 때, 가장 인접한 두 공유기 사이의 거리는 공유기 배치를 어떻게 하냐에 따라 달라진다. 그러므로 공유기 배치를 어떻게 할까에 집중했다.

그런데, 도저히 내 머리로는 일정한 규칙을 찾을 수가 없었다. 그나마 내가 생각해낸 아이디어는, 첫 번째 집과 마지막 집에는 공유기를 설치한 상태로 시작하자 정도였다.

하지만, 중간중간에 어떤 집에 공유기를 설치할지에 대해서는 생각해내지 못 하고 결국 풀이법을 찾아봤다.

올바른 접근법

이 문제는 결국, 구해야 하는 최소거리에 집중해야 한다.

우리가 설정한 최소거리 t에 따라 설치할 수 있는 공유기 수가 정해지게 되는데, 우리는 t가 최소 거리중 최대일 때를 찾아내는 것이다.

이렇게 t의 값을 바꿔가며 답을 찾아내는 것이고, t를 바꿔가는 과정에서 이분 탐색을 사용할 것이다.

결국 핵심은 다음과 같다.

0. 입력받은 좌표를 오름차순 정렬하고, 첫 번째 집에 공유기를 설치한 상태에서 시작한다.
1. 최소거리 t를 설정한다.
2. i번째 공유기를 설치한 집으로부터 t 이상의 거리를 두고 있는 집 중, 가장 가까운 집에 i+1번째 공유기 설치한다.
3. 마지막 집까지 2번 과정을 반복한 뒤에 설치된 공유기 수를 확인한다.

이때, 설치된 공유기 수와 가지고 있는 공유기 수를 비교한다. (가지고 있는 공유기 수는 문제에서 입력값 c로 주어진다.)

• 설치된 수 > 가지고 있는 수 : 최소거리를 작게 설정했기 때문에 가지고 있는 공유기의 수보다 많은 양을 설치하게 된다. -> 최소거리를 늘린다.
• 설치된 수 < 가지고 있는 수 : 최소거리를 크게 설정했기 때문에 가지고 있는 공유기를 다 못 쓰게 된다. -> 최소거리를 줄인다.
• 설치된 수 == 가지고 있는 수 : 우리가 결국 구해야 하는 상황인 최소 거리가 최대일 때인지 알 수 없기 때문에 -> 최소거리를 늘린다.

이분 탐색 + 매개 변수 탐색의 과정이다.

중요한 점은, 설치된 수가 c와 같아져도 최대인지 알 수 없기 때문에 최소 거리를 늘리면서 최대일 때를 찾는다는 것이다.

결국, 조건을 부합(설치된 수 == 가지고 있는 수)하지 않기 직전 값을 구하면 된다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        int lo = 1; // 가능한 최소 간격
        int hi = arr[n - 1]; // 입력받은 집들의 최대 간격

        while (lo <= hi) {
            int mid = (lo + hi) / 2; // 최소 거리 설정

            int position = 0; // 공유기 설치 위치(처음부터 시작)
            int cnt = 1; // 설치 가능한 공유기 수
            for (int i = 1; i < n; i++) {
                if (arr[i] - arr[position] >= mid) {
                    position = i;
                    cnt++;
                }
            }

            if (cnt < c) { // 설치된 공유기 수가 가지고 있는 공유기의 수보다 적으면
                hi = mid - 1; // upper bound 내림으로써 최소 거리 줄인다.
                continue;
            }

            //설치된 공유기 수가 가지고 있는 공유기 수보다 크다면
            lo = mid + 1; // lower bound 올림으로써 최소 거리 늘린다.

        }

        // 설치한 수 == 가지고 있는 수가 되었을 때 while문을 끝내지 않고
        // 설치한 수 < 가지고 있는 수가 될 때가 되었을 때 끝냈기 때문에
        // 최소 거리의 최대(조건을 부합하지 않기 직전) 값을 출력하기 위해 1을 빼준다.
        System.out.println(lo - 1);
    }
}

지원 동기

프리코스 1주차 회고에 앞서, 지원 동기에 대해서 곱씹어보았다. 나는 2가지의 큰 목적을 가지고 지원했던 것 같다. 성장과, 도전, 내 자신을 평가하고 싶은 마음이다.

대부분의 지원자는 우테코에 지원하여 합격하고, 과정을 수료하는 과정에서 경험하게 될 개발자로서의 성장을 목표로 지원할 것이라고 생각하고, 나 역시 그러한 목표를 가지고 지원했다.

성장하고 싶은 마음에 더해, 내 자신을 평가하고 싶은 마음도 있었다. 도전이라고도 할 수 있겠다! 휴학을 결심한 뒤로 나름대로 열심히 공부하며 공부 시간만큼은 전보다 많이 늘었고, 여러 부트캠프/동아리에 지원해보며 자소서 작성 능력(나를 어필하는 능력?)도 전보다는 나아졌다고 생각하는데 과연 우테코에도 열정을 가지고 지원하면 합격할 수 있을까? 라는 생각이 들었다. 나는 우테코 4기에도 지원했는데, 그때는 실력이 안 좋을 뿐 아니라 개발 공부에 전혀 열정을 가지고 있지 않았을 때라서 1차 코테에서 광탈했다. 내 나름대로 열심히 공부하고 있다고 느끼는 지금, 나는 우테코가 원하는 인재상에 해당되는 사람인지 알고 싶어졌다.

물론 우테코에 붙고 싶은 마음은 여느 지원자만큼 크고, 내가 실력이 좋다고 생각하며 오만함에 빠져 우테코 선발 과정을 테스트해보겠다거나 하는 마음은 전혀 없다. 비전공자도 뽑는 과정이니만큼, 실력보다도 내가 합격할 수 있을만큼의 열정을 불태울 수 있는가에 대한 도전인 것이다.

1주차 과제

1주차 과제를 진행하며 느낀 점

문제 난이도

문제 유형은 코딩테스트와 유사했고, 총 7문제를 풀어야 했다. 내가 PS에 능한 것은 아니라서 문제 난이도를 논하는 것이 부끄럽지만, 특정 알고리즘을 구현해야 한다거나 하는 문제는 없었고 자바로 코드를 짜본 사람이라면 문제 난이도 자체는 그렇게 어렵지 않게 느껴졌을 것이라고 생각한다.

제일 어려운 문제가 백준 solved.ac 기준 실버3,4쯤이지 않을까 싶다.

과제를 진행하며 신경 쓴 부분

변수명, 메서드명 작명 개발자의 크고 어려운 업무 중 하나가 변수 이름 짓기라는 농담을 들은 적이 있다. 근데 농담이 아니었다는 것을 과제를 진행하며 깨달았다.

나는 다른 누군가가 내 코드를 볼 일이 별로 없었기 때문에, 가독성이 좋은 코드, 클린 코드를 작성해야겠다는 생각을 하지 않고 코드를 작성해왔다. (int는 무조건 num이지 ㅋㅋ) 하지만, 우아한형제들이 코드의 가독성을 중요시한다는 것을 알게 되니 평소 내가 짜던 코드대로 작성할 수가 없었다.

변수,메서드 네이밍 컨벤션을 열심히 찾아가며 변수명,메서드명만 보고도 어떤 의미를 가지는지 짐작이나마 할 수 있도록 작성했다. 이것도 역시 내 기준이기 때문에 남이 본다면 어떨지 모르겠다..

이렇게 고민해가며 네이밍을 하며 느낀 점은

1. 창작의 고통
2. 변수명, 메서드명이 너무 길어진다 그 예시로, 비슷한 닉네임을 가진 크루의 이메일을 찾는 함수를 만들었는데.. 함수명이 findSimilarNicknameCrewEmail이었다. 어떤 의미를 가지는 메서드인지 설명할 수 있는 이름을 짓다보니 길이가 너무 길지는 않은가 싶고, 지금 봐도 괜찮게 작명한 건지 모르겠다.

기능 목록 작성, 기능 단위 커밋 과제 명세서에 기능 목록을 만들고, 기능 단위로 커밋하라는 내용이 있었다.

협업 경험이 적은 나는 그 적은 협업 경험 속에서도 기능 단위로 커밋한 경험이 없었기에 신경을 쓰며 진행해야 됐다.

사실 이 명세는 사람마다 해석이 나뉘는듯 했다. 슬랙의 커뮤니티를 참고했을 때, 1주차 과제의 경우 7개의 문제를 풀어서 제출하는 것이기 때문에 한 문제를 하나의 기능으로 보고 총 7번의 커밋만 하면 된다는 해석, 하나의 문제 속에서 구현할 기능을 각각 커밋해야 되기 때문에 7번 이상의 커밋을 해야 된다는 해석으로 나뉘었다.

나는 처음에 전자의 입장이었지만, 후자의 얘기를 들으면서 각각의 기능 별로 커밋을 하는 열정을 보여서 나쁠 것 없다는 생각에 후자를 택했다.

모듈화 변수,메서드명 작명과 같은 맥락으로 클린 코드를 작성하기 위해 모듈화에도 신경썼다.

변수명 작명, 기능 단위 커밋과 비교했을 때 모듈화는 그나마 신경을 덜 써도 됐다. 왜냐하면, 기능 목록을 작성하고 보니 그 기능대로 모듈을 만들면 됐기 때문이다.

이것이 우테코가 의도한 바가 아닐까 생각했다. 기능 목록을 만들어 놓고 보니, 기능 별로 구현을 하게 되고 자연스럽게 모듈화를 하게 되는 것 말이다.

그 외

채점을 이렇게 할 수 있다고?..

1주차 과제를 끝내고 제출하며 신기하다고 느낀 부분이 있다. 과제 제출은 과제를 완료한 뒤에 내 github repository에서 우테코의 repository에 Pull Request를 하고, 웹사이트를 통해 다시 한 번 제출해야 하는 구조다.

근데 !!

웹 사이트를 통해 과제를 제출할 때, Pull Request 주소를 첨부하면 자동으로 코드를 실행하여 테스트를 진행한다.

나는 이게 신기했다. 코드를 따로 제출해야 되는 건가 하고 들어갔는데 Pull Request 주소만 제출하면 알아서 코드를 실행한다는 것이 신기했다. 다른 사람에겐 별 거 아닐 수 있지만, 나에게는 이러한 디테일이 '역시 우테코인가..'라고 생각하게 만들었다.

전반적인 느낌

우테코는 프리코스만으로도 얻어갈 것이 많고 도움된다는 얘기를 들은 적이 있다. 프리코스를 진행하기 전까지는 체감하지 못 하고 있었는데, 참여해보니 왜인지 알 것 같다.

클린 코드를 지향한다는 점에서 가장 크게 느꼈다. 나처럼 협업의 경험이 적고, 프로그래밍 학습 이력이 그렇게 길지 않으며 남이 보지 않는 코드만 작성하는 사람들은 클린 코드를 의식하며 코딩할 일이 많지 않다고 생각한다.

그런 사람들도 우테코가 지향하는 바를 알고 있고, 우테코에 열정을 가지고 있다면 가독성 좋은 코드를 짜기 위해 노력할 수 밖에 없다.

나는 하나의 문제를 풀면서, 문제를 어떻게 풀어나가야 좋을지에 대한 고민은 한 적이 많았지만 변수명, 메서드명을 어떻게 의미 있게 작명할지와 가독성 좋은 코드를 짤지에 대한 고민은 한 적이 없었다. 이렇게 신경 쓰지 않았던 부분에 대해서 일깨워준 것만으로도 내 부족함을 깨닫는 좋은 경험을 했다고 생각한다.

고작 1주차 진행하면서도 이렇게 느낀 점이 많으니, 남은 3주도 열심히 참여하여 비록 합격하지 않더라도 많은 것을 얻어갈 수 있도록 해야겠다.

프로젝트 생성

1. H2 데이터베이스 설치
   • 매우 가볍기 때문에 실습용 DB로 매우 적절하다.
   • 웹용 쿼리툴 제공
2. Maven 프로젝트 생성
   • 자바 라이브러리, 빌드 관리
   • 라이브러리 자동 다운로드 및 의존성 관리

pom.xml : 설정 파일

• <dependencies> </dependencies> 안에 필요한 라이브러리 넣으면 된다.
  • org.hibernate : hibernate-entitymanager 받으면 필요한 파일 땡겨온다.

📌 라이브러리 버전 선택하는 방법 (hibernate 기준) 내가 사용하려는 스프링부트 버전의 Reference 문서에 들어가서 org.hibernate를 검색해서 쭉 내려보면 해당 스프링부트 버전에 맞는 hibernate 버전이 나온다. 이를 선택하면 된다.

JPA 설정

persistence.xml : JPA 설정 파일

• src/resources/META-INF/persistence.xml 파일 생성
• <persistence version = 2.2 ~ > : JPA 버전이 2.2라는 것을 의미한다.
• <persistence-unit name="hello"> : 데이터베이스 이름은 “hello”로 할 것이다~
• 필수 속성을 넣어줘야 된다.
  • 어떤 DB 드라이버 쓸지
  • username
  • password
  • 접근 url
  • hibernate.dialect : 어떠한 DB를 사용한다고 알리는 것. → DB 방언 지정
• javax.persistence로 시작 : JPA 표준 속성
• hibernate로 시작 : 하이버네이트 전용 속성

데이터베이스 방언

• JPA는 특정 DB에 종속적이지 않다. → 어느 DB를 사용해도 무방하다.
• 그러나 각각의 DB가 제공하는 SQL 문법과 함수는 조금씩 다르다.
• SQL 표준을 지키지 않는 특정 데이터베이스의 문법, 고유한 기능을 방언이라고 부른다.
  • 가변 문자 : MySQL - VARCHAR / Oracle - VARCHAR2
  • 문자열 자르는 함수 : SQL 표준 - SUBSTRING() / Oracle - SUBSTR()
  • 페이징 : MySQL - LIMIT / Oracle - ROWNUM

JPA 구동 방식

• JPA 내의 Persistence라는 클래스가 persistence.xml 설정 정보를 읽어서 EntityManagerFactory 라는 클래스를 생성한다.
  • (Java)Persistence.createEntityManagerFatory() 함수에 persistence.xml 파일에서 설정한 unit-name 인자로 주면서 생성한다.
• EntityManagerFactory에서 필요할 때마다 EntityManager 를 생성해서 사용한다.
  • (Java)emf.createEntityManager() : EntityManager 생성
  • EntityManager를 Java의 Collection과 같이 생각해도 된다.
  • 고객의 요청이 올 때마다 EntityManager를 생성했다가 다 쓴 뒤엔 닫아준다.
    • 쓰레드간에 공유하면 절대 안 된다.
• EntityManager 사용이 끝나면, 꼭 닫아준다.
  • EntityManager는 DB Connection을 계속 달고 있기 때문에 닫아줘야 한다.

EntityManagerFactory는 애플리케이션이 load될 때, 하나만 만들고 하나의 트랜잭션마다 EntityManager를 생성해서 처리한다.

JPA에서 데이터 변경은 무조건 트랜잭션 안에서 일어나야 된다. 그렇기 때문에, em을 받는 것으로 끝이 아니라, em.getTransaction()을 통해 트랜잭션을 얻고, 시작해준 뒤에 데이터 수정을 하면 된다. (끝난 뒤에는 트랜잭션.commit() 을 통해 변경사항 DB에 반영)

작업에 문제가 생긴다면, 트랜잭션을 commit하지 않기 위해서 try-catch문 안에 코드를 작성한다.

JPA CRUD

• 저장 : em.persist(member)
• 조회 : em.find(Member.class, 1L(PK))
• 삭제 : em.remove(member)
• 수정 : member.setName("helloJPA") → setter로 이름을 바꿔주기만 해도 DB에 적용된다.
  • JPA를 통해서 엔티티를 가져오면 JPA가 해당 엔티티를 관리한다. 그리고, 트랜잭션이 커밋되는 시점에 JPA가 관리하는 모든 엔티티에 변화가 있는지 체크한다. 만약 변화가 있다면, 트랜잭션 커밋 시점 직전에 UPDATE 쿼리를 날리고 커밋한다.

전체 회원 조회, 이름이 같은 회원 검색 등 조건이 붙은 조회는?

: 가장 단순한 조회 방법인 JPQL을 사용한다

• JPA에서 제공하는 SQL을 추상화한 객체 지향 쿼리 언어
  • JPQL은 엔티티 객체를 대상으로 쿼리
  • SQL은 데이터베이스 테이블을 대상으로 쿼리

List<Member> result = em.createQuery("select m from Member as m", Member.class)
        .getResultList();

일반 쿼리문과는 다르다.

• JPA에서는 코드를 짤 때 절대 테이블을 대상으로 쿼리를 작성하지 않는다. Member 객체(엔티티 객체)를 중심으로 쿼리를 작성한다.
• pagination 가능하다.
  • .setFirstResult()
  • .setMaxResult()

검색을 할 때, 테이블이 아닌 엔티티 객체를 대상으로 검색하지만 모든 DB 데이터를 객체로 변환해서 검색하는 것은 불가능하기 때문에 애플리케이션에서 필요한 데이터만 DB에서 불러오려면 결국 검색 조건이 포함된 SQL이 필요하다.

객체와 테이블을 생성하고 매핑하기

1. 자바 객체 클래스에 @Entity 꼭 넣기
   • 애플리케이션이 로딩될 때, JPA가 해당 클래스를 인지하고 관리해야겠다고 인식함
2. PK(Primary Key)에 @Id 어노테이션
   • 어노테이션은 웬만하면 javax.persistence 의 어노테이션 선택
3. DB 테이블 이름은 USER이고, 저장하려는 객체의 Class 이름이 Member로 다르다면 @Table(name = "USER") 와 같이 어노테이션을 작성해준다.
   • 쿼리가 나갈 때, USER 테이블에 가도록 함
4. DB의 Column과 객체의 필드명이 다르다면, @Column(name = "username")과 같이 어노테이션 작성

References

김영한 님 '자바 ORM 표준 JPA 프로그래밍 - 기본편'

현재 데이터베이스 세계의 헤게모니는 관계형 DB이다! (Oracle, MySQL)

헤게모니 : 우두머리의 자리에서 전체를 이끌거나 주동할 수 있는 권력.

그렇기 때문에, 현재는 객체를 관계형 DB에 저장하고 관리해야 되는 시대다.

근데, DB는 SQL만 알아들을 수 있기 때문에 결국 계속해서 SQL을 작성해야 된다.

그렇다면, SQL 중심적인 개발의 문제점은?

• 무한 반복, 지루한 코드
• 객체 CRUD - 필드 추가 : 객체에 필드를 추가하면 각 sql문에도 이를 모두 추가해줘야 된다.

→ SQL에 의존적인 개발을 하기 어렵다.

패러다임의 불일치

객체가 나온 사상과, 관계형 데이터베이스가 나온 사상이 너무나도 다르다.

• 관게형 데이터베이스 : 데이터를 잘 정규화해서 보관하는 것이 목표
• 객체 : 필드와 메서드를 묶어서 캡슐화하는 것이 목표

그렇지만, 위에서 말했듯이 현재는 관계형 DB를 메인으로 사용하는 시대이기 때문에 가장 현실적인 대안은 객체를 관계형 DB에 저장하는 것이다.

즉, 객체를 관계형 DB에 저장해야 되고, 객체를 SQL로 변환해야 된다. 그렇다면, 이러한 작업을 SQL 매퍼( == 개발자)가 하는 것이다.

객체와 관계형 데이터베이스의 차이

1. 상속 : 관계형 DB에는 상속 관계가 없다.
   1. Table 슈퍼타입, 서브타입이라는 비슷한 개념은 존재한다.
2. 연관관계 : 객체는 참조를 통해 필요한 정보를 가져오고, 관계형 DB에는 PK와 FK를 통해 조인을 해서 정보를 찾는다.
   1. A라는 객체가 B라는 객체를 필드로 가지고 있을 때, A.getB()를 통해 B에 접근할 수는 있지만 B에서 A로는 접근할 수 없다. 즉, 한 방향으로만 접근할 수 있다.
   2. 하지만, 테이블은 FK를 통해 조인하기 때문에 양방향으로 접근이 가능하다.

객체 그래프 탐색 : 객체는 .get() 이나 . 을 통해서 관계가 있는 객체를 자유롭게 접근할 수 있어야 한다.

하지만, DB에서는 처음 실행하는 SQL에 따라 탐색 범위가 결정된다.

• Member와 Team과 Order가 연관관계를 가지고 있는데, SQL을 작성할 때, Member와 Team으로만 조인한 결과값을 가져오게 되면 Member는 Order와 연관관계를 가지고 있음에도 Member를 통해 Order에 자유롭게 접근할 수 없게 된다.

계층형 아키텍처 : 다음 계층에 대해서 신뢰를 가지고 있어야 하는데, DB에서 가져온 결과값이 어떤 탐색 범위를 가지고 있는지 직접 코드를 까보기 전까지는 알 수 없다. 그렇기 때문에 진정한 계층형 아키텍처에서의 진정한 의미의 계층 분할이 어렵다.

1. 비교하기 : 같은 식별자로 두 객체를 테이블에서 조회했을 때, 두 객체가 같은지 확인하면 다르다는 결과를 확인할 수 있다. 하지만, Java Collection에서 두 객체를 get 해서 같은지 검사하면 참조값이 같기 때문에, 같다는 결과를 확인하게 된다.
   1. 즉, Java Collection에서 객체를 다룰 때와 SQL에서 객체를 다룰 때 중간에 Mismatch가 발생한다는 것을 알 수 있다.

객체답게 모델링 할수록 매핑 작업만 늘어나기 때문에 SQL에 맞춰서 객체를 설계할 수 밖에 없게 된다.

그렇다면 객체를 자바 컬렉션에 저장하듯이 DB에 저장할 수는 없을까? → JPA

JPA란? (Java Persistence API)

자바 진영의 ORM 기술 표준

ORM?

• Object-relational mapping(객체 관계 매핑)
• 객체는 객체대로 설계
• 관계형 DB는 관계형 DB대로 설계
• ORM 프레임워크가 중간에서 매핑!
• 대중적인 언어에는 대부분 ORM 기술이 존재

JPA 동작

JPA는 애플리케이션과 JDBC 사이에서 동작하며, 객체와 관계형DB의 패러다임 불일치를 해결한다.

• 저장
  1. Java 애플리케이션에서 JPA에게 Member 객체를 넘긴다.
  2. JPA가 Member 객체를 분석해서 적절한 Insert 쿼리를 생성한다.
  3. JPA가 JDBC API를 사용해서 DB에 쿼리를 보내고, 결과를 받는다.
• 조회
  1. JPA가 Member 객체를 보고 적절한 Select 쿼리를 생성한다.
  2. JDBC API를 통해서 DB에게 결과를 받은 뒤에 이를 객체에 매핑한다.

JPA의 역사

과거에 EJB라는 자바 표준 ORM 기술이 있었다. 이는 인터페이스를 매우 많이 구현해야 하고, 속도가 느리고 성능이 좋지 않다는 여러 단점이 있었다.

이를 해결하기 위해 하이버네이트라는 오픈 소스 프레임워크가 개발되었다. 자바 측에서 이러한 하이버네이트를 복사-붙여넣기 하듯 만든 표준 ORM이 JPA다.

• 하이버네이트를 다듬어서 만들었다.

JPA 표준 명세

JPA는 인터페이스의 모음이다. 이를 구현한 3가지 대표적인 구현체는 다음과 같다.

• 하이버네이트(8~90% 사용), EclipseLink, DataNucleus

JPA 2.0 이후로는 대부분의 기능이 잘 작동한다.

JPA를 왜 사용해야 하는가?

• 생산성 : CRUD 기능이 이미 만들어져 있어서 한 줄로 구현 가능하다.
  • 수정의 경우에는 member.setName(”변경할 이름”)만 작성하더라도 DB에 변경 사항이 적용된다.
  • 마치 Java Collection에서 객체를 다루듯이
• 유지보수
  • 기존 : 필드 변경시 모든 SQL이 수정해야 된다.
  • JPA : 필드만 추가하면 된다. SQL은 JPA가 알아서 처리한다.
• 객체-관계형DB 패러다임 불일치 해결
  • 상속 : Item 클래스를 상속하고 있는 Album 클래스 객체를 저장하려고 할 때, jpa.persist(album) 코드 하나만 작성하면 나머진 JPA가 알아서 처리해준다.(ITEM 테이블과 ALBUM 테이블에 Insert 쿼리 각각 날려준다.) → 조회 등 나머지 작업에서도 마찬가지
• 연관관계, 객체 그래프 탐색 : 테이블에서 JPA를 통해 가져온 객체로 연관관계를 가지는 모든 객체에 자유롭게 접근할 수 있다.
  • Member 객체를 가져왔고, 이를 통해서 Order 객체에 접근하려고 하면 그 시점에 JPA가 알맞는 쿼리를 날려준다(지연 로딩) → 다음 계층을 신뢰할 수 있게 된다.
• 비교하기 : 동일한 트랜잭션에서 조회한 엔티티는 같음을 보장한다
  • JPA를 통해 같은 식별자로 두 객체를 조회하면 두 객체는 같은 객체다.

JPA의 성능 최적화 기능

중간 계층에서는 다음과 같은 일을 할 수 있다.

• 모아서 쏘는 버퍼링
• 읽을 때 캐싱하기

중간 계층에 존재하는 JPA 역시 이와 같은 기능을 통해 성능을 더욱 끌어올릴 수 있다.

1. 1차 캐시와 동일성 보장

   1. 같은 트랜잭션 안에서는 같은 엔티티를 반환한다. - 캐싱과 비슷한 개념. 하지만, 매우 짧은 시간(한 트랜잭션)만 유지되므로 큰 성능 향상을 기대하긴 어렵다.

2. 트랜잭션을 지원하는 쓰기 지연(버퍼링)

   Insert 쿼리를 3개 보내고 싶을 때, 이를 하나씩 3번 보내는 것은 네트워크를 3번 타야 되기 때문에 한 번에 3개를 모아서 보내도록 할 수 있다.

3. 지연 로딩과 즉시 로딩

   1. 지연 로딩 : 객체가 실제 사용될 때 로딩

   2. 즉시 로딩 : JOIN SQL로 한 번에 연관된 객체까지 미리 조회

      JPA에서는 지연 로딩, 즉시 로딩을 옵션을 통해 선택할 수 있다. → 상황에 따라 전략적으로 설계 가능하다.

ORM은 객체와 RDB 두 기둥 위에 있는 기술이다. 그렇기 때문에, 두 개념을 모두 밸런스 있게 알고 있어야 한다. (김영한님은 관계형 DB가 더 중요하다고 생각한다.)

References

김영한 님 '자바 ORM 표준 JPA 프로그래밍 - 기본편'

작성한 함수가 정상적으로 작동하는지 확인하기 위해 설계하는 코드

📌 TDD : 함수를 구현하기 이전에 함수에서 발생할 수 있는 예외 시나리오를 모두 생각한 뒤에 이를 바탕으로 코드 설계하는 개발 방법

테스트 함수를 먼저 구현한 뒤에 기능을 구현하면 속도는 느려질 수 밖에 없지만, 프로그램의 오류를 미리 고려하고 구현하기 때문에 안정성을 높일 수 있다.

테스트 종류

• Integration Test(통합 테스트) : 모듈 간의 호환성 확인하기 위해 수행하는 테스트
• Unit Test(단위 테스트) : 하나의 모듈을 기준으로 독립적으로 진행되는 가장 작은 단위의 테스트
  • 여기서의 모듈은 애플리케이션에서 작동하는 하나의 기능 또는 메소드

단위 테스트

== 유닛 테스트

특징

• 해당 부분만 독립적으로 테스트하기 때문에 어떤 코드를 리팩토링하여도 빠르게 문제 여부를 확인
• 함수와 메소드에 대한 모든 테스트 케이스가 통과하는지 확인하는 절차

좋은 테스트란?? (FIRST)

Fast: 테스트는 빠르게 동작하여 자주 돌릴 수 있어야 함
Independent: 각각의 테스트는 독립적이며 서로 의존해서는 안됨
Repeatable: 어느 환경에서도 반복 가능해야 함
Self-Validating: 테스트는 성공 또는 실패로 bool 값으로 결과를 내어 자체적으로 검증되어야 함
Timely: 테스트는 적시에 즉, 테스트하려는 실제 코드를 구현하기 직전에 구현해야 함

📌 given-when-then 패턴

• 1개의 단위 테스트를 3가지 단계로 나누어 처리하는 패턴이다.
  • given (준비) : 어떠한 데이터가 준비되었을 떄
  • when (실행) : 어떠한 함수를 실행하면
  • then (검증) : 어떠한 결과가 나와야 한다.

JUnit5

자바에서는 JUnit5와 AssertJ를 함께 이용해서 테스트를 진행한다.

테스트 인스턴스 라이프사이클

• @BeforeAll : 클래스 맨 처음에 실행
• @AfterAll : 클래스 맨 끝에 실행
• @BeforeEach : 테스트 하나 시작할 때마다 실행
• @AfterEach : 테스트 하나 끝날 때마다 실행

: 컬렉션이나 배열의 원소를 흐름으로 간주하는 것

함수형 프로그래밍

: 수학적 함수의 계산을 통해 자료를 처리하고 상태와 가변 데이터를 멀리하는 프로그래밍 패러다임

함수형 프로그래밍이기 위한 조건,특징

• 함수의 순수성 : 동일한 인자를 통해 다수 호출되는 함수들은 항상 동일한 값을 반환
  • 함수 실행하는 동안 side effect 존재하지 않는다.
    • side effect?
    • 함수 외부에 정의된 변수를 수정
    • 콘솔 출력
    • 예외 발생
    • 파일 입출력
  • 함수 실행하기 위한 상태가 없다.
• 함수는 일급이며 고차일 수 있음
• 변수의 불변
• 함수의 참조 투명성
• 람다 미적분 기반

외부 반복자와의 차이

• 외부 반복자(for, while)의 경우에는 반복해서 컬렉션 요소에 직접 접근하며 어떻게 구현해야 될지를 중심적으로 생각해야 되지만, 내부 반복자(stream)의 경우에는 컬렉션 내부에서 요소를 반복시키고, 개발자는 요소당 처리할 코드만 작성하면 된다. 즉, 객체를 통해 무엇을 할지를 중심적으로 생각할 수 있다.

  하지만, stream에 내부적으로 이미 구현돼있는 함수를 사용하는 것이기 때문에, 기능 사용에 있어서 제한될 수 있다.

• stream()은 순수함수이기 때문에 병렬 처리가 가능하다.

스트림 얻기

• 컬렉션 스트림 얻기 : 컬렉션에는 이미 스트림이 구현되어 있다. list.stream()과 같이 사용하면 된다.
• 배열 스트림 얻기 : Arrays.stream(int [] arr) 과 같이 사용
• 숫자 범위 스트림 얻기 : IntStream stream = IntStream.rangeClosed(1, 100);

스트림 파이프라인

여러 개의 스트림이 연결된 구조 컬렉션/배열.스트림얻기().중간스트림().중간스트림().최종처리()

• 대량의 데이터를 가공해서 축소하는 것을 리덕션이라고 한다.
  • 합계, 평균값, 최소값, 최대값 등이 대표적인 리덕션 결과물
• 중간 스트림이 생성될 때, 요소들이 바로 중간 처리(필터링,매핑,정렬) 되는 것이 아니라 최종 처리 시작되기 전까지 중간 처리는 지연되었다가 최종 처리가 시작되면 컬렉션 요소가 하나씩 중간 스트림에서 처리되고 최종 처리까지 오게 된다.
  • lazy loading!

• 반환값이 스트림 형태
• 메소드 종류
  • 필터링 / 중복제거 filter, distinct
  • 매핑 flatMapXXX, mapXXX, asDobuleStream()
  • 정렬 sorted
  • 중간 결과물 반복 peek

• 반환값이 기본타입이거나 OptionalXXX

  • Optional 클래스 : 반환 값이 있을 수도 있고, 없을 수도 있을 때 사용한다.

    OptionalDobule optional = list.stream().mapToInt(Integer :: intValue).average();
    System.out.println(optional.isPresent() ? optional.getAsdouble() : "0.0"); 

  • optional에 값이 들어있다면 출력, null이라면 “0.0” 출력하는 코드

• 메소드 종류

  • 매칭 allMatch, anyMatch, noneMatch
    • 리턴 타입이 boolean
  • 기본 집계 count, max, min, average, sum, findFirst
  • 수집 collect
  • 최종 결과물 반복 forEach

배열은 크기가 정적이기 때문에 추가 연산시 자리가 부족한 상황이 발생하는 한계가 있다.

ex) 크기가 5인 배열이 꽉 차 있을 때, 원소를 하나 더 추가하고 싶다면 다음 과정을 직접 구현해야 한다.

• 크기 늘린 배열 새로 생성
• 기존 배열 복사
• 새 원소 삽입

Collection을 이용하면 배열을 동적으로 변경해서 사용할 수 있다.

• 왜 프레임워크? : 컬렉션을 이용하면 컬렉션 내부에 구현된 메소드만 사용할 수 있기 때문에 프레임워크라고 명명한다.

주요 인터페이스

• List

  • 순서 유지

  • 인덱스 존재

  • 구현 클래스

    • ArrayList

      • 배열 이용해서 원소 유지
      • 사이즈 부족하면 50% 크기 늘림(자바에서)
      • 주소 연속적으로 증가한다.(순차적으로 주소 할당)
        • {1, 2, 3, 4} 의 주소 ⇒ {100, 200, 300, 400} 과 같이 순차적으로

    • Vector (Synchronized)

      Sycnhrnoized를 유지하는 List

      : 두 스레드간의 공유 객체가 있을 때, 동시에 DB에 접근하여 일관성을 해치지 않도록 하기 위해 순서를 만들어주는 Sycnhronized 키워드로 모든 메서드가 구현되어 있다.

      동적 배열을 의미하는 “Re-sizable Array”와, 동시성을 의미하는 “Synchronization”

      • 모든 메서드가 동기화를 하며 동시성을 챙기다보니 Vector를 사용하면 시간이 저하되고, 애플리케이션의 성능이 떨어진다.
      • 그렇기 때문에 Vector보다는, (동적 배열)한 가지만 구현한 ArrayList를 사용하다가 동기화가 필요할 때마다 Collections.synchronizedList()을 사용하는 게 더 유연성 있고 좋은 방법이다.

    • LinkedList

      원소 추가/삽입 성능이 향상된 List이다.

      원소의 추가나 삭제하는 동안 인덱스가 물리적인 주소의 순서와 달라질 수 있기 때문에 다시 제일 앞의 노드부터 돌면서 인덱스를 부여하는 작업이 필요함

      • 0번째 인덱스는 100번지에 있고, 1번쨰 인덱스는 200번지에 있고~ 등 각 인덱스마다의 주소를 매핑해놓는다. → 매핑해놓았기 때문에 원소 추가/삽입이 훨씬 빠르다.

      • but, 추가/삽입 연산 일어날 때마다 JVM이 인덱싱(테이블) 업데이트하는 시간이 있고, 주소가 연속적이지 않기 때문에 원소를 검색하는 시간이 느리다.

      • vs ArrayList*

        ArrayList는 인덱스를 통해 바로 원소의 위치를 아는 것이 가능하다.

      • 처음 시작 주소 + i * (int형 바이트)

        즉, 인덱싱이 빠르다 == 검색이 빠르다.

• Set

  • 집합 개념

  • 인덱스라는 개념이 없다 → 순서 유지 보장 X

  • 원소 중복 불가

  • 구현 클래스

    • HashSet

      해싱된 값에 따라서 주소가 할당되기 때문에 순서가 유저되지 않는다.

    • LinkedHashSet

      데이터가 삽입된 순서를 저장함으로써 순서가 유지된다.

• Map

  • 인덱스라는 개념이 없다. → 순서 유지 보장 X
  • 인덱스의 개념 대신 Key를 통해 Value에 접근
  • 키 중복 불가, 원소 중복 가능

• Stack

• Queue

최상위 클래스인 Object 클래스를 통해 모든 타입의 객체를 받도록 할 수는 있지만, 우리가 Pencil클래스 객체를 넣어도 Object 를 반환하기 때문에 실제 인스턴스의 필드,메서드에 접근하기 위해서는 형변환이 필요하다.

→ 이를 해결하기 위해 제너릭을 사용할 수 있다.

제너릭을 사용한다면?

• 객체 생성 시점에 원하는 데이터 타입을 넣어줄 수 있다.
  • 모든 데이터 타입을 받기 위해 일단 Object 타입으로 객체를 받은 뒤 형변환을 하는 과정이 필요없어진다!
• 컴파일시에 데이터 타입 체크 가능하다.

제너릭 타입 파라미터 네이밍 컨벤션

• E : Element
• K : Key
• N : Number
• T : Type
• V : Value

타입 파라미터 제한하기

• 상한 타입 제한

public Class Gifts<T extends Item> {
    ...
}

→ Gifts의 타입으로 Item 하위의 클래스만 올 수 있다.

• 하한 타입 제한

public Class Gifts<T super Item> {
    ...
}

→ Gifts의 타입으로 Item 상위 클래스만 올 수 있다.

제너릭 메서드

매개 변수 또는 리턴 타입으로 타입 파리미터를 갖는 메서드

public T getItem() {
    return item;
}