Command(변경) Query(조회) / Responsibility(역할) Segregation(분리)로 나눠서 보면 이해가 쉽다.
"변경역할을 수행하는 구성요소와 조회역할을 수행하는 구성요소를 분리하는 패턴"이라고 한다.
어떤 경우에 어떻게 사용하고, 어떤 효과가 있는지 알아보자.
왜 사용하는가?
일반적인 웹서비스의 기능은 CRUD(Create, Read, Update, Delete)이며, 도메인을 정의해놓고 변경, 조회 작업을 모두 수행한다. 간단한 기능에는 적합하지만, 서비스가 복잡해질수록 다양한 요구가 생기며, 변경 역할과 조회 역할은 다른 성격을 띄게 되어 분리의 필요성이 커진다.
ex) 홈페이지에 카테고리별 인기글을 노출시키고 싶다면?
-> 카테고리, 게시글이라는 도메인이 존재한다고 하면, 카테고리로 묶은 뒤 조회수로 정렬하여 가져와야 할 것이다. 이런 작업들이 여러 도메인에 걸쳐 전시 조회를 위해 존재한다!
즉, UX나 비즈니스 요구사항이 복잡해져 데이터를 관리하는 역할과 데이터를 조회하여 보여주는 역할이 구분되어야 할 때 CQRS 아키텍쳐를 고려해보면 좋을 것 같다. 조회 역할만 분리 시 조회 성능을 높일 수 있다.
어떻게 적용할까?
그렇다면 기존의 시스템에서 조회와 변경이라는 역할을 어떻게 분리해낼 수 있을까?
생각할 부분이 여러가지가 있지만, 우선 프로세스와 DB 관점에서 카테고리별 인기글이라는 기능에 대하여 조회와 변경 역할을 분리한다고 생각해보자.
프로세스와 DB
1. 같은 프로세스, 같은 DB
변경과 조회의 역할을 코드 수준에서만 분리하는 방법이다. 가장 간단하며, 구현하기 쉬우나 코드 상의 분리만 일어날 뿐 실제 변화는 거의 없다.
2. 같은 프로세스, 같은 DB(다른 테이블)
변경과 조회의 역할을 코드 수준에서 분리하고, 데이터 수준에서는 같은 DB 내의 테이블만 변경하는 방법이다. 명령 역할에서 데이터 변경 시 해당 변경을 [카테고리별 인기글] 테이블에도 반영해주며, 조회 역할은 카테고리별 인기글 테이블만 조회한다.
3. 같은 프로세스, 다른 DB : 레디스 사용
조회 역할을 위한 [카테고리별 인기글]을 별도 DB로 분리한다.(Redis를 사용하면 조회 기능을 향상시킬 수 있다.) 명령 역할에서 게시글이나 카테고리에 변경을 수행했을 때, 해당 변경 내용을 [카테고리별 인기글]을 가지고 있는 DB에 전파해주어야 한다. 변경 전파에 관한 내용은 더 아래에서 살펴보기로 하자.
4. 다른 프로세스, 다른 DB
마이크로서비스와 같이 코드, 데이터 단에서 별도의 서비스로 분리하는 방법이다.
도메인 변경 내용 전파
변경 역할을 하는 프로세스와 조회 역할을 하는 프로세스가 다른 DB를 사용하는 경우, 변경 역할 DB(게시글, 카테고리)의 변경 내용을 조회 역할 DB에 전파해야 한다. 유실되어도 되는 데이터인지, 기대 전송 속도가 얼마나 되는지에 따라 알맞게 사용하면 된다.
1. 직접 전파
2. 변경사항 발생 시 변경 내용을 DB에 저장하고, 전파기가 변경내역을 읽고 전파
3. CDC(Change Data Capture) 활용
데이터 구조
조회 역할을 하는 DB쪽의 도메인 설계는 어떻게 할까?
1. 변경 역할 DB의 도메인과 비슷하게 설계한다.
2. 조회가 들어오는 Query를 거의 그대로 저장한다.
이건 아직 어떻게 할지 모르겠다. 2번으로 해야할 것 같긴 한데 더 찾아봐야지. (좋은 자료 있으면 추천 부탁드립니다..)
정수들이 담긴 배열 nums와 목표 target이 주어질 때, 배열 nums 내의 특정 두 수의 합은 target이 된다.
해당 두 수의 index를 return해라.
2. 풀이
2가지 풀이 방법으로 풀어보자.
1) Two Pointer : 두개의 포인터를 가지고 배열을 탐색하는 기법이다. a. 배열을 오름차순으로 정렬한다. 이 때, 기존 idx를 보존할 수 있도록 [num, idx] 형태로 저장 후 정렬한다. b. 두개의 포인터(left = 0, right = len(nums)-1)를 만들고 합(nums[left][0] + nums[left][1])을 구한다. c. (반복) 합이 target보다 작은 경우 left를 오른쪽으로 한칸, 클 경우에는 right를 왼쪽으로 한칸 이동시킨다. d. 합이 target과 일치하면, 두 수의 idx를 반환한다.
시간 복잡도 : O(nlogn)
공간 복잡도 : O(1)
2) Hash Map : 배열을 순차적으로 탐색하며 확인한 내용을 해시 맵에 기록한다. Two Pointer 보다 속도가 빠르지만, 메모리를 추가적으로 사용한다.
a. nums를 순차적으로 탐색하며 아래의 과정을 수행한다. 탐색 과정의 정수 : num a-1) Hash Map의 key들 중 num이 있는지 확인한다. a-2) 있다면 해당 key의 value와 num의 idx를 return하고, 없다면 Hash Map에key: target - num.value: idx 로 기록한다. 시간 복잡도 : O(n) 공간 복잡도 : O(n)
고려해야 할 사항 : 추가/삭제 같이 검색 이외의 작업에 들어가는 비용, 주어진 자료구조, 데이터의 형태 등을 종합적으로 평가하여 최적의 검색 알고리즘을 선택해야 한다. 배열이 주어지고 그 안에서 특정한 Key값을 찾는다고 할 때, 아래와 같은 방법들을 고려할 수 있다.
선형 검색(Linear Search)
무작위로 주어진 데이터에 대하여 순차적으로 검색하는 방법. 검색 시간이 데이터의 크기에 선형적으로 비례한다.
방법 : 맨 앞, 혹은 맨 뒤부터 순차적으로 Key 값을 찾는다.
종료 조건 : 1. Key와 일치하는 원소를 찾은 경우
2. 배열의 길이를 넘어선 경우
시간복잡도 : O(n)
* 보초법 : 배열의 맨 끝에 찾는 원소를 추가하여 매번 배열의 끝인지 확인할 필요를 줄이는 방법.
이진 검색(Binary Search)
정렬된 데이터에 대하여 효율적으로 검색할 수 있는 알고리즘. 한번 비교를 수행할 때마다 비교 대상의 데이터 수가 반으로 줄어든다.
방법 : 맨 왼쪽 끝 원소의 Index를 Left, 맨 오른쪽 끝 원소의 index를 Right라고 한 뒤, Center의 값과 Key값을 비교한다. 대소 여부에 다라 Left, Right 값을 변경한다.
종료 조건 : 1. a[Center]가 key와 일치하는 경우
2. 검색 범위가 더이상 없는 경우
시간복잡도 : O(logn)
해시(Hashing)
데이터를 저장할 위치를 해시 함수를 사용하여 결정하는 방법. 키값을 해시 함수를 통과시켜 해시값을 얻어낸 뒤, 해시값에 해당하는 인덱스에 키를 저장한다. 키를 해시값으로 변환하는 함수를 해시 함수, 해시 테이블에서 만들어진 원소를 버킷이라고 한다.
해시 함수의 예시 : 13으로 나눈 나머지
위와 같은 해시 함수에 대하여 같은 해시 값을 가진 키가 존재하는 경우 충돌이 일어날 수 있다. 예를 들어, 14도 13으로 나눈 나머지가 1이고, 27도 13으로 나눈 나머지가 1이기 때문에 해시 값이 같은 Key가 존재하게 된다. 이를 해시 충돌이라고 하고, 다음과 같은 두가지 방법으로 처리한다.
1) 체인법 : 해시값이 같은 원소를 연결 리스트로 관리한다.
2) 오픈 주소법 : 버킷이 가득 찬 경우를 대비하여, rehash 함수를 정의한다. 이후 가득찬 버킷에 추가할 일이 생기면, 빈 버킷을 찾을 때까지 rehash를 반복한다.
쓰레드를 사용하는 이유 : 동시성을 보장하기 위해 사용한다. 예를 들어 서버를 생성한다고 하자. 하나의 프로세스로 구성된 서버는 한번에 한명의 클라이언트의 요청밖에 처리할 수 없다. 여러 개의 프로세스로 구동되는 서버를 사용할 수도 있지만, 프로세스는 개별 공간이 크고, Context Switching에도 시간이 오래 걸린다.(프로세스의 Context 스위칭 시, CPU 레지스터, RAM과 CPU 사이의 캐시 메모리까지 초기화된다. 쓰레드의 경우 개별 컨텍스트만 Switching 해주면 된다.)
기본적으로 하나의 프로세스는 하나의 쓰레드를 가지고 생성되며, 생성된 프로세스 안에서 쓰레드를 추가하면 멀티쓰레딩이라고 한다. 멀티쓰레드는 한개 프로세스의 컨텍스트 안에서 돌아간다. 각각 쓰레드는 자신만의 별도의 쓰레드 컨텍스트를 가지며, 쓰레드 ID, 스택, 스택 포인터, 프로그램 카운터, 조건 코드, 범용 레지스터 값들이 포함된다. 나머지 자원은 다른 쓰레드와 공유한다.(만일 A 쓰레드가 B 쓰레드의 스택을 가리키는 포인터를 획득한다면, 해당 포인터를 활용하여 다른 쓰레드의 스택데이터를 조작하는게 가능하다.)
1.Stack: 프로그램 실행 과정에서 생성되는 지역변수, 주소값 등을 저장하는 공간(순차적으로 주소가 낮아지는 방향으로 쌓임)
2.Heap: 동적으로 할당되는 메모리 공간 (By malloc ...)
3. Static : 1) Data : 초기화된 전역변수가 저장된다.
2)BSS: 초기화되지 않은 전역변수가 저장된다.
4.Code: 프로그램 실행 코드
쓰레드의 장점 : 다수의 쓰레드가 같은 프로그램의 변수들을 공유하기 쉽다.
쓰레드의 단점 :
1. 쓰레드 간의 동기화 문제가 발생한다. A 스레드가 어떤 자원을 사용하다가, B스레드로 제어권이 넘어간 후, B 스레드가 해당 자원을 수정했을 때, 다시 제어권을 받은 A스레드가 해당 자원에 접근하지 못하거나 바뀐 자원에 접근하게 되는 문제가 발생할 수 있다.
2. 멀티프로세싱은 운영체제의 스케쥴러가 관장하는 반면, 멀티스레드는 운영체제가 처리하지 않기 때문에 프로그래머가 직접 동기화 문제에 대응할 수 있어야 한다. --> 일반적으로, 운영체제가 여러분의 쓰레드를 위해서 정확한 순서를 선택하게 될지 예측하는 방법은 없다.
3. 디버깅이 까다롭다.
4. 하나의 쓰레드에 문제가 발생하면 전체 프로세스가 영향을 받는다.
한 프로세스 내에서 쓰레드간 공유하는 공간은 반드시 관리되어야 한다. 하나의 쓰레드가 수정하는 경우 다른 쓰레드는 잠시 대기해야 한다. 이런 공간을 Critical Region이라고 하고, 해당 영역을 관리하기 위해 사용하는 키를 Mutex라고 한다.(Mutex는 1과 0의 값만을 가지는 Binary Mutex이다.)
아래의 예시를 보자. (공유된 메모리에 대한 잘못된 접근의 예시 : 출처 : CSAPP)
[ badcnt.c ]
0. niters라는 변수를 입력받는다.
1. cnt=0 라는 전역변수를 선언하고, thread()함수를 실행하는 쓰레드를 2개 생성한다.
thread 함수 : niters만큼 cnt를 증가시킨다.
프로그램의 의도 : 프로세스를 두개 생성한 뒤 전역변수 cnt를 niters만큼씩 증가시킨다.
/*
* badcnt.c - An improperly synchronized counter program
*/
/* $begin badcnt */
/* WARNING: This code is buggy! */
#include "csapp.h"
void *thread(void *vargp); /* Thread routine prototype */
/* Global shared variable */
volatile long cnt = 0; /* Counter */
int main(int argc, char **argv)
{
long niters;
pthread_t tid1, tid2;
/* Check input argument */
if (argc != 2) {
printf("usage: %s <niters>\n", argv[0]);
exit(0);
}
niters = atoi(argv[1]);
/* Create threads and wait for them to finish */
pthread_create(&tid1, NULL, thread, &niters);
pthread_create(&tid2, NULL, thread, &niters);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
/* Check result */
if (cnt != (2 * niters))
printf("BOOM! cnt=%ld\n", cnt);
else
printf("OK cnt=%ld\n", cnt);
exit(0);
}
/* Thread routine */
void *thread(void *vargp)
{
long i, niters = *((long *)vargp);
for (i = 0; i < niters; i++) //line:conc:badcnt:beginloop
cnt++; //line:conc:badcnt:endloop
return NULL;
}
/* $end badcnt */
하지만 실제로 프로그램을 실행해보면, 아래와 같이 의도치 않은 결과가 나오는 것을 볼 수 있다.
무엇이 문제일까?
우리가 사용하는 C언어 아래에는 또 어셈블리어가 있다. C언어에서는 최소 단위라고 생각되는 함수들이, 실제로 어셈블리어 단계에서는 여러 단계를 거쳐 수행된다. 해당 예제에서 문제가 되는 아래 부분이 실제로 CPU에서 어떻게 수행되는지 보자.
for (i = 0; i < niters; i++) //line:conc:badcnt:beginloop
cnt++; //line:conc:badcnt:endloop
간단히 정리해보면, cnt++; 이라는 작업은 CPU 입장에서 아래와 같은 세 개의 작업으로 구분된다.
1) Load(L) : 메모리에 저장된 cnt를 불러와서 레지스터 r1에 저장한다.
2) Update(U) : r1에 있는 데이터에 1을 더한다.
3) Store(S) : r1에 있는 데이터를 메모리에 다시 저장한다.
1번 쓰레드가 수행해야 하는 작업을 L1, U1, S1이라고 하고 2번 쓰레드가 수행해야 하는 작업을 L2, U2, S2라고 하자.
원래는 L1, U1, S1 -> L2, U2, S2 순서대로 수행되는 것이 작성자의 의도이지만, 쓰레드 간의 실행 순서는 우리가 조작할 수 있는 범위를 벗어난다. 위와 같이 L1->U1->L2->S1->U2->S2순서대로 작업이 일어나면, cnt는 2가 아닌 1이 되면서 의도와 다른 결과가 나오게 된다.
따라서 이런 공유 영역들을 조절할 때는 아래와 같이 Mutex를 사용한다. Mutex는 공유된 자원(Critical Section)에 접근하는 키이다. 키를 가진 사람만 접근할 수 있도록 1이면 접근 가능, 0이면 사용중을 의미한다. 쓰레드가 공유 자원에 접근하려고 할 때 Mutex를 확인하고, 누군가가 사용중이면(Mutex == 0이면) 다음 쓰레드에게 실행 순서를 넘겨준다.(술집의 화장실 키를 생각하면 된다. 키가 없으면 기다리고, 키가 있으면 들고간다.)
P 함수는 Mutex가 1이면 0으로, V 함수는 Mutex가 0이면 1로 만들어주는 함수이다. 위의 코드를 작성자의 의도대로 수정하면 아래와 같다.
/*
* goodcnt.c - properly synchronized counter program
*/
#include "csapp.h"
void *thread(void *vargp); /* Thread routine prototype */
/* Global shared variable */
volatile long cnt = 0; /* Counter */
sem_t mutex;
int main(int argc, char **argv)
{
long niters;
pthread_t tid1, tid2;
Sem_init(&mutex, 0, 1);
/* Check input argument */
if (argc != 2) {
printf("usage: %s <niters>\n", argv[0]);
exit(0);
}
niters = atoi(argv[1]);
/* Create threads and wait for them to finish */
pthread_create(&tid1, NULL, thread, &niters);
pthread_create(&tid2, NULL, thread, &niters);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
/* Check result */
if (cnt != (2 * niters))
printf("BOOM! cnt=%ld\n", cnt);
else
printf("OK cnt=%ld\n", cnt);
exit(0);
}
/* Thread routine */
void *thread(void *vargp)
{
long i, niters = *((long *)vargp);
for (i = 0; i < niters; i++){
P(&mutex); // Mutex += 1 if Mutex == 0
cnt++;
V(&mutex); // Mutex -= 1 if Mutex == 1
}
}
/* $end goodcnt */
Dynamic Programming(동적 프로그래밍)은 구하고자 하는 최적해가 부분문제들로 이루어져있고 부분문제들이 또다른 작은 부분문제들로 이루어졌을 때 풀이시간 단축을 위해 사용된다. 반복되는 부분문제들을 한번씩만 계산하여 저장한 뒤,저장한 값을 사용하여 중복되는 부분문제들의 계산을 줄이는 방법이다. 저장된 값을 재사용함에 따라 풀이시간은 감소하지만, 저장하는 값들의 공간만큼 메모리 공간이 더 소모된다는 단점이 있다.
DP 문제를 풀때의 일반적인 접근은 아래와 같다.
1. 최적해의 구조적 특징을 찾는다.
2. 최적해의 값을 재귀적으로 정의한다.
3. 최적해의 값을 Bottom-Up으로 계산한다.
4. 계산된 정보들로부터 최적해를 구성한다.
정의만 읽어보면 두루뭉실하니, 예제를 보면서 이해해보자.
Problem: 피보나치 수열의 N번째 숫자를 구하라.
1. 피보나치 수열의 구조적 특징 : n번째 숫자는 n-1번째 숫자와 n-2번째 숫자를 더한 값이다.
피보나치 수열
2. 최적해의 값을 재귀적으로 정의한다.
def fib(n):
if n==1 or n==2:
result = 1
else:
result = fib(n-1) + fib(n-2)
return result
이 상태로도 풀이가 가능하지만, 시간초과 / Recursion Limit 초과로 불가능한 경우가 많다. 위의 코드대로 풀이를 진행하면, fib(5)를 구할 때 아래와 같이 반복된 계산을 수행하게 된다.
색깔별로 중복된 계산을 표시했다.
따라서, 현재 구현된 재귀 방식의 시간복잡도는 O(2^n)이다. 계산 횟수를 줄이기 위해 계산값들을 memo라는 배열 안에 저장하고, 저장된 값들을 사용해보자.
def fib(n):
memo = [0, 1, 1]
memo.extend([0 for _ in range(n)])
def find(n):
if memo[n]:
return memo[n]
else:
result = find(n-1) + find(n-2)
memo[n] = result
return result
return find(n)
우선 memo라는 배열을 만들어준 뒤, 계산한 값은 memo[n]에 저장한다. memo[n] 값이 존재하는 경우, 계산하지 않고 바로 이 값을 사용한다. 이렇게 중복되는 부분문제들의 결과값을 저장하여 사용하는 방법을 Memoization이라고 한다.
위와 같은 방식의 시간복잡도는 O(n)이 된다.
3. 최적해의 값을 Bottom-Up으로 계산한다.
위와 같은 방법은 재귀적으로 호출하기 때문에 Max Recursive Limit에 걸리는 문제가 발생할 수 있다. 따라서 그냥 1부터 n까지 순차적으로 memo 배열을 채워가는 방식을 생각할 수 있는데, 이를 Bottom-up 방식이라고 한다. 재귀를 사용한 것보다 더 간단하고, 빠르다.
def fib(n):
memo = [0, 1, 1]
memo.extend([0 for _ in range(n)])
for i in range(3, n+1):
memo[i] = memo[i-1] + memo[i-2]
return memo[n]
물론 피보나치보다 더 어려운 문제들을 접할 때는, 최적해의 구성을 통해 부분문제들을 정의하는 것이 매우 어려울 때가 많다. 추후 다른 문제들 Review를 통해 알아본다
