팔로잉 기반 피드 아키텍처 설계하기

   100만 구독자, 100k 팔로워를 가지고 있는 인플루언서, 연예인도 아니지만 수많은 구독자를 가지고있는 일반인들을 요즘에는 흔하게 찾아볼 수 있다. 그리고 이런 계정을 팔로워하면, 당연히 내 피드에 떠야한다고 생각했다. 당연하다. 하지만 내가 직접 구현하려고 하니 뭐 하나 당연한게 없었다. 

  사내에서 "팔로잉 - 팔로잉 기반 피드"프로젝트에 백엔드 엔지니어로써 참여했었다. DB 설계, API 설계, 기능 개발, 배포이후 모니터링 전반적인 작업들을 담당했었다. 이번 포스팅에서는 팔로잉의 아키텍처 설계단계에서 고민했었던 지점들에 대해서 이야기해보려고한다.

실제 LINER 화면

---

[ IN 연산으로 처리하기 ]

   팔로잉 기반 아키텍처 구조를 생각할때 제일 간단하게 생각해낼 수 있는 방법일 것이다. 내가 따르고 있는 친구들의 게시글을 조회하기 위해서, 내가 따르는 사람들을 모두 IN에 넣어 이들의 게시글을 조회하는 방식이다. 하지만 문제점이 있다. 팔로잉의 숫자가 늘어나게 되면 인덱스를 제대로 타지 못한다는 문제다. 
  인스타그램에서는 7,500개의 팔로우 제한이 있으며(자신이 팔로우 하는것에 대하여만, 남이 나를 팔로잉하는 것에는 수 제한이 없음), 트위터와 페이스북에서는 5,000개의 팔로우 제한이 있다.[1][2][3] 이에 기반하여 서비스에 1000명정도의 팔로우 제한을 걸어둔다고 생각을 했고,  1000명의 팔로우를 한 유저가 있을때 다음과 같은 쿼리가 나갈 수 있다. 'select * from (게시글 테이블명) where user_id in (1,2,3,4,5...1000)' 하지만 이런식으로 in절에 값이 너무 많이 들어가게되면 인덱스를 제대로 타지 못하게되면서 성능 문제가 생길 수 있다. 

 * eq_range_index_dive_limit

   : IN 절내에 값의 크기가 eq_range_index_dive_limit값(default 200)을 초과할 경우 실행계획을 세울 때, index dive 방식이 아닌 index statistics 방식을 사용하도록 한다. index dive란, 실행계획을 세울때 index range scan을 위한 최적화시 row를 예측하기위해 직접 index를 이용해서 row수를 예측하도록 하는 방식이며[4],  index statistics방식은 MySQL 5.6부터 적용된 방식으로, index dive가 아닌 인덱스 통계정보를 바탕으로 실행계획을 세우도록 하는 방식이다. 통계정보가 정확할때도 있지만, 100% 신뢰할 수는없기 때문에 생각지 못한 성능저하를 발생시킬 수 있다.[5] [6]

*  range_optimizer_max_mem_size

   : 수행하는 쿼리의 용량이 range_optimizer_max_mem_size 값을 초과하게되면 옵티마이져가 풀스캔 혹은 이외의 인덱스를 태우도록 한다. [7]

* MATERIALIZED select type
   : 실제로 예상쿼리인 select * from (게시글 테이블명) where user_id in (1,2,3,4,5...1000) order by id desc limit 20 의 실행계획을 돌려보았을때 MATERIALIZED 라는 select type이 발생했었다. 

  : MATERIALIZED은 MySQL 5.6 버전에 추가된 셀렉트 타입으로, IN 절 내의 서브쿼리를 임시테이블로 만들어 조인을 하는 형태로 최적화를 해준다. 참고로 5.6 버전에서는 IN절내에 서브쿼리가 존재하는 경우 매 레코드 마다 서브쿼리를 실행시키는 형태로 수행되었다고 한다.

[ 다른 소셜 네트워크 서비스 아키텍처 ]

   이정도로 생각하고나니, MySQL의 쿼리 성능 개선작업만으로는 될 수 있는 문제가 아니라고 생각이 들었고, 다른 소셜형 네트워크 서비스들에서는 어떤 아키텍처를 사용하고 있는지 조사하기 시작했다.

  포스팅 전송, 즉 팬아웃(fanout)은 어떤 사용자의 새 포스팅을 그 사용자와 친구 관계에 있는 모든 사용자에게 전달하는 과정이다. 널리 알려진 소셜형 네트워크 서비스들의 팬아웃 기능에는 크게 두가지모델이 있다. 하나는 쓰기 시점에 팬아웃하는 모델(fanout-on-write, 또는 push 모델)이고, 다른 하나는 읽기 시점에 팬아웃 하는 모델(fanout-on-read, 또는 pull 모델)이다. fanout-on-write모델의 대표 서비스는 트위터가 있고, fanout-on-read 모델의 대표 서비스로는 페이스북이 있다. 각각의 모델들에 대해서 간략하게 살펴보고, 트위터와 페이스북이 왜 그 모델들을 선정하였으며, 선택한 모델들의 한계점을 넘기기위하여 어떤 노력들을 했는지 알아보겠다.

 

* Push 모델
   : 새로운 포스팅을 기록하는 시점에 뉴스피드를 갱신하게 된다. 다시 말해, 포스팅이 완료되면 바로 해당 사용자의 캐시에 해당 포스팅을 기록하는 것이다.

  : 새 포스팅이 기록되는 순간에 뉴스 피드가 갱신됨으로(on-demand가 아닌 pre-computed), 뉴스피드를 읽는데 드는 시간이 짧아진다는 장점이 있다. 하지만 서비스를 잘 사용하지 않는 비활성화 유저의 뉴스 피드도 갱신해야하므로 컴퓨팅 자원이 낭비될 수 있다는 문제점이 있다. 또한 팔로워가 많은 사용자의 경우, 친구 목록을 가져고오고 그 목록에 있는 사용자 모두의 뉴스피드를 개신하는 데 많은 시간이 소요될 수 있다. 흔히 hot-key, hot-spot 문제, 유명인 문제, 저스틴 비버 문제등등...이라고 부르는 문제이다.

 

 

* Pull 모델
   : 피드를 읽어야하는 시점에 뉴스 피드를 갱신하는 요청 기반(on-demand)모델이다. 사용자가 본인의 피드를 로딩하는 시점에 새로운 포스트를 가져오게 된다. 

  : 비활성화된 사용자에 대해 어떠한 컴퓨팅 자원도 소모하지 않아도 된다는 장점이 있다. 또한 데이터를 친구 가각에 푸시하는 작업이 필요 없으므로 핫키문제도 생기지 않는다. 하지만, 뉴스피드를 읽는데 많은 시간이 소요될 수 있다는 단점이 존재한다.

 

[ 페이스북 : Pull 모델 ]

  페이스북은 소셜 그래프를 push 보다는 최대한 pull 하는 방식을 선택해왔다. 이러한 구현 전략은 DB에 많은 읽기를 요구하게된다. 이때문에 페이스북은 주커버그가 초기 페이스북을 만들던 2005년 부터 memcache를 사용해왔다. 하지만, 페이스북 피드의 요구사항이 복잡해짐에 따라서 TAO(The Associations and Objects)를 도입하게 되었다. TAO는 그래프 자료구조의 write-through 분산캐시다. TAO의 키워드를 하나씩 이야기해보면서 좀 더 살펴보겠다.

 

- 그래프 자료구조

https://www.usenix.org/system/files/conference/atc13/atc13-bronson.pdf

  페이스북의 피드를 보면 자신이 팔로우한 사람의 글 뿐만아니라, 내가 팔로우한 사람이 좋아요를 누른 글, 내가 팔로우한 사람이 놀러갔었던 장소 등으로 이루어져있는 것을 알 수 있다. 좋아요, 팔로우, 댓글, 공유, 장소 체크인, 멘션 등등 다양한 정보로 얽혀져있다는 뜻이다.

  “앨리스가 Golden Gate Bridge에 가서 친구인 bob을 태그했다, Golden Gate Bridge에 간 글을 bob의 친구인 Cathy가 댓글을 남겼고, 그 댓글에 Cathy의 친구인 David가 좋아요를 눌렀다.” 위 그림이 표현하는 문장이다. 이 문장을 만약에 내가 가장 처음에 말했었던 OR 을 사용했었다면, 피드를 구성하기 위해서 수많은 테이블과 캐시들을 헤집고 다녔어야할 것이다. “어떻게 하면 최소한의 구조로 최대한의 표현력을 가지며 피드 정보를 빠르게 읽을 수 있을까?”에 대한 고민의 답으로 페이스북은 그래프 자료 구조를 사용하였다.

 

- 성격이 다른 두개의 DB(Memcache, MySQL) 유지에 대한 어려움

TAO 이전에는 페이스북의 웹서버가 MySQL에 직접 접근하여 소셜 그래프를 읽거나 작성했으며, memcahe를 lookaside 캐시로 사용했다. memcache는 키-값 데이터 모델이 있는 범용 네트워크 인메모리 데이터 저장소다. 캐시 누락시, 자동으로 채우거나 캐시 일관성을 유지해주지는 않았다. 때문에 엔지니어들은 MySQL과 memcache 라는 두개의 데이터 저장소에, 서로 다른 데이터 모델로 작업을 했어야했다. Memcahce-MySQL 조합을 효율적으로 사용하기 위해서는 시스템 내부에 대한 상당한 지식이 필요했고, 이로 인한 버그와 성능문제로 이어지는 실수가 있었다. 또한 제품의 요구사항이 변함에 따라 테이블 스키마를 변경하려면 각 데이터 베이스 운영자간의 조정이 필요했다. TAO는 이러한 작업들을 추상화하여 lookaside 캐시 아키텍처의 근본적인 단점을 피할 수 있었다. TAO는 persistence DB로 MySQL을 계속 사용하지만, 데이터베이스에 대한 접근을 중재하고 자체 그래프 인식 캐시를 사용한다.

캐시의 최종 일관성 유지를 위한 leader-follower 캐시 아키텍처도 흥미롭게 읽었는데, 이는 Meta 기술블로그[8], 혹은 논문의 4 Architecture로 가면 더 자세하게 알 수 있다.[9]

 

 

[ 트위터 : Push 모델 ]

http://content.time.com/time/specials/packages/article/0,28804,1901188_1901207_1901196,00.html

  페이스북은 게시판 구조에서부터 시작해왔었다. 게시판의 필터 검색이라는 기능처럼, 피드를 구성해갔다. Pull 모델을 사용하고, 더 빠르게 조회가 가능하도록 캐시를 적극적으로 사용했다. 위 그림에서의 트위터 소개를 보면, friend with communicate, exchange of quick frequent answer 이라는 문장을 볼 수 있다. 애초에 트위터라는 서비스는 메시지 전달이라는 관점에서 시작된 서비스다. 트위터의 트레이드 마크로 알려진 140자 제한은 SMS 글자수로 부터 시작되었다. 이처럼 SMS, 이메일 서비스와 흡사하게 시작한 트위터는 아키텍처에도 이러한 특징들을 담고 있다. 나의 메시지를 수신하는 사람들은 나를 팔로우하는 사람들이며, 결국 내가 메시지을 올린다는 것은 나를 팔로우하는 사람들의 받는 메시지함으로 수신되어야 한다는 것이다. 이메일의 경우에는 전체 문자를 배달하지만, 트위터의 경우에는 원본메시지는 하나만 두고, 팔로워들의 타임라인에는 참조키만 저장시키는 방식을 사용한다.

  쓰기 요청에 비해 읽기 요청이 많은 서비스라면, 차라리 읽기에 부담을 주는 페이스북의 Pull 모델보다는 트위터의 Push 모델이 좋은 선택일 수 있다. 하지만 이 또한 꽤 높은 비용이 들 수 있다. 내가 팔로우하고 있는 누군가가 트윗을 쓸 때마다 내 타임라인에 트윗의 참조 키가 배달된다. 저스틴 비버를 예로 들어 생각해보면, 저스틴 비버는 현재 1.1억 팔로워를 가지고 있다. 1억명 중에는 사실 트위터를 방문한지 한달이 넘은 이탈유저들도 많이 포함되어있을 것이다. 하지만 이 모든 사람들에게 트윗의 참조키를 전송해야만 한다. 대략적으로 계산을 해보면 8바이트(참조 키 크기) x 1억 = 800MB나 된다. 이런 인플루언서들이 트윗을 작성하는 순간에 엄청난 양의 데이터를 저장해야 하는데, DB로 이런 트래픽을 실시간으로 받아내는 것은 어렵기 때문에 사용자의 트윗 수신함, 즉 타임라인은 Redis 클러스터로 구성하며[10] 결국에는 MySQL로 저장하고, Gizzard( twitter sharding and replication framework on top of MySQL)를 사용하고 있다고 한다.[11]

 

   Pull(fanout-on-read) 모델은 사용자가 피드를 조회할때 큰 연산을 필요로 하고, Push(fanout-on-write) 모델은 사용자가 글을 게시할때 큰 연산을 필요로 한다. 때문에 Pull 모델을 선택한다면 "어떻게 하면 조회시간을 줄일 수 있느냐?"가 관건이고, 페이스북은 이 문제를 해결하기위해서 조회를 더 효과적으로할 수있는 TAO를 만들었다. 이에 반해 Push(fanout-on-write) 모델은 "이 많은 데이터들을 어떻게 저장시킬 것인가, 어떻게하면 빨리 저장시킬것인가?"가 관건이고, 트위터를 이를 해결하기 위해서 DB에 최종 일관성과 MySQL 샤딩을 위한 Gizzard를 도입했다. 하나를 반드시 선택하기 보다는 pull과 push를 혼합으로 사용하는 방법도 있을 수 있다. 대부분의 사용자에 대해서는 Push 모델을 사용하고, 팔로워가 아주 많은 사용자의 경우에는 팔로어로 하여금 해당 사용자의 포스팅을 필요로 할때 가져가도록 하는 Pull 모델을 사용하는 방법이 될 수 있을 것이다. 이처럼 pull과 push의 혼합으로 해결할 수 있다는 논문이 Yahoo에서 나왔다.[12] 어떤 모델이 더 우수하기 보다는 서비스 특성과 현재 개발 상황에 맞게 선택하면 그것이 가장 최선의 방법이라고 생각한다.

 

 

 

Ref)

[1] https://www.instafollowers.co/blog/limits-on-instagram

[2] https://mention.com/en/reports/instagram/followers/

[3] https://help.twitter.com/en/rules-and-policies/twitter-limits
[4] http://small-dbtalk.blogspot.com/2016/02/

[5] https://jobc.tistory.com/216

[6] https://dev.mysql.com/doc/refman/8.0/en/server-system-variables.html#sysvar_eq_range_index_dive_limit

[7] https://dev.mysql.com/doc/refman/8.0/en/server-system-variables.html

[8] https://engineering.fb.com/2013/06/25/core-data/tao-the-power-of-the-graph/

[9] https://www.usenix.org/system/files/conference/atc13/atc13-bronson.pdf

[10] https://blog.twitter.com/engineering/en_us/a/2012/mysql-at-twitter

[11] https://github.com/twitter-archive/gizzard
[12] https://hyse.org/pdf/distsyspapers/sigmod278-silberstein.pdf

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