대규모 서비스에서 알고리즘과 자료구조의 중요성

패스트 캠퍼스 (The Red: 4천만 MAU를 지탱하는 서비스 설계와 데이터 처리 기술 by 카카오페이지 기술전략이사 윤진석) 필기록입니다.

---

 

이번 세션에서는 서버 레벨이 아닌 코드 레벨에서 확장성에 대해 살펴본다. 

 

다음과 같이 시장의 요구 사항과 사업의 요구사항이 있을 때를 생각해보자. 

 

 

 

내 주변 객실을 검색하라라는 문제를 살펴보면 

 

현재의 내 위치 원점에서 -> 각각의 점들 계산

즉, 2차 평면 거리 계산 문제가 된다.  

 

int[][] point = {{3,3}, {5,-1}, {-2,4}}

 

1. 유클리드 거리 계산

2. 원점으로부터 거리 순으로 정렬

3. 상위 k개 출력 

 

유명한 알고리즘 문제인 find K closest points to the origin 

 

코드를 구현해보면 다음과 같이 표현해볼 수 있다. 

 

int[][] point = {{3,3}, {5,-1}, {-2,4}}
Map map = new HashMap<Integer, Integer>();

for (int i=0; i< point.length; i++){
  map.put(i, (int) (Math.pow(point[i][0], 2) + Math.pow(point[i][1], 2)));
} 

map.entrySet()
  .stream()
  .sorted(Map.Entry<Integer, Integer>comparingByValue())
  .forEach(System.out.println);

 

포인트 값이 주어졌을 때, 원점에서부터 모든 거리를 유클리드 거리 계산을 통해서 구하는데, 모든 점과 나와의 거리를 계산을 하고, 정렬 후 상위 k개를 구한다. 

 

거리 계산을 하는 것은 N개의 데이터가 주어진다고 하면  O(N), 거리 정렬은 (NlogN) 

 

Big O 노테이션의 시간복잡도 차이가 다음과 같으므로 

 

 

정렬 부분에서 백만 개의 데이터가 넘어가기 시작한다면 1초를 넘어갈 수 있다. 

 

내 현재 위치로부터 가까운 객실을 계산하는 로직이 따라서 헤비해질 수 있다. 

 

 

 

구면 코사인 법칙을 사용하는 예시를 살펴보자. 

 

 

방금의 자바 로직을 SQL 쿼리로 계산할 수 있다면 

시간 복잡도는 동일하게 거리계산 O(n) + 거리 정렬 O(nlogn) 

-> 10만 건의 데이터를 다룬다고 하면 64MB 데이터 사이즈를 다루게 된다. 

 

이에 더하여 API 서버가 분산을 하더라도 N개의 요청이 동시에 들어오면 메인 DB에 몰리게 된다. 

-> 데이터베이스에 거리 계산과 정렬 연산 부하가 몰리게 된다. 

 

 

순전히 데이터베이스 서버에 의존하지 않고 계산 연산을 API 서버에 분산하면 연산 부하는 어느 정도 해소할 수 있다. 

 

 

 

데이터베이스에 대한 튜닝을 해보면 어떨까? 

 

예를 들어, 

Q. 인덱스를 걸면 빨라지지 않나요? 

 

그렇지 않다. OrderBy 절은 어쨌든 전체 데이터를 메모리 상으로 끌어올려야 하기 때문에 인덱스로 해결되지 않는다. 

 

이러한 문제 때문에 Mysql에서도 공간색인(Spatial Indexing) 과 같은 방법론들이 대두되고 있다. 

 

2차 평면에 Object를 색인하는 Quad-Tree나 R-Tree를 이용한 방식을 사용하기도 한다. 

 

그런데 만약 문제를 좀 더 심화시켜서 내 주변 택시를 찾는다고 하면 어떨까? 즉, 택시처럼 위치가 수시로 변경된다면? 

이러한 경우 공간 색인으로도 해결하기가 어려워진다. 

 

 

 

 

다음의 사례를 살펴보자.

 

안심번호 할당문제 

 

요구사항: 통신사로부터 10,000개의 안심번호를 할당받았다. 안심번호를 원하는 고객에게 할당해달라. 

 

해당하는 안심번호를 관리하는 데이터베이스 테이블이 다음과 같이 있다고 할때, 

 

 

Update를 통해서 할당할 수 있다. 하지만, 동시에 접근하는 경우 경합 문제가 발생한다. 

 

예를 들어, User1과 User2가 동시에 이러한 쿼리를 실행하는 경우. 

 

이러한 문제를 해결하는 Lock, Mutex, Semaphore 등 공유 자원에 대한 동시 접근 제어 처리에 대한 지식이 있어야 해결 가능하다. 

 

 

이와 같이 간단한 요구 사항이라도 구현을 어떻게 하느냐에 따라 잠재적인 위험 요소를 갖는다. 

 

 

 

구글의 분산 마킹 서비스 개요를 보면 다음과 같다. 

여러 가지 서비스들이 동시에 메인 데이터베이스에 접근하는 경우의 문제를 살펴보면, 중간에 락 매니저가 존재하여 어떤 데이터베이스의 접근 로직을 관리한다. 

->락을 관리하여 Race 컨디션을 피할 수 있다. 

 

 

 

알고리즘이 엉성하다는 것은 무엇일까?

- 공간이 낭비되거나

- 재활용 자원을 잘못 활용되거나

- 수행시간이 느리거나 

 

 

 

요약 

 

간단한 기능 요구 사항을 하나 구현하더라도, 알고리즘을 잘 알고 모르고에 따라 구현의 성숙도, 품질, 생산성이 크게 달라질 수 있다. 

 

알고리즘에 대한 지식은 단순히 관문을 통과하기 위해서가 아니라 현업에서도 매우 중요한 역할을 한다.