GN⁺: 불완전한 시스템의 장점: Bluesky의 손실(Lossy) 타임라인

• 시스템 설계시 완벽한 일관성, 가용성, 낮은 지연시간, 높은 처리량을 동시에 만족하기는 사실상 어려운 과제임
  • 애플리케이션에 맞는 균형점을 찾는 방식으로 적합한 설계를 찾는 것이 중요함
• Bluesky의 팔로잉 피드/타임라인 설계에서 쓰기 성능을 개선하기 위해 일관성을 일부 희생하는 트레이드오프를 적용함
  • 그 결과 사용자에게 부정적인 영향을 주지 않으면서 P99 지연시간이 96% 이상 감소하는 효과를 봄

타임라인 팬아웃

• Bluesky에서 사용자가 게시물을 올리면, 시스템에 의해 인덱싱되고 데이터베이스에 저장되어 API 응답으로 제공됨
• 동시에 이 게시물을 팔로워 각각의 타임라인 테이블에 삽입하는 “팬아웃” 과정을 거침
• 이는 팔로워 목록을 조회한 뒤, 각 팔로워의 타임라인 테이블에 역순 삽입을 수행함
• 타임라인 테이블은 사용자별로 파티셔닝되어 분산 DB(ScyllaDB)에 저장되고, 고가용성을 위해 여러 샤드에 복제됨
  • 사용자마다 다른 샤드에 할당될 수 있음
• 저장 공간 절약을 위해 일정 길이를 넘어가는 타임라인은 오래된 게시물 레퍼런스를 정기적으로 삭제함

핫 샤드 문제

• Bluesky는 약 3,200만 명의 사용자가 있으며, 타임라인 데이터베이스는 수백 개의 샤드로 나뉨
• 수백만 명이 사용하는 시스템에서, 극단적으로 많은 팔로잉 관계를 가진 사용자가 존재할 수 있음
  • 예: 수십만 명을 팔로우하는 사용자
• 한 샤드에는 다수의 사용자 타임라인이 함께 저장됨
• 특정 사용자가 매우 많은 쓰기를 유발하면 해당 샤드가 과부하 상태(“핫 샤드”)가 됨
• 이러한 핫 샤드는 쓰기나 읽기 연산이 집중되어, 같은 샤드의 다른 사용자들에게도 지연이 전파되는 문제가 생김

지연시간 누적

• 한 사용자가 2,000,000명의 팔로워를 가질 경우, 순차적으로 쓰기하면 20분 이상 걸릴 수 있음
• 이를 줄이기 위해 팬아웃을 병렬화하면 평균 지연시간은 짧아짐
• 그러나 P99 지연시간(약 15밀리초 이상)이 여러 번 발생하여 병렬 작업 전체를 지연시킬 수 있음
• 팔로워가 매우 많은 경우, P99 혹은 P99.9 지연으로 인해 전체 팬아웃 시간이 최악의 경우 수 분에서 수십 분까지도 늘어날 수 있음

Lossy(손실) 타임라인

• 팔로잉 수가 지나치게 많은 사용자에게는 모든 게시물을 정확히 순서대로 보여주는 것이 현실적으로 불가능함
• 사람이 실제로 모든 게시물을 소비하기도 어려움
• 따라서 일정 기준치(예: ‘reasonable_limit’)를 넘는 팔로잉 수를 가진 사용자의 타임라인에는 일부 쓰기를 확률적으로 “드롭”하는 방식을 도입함
• loss_factor = min(reasonable_limit / num_follows, 1) 공식을 사용함
• 팬아웃 시에 무작위 값을 생성하여 loss_factor보다 큰 경우 타임라인 쓰기를 생략함
• 이를 통해 특정 사용자 타임라인에 대한 과도한 쓰기를 제한하고, 샤드 전체 성능 저하를 방지함

캐싱에 대하여

• 타임라인 쓰기는 초당 백만 건 이상 발생하기 때문에, 각 쓰기마다 사용자 팔로잉 수를 DB에서 직접 조회하면 부하가 매우 커짐
• 대신 Redis에 팔로잉 수가 높은 계정을 정렬 세트(sorted set)로 캐싱함
• 팬아웃 서비스 인스턴스는 30초마다 이 캐싱 정보를 메모리에 로드함
• 결과적으로 팬아웃 과정 중에도 고팔로잉 사용자 정보를 빠르게 조회할 수 있음
• 캐싱 정보가 완벽히 최신일 필요는 없으므로, 약간의 불완전성을 감수하며 성능과 확장성을 높이는 접근임

결과

• 로시 타임라인을 도입한 후 Timelines 데이터베이스에서 핫 샤드가 사실상 사라짐
• 팬아웃 한 페이지를 처리하는 데 걸리는 P99 지연이 90% 이상 줄어듦
• 전체 팬아웃 작업 시간을 보았을 때, P99 기준으로 5~10분 걸리던 작업이 10초 미만으로 단축됨
• 일관성을 일부 희생해도 서비스 이용자 기대치를 충분히 만족하며 대규모 확장성을 유지할 수 있음을 보여줌
• Bluesky 타임라인 아키텍처에는 여전히 개선 여지가 있지만, 이번 변경으로 쓰기 처리량과 확장성을 크게 향상시켰음

[neo]

Hacker News 의견

• 시스템 애호가로서 이런 기사를 즐기는 사람임. "완벽해야 한다"는 사고방식에 빠지기 쉬움

  • Blekko 검색 엔진의 백엔드에서 '결국 일관성 있는' 인덱스를 구축했음. 이는 사용자에게 더 빠르게 업데이트를 제공하지만, 동일한 쿼리를 수행하는 두 사용자가 약간 다른 결과를 얻을 수 있음
  • 시스템 이론이 많이 적용되며, 긍정적인 피드백이 있을 경우 진동할 가능성이 있음. 검색 엔진에서는 사용자가 클릭한 링크에 가중치를 부여하는 랭커가 긍정적인 피드백을 제공함
  • 시스템이 "비판적으로 감쇠"되도록 유지하는 것이 중요했음. 이는 빠르게 수렴하도록 함
  • 사용자의 타임라인이 샤딩되고 피드백 루프(예: '좋아요'나 '리포스트')가 있는 방식이 흥미로운 문제 공간으로 보임

• 타임라인을 계정의 인기도에 따라 하이브리드 방식으로 구현하지 않는 이유가 궁금함

  • 유명인 계정의 경우, 모든 메시지를 수백만 명의 팔로워에게 퍼뜨리는 대신, 팔로워의 타임라인을 제공할 때 유명인의 게시물을 가져와 병합하는 것이 더 저렴할 것임
  • 수백만 명의 팔로워가 그렇게 하면, 핫 캐시에서 읽기 전용으로 가져오는 것이 저렴할 것임

• 흥미로운 문제에 대한 흥미로운 해결책임. 공유해줘서 고마움

  • 저자가 "유명인"에서 "봇"으로 전환하는 부분을 이해하는 데 어려움이 있었음
  • 저자는 "손실 타임라인"이라는 완전히 다른 개념을 도입한 것처럼 보였음

• 일관성을 희생하는 이 전략에 대해 궁금함. 읽기나 쓰기에서 완전한 팬아웃이 아닌 다른 방법에 대한 생각이 있는지 궁금함

  • 모든 사용자의 타임라인에 쓰는 대신, 적어도 한 명의 팔로워가 있는 샤드에 한 번만 쓰는 방법을 상상해봄
  • 읽기 시, 주어진 사용자의 콘텐츠를 가져와 실제 팔로워를 필터링함
  • 읽기가 샤드 내에 위치하므로 지연 시간이 낮음
  • 메가 팔로워의 경우 페이지가 오래된 항목을 보지 않음

• 모든 사용자가 팔로우하는 수천 명의 사용자가 게시한 모든 것을 완벽하게 시간순으로 제공할 필요는 없지만, 타임라인에 항상 새로운 콘텐츠가 있도록 충분한 콘텐츠를 제공하는 것이 합리적임

  • 해결책이 불완전한 시간순서가 아니라 피드에서 게시물이 누락된 것처럼 보였음

• 핫 샤드 문제를 피하기 위해 팔로워 수를 제한하는 것이 어떻게 작동할지 궁금함

  • 각 사용자는 1000명의 팔로워마다 별도의 타임라인을 가지며 클라이언트가 이를 병합함
  • 필요하다면 실제 타임라인의 일부만 로드하여 손실 부분을 수행할 수 있음

• AWS는 이 문제에 대한 멋진 일반적인 접근 방식을 가지고 있음

  • 각 사용자를 여러 샤드에 할당하여 다른 사용자가 모든 샤드를 공유할 가능성을 줄임
  • 처음부터 셔플 샤딩을 했다면 많은 다른 사용자에게 영향을 주지 않고 새로운 문제를 해결할 수 있었을 것임

• 수십만 명의 사용자를 팔로우하는 계정은 콘텐츠를 긁어모으는 봇 계정임이 분명함. 차단하고 끝내겠음

  • 기술적 도전에 대해 읽는 것을 좋아함. Twitter는 수백만 명의 팔로워를 가진 유명인을 위한 특별한 아키텍처를 가지고 있음
  • Bluesky가 유사한 클론이라면 왜 이를 따르지 않았는지 궁금함

• 사용자의 프로필로 직접 이동하여 모든 게시물을 볼 때, 타임라인에 있어야 할 게시물이 없는 경우가 있음

  • Bluesky에서 100명 미만의 사용자를 팔로우하지만, 가끔 타임라인에서 사용자의 게시물을 보지 못하는 이유를 설명함

• 각 "페이지"가 다음 페이지를 가져오는 것을 차단하는 방식으로 팬아웃을 구현한 이유가 궁금함

  • 페이지 가져오기 활동은 연속적으로 팔로워를 가져와야 하며, 페이지의 모든 항목이 업데이트될 때까지 기다리지 않아야 함
  • 페이지를 가져와 S3에 저장하고 메타데이터와 S3 위치를 큐(SQS)에 게시하는 가져오기 구성 요소를 가지는 것이 떠오름
  • 이 시스템에서 동시성을 더 잘 제어할 수 있으며, 샤드를 키로 사용하여 큐에서 파티셔닝하여 작업을 "느리게" 할 수 있음