พจนานุกรม CRDT: คู่มือเชิงปฏิบัติสำหรับโครงสร้างข้อมูลแบบกระจาย

 (iankduncan.com)
25 คะแนน โดย GN⁺ 2025-12-01 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • CRDT (Conflict-free Replicated Data Type) คือโครงสร้างข้อมูลแบบกระจายที่ทำให้ สามารถผสานข้อมูลให้สอดคล้องกันได้โดยไม่ต้องมีการประสานงาน แม้จะเกิดการแบ่งเครือข่ายหรือมีการแก้ไขพร้อมกัน
  • หากการผสานข้อมูลเป็นไปตามคุณสมบัติ สลับที่ได้·เปลี่ยนหมู่ได้·ไอดีมโพเทนต์ ก็จะทำให้รีพลิกาทั้งหมดค่อย ๆ ลู่เข้าสู่สถานะเดียวกันในที่สุด
  • ตัวอย่างรูปแบบที่สำคัญ ได้แก่ G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Register, MV-Register, RGA, WOOT, Logoot ซึ่งแต่ละแบบรองรับความต้องการด้าน การเพิ่ม·การลบ·การเพิ่มซ้ำ·การรักษาลำดับ ที่ต่างกัน
  • Delta CRDT ช่วยเพิ่มประสิทธิภาพด้วยการส่งเฉพาะส่วนที่เปลี่ยนแปลงแทนสถานะทั้งหมด และ Garbage Collection เป็นโจทย์สำคัญในการแก้ปัญหาการสะสมของเมทาดาทา
  • แม้ CRDT จะไม่ใช่คำตอบที่สมบูรณ์แบบ แต่ก็ถือเป็นทางเลือกที่ทรงพลังสำหรับ ระบบที่ให้ความสำคัญกับความพร้อมใช้งานมากกว่าความสอดคล้องกันแบบทันที

แนวคิดพื้นฐานของ CRDT

  • CRDT คือ โครงสร้างข้อมูลที่สามารถผสานกันได้โดยไม่ต้องประสานงาน แม้จะมีการแก้ไขพร้อมกันในสภาพแวดล้อมแบบกระจาย
    • หากการผสานมีคุณสมบัติ commutative (สลับที่ได้), associative (เปลี่ยนหมู่ได้) และ idempotent (ไอดีมโพเทนต์) รีพลิกาทั้งหมดจะลู่เข้าสู่สถานะเดียวกัน
  • ออกแบบโดยอิงแนวคิด Lattice (แลตทิซ) เพื่อให้สถานะเคลื่อนที่ “ขึ้นด้านบน” เท่านั้นเสมอ
    • ตัวอย่าง: G-Counter ผสานตัวนับของแต่ละรีพลิกาด้วย max เพื่อรับประกันการรวมผลโดยไม่สูญหาย
  • CRDT มี 2 แนวทางหลัก คือ State-based (CvRDT) และ Operation-based (CmRDT)
    • CvRDT ผสานสถานะทั้งหมด ส่วน CmRDT กระจายตัวปฏิบัติการ

ประเภท CRDT หลัก ๆ

  • G-Counter: ตัวนับที่เพิ่มได้อย่างเดียว โดยรวมค่าของแต่ละรีพลิกาเข้าด้วยกัน
  • PN-Counter: รวม G-Counter สำหรับการเพิ่มและการลดเข้าด้วยกัน เพื่อรองรับตัวนับสองทิศทาง
  • G-Set: เซตที่เพิ่มได้อย่างเดียว
  • 2P-Set: เพิ่มและลบได้ แต่เพิ่มกลับเข้าไปใหม่ไม่ได้
  • LWW-Element-Set: อิง timestamp โดยให้การปฏิบัติการล่าสุดเป็นฝ่ายชนะ
  • OR-Set: ใช้แท็กที่ไม่ซ้ำกันเพื่อ ผสานข้อมูลโดยไม่สูญหายเมื่อมีการเพิ่มพร้อมกัน และทำงานแบบ add-wins
  • LWW-Register / MV-Register: สำหรับเก็บค่าเดี่ยว โดย LWW มีผู้ชนะเพียงค่าเดียว ส่วน MV เก็บค่าที่เกิดพร้อมกันทั้งหมด
  • OR-Map: โครงสร้างแบบแมปที่รวม OR-Set ตามแต่ละคีย์
  • RGA / WOOT / Logoot / LSEQ: CRDT สำหรับข้อมูลลำดับแบบ sequence
    • RGA อิงต้นไม้, WOOT อิงการอ้างอิงสองทิศทาง, Logoot/LSEQ อิงตัวระบุตำแหน่ง

แนวคิด CRDT ขั้นสูง

  • Causal CRDTs: ใช้เวกเตอร์เวอร์ชันเพื่อติดตามความสัมพันธ์เชิงเหตุและผล ทำให้ตรวจจับความขัดแย้งได้แม่นยำขึ้น
  • Delta CRDTs: ส่งเฉพาะส่วนที่เปลี่ยนแปลง (delta) แทนสถานะทั้งหมด เพื่อเพิ่มประสิทธิภาพของเครือข่าย
  • Tree CRDTs: รองรับการทำสำเนาข้อมูลแบบลำดับชั้น เช่น ระบบไฟล์ โดยต้องรักษาความสัมพันธ์พ่อ-ลูก
  • Observed-Remove Shopping Cart: ตัวอย่างตะกร้าสินค้าอีคอมเมิร์ซที่รวม OR-Set กับ PN-Counter เข้าด้วยกัน

ปัญหา Garbage Collection

  • CRDT ต้องสะสมเมทาดาทาอย่างต่อเนื่องเพื่อให้เกิดการลู่เข้าสู่สถานะเดียวกัน จึงเกิด ปัญหาการเติบโตไม่สิ้นสุด
    • ตัวอย่าง: แท็กของ OR-Set, tombstone ของ RGA
  • มีหลายกลยุทธ์ เช่น การหมดอายุแบบอิงเวลา, การลบแบบอิงฉันทามติ, การติดตามเชิงเหตุและผลด้วยเวกเตอร์เวอร์ชัน, การกำหนดเพดานเมทาดาทา, checkpoint/rebase
  • แต่ละวิธีต้องแลกเปลี่ยนกันระหว่าง ความปลอดภัย (ป้องกันการฟื้นคืนแบบซอมบี้) กับ ประสิทธิภาพด้านพื้นที่

ประสิทธิภาพและแนวทางการเลือกใช้

  • ความซับซ้อนด้านพื้นที่และเวลาของ CRDT แต่ละประเภทแตกต่างกันไปตามจำนวนรีพลิกา จำนวนองค์ประกอบ และจำนวนแท็ก
    • G/PN-Counter แปรผันตามจำนวนรีพลิกา, OR-Set แปรผันตามจำนวนแท็ก, RGA มี tombstone สะสม
  • Delta CRDT ช่วยปรับปรุงประสิทธิภาพการผสานได้อย่างมาก
  • เกณฑ์การเลือกใช้:
    • ต้องการแค่การเพิ่ม → G-Counter, G-Set
    • ต้องการการลบ แต่ไม่จำเป็นต้องเพิ่มซ้ำ → 2P-Set
    • ยอมรับ LWW ได้ → LWW-Set/Register
    • ต้องการเก็บการแก้ไขพร้อมกัน → OR-Set, MV-Register
    • ต้องการรักษาลำดับ → RGA, Logoot
    • โครงสร้างซ้อนกัน → OR-Map

บทสรุป

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

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

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

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

  • หนึ่งในจุดที่น่าสนใจของ CRDT คือมันไม่ใช่แค่ ไลบรารีที่ประกอบจาก CRDT ระดับล่างหลายตัว
    ตัวอย่างเช่น Automerge เป็น CRDT ที่สมบูรณ์ในตัวเอง และรับประกันความสอดคล้องแม้ภายใต้ภาวะ concurrent ผ่าน การพิสูจน์ทางคณิตศาสตร์
    ทีม Automerge ตรวจสอบดีไซน์ด้วยเครื่องมือพิสูจน์ทฤษฎีบทอย่าง Isabelle และตั้งเป้าสร้าง implementation ที่ทั้งเร็วและแม่นยำโดยนำเทคนิคด้านประสิทธิภาพล่าสุดจากโลกฐานข้อมูลมาใช้
    ถ้าคุณกำลังสร้าง SaaS ที่ต้องการการทำงานร่วมกันแบบเรียลไทม์ เช่น Notion หรือ Figma ก็สามารถนำ โครงสร้างข้อมูลสำหรับการทำงานร่วมกัน ไปใช้ได้ทันทีแม้จะไม่เข้าใจทฤษฎีที่ซับซ้อน
    ฝั่งแบ็กเอนด์มีแค่ key-value storage ธรรมดาก็พอ และฝั่งฟรอนต์เอนด์ก็ใช้แค่ไลบรารีตัวเดียว

    • Automerge มี API ที่ดีเยี่ยมไม่ใช่แค่ใน Rust แต่รวมถึง Javascript และ C ด้วย
      ผมเองก็เคยทำ ไลบรารี automerge บน Redis และสามารถสร้าง เซิร์ฟเวอร์ซิงก์แบบต่อเนื่องถาวร ที่สมบูรณ์ได้โดยใช้ pub/sub
      ยังทำเดโมซิงก์เอกสารระหว่างหลายเบราว์เซอร์ได้อย่างรวดเร็วด้วยฟีเจอร์ websocket ของ Webdis
    • Automerge ยอดเยี่ยมก็จริง แต่ก็ยังให้ความรู้สึกว่าเน้น แนวทางเชิงวิชาการ ค่อนข้างมาก
      ถ้าต้องการ DX ที่ดีกว่าและ full-stack DB บนพื้นฐาน CRDT ขอแนะนำ Triplit.dev แม้ความเร็วในการพัฒนาจะช้าลงบ้าง แต่ฟังก์ชันต่าง ๆ ก็ถือว่าพร้อมใช้งานมากแล้ว
    • การที่ Automerge เป็น CRDT ที่สมบูรณ์ไม่ได้ทำให้น่าแปลกใจนัก
      ส่วนตัวผมก็ชอบ Loro เหมือนกัน แต่ยังเป็น โครงสร้างแบบอิงเอกสาร อยู่ จึงขาด query engine และถ้าจะดึงข้อมูลที่ต้องการก็ต้องระบุรายการ nested ที่เฉพาะเจาะจงเอง
    • การที่ Automerge ไม่รองรับ self-hosting เป็นข้อจำกัดร้ายแรงสำหรับแอปพลิเคชันจำนวนมาก

  • เป็นบทความที่สรุป CRDT ได้ดีตั้งแต่พื้นฐานไปจนถึงแนวคิดขั้นสูง
    เสริมอีกนิดว่า Riak ยังถูกดูแลอยู่ในรูปของ OpenRiak

    • เพิ่งรู้จัก OpenRiak เป็นครั้งแรก แต่พอเห็นว่าเพื่อนร่วมงานเก่า ๆ มีส่วนร่วมอยู่ก็รู้สึกดีใจ Basho เป็น กลุ่มวิศวกรที่ยอดเยี่ยม จริง ๆ

  • ตลอด 2 ปีที่ผ่านมา ผมพัฒนา CRDT ด้วยตัวเอง แต่สุดท้ายก็ตระหนักว่ามันมี trade-off มากเกินไป เลยเปลี่ยนไปใช้เฟรมเวิร์ก OT แบบอิง ID แทน
    วันอังคารนี้ผมมีแผนจะเปิดตัว Docnode.dev อยากฟังฟีดแบ็กครับ
    ต่อไปก็มีแผนจะเพิ่มโหมด CRDT สำหรับกรณีที่ต้องใช้ P2P

    • อยากรู้ว่า trade-off แบบไหนที่เป็นปัญหามากที่สุด

  • CRDT หรือ OT เป็นโครงสร้างที่พยายามแก้ปัญหาเวลาคนหลายคนแก้ไขย่อหน้าเดียวกันพร้อมกัน แต่ในความเป็นจริงสถานการณ์แบบนั้น แทบไม่เกิดขึ้นเลย

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

  • OR-Set ที่พูดถึงในบทความนี้ คล้ายกับวิธี merge ที่ Monotone ใช้มาตั้งแต่ปี 2005
    ดูข้อมูลที่เกี่ยวข้องได้ใน เอกสาร MarkMerge

  • CRDT ยังเป็นเรื่องที่ต้อง ลงมือ implement เอง อยู่มาก
    เมื่อสองเดือนก่อนผมก็สร้างเอนจิน CRDT แบบ sequence โดยได้แรงบันดาลใจจาก diamond types
    ผมลองขอความช่วยเหลือจาก AI แล้ว แต่สำหรับ ปัญหาที่เน้นตรรกะ แบบนี้ มันช่วยอะไรไม่ได้เลย
    เลยรู้สึกว่าจำเป็นต้องมี black-box test เพื่อตรวจสอบว่า LLM เข้าใจตรรกะใหม่ ๆ ได้จริงหรือไม่

    • สงสัยว่าใช้ของอย่าง Loro ไปเลยจะเป็นยังไง

  • บทความยอดเยี่ยมมาก แต่ผมคิดว่าพจนานุกรมคำศัพท์ควรมี ดัชนี (index) ด้วย

  • ทำให้คิดว่า CRDT สุดท้ายแล้วคือการ ผลักภาระเรื่อง merge conflict จาก DB ไปไว้ที่ application logic หรือเปล่า

    • CRDT สามารถออกแบบให้อยู่ภายใน DB ได้เหมือนกัน ใน Riak ก็มีเป้าหมายแบบนั้นโดยตรง
      ถ้าเขียนได้ถูกต้อง ก็สามารถ แก้ปัญหาการรวมข้อมูลอัตโนมัติ ได้ไม่ว่าจะอยู่ที่เลเยอร์ไหน
    • ผมเองก็กำลังออกแบบ graph DB ที่ใช้เทคนิค CRDT บน PostgreSQL
      ปัญหาใหญ่ที่สุดคือการจัดการกับ UNIQUE/PRIMARY KEY conflict
      วิธีแก้คือแจกจ่าย namespace ของ ID ให้แต่ละเซิร์ฟเวอร์ แล้วให้การสร้างครั้งแรกเป็นฝ่ายชนะ ส่วนกรณีชนกันก็เปลี่ยนชื่อหรือลบออก
      ถ้าใช้สคีมา EAV ก็สามารถทำ graph traversal ได้ง่ายด้วย recursive CTE ใน SQL
      แต่ PostgreSQL ไม่มี type แบบ ANY จึงทำให้แสดง object ที่มี attribute หลากหลายได้ยาก และฟังก์ชัน FOREIGN KEY ก็ต้องทำเอง
      ถึงอย่างนั้นโครงสร้าง EAV ก็มีข้อดีต่อการออกแบบ meta-schema อย่างเช่นการสืบทอด
      ถ้ากำหนด type ของ CRDT ใน PostgreSQL ได้โดยตรงก็คงดี แต่ตอนนี้ยังไม่สามารถจำกัด monoid operation ได้
      สุดท้าย CRDT สำหรับคอลัมน์ที่ไม่ใช่คีย์ก็ต้องจัดการในชั้นแอปพลิเคชัน
      สรุปคือ CRDT สามารถ implement ภายใน RDBMS ได้เช่นกัน แต่แนวทางจะต่างกันไปตามว่า จะวาง business logic ไว้ที่ไหน