얼마 전에 데이터 중심 애플리케이션 설계라는 책을 읽다가 나온 예시였는데 "수많은 팔로워를 가진 사람의 트윗은 팔로워에게 어떻게 전달될까?" 라는 주제였어.
그 책에서는 데이터 플로우 단계의 해법만 간단히 언급하고 지나갔는데 이걸 조금 더 자세히 설계랑 구현 측면에서 풀어보고 싶더라고.
면접에서 시스템 디자인 단골 문제일 것 같긴 한데 어차피 정답은 없는 문제라 이런 방향으로 고민해봤다 정도로만 생각해 줘.


- 제한 사항
일단 유명인이라고 하면 바로 생각나는 그 이름, 트럼프의 팔로워를 찾아보니 1.1억명이고 일론 머스크는 2.3억명이더라.
여기서는 계산하기 쉽게 팔로워 1억명인 트럼프를 기준으로 할게.
그래서 최대 팔로워는 1억명이고, 메시지는 최대 140자(x에서 지금은 280자까지 가능하다고 하네), 그리고 모든 팔로워가 특정 시간 내에 메시지를 수신받아야 한다는 제한 사항을 가진 상태로 설계를 해볼거야.
설계는 크게 두 가지로 나눠서 포스트가 팔로워에게 전달되는 플로우의 설계와 실제 전달까지의 최적화 설계를 하나씩 풀어볼게.
(x로 바뀌면서 트윗이라는 이름이 포스트로 바뀌었으니 아래부터는 포스트로 계속)


- 초기 설계
일단 트럼프가 포스트를 하나 쓰면 postDB에 아래처럼 저장된다고 가정해보자.

postDB
{
  id: "trump",
  num: 1237,
  msg: "Make America Great Again"
}

그리고 트럼프를 팔로우한 사람의 정보는 followDB에 이렇게 저장된다고 생각해보고.

followDB
{
  id: "maga_fan1",
  follow_id: "trump"
}

포스트를 쓰고, 팔로워에게 알려주는 기능을 1분짜리 설계로 해보면 대충 아래 플로우가 떠오를거야.

1. 포스트를 DB에 기록한다.
2. 작성자 id를 팔로우한 id 목록을 얻는다.
SELECT id FROM followDB WHERE follow_id="trump"
3. id 목록에 있는 사람에게 push로 포스트를 보낸다.

여기서 팔로우한 id 목록이 1만개라면 하나의 인스턴스에서 버틸 수 있겠지만 1억명이라면 얘기가 달라질거야. 1억명의 id 목록을 한번에 가져오는 것만 해도 엄청난 리소스가 소비되겠지. 따라서 설계의 첫 목표는 "엄청난 수의 id 목록을 가져오기" 부터 시작해볼게.


- id 목록 가져오기
followDB에서 id를 1만개씩 가져오는 DB쿼리를 생각해보면 limit, offset을 통해 pagination으로 가져오거나, id로 인덱스 등록해서 last_id 를 저장하고 이거 다음부터 n개를 가져오는 cursor pagination을 사용할 수 있을거야.
그런데 첫번째 pagination 기법은 O(N)의 복잡도를 가지고 있어서 offset이 커질수록 선형적으로 느린 연산이 될거고, 두번째인 last_id 기준으로 하는건 여러 인스턴스에서 작동되지 못하기 때문에 scaleout 측면에서 불리해.

id를 최대 1만개씩 가진 n개 그룹으로 나누고, 이를 여러 worker에서 하나씩 가져가서 동시에 작업 가능하면 좋겠는데.. 라는 생각이 들어서 이 요구사항으로 팔로워 설계를 다시 해볼게.


- follow 동작 재설계
일단 follow 시에 자신의 group_id를 추가하는 방식으로 followDB 스키마를 바꿔봤어.

followDB
{
  id: "maga_fan1",
  follow_id: "trump",
  group_id: 1
}

이 group_id를 만드는 방법에는 순차 할당과 해시 할당이 사용될 수 있어. 순차 할당은 말 그대로 follow 요청을 차례대로 1번 그룹에 1만명을 등록하고, 1만1번째부터 2번 그룹으로 넘어가서 할당하는 방식이고, 해시는 자신의 id를 해싱해서 고유 숫자로 바꿔서 분산하는 방식이야.
1억개의 데이터를 하나의 DB에 담는건 지나치게 비효율적이니까 수평 파티셔닝의 파티션 키로 follow_id, group_id 를 넣어서 실제 쿼리 시에 하나의 인스턴스에만 접근하도록 하는 구조가 우선적으로 이루어져야 해.

순차 할당은 99%의 소규모 인플루언서도 동일한 룰로 follow 구조를 유지하기 편하다는 장점이 있는 반면, 삭제할 때에 내가 속한 group_id를 보내줘야 하는 단점이 있어. 안 그러면 수평 파티셔닝된 모든 DB 인스턴스로 쿼리를 보내야 하니까.
해싱 방식은 id 자체로 group_id를 계산할 수 있기 때문에 등록/삭제 시에는 편한데, 낮은 팔로워를 가진 아이디도 작은 크기의 그룹이 모든 DB 인스턴스에 분산되니 쿼리 효율성이 낮아지는 단점이 많이 커져.
그래서 여기서는 순차 할당 방식으로 선택해서 조금 더 구조를 다듬어볼게.

순차 할당 시에 group_id를 할당하는 방법으로는 가장 최근에 쓰인 group_id를 가져오고, 해당 group_id 인원이 1만명이 넘어갔는지 확인해서 넘어갔다면 다음 group_id를 전달하는 방식이 이상적일거야. 그런데 다른 측면도 생각해보면 예전에 팔로우한 유저가 언팔로우할 경우에 과거엔 1만명까지 채웠던 그룹 안의 아이디 개수가 점차 줄어들기만 할거쟎아? 
이건 메모리 단편화 문제와 비슷한 해법을 사용할 수 있는데, group_member_count를 관리하는 DB를 새로 만들어서 거기에 언팔로우 시에 그 group_id를 넣어서 다시 사용하도록 할 수도 있고, 일정 시간마다 돌아가는 크론에서 특정 개수 이하로 내려간 group끼리 병합해서 재구성하는 전략도 있을거야. 여기서는 전자를 활용할 때 추가되는 DB 스키마만 잠깐 넣어볼게. 순서는 상관없이 id 개수만 필요하기 때문에 이보다 복잡해지진 않겠지.

group_member_countDB
{
  id: "trump",
  group_id: 5,
  count: 9433
}

트럼프를 팔로우/언팔로우 할 때마다 이 레코드의 count 항목을 증감시켜주면 되겠지. 이건 raw데이터가 이미 존재하고 딱히 엄밀할 필요는 없기 때문에 캐시로 구현해도 상관없긴 한데, 캐시로 하면 복구 전략을 따로 세워야 하는 단점이 있어.

다시 트럼프를 팔로우하는 경우로 돌아와보면, 해당 유저는 비어 있는 group_id를 사용하거나 혹은 가장 최근에 쓰인 group_id를 사용해야 하니까 어딘가에 가장 최근의 group_id를 기록하고 있으면 좋겠지. 그건 follow_id마다 하나씩만 가지고 있는게 좋으니 테이블을 하나 더 만들어볼게.

recent_groupDB
{
  id: "trump",
  recent_group_id: 5,
  max_group_id: 20
}

자. 여기까지 개선된 follow 동작을 정리해보면, 최근 사용한 group_id를 가져와서 group_member_countDB에 해당 group_id의 count를 확인해서 1만이 넘지 않았다면 그대로 쓰고, 넘었다면 count가 1만 아래인 group_id를 다시 가져오거나 그런 그룹이 없다면 max_group_id를 하나 더해서 21번째 그룹을 새로 생성해서 그걸 사용하면 될거야. 그 후에 recent_groupDB를 갱신도 필요해.

위에는 대충 썼지만 실제 코드에서는 count가 1만보다 작은 group_id를 가져오라고 하면 안돼. 왜냐하면 언팔로우한 유저가 한명 발생해서 9999명인 group_id를 가져오게 된다면, 한명 채우고 다시 바꿔야 하기 때문이야. 그래서 이런 타입의 값에는 최대값과 동일하게 두는게 아니라 문턱값을 두는 전략이 유리해. 나라면 문턱값을 7천 정도로 설정할 것 같아.


- 포스팅이 팔로워에게 전달되는 설계 정리
이렇게 우리는 follow 구조 설계를 통해 1만명씩 할당된 순차적인 그룹을 만들었고, 이제 이걸 사용해서 group_id로 수평 파티셔닝 되어있는 DB에서 id 목록 1만개를 가져올 수 있게 되었어.
여기까지 설계되었으면 그 다음은 일반적인 서비스 브로커 형식으로 group_id 개수만큼 worker queue에 넣고, 이를 push worker가 가져가서 해당 group_id의 id 목록을 얻어와서 push 보내는 방식으로 사용하게 되는 거지.

여기엔 적용안된 다른 개선 사항도 몇 가지 고민해봤는데, sns 사용 빈도에 따라 group_id를 열성 유저, 활성 유저, 휴면 유저로 분리해서 넣고, 해당 타입에 따라 push 처리 우선 순위를 높이는 방법이야.
아무래도 열성 유저(하루 방문이 5회 정도) 그룹은 알림 속도에 민감할거라 우선 순위를 높여서 몇초라도 더 빨리 보내주는거지. 휴면 유저 그룹은 worker가 좀 여유로울 때 조금씩 처리해도 될거야.
그리고 팔로워가 전 세계에 있으니 push 메시지를 접속한 국가 기준으로 그룹을 zone마다 분리해서 보내면 지연 시간 감소와 장애 연관도가 줄어들어 좋을거고.

다만 설계가 지금보다 더 복잡해질테니 일단 아이디어 수준에서 남겨놓고, 다음은 전달 방식의 최적화 설계를 살펴볼게.


- 전달 방식의 최적화
팔로워에게 어떤 데이터를 보내야 할 지 하나씩 생각해보면, 팔로우 아이디, 포스트, 팔로워 아이디, 시간이 있겠고 나머지는 숫자 데이터(조회수, 답글, 리트윗, 좋아요, 북마크)가 있어.
보낼 데이터 중에 가장 길이가 긴 포스트는 문자열 압축 방법이 참 많지만 (기본적인 허프만 알고리즘이나 단어를 사전에 등록해서 사용하는 LZW 등) 여기서는 영문 140자를 압축없이 그대로 전달한다는 가정 하에 생각해볼게.

데이터를 binary로 직렬화한다면 패킷 크기가 많이 줄어들지만 복호화 전용 로직이 필요하기 때문에 범용적이지 않아. 따라서 어떤 곳에서든 해석 가능한 JSON 형식으로 전달하는게 이상적인데 그러면 포스트에 있는 텍스트를 가시성 문자로만 구성되도록 강제 변환하는게 좋을거야.
예를 들어 ascii 코드 22번은 SYN 전송 제어 문자인데 JSON은 전송될 때 문자열로 직렬화(JSON.stringify)하여 보내기 때문에 내가 예상했던 것과 크기 차이가 많이 나거든. 아래 코드를 볼게.

var a = "ab\x16cd";  // char: 22
var b = JSON.stringify(a);
console.log(a, a.length, b, b.length)
// abcd 5 "ab\u0016cd" 12

주석으로 된 부분이 실제 출력 결과인데, 문자열에서 출력해도 안보이는 1바이트 제어 문자가, JSON 직렬화로 풀어지니까 6바이트로 커진 모습이야.
저렇게 바꿔지는 이유 중에 하나는 바이너리가 아닌 텍스트 사이에 제어 문자가 있으면 방화벽이나 프록시가 해킹 시도 혹은 비정상 데이터로 간주하고 패킷을 차단할 수도 있기 때문이야. 그래서 JSON 표준에서는 제어 문자를 유니코드 시퀀스(\uXXXX)로 바꾸는데 이게 싫으면 base64로 변환해서 저장&전송하는 방식을 사용하는게 일반적이야.

저런 제어 문자를 허용한다면 클라이언트에서는 140자로 셌지만 실제 직렬화 후에는 최대 6배(720바이트)까지 늘어날 수 있어. 그래서 문자 개수를 제한할 때는 라인 피드같은 특수 문자도 포함되는지 여부가 최대 문자 개수에 민감하게 영향 주기도 해.
다만 요즘엔 2바이트 유니코드를 기본으로 삼기 때문에 대부분 문자 개수*2 만큼의 바이트를 실제 저장 공간으로 할당해놓을거야.

잠깐 딴길로 빠져서, JSON 직렬화 테스트 중에 흥미로운 부분이 있었는데 일반적인 비표시 제어 문자들은 유니코드 형식으로 변환되는 반면, 일부 제어 문자는 조금 더 짧게 변환되더라고. 
아래는 캐리지 리턴 문자로 테스트했는데 이 제어 문자는 기존값 b와 다르게 유니코드 형식으로 나오지 않은걸 볼 수 있어.

var c = JSON.stringify("ab\x0Dcd");  // char: 13
console.log(c, c.length);
// "ab\rcd" 8
var b = JSON.stringify("ab\x16cd");  // char: 22
console.log(b, b.length);
// "ab\u0016cd" 12

그래서 관련 rfc문서를 살펴보니 특정 제어 문자들은 유니코드가 아닌 변환 테이블이 별도로 존재하더라. 탭문자나 라인 피드, 백스페이스 문자 등
https://datatracker.ietf.org/doc/html/rfc4627.html#section-2.5
자주 쓰기도 하고 입력한 텍스트를 그대로 표시하는데 필수적인 문자니까 따로 되어있는게 당연하긴 한데 사소하지만 참 디테일하다 싶었어.


어쨌든 다시 돌아가서, 최대 문자열 길이를 포함해서 전체 패킷이 가변적이지 않아야 하는 주요 이유 중에 하나는 패킷 조각화를 막기 위해서야.
1억번의 메시지를 날려야 하는데 만약 라우터의 MTU를 살짝 넘어서게 되면 패킷 단편화가 일어나서 전송 횟수가 2배가 되고, 분할/조립 비용이 추가로 들게 될거야. 더 큰 문제는 이게 숨겨진 비용이라 깊숙히 모니터링을 해야 비로소 보인다는 거지.
그래서 설계 시점에서 MTU 내에서 사용 가능한 최대 용량을 설정해두고, 이를 기반으로 필드의 개수나 압축 여부 등을 결정해야 할거야.

대다수의 네트워크 장비에서는 MTU(Maximum Transmission Unit)로 1500을 사용하는데 아주 오래된 시스템이나 일부 임베디드에서는 500대를 사용한다고도 해. 
MTU는 3단계 IP계층의 값이니까 실제 TCP 계층에서는 IP헤더+TCP헤더 사이즈인 40바이트를 뺀 1460으로 맞춰야 해. 
이 값은 MSS(Maximum Segment Size)라고 부르는데 tcp handshake 시에 서버로부터 받아서 그에 맞게 자동으로 잘라 보내기 때문에 IP계층의 단편화를 최소한으로 동작하게 만들어 주고 있어. (tcp handshake에 대한 자세한 내용은 여기)
https://frogred8.github.io/docs/033_tcp_3-way_handshake/

다만 저 값에서 여유를 좀 두는게 좋은데 기존에는 IP헤더+TCP헤더인게 vpn 연결 시에는 IP헤더+vpn헤더+(원본IP헤더+TCP헤더)로 시스템 헤더 용량이 더 커지니까 vpn 환경에서는 IP계층에서 단편화가 일어날 수 있어. 
참고로 UDP는 MSS를 사용하지 않기 때문에 MTU가 넘어가는 용량을 보내면 IP계층에서 단편화가 발생하게 되니 UDP는 더 보수적으로 용량을 줄이는게 좋아.

공개된 장비의 MTU 테스트는 간단히 핑으로 할 수 있어. icmp 메시지에 데이터 크기를 추가하고 unfragment 옵션을 켜주면 끝이야.

$> ping google.com -D -s 1472

MTU 테스트인데 1500이 아닌 이유는 icmp 메시지가 IP계층이라서 IP헤더+ICMP헤더 사이즈가 28바이트라서 그래.
저 값을 조금씩 늘리면서 테스트하면 되는데 보통은 저거보다 크면 Message too long 메시지가 나오면서 안될거야. 공인망에서는 워낙 많은 장비를 지나가기 때문에 모든 장비가 1500 고정이라고 생각하면 돼.

다만 점보 프레임이라는 기술을 통해 MTU 9000이상을 사용할 수도 있는데 이는 주고받는 장비가 둘 다 지원할때만 가능해. 따라서 보통 내부망에서만 가능하지.
AWS EC2에서는 기본적으로 점보 프레임이 적용되어서 같은 그룹끼리는 사용이 가능하다던데 내부 데이터 교환이 많은 편이면 ifconfig로 MTU 한번 확인해보는 것도 좋을거야.
https://aws.amazon.com/ko/blogs/tech/aws-mtu-mss-pmtud/


- 설계 명세
이 설계를 기준으로 트럼프의 포스트 하나에 대해 필요 서비스 개수와 트래픽 등을 예측해볼게.
개별 팔로워에게 전달할 데이터 종류는 아이디와 메시지, 시간 외에 기타 데이터(조회수 등) 네다섯개 있는데 이걸 JSON 직렬화 시 늘어나는 크기를 생각해서 500바이트라고 어림잡아서 계산해볼게.

트럼프는 1억명의 팔로워니까 1만명 정도 차있는 그룹이 1만개 생성되어 있을거고, 여기서 하나의 push 서비스 tps가 5천이라고 한다면, 10초 내에 1만개의 그룹을 처리하려면 2천개의 트럼프 전용 push 서비스 인스턴스가 필요해.
전체 점유 시간은 2만초, 약 5시간 30분이 걸리는 작업이야. 이 말은 반대로 말해서 하나의 push 인스턴스로 진행한다면 저 정도가 걸린다는거지.

트래픽은 내부/외부 기준으로 살펴볼게. 
내부로는 하나의 그룹마다 이걸 전달해줘야 하니 개별 push 서비스가 가져가야 할 데이터는 500바이트*1만개 그룹을 해서 5MB 정도의 트래픽이 발생해. 
이건 위에서 정해진 지연시간을 기준으로 최대 대역폭을 계산해야 하는데 10초로 본다면 1초당 500KB 만큼의 내부 대역폭이 필요할거야. 

외부 트래픽은 각 push 서비스가 전달받은 500바이트를 1억명에게 보내면 50GB라는 큰 수치가 나오는데 이걸 비트로 환산하면 전체 전송 시 400Gbit가 필요해.
일반적인 빌딩에서 쓰는 백본은 10Gbps망을 사용하는데 AWS에서는 LAG(Link Aggregation Group) 기술을 사용해 하나의 백본 라인이 4개의 100Gbps 라인을 합친 400Gbps를 사용한다고 해. 이런 라인이 몇 개나 있는데다가 이건 2023년 자료니까 지금은 더 엄청나겠지.
https://aws.amazon.com/blogs/networking-and-content-delivery/growing-aws-internet-peering-with-400-gbe/

어쨌든 모든 팔로워에게 전달하는 트래픽이 400Gbit니까 10Gbps 라인을 온전히 혼자 사용한다해도 최소 40초가 걸리는 작업이야. 이쯤되면 전용 백본 라인을 별도로 임대해야하는 수준이지.
다만 여기서의 외부 트래픽은 하나의 zone에서 나가는 트래픽이 아니라 전 세계로 분산될거라서 대충 10개 zone으로 분산된다면 10Gbps 4초로 줄어들 수 있을거야.
알람 최대 지연시간을 10초로 늘린다면 외부 대역폭 5Gbps 라인만 빌려도 될텐데, 만약 외부 대역폭이 1Gbps로 제한되어 있다면 40초 안에 전송할 방법은 없다고 봐야겠지.

여기까지 설계가 대충 끝나게 되면 타팀과 최종 문서로 논의할 때는 알람 최대 지연시간이 10초, 50초, 500초 정도의 시나리오(각 시간마다의 push 서비스 인스턴스 개수나 백본의 대역폭 등)를 제공해서 가장 비싼 자원의 최대치가 기준이 되어 지연시간이 정해지게 될거야.
기획팀에서 10초 내에 무조건 전달해야돼! 라고 하면 바로 계산서를 들이밀면 되는 거지. (네 그러면 백본망 확장이 필요하고, 인스턴스 N개 유지비 얼마가 더 들고 블라블라)


- 실제 사용 중인 아키텍처
x에서 실제로는 어떻게 구현되어 있는지 글 다 쓰고 나서 찾아봤는데 이 글이 가장 잘 나와있네.
https://medium.com/@kaur.exe/5239256c4234

이걸 대충 요약해보면, x에서는 하이브리드 전략을 쓰는데 일반 유저는 push로 보내지만 헤비 인플루언서의 포스트는 그 자신의 타임라인에만 저장했다가 팔로워가 타임라인을 보는 시점에 그 사람 자신의 타임라인과 내가 팔로우한 헤비 인플루언서의 타임라인을 합쳐서 보여주는 pull 방식으로 구현했다고 해.
만약 트럼프의 포스트가 나에게 알람이 왔다면 그건 백그라운드에서 내 타임라인을 pull하면서 트럼프의 타임라인이 업데이트 되었다는걸 확인했기 때문에 그럴거라고 예상할 수 있어. (난 sns를 안해서 그렇게 동작하는지는 잘 모르겠다..)

그리고 아래 논문에는 다른 sns(페북, 인스타그램 등)의 feed 아키텍처도 간단히 나와있는데 설계의 지향점이 조금씩 다르다는 것도 재밌네. 스샷으로 그 페이지만 넣어봤어.
https://www.ijcaonline.org/archives/volume179/number48/sudhakaran-2018-ijca-917224.pdf


- 결론
1) sns에서 헤비 인플루언서의 글 전파에는 엄청난 자원이 소모된다.
2) 실제 서비스에서는 정공법으로 공략하기보단 사용자 인터페이스를 고려한 하이브리드 전략이 유리하다.
3) 메시지를 최대한 덜 보내는 방법이나 데이터 재사용, 캐시에 대한 부분도 더 고민해보면 재밌을 것 같다.
4) 책 읽다가 지겨워서 잠깐 고민해본다는게 꽤 길어졌네..

이전글: https://frogred8.github.io/
#frogred8 #design

---