소셜 네트워크 서비스의 아키텍처에 대하여 분석하기 1편

배경

취업하기 전 인상깊게 읽은 글이 있다. 절반도 이해하지 못했는데 경력이 쌓이면 언젠가 이해할 수 있겠지? 라고 생각했었다. 그리고 4년차 개발자가 된 지금은 어떤지 알고 싶어졌다. 프론트개발만 하고 있기 때문에 그때와 달라진게 있을까? 싶은 생각도 있지만 CS 지식도 쌓인 만큼 조금 달라졌길 기대한다.

 

본문

위에서부터 한문단씩 읽으면서 생각을 정리해보겠다.(굳이 설명을 덧붙이지 않아도 되는 부분은 생략)

 

작성자 OR 굴비 알고리즘의 연산 비용을 계산해 보자. 내가 따르는 친구의 수를 m이라 하고 전체 사용자 수를 n이라고 한다면 전체 사용자 검색 연산의 시간 복잡도는 O(m log(n))이 된다. 물론, 각 사용자별로 정렬된 게시물 레코드 식별자 리스트를 찾은 후에도 각 사용자별 레인지 쿼리를 수행하고 결과를 하나로 병합한 후 다시 병합된 리스트에서 레인지 쿼리를 수행해야 하지만, 이는 앞의 비용들에 비하면 충분히 무시할만한 것이므로 넘어가자. 이쯤 되면, 혹자는 O(m log(n)) 연산이 뭐가 그리 무자비한 것이냐며 역정을 낼 수도 있겠다.

log(n)이 어디서 나오는걸까?

일반적인 해시테이블을 사용하게 된다면 사용자 수가 몇 명이든지 상관없이 O(1)로 접근 가능하다.

옛날에 공부했던 자료구조 책을 꺼내서 해시를 찾아보면 아무리 뛰어난 해시 함수를 사용한다고 해도 충돌을 완전히 피하는 것은 불가능하다고 나와있다. 4000만 이상의 사용자 수가 있다면 당연히 해시 함수를 이용해 O(1)로 접근하는 것은 불가능하다.

사실 데이터베이스를 조금만 공부해보면 많은 데이터베이스는 인덱싱을 위해 B-tree, B+tree를 사용하는 것을 알 수 있다.

그리고 B-tree의 높이는 log(n)이기 때문에 검색 시간은 log(n)이 된다.

 

그렇다면, 일반적인 게시판 페이징 오퍼레이션에 비해서 상대적으로 얼마나 무거운지 비교해 보자. 전체 게시물의 수를 l이라고 한다면 게시판 페이징 비용은 O(log(l))이다. 사용자별 평균 보유 게시물 수를 k라고 한다면, l은 k * n이기 때문에 사용자 검색과 게시판 페이징 연산 비용의 비교는 O(m log(n)) 대 O(log(kn))로 나타낼 수 있다. 사실, 정확하게 Big O 분류 관점에서 m과 k는 상수로 볼 수 있기 때문에 두 복잡도는 같다고 볼 수 있다. 하지만 굳이 시간 비용을 비교해 보자면 m 대 log(k)/log(n)+1, 즉 평균 친구 수 대 log(사용자별 평균 보유 게시물 수)/log(전체 사용자 수) + 1이다. 확실히 전자의 자릿수가 몇 개 더 많다. Facebook의 통계 데이터를 대입해 보면, 전체 사용자가 약 10억명에 평균 친구 수는 342명[4]이고 월간 평균 게시물 수는 36건[5]이며 연간 단위 파티션 상황에서 연간 누적으로 평균 432개의 게시물을 가진다면 대략 342:1.3 정도로 작성자 검색은 게시판 페이징에 대비 대략 260배 정도나 더 무겁다고 추정할 수 있다. 즉, 모든 사용자가 자신의 모아 보기를 보는 매 순간 이런 비용이 발생한다는 것이다.

이건 고등학교 때 배우는 로그계산식만 기억하고 있다면 알 수 있다. 나도 일반 게시판 기반의 서비스는 개발해본적이 있다. 근데 260배의 비용이 더 발생한다면.. 그리고 유저수가 많다면.. 쿼리최적화도 방법이겠지만 결국에 답은 답은 캐시밖에 없는 것 같다. sns 특성상 캐시를 사용해도 긴 시간을 유지할 수는 없다. 물론 여러개의 캐시를 조합해서 사용해야겠지만 많이 어려워보인다. 특히나 4000만 이상의 많은 사용자는 더 그렇다. 페이스북과 트위터를 예시로 들었는데 두 가지 다 굉장히 복잡해보인다.

 

이런 시간 비용을 줄이는 방안은 무엇일까? 여기서 반사적으로 생각할 수 있는 대안은 바로 캐시를 적용하는 것이다. 소셜 피드에서는 최신 데이터를 가장 빈번하게 요청하기 마련이다. 하지만 DB 수준의 캐시를 적용하면 다양한 서비스 쿼리 때문에 원하지 않는 데이터 블록이 자동으로 캐싱될 수 있으므로 프로그래밍으로 조절할 수 있는 캐시가 필요하다. LAMP 스택에서 가장 흔하게 쓸 수 있는 memcached를 최신 피드에 대한 look-ahead 캐시로 사용한다면 DB로 가는 트래픽을 크게 줄이고 빠르게 반응할 수 있다. 물론 이런 속도를 공짜로 얻을 수 있는 것은 아니다. 결국, 비즈니스 로직상에서 일관성을 유지하기 위한 상당한 코딩이 필요하기 때문이다.

오 맞췄다. 맞췄다기보다는 너무 당연한 얘기다. 

look-ahead 캐시는 미래에 필요할 것으로 예상되는 데이터를 미리 가져와서 캐시에 저장하는 기법이다.

일단 더 읽어보자

 

이제 시간 복잡도는 어느 정도 줄였다. 하지만 겨우 이 정도로 무자비한 연산이라고는 할 수 없다. 엄청난 데이터양을 생각해 보자. Facebook에는 하루에 10억 개의 상태 메시지가 올라온다.[6] Facebook의 일간 데이터 저장량을 추정해 보면, 상태 메시지에서 이미지 등의 부가 데이터를 제외한 순수 텍스트만 평균적으로 300바이트 정도를 쓴다고 가정했을 때, 상태 데이터 텍스트만 하루에 약 280GB가 쌓인다. 너무나 당연하게도 이 정도 데이터양을 지탱하기 위해서는 여러 서버를 사용할 수밖에 없다. Facebook은 4,000대 이상의 MySQL 샤드와 9,000대 이상의 memcached 샤드를 구성해 사용하고 있다.[7] 이 정도 규모의 샤드라면 데이터를 찾아 사용하기 위한 또 다른 다계층 중간 서버들이 필요하고, 이러한 복잡한 구성 때문에 프로그램 로직은 구성에 묶일 수 밖에 없다. 이러한 엄청난 규모의 샤드상에서 개발하는 그들은 '죽음보다 더 끔찍한 운명(fate worse than death)'이라고 자조하곤 한다.

샤드(sharding): 데이터베이스의 수평적 확장

글로만 봐도 끔찍하다는 생각이 든다. 데이터베이스의 확장은 굉장히 어렵다고 들었는데 저정도의 확장이라면.. 끔찍하다.

 

혹자는 이런 공간 복잡도는 SNS의 특성만으로 기인한 것은 아니라고 할 수도 있다. 하지만 진짜 문제는 거대한 클러스터를 구성하고 나서야 비로소 보이게 된다. 내 친구들의 데이터가 같은 샤드 내에서 옹기종기 모여 살 수 있었다면 행복했을 것이다. 하지만 샤드 내 데이터가 커진다면 결국 각 친구의 데이터가 곳곳에 흩어져 살 수밖에 없고, 또 새로 사귄 친구의 데이터는 샤드 #3989에 거주하고 있다. 이제, 작성자 OR 굴비 알고리즘은 어떻게 돌릴 수 있을까?

와 내가 윗 문단을 읽고 고민했던 부분이다. 예전에 이 글을 읽어서 그럴수도있는데 이미 알고 있었다. 성장했다?!

 

가장 먼저 해결할 문제는 사용자의 데이터가 어디에 살고 있는지 주소를 찾을 방법이 있어야 한다는 것이다. 어떤 서버에 데이터가 있는지 하나하나 관리할 수도 있고, 해시 함수를 사용해 해시 결과가 해당 서버로 바로 안내할 수도 있다. 전자는 주소의 유연성이 있지만 그 유연성을 지탱할 거대한 저장소가 필요하고, 후자는 단순하고 저장소가 필요 없지만 유연성이 떨어진다. 이러한 문제를 해결하기 위해 분산 환경에서는 둘의 장점을 혼합해 제공하는 consistent hashing[8] 기반의 구조를 자주 사용한다. 쉽게 설명하자면, 각 데이터의 저장소 주소를 저장하기보다 한정된 전체 주소를 여러 범위로 나누어 각 저장소에 대응시켜 사용하는 방식이다.

이제부터 좀 모르는게 많이 나오기 시작했다.. 구글링 + calude와 함께 했다.

 

나는 이 문단을 읽고 한 가지 생각이 떠올랐다. id가 하나씩 더해지는 구조라고 가정한다면(물론 id를 uuid가 아니라 이런식으로 만드는건 문제가 있을 수 있다.) 1~10,000까지는 1서버, 10,001~20,000 까지는 2 서버 이런식으로 저장하면 안되나? 라는 생각이 들었다. claude에게 물어보니 이건 Range-based Partitioning이라고 하고 실제로도 많이 사용된다고 한다. 장점도 있지만 아래의 단점이 꽤 치명적으로 느껴졌다.

 

Range-based Partitioning

단점 목록

핫스팟 문제: 10년전에 페이스북에 가입한 사람들과 1일전에 페이스북에 가입한 사람 중 누가 더 활발하게 활동할까? 높은 확률로 후자일것이다.

데이터 스큐: 가입일과 상관없이 특정 서버에 유저가 몰릴 수 있다.

확장 시 재배치: 확장할 때 데이터의 재배치가 어렵다.

탈퇴 문제(내가 생각함):

  데이터 스파스 문제: 오래된 서버는 대부분 탈퇴하고 최근 서버는 대부분 남아있다.

  서버 불균형 심화: 위 이유로 서버마다 부하 문제도 있고 유령 서버도 존재한다.

  리소스 낭비: 데이터가 낭비되고 있으면 그만큼 리소스도 낭비된다.

 

다시 생각해보니 게임에서는 Range-based Partitioning을 많이 사용하는 것 같다. 그리고 위에서 단점들을 얘기했지만 모든 아키텍쳐가 그렇듯 하나만 가지고 모든걸 해결할 수는 없다. 여러가지를 조합해서 사용해야한다.

백엔드 기본 지식을 어느정도는 따라가려고 했는데 이런 아키텍쳐 레벨까지 들어가니까 알아야 될게 너무 많은 것 같다. 그냥 이정도 수준의 글을 읽고 인사이트를 얻는 정도로 멈춰야 될 것 같다. 잠깐 이유가 있어서 대규모 데이터 처리에 대해서 관심을 가진적이 있었는데 음.. 뭐 사실 사이드프로젝트 수준이라면 적당한 캐시정도만 사용해도(아니 캐시 사용할일도 솔직히 없지) 다 커버 가능하다. 그리고 요즘은 서버 성능도 좋아져서 서버 확장도 거의 필요하지 않은 것 같다.(db도 마찬가지겠지)(오해가 있을것같은데 mau 많이 나오는 그런 서비스를 얘기하는게 아니다..) 만약 너무 프로젝트가 잘된다면 그 때는 다른 사람에게 넘겨줘야겠지.

 

consistent hashing

위의 이유로 Range-based Partitioning은 어렵다는 걸 알았다. 이제는 consistent hashing에 대해 알아보자.(나는 처음보는 개념)(개념이 어려운건아닌데 꽤 복잡해서 글을 따로 분리해서 쓸까 하다가 일단은 가볍게 적는다.)

consistent hasing은 우리나라 말로 안정 해시라고 부른다.

서버에 그냥 해시를 사용한다고 가정해보자. 그리고 유저수가 많아져서 서버를 추가한다고 해보자. 그러면 심각한 문제가 생긴다. 

기존 서버가 3대가 있어서 해시키에 %3 로직을 통해 서버를 할당하고 있다고 가정해보자. 그런데 서버가 추가된다면 %4를 하게 되고 이때 많은 서버가 이동하게 된다. 즉 일반적인 해시를 사용하면 서버의 추가 제거에 대해 유연하게 대응하지 못한다.

 

해시 링(hash ring)

이때 해시 링(hash ring)이라는 개념이 등장한다.

링(원)을 그려보자. 그리고 서버들이 링 위에 있다고 가정해보자. 그리고 링 위에는 n개의 공간이 있다.(점이라고 생각하면 쉽다.)

 

예시와 함께 살펴보자. 공간이 10개가 있고 A(1에 위치),B(6에 위치) 서버가 존재한다고 가정해보자.

이 때 임의의 공간에 접근했을 때 시계방향에서 가장 가까운 서버로 접근하게 된다.

0,1,7,8,9에 접근한다면 A

2,3,4,5,6에 접근한다면 B

 

이때 C(4에 위치) 서버가 추가된다고 가정해보자. 그러면 2,3,4는 C에 배치될 것이고 나머지는 기존과 동일하다.

그리고 B 서버가 삭제된다고 가정해보자. 그러면 5,6이 A 서버로 배치될 것이다.

위와 같이 비교적 쉽게 추가 제거가 가능해진다.

 

> 부가 설명

해시 함수로 SHA 256 알고리즘을 사용하면 해시 공간은 2^256만큼의 공간을 사용할 수 있게 된다. 즉 9000대가 아니라 그보다 훨씬 큰 규모의 샤딩도 가능해진다.(물론 페이스북 정도의 규모라고 할지라도 이만큼의 공간은 필요없다.)

서버의 배치도 알고리즘을 통해 적절한 곳에 위치시켜야한다.(균등분포해시함수)

 

Virtual Nodes(가상 노드)

사실 위의 예시에서도 문제가 하나 발생했다. C 서버가 추가되었을 때 A에서 다른 서버의 약 2배만큼의 부하가 걸리고 있다. 그리고 이는 서버가 적을 때 더 문제가 크게 발생한다.

각 서버를 여러개의 가상 노드로 나누면 이 문제를 해결할 수 있다. 결국 서버가 적어서 편차가 커지는게 문제였는데 가상 노드로 이 편차를 해결한 것이다.

근데 당연히 트레이드오프가 있다. 서버가 추가 제거 되었을 때 가상노드들에 대한 처리가 필요하고 메모리도 더 많이 필요하다.

 

물론, 그 주소 범위와 저장소의 대응 테이블은 HBase와 같이 master-slave 모델, 또는 Cassandra와 같이 peer-to-peer 모델로 공유할 수도 있다.

master-slave: master 서버에서 모든 정보를 관리해서 특정 데이터가 어떤 (slave)서버에 있는지 알려주는 방식

관리하기가 쉽다. 단, master 서버가 죽으면 큰일난다.

 

peer-to-peer: 모든 서버가 동등하게 정보를 공유하는 방식.

장애 대응에 유리하다. 단, 서버들간에 데이터 동기화가 복잡하다.

 

후기

페이스북, 트위터를 간단하게라도 풀스택으로 개발해보고 싶어졌다.(현실적으로 힘들다면 아키텍쳐 레벨정도만이라도) 이런건 글로만 읽어서 배워지지 않는다. 진짜 얕은 경험이라도 해봐야 더 잘 느낄 수 있다고 생각한다. 로컬에서 개발하는거에는 캐시같은게 사실 필요없지만 부하 테스트를 진행하면서 하면 꽤 유의미하겠다 라는 생각이 들었다. 올해는 계획한게 있어서 힘들고 내년 목표로 잡아야겠다.

md형태가 아니다보니 가독성좋게 글 쓰는게 좀 어렵다.. 티스토리에서 md를 애매하게 지원하기는 하는데 진짜 좀 애매하게 지원해서..

블로그 이사를 해야하나 작은 고민이 생긴다.

 

원본링크

https://d2.naver.com/helloworld/551588

 

참고링크

https://jiwondev.tistory.com/299