ข้อดีของระบบที่ไม่สมบูรณ์แบบ: ไทม์ไลน์แบบสูญเสียข้อมูลของ Bluesky

 (jazco.dev)
16 คะแนน โดย GN⁺ 2025-02-20 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ในการออกแบบระบบ เป็นโจทย์ที่แทบเป็นไปไม่ได้ในทางปฏิบัติที่จะทำให้ได้ทั้งความสอดคล้องสมบูรณ์แบบ ความพร้อมใช้งาน เวลาแฝงต่ำ และปริมาณงานสูงพร้อมกัน
    • สิ่งสำคัญคือการหาแบบออกแบบที่เหมาะสมผ่านการหาจุดสมดุลที่สอดคล้องกับแอปพลิเคชัน
  • ในการออกแบบฟีด Following/ไทม์ไลน์ของ Bluesky มีการใช้ trade-off โดย ยอมลดความสอดคล้องลงบางส่วน เพื่อ ปรับปรุงประสิทธิภาพการเขียน
    • ผลลัพธ์คือ ลด P99 latency ได้มากกว่า 96% โดยไม่ส่งผลกระทบเชิงลบต่อผู้ใช้

การ fanout ของไทม์ไลน์

  • เมื่อผู้ใช้โพสต์ข้อความบน Bluesky ระบบจะทำการสร้างดัชนี เก็บลงฐานข้อมูล และให้บริการผ่าน API response
  • ในเวลาเดียวกัน โพสต์นี้จะผ่านกระบวนการ “fanout” โดยแทรกลงในตารางไทม์ไลน์ของผู้ติดตามแต่ละคน
  • กระบวนการนี้จะดึงรายการผู้ติดตาม แล้วทำการแทรกแบบย้อนลำดับลงในตารางไทม์ไลน์ของผู้ติดตามแต่ละราย
  • ตารางไทม์ไลน์ถูก partition ตามผู้ใช้และจัดเก็บในฐานข้อมูลแบบกระจาย (ScyllaDB) พร้อมทำ replication ไปยังหลาย shard เพื่อความพร้อมใช้งานสูง
    • ผู้ใช้แต่ละคนอาจถูกจัดสรรไปยัง shard ที่ต่างกัน
  • เพื่อประหยัดพื้นที่จัดเก็บ ไทม์ไลน์ที่ยาวเกินขนาดที่กำหนดจะมีการลบ reference ของโพสต์เก่าออกเป็นระยะ

ปัญหา hot shard

  • Bluesky มีผู้ใช้ประมาณ 32 ล้านคน และฐานข้อมูลไทม์ไลน์ถูกแบ่งออกเป็นหลายร้อย shard
  • ในระบบที่มีผู้ใช้งานระดับหลายล้านคน อาจมีผู้ใช้ที่มีความสัมพันธ์การติดตามจำนวนมากผิดปกติได้
    • เช่น ผู้ใช้ที่ติดตามคนอื่นหลายแสนบัญชี
  • หนึ่ง shard จะเก็บไทม์ไลน์ของผู้ใช้หลายคนร่วมกัน
  • หากผู้ใช้บางรายก่อให้เกิดการเขียนจำนวนมากผิดปกติ shard นั้นก็จะเข้าสู่ภาวะโอเวอร์โหลด (“hot shard”)
  • hot shard เหล่านี้ทำให้การอ่านหรือเขียนกระจุกตัว และความล่าช้าจะลามไปถึงผู้ใช้อื่นที่อยู่บน shard เดียวกัน

การสะสมของเวลาแฝง

  • หากผู้ใช้คนหนึ่งมีผู้ติดตาม 2,000,000 คน การเขียนแบบลำดับต่อเนื่องอาจใช้เวลามากกว่า 20 นาที
  • เพื่อแก้ปัญหานี้ การทำ fanout แบบขนานช่วยลดเวลาแฝงเฉลี่ยได้
  • อย่างไรก็ตาม P99 latency (ราว 15 มิลลิวินาทีขึ้นไป) อาจเกิดขึ้นหลายครั้งและทำให้งานแบบขนานทั้งหมดช้าลง
  • เมื่อมีผู้ติดตามจำนวนมากมาก P99 หรือ P99.9 latency อาจทำให้เวลา fanout ทั้งหมดเลวร้ายที่สุดยืดออกจากระดับหลายนาทีไปจนถึงหลายสิบนาที

ไทม์ไลน์แบบ Lossy

  • สำหรับผู้ใช้ที่ติดตามบัญชีจำนวนมากเกินไป การแสดงทุกโพสต์อย่างถูกต้องครบถ้วนตามลำดับนั้นแทบเป็นไปไม่ได้ในทางปฏิบัติ
  • และในความเป็นจริง มนุษย์เองก็ยากจะบริโภคโพสต์ทั้งหมดได้
  • ดังนั้น สำหรับไทม์ไลน์ของผู้ใช้ที่มีจำนวนการติดตามเกินเกณฑ์ที่กำหนด (เช่น reasonable_limit) จึงมีการนำวิธี “drop” การเขียนบางส่วนแบบสุ่มตามความน่าจะเป็นมาใช้
  • ใช้สูตร loss_factor = min(reasonable_limit / num_follows, 1)
  • ระหว่าง fanout จะมีการสร้างค่าสุ่ม และหากค่ามากกว่า loss_factor ก็จะข้ามการเขียนลงไทม์ไลน์
  • วิธีนี้ช่วยจำกัดการเขียนที่มากเกินไปต่อไทม์ไลน์ของผู้ใช้บางราย และป้องกันไม่ให้ประสิทธิภาพของ shard ทั้งก้อนลดลง

ว่าด้วยการแคช

  • การเขียนไทม์ไลน์เกิดขึ้นมากกว่าหนึ่งล้านครั้งต่อวินาที ดังนั้นถ้าต้อง query จำนวนบัญชีที่ผู้ใช้ติดตามจากฐานข้อมูลโดยตรงทุกครั้งที่เขียน ภาระโหลดจะสูงมาก
  • แทนที่จะทำเช่นนั้น ระบบจะ cache บัญชีที่มีจำนวนการติดตามสูงไว้ใน Redis ด้วย sorted set
  • อินสแตนซ์ของบริการ fanout จะโหลดข้อมูลแคชนี้เข้าหน่วยความจำทุก ๆ 30 วินาที
  • ส่งผลให้สามารถตรวจสอบข้อมูลผู้ใช้ที่มีจำนวนการติดตามสูงได้อย่างรวดเร็วแม้อยู่ระหว่างกระบวนการ fanout
  • เนื่องจากข้อมูลแคชไม่จำเป็นต้องทันสมัยสมบูรณ์แบบ แนวทางนี้จึงยอมรับความไม่สมบูรณ์เล็กน้อยเพื่อแลกกับประสิทธิภาพและความสามารถในการขยายระบบ

ผลลัพธ์

  • หลังนำไทม์ไลน์แบบ lossy มาใช้ ปัญหา hot shard ในฐานข้อมูล Timelines ก็แทบหายไป
  • P99 latency สำหรับการประมวลผล fanout หนึ่งหน้า ลดลงมากกว่า 90%
  • เมื่อมองที่เวลารวมของงาน fanout ทั้งหมด งานที่เดิมใช้เวลา 5–10 นาทีในเกณฑ์ P99 ถูกลดลงเหลือต่ำกว่า 10 วินาที
  • สิ่งนี้แสดงให้เห็นว่า แม้จะยอมเสียความสอดคล้องไปบางส่วน ก็ยังสามารถตอบสนองความคาดหวังของผู้ใช้บริการได้อย่างเพียงพอ พร้อมรักษาความสามารถในการขยายระบบระดับใหญ่
  • สถาปัตยกรรมไทม์ไลน์ของ Bluesky ยังมีพื้นที่ให้ปรับปรุงต่อไป แต่การเปลี่ยนแปลงครั้งนี้ช่วยเพิ่มทั้งปริมาณงานเขียนและความสามารถในการขยายระบบอย่างมาก

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-02-20
ความคิดเห็นจาก Hacker News

  • ในฐานะคนที่ชอบระบบ ก็เป็นคนที่ชอบบทความแบบนี้มาก และมันง่ายที่จะติดอยู่กับแนวคิดที่ว่า "ต้องสมบูรณ์แบบ"

    • เคยสร้างดัชนีแบบ 'eventually consistent' ในแบ็กเอนด์ของเสิร์ชเอนจิน Blekko ซึ่งทำให้ส่งอัปเดตให้ผู้ใช้ได้เร็วขึ้น แต่ก็อาจทำให้ผู้ใช้สองคนที่ค้นหาคำค้นเดียวกันได้ผลลัพธ์ต่างกันเล็กน้อย
    • มีการนำทฤษฎีระบบมาใช้เยอะ และถ้ามี positive feedback ก็มีโอกาสเกิดการสั่นได้ ในเสิร์ชเอนจิน ตัวจัดอันดับที่ให้น้ำหนักกับลิงก์ที่ผู้ใช้คลิกจะเป็นตัวให้ positive feedback
    • สิ่งสำคัญคือการทำให้ระบบอยู่ในสภาพ "critical damping" ซึ่งช่วยให้มันคอนเวอร์จได้อย่างรวดเร็ว
    • วิธีที่ไทม์ไลน์ของผู้ใช้ถูกแบ่งชาร์ดและมีฟีดแบ็กลูปอยู่ด้วย (เช่น "ถูกใจ" หรือ "รีโพสต์") ดูเป็นพื้นที่ปัญหาที่น่าสนใจ

  • สงสัยว่าทำไมถึงไม่ทำไทม์ไลน์แบบไฮบริดตามความนิยมของบัญชี

    • สำหรับบัญชีคนดัง แทนที่จะกระจายทุกข้อความไปยังผู้ติดตามหลายล้านคน การดึงโพสต์ของคนดังมาแล้วรวมตอนเสิร์ฟไทม์ไลน์ให้ผู้ติดตามน่าจะถูกกว่า
    • ถ้ามีผู้ติดตามหลายล้านคนทำแบบนั้น การดึงจาก hot cache แบบอ่านอย่างเดียวน่าจะถูกกว่า

  • เป็นวิธีแก้ปัญหาที่น่าสนใจสำหรับปัญหาที่น่าสนใจ ขอบคุณที่แชร์

    • อ่านแล้วมีปัญหาในการเข้าใจช่วงที่ผู้เขียนเปลี่ยนจาก "คนดัง" ไปเป็น "บอต"
    • ดูเหมือนผู้เขียนจะนำเสนอแนวคิดที่ต่างออกไปโดยสิ้นเชิงในชื่อ "lossy timeline"

  • สงสัยเกี่ยวกับกลยุทธ์นี้ที่ยอมแลกความสอดคล้องกันไป และอยากรู้ว่ามีความคิดเกี่ยวกับวิธีอื่นที่ไม่ใช่ fan-out แบบเต็มในการอ่านหรือการเขียนหรือไม่

    • แทนที่จะเขียนไปยังไทม์ไลน์ของผู้ใช้ทุกคน ลองนึกถึงการเขียนเพียงครั้งเดียวต่อชาร์ดที่มีผู้ติดตามอย่างน้อยหนึ่งคน
    • ตอนอ่านก็ดึงคอนเทนต์สำหรับผู้ใช้ที่กำหนดแล้วกรองผู้ติดตามจริงออกมา
    • การอ่านอยู่ภายในชาร์ดจึงมี latency ต่ำ
    • สำหรับผู้ติดตามระดับมหาศาล หน้าเพจจะไม่เห็นรายการเก่าที่ค้างอยู่

  • ไม่จำเป็นต้องส่งมอบทุกอย่างที่ผู้ใช้หลายพันคนที่ทุกคนติดตามโพสต์ไว้แบบเรียงตามเวลาอย่างสมบูรณ์ แต่การมีคอนเทนต์มากพอให้ไทม์ไลน์มีของใหม่อยู่เสมอก็ดูสมเหตุสมผล

    • วิธีแก้ดูเหมือนไม่ใช่ลำดับเวลาที่ไม่สมบูรณ์ แต่เหมือนมีโพสต์หายไปจากฟีดมากกว่า

  • สงสัยว่าการจำกัดจำนวนผู้ติดตามเพื่อหลีกเลี่ยงปัญหา hot shard จะทำงานอย่างไร

    • ผู้ใช้แต่ละคนมีไทม์ไลน์แยกกันทุก ๆ ผู้ติดตาม 1000 คน แล้วให้ไคลเอนต์รวมเข้าด้วยกัน
    • ถ้าจำเป็น ก็สามารถโหลดเฉพาะบางส่วนของไทม์ไลน์จริงเพื่อทำส่วนที่เป็น lossy ได้

  • AWS มีแนวทางทั่วไปที่เจ๋งสำหรับปัญหานี้

    • กำหนดผู้ใช้แต่ละคนไปยังหลายชาร์ดเพื่อลดโอกาสที่ผู้ใช้อื่นจะใช้ทุกชาร์ดร่วมกัน
    • ถ้าทำ shuffle sharding มาตั้งแต่แรก ก็น่าจะแก้ปัญหาใหม่ ๆ ได้โดยไม่กระทบผู้ใช้อื่นจำนวนมาก

  • บัญชีที่ติดตามผู้ใช้หลายแสนคนนั้นชัดเจนว่าเป็นบอตที่ไล่กวาดคอนเทนต์ ควรบล็อกไปเลยแล้วจบ

    • ชอบอ่านเรื่องความท้าทายทางเทคนิค Twitter มีสถาปัตยกรรมพิเศษสำหรับคนดังที่มีผู้ติดตามหลายล้านคน
    • ถ้า Bluesky เป็นโคลนที่คล้ายกัน ก็สงสัยว่าทำไมถึงไม่ทำตามแนวทางนั้น

  • เวลาเข้าไปที่โปรไฟล์ของผู้ใช้โดยตรงเพื่อดูโพสต์ทั้งหมด บางครั้งก็มีโพสต์ที่ควรอยู่ในไทม์ไลน์แต่หายไป

    • อธิบายได้ว่าทำไมใน Bluesky ถึงติดตามผู้ใช้น้อยกว่า 100 คน แต่บางครั้งก็ไม่เห็นโพสต์ของบางคนในไทม์ไลน์

  • สงสัยว่าทำไมถึงทำ fan-out ในแบบที่แต่ละ "หน้า" ไปบล็อกการดึงหน้าถัดไป

    • กิจกรรมดึงหน้าเพจควรดึงผู้ติดตามต่อเนื่องไปได้ และไม่ควรรอให้ทุกรายการในหน้านั้นอัปเดตเสร็จก่อน
    • นึกถึงการมีคอมโพเนนต์ดึงข้อมูลที่ดึงหน้าเพจมา เก็บลง S3 แล้วโพสต์เมทาดาทากับตำแหน่ง S3 ลงคิว (SQS)
    • ในระบบแบบนี้จะควบคุม concurrency ได้ดีกว่า และสามารถใช้ชาร์ดเป็นคีย์เพื่อแบ่งพาร์ทิชันในคิวและทำให้งาน "ช้าลง" ได้