ID ที่ไม่ซ้ำกันในระดับจักรวาล

 (jasonfantl.com)
25 คะแนน โดย GN⁺ 2026-02-20 | 4 ความคิดเห็น | แชร์ทาง WhatsApp
  • สำรวจ วิธีมอบ ID ที่ไม่ซ้ำกันอย่างเด็ดขาดให้กับอุปกรณ์หรือวัตถุ โดยเปรียบเทียบแนวทางแบบสุ่ม (random) กับแบบกำหนดแน่นอน (deterministic)
  • แนวทางแบบสุ่มสามารถทำให้โอกาสชนกันแทบเป็น 0 ได้ หากใช้ จำนวนบิตที่มากพอ โดยมีตั้งแต่ UUID (122 บิต) ไปจนถึง ขีดจำกัดการคำนวณของเอกภพทั้งหมด (798 บิต)
  • สำหรับแนวทางแบบกำหนดแน่นอน มีการเสนอหลายสคีม เช่น ตัวนับศูนย์กลาง, โครงสร้างลำดับชั้นแบบมอบหมาย (Dewey), ต้นไม้ทวิภาค (Binary), โทเค็น (Token) และวิเคราะห์ ลักษณะการเติบโตของความยาว ID ของแต่ละวิธีผ่านการจำลอง
  • ยังมีการนำเสนอการพิสูจน์ทางคณิตศาสตร์ว่า ทุกสคีมแบบกำหนดแน่นอน ไม่อาจหลีกเลี่ยงการเติบโตเชิงเส้น (linear) ในกรณีเลวร้ายที่สุด ได้
  • บทสรุปคือ วิธีที่ใช้งานได้จริงและมีประสิทธิภาพแม้ในระดับการขยายตัวแบบจักรวาล คือการสร้าง ID แบบสุ่ม ส่วนวิธีแบบกำหนดแน่นอนนั้นไม่มีประสิทธิภาพ

ความจำเป็นของ ID ที่ไม่ซ้ำกันและการตั้งโจทย์

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

แนวทางแบบสุ่ม (Random)

  • วิธีที่ง่ายที่สุดคือ เลือกตัวเลขแบบสุ่ม
    • สร้างได้จากที่ใดก็ได้โดยไม่ต้องมีการจัดการจากศูนย์กลางหรือการซิงก์
  • โอกาสชนกันสามารถ ควบคุมได้ด้วยการเพิ่มจำนวนบิต และปรับให้เข้าใกล้ 0 ได้ในทางปฏิบัติ
  • UUID (122 บิต) คาดว่าจะเริ่มเกิดการชนกันเมื่อสร้าง ID ประมาณ $2^{61}$ รายการ
  • หากพิจารณา ขีดจำกัดการคำนวณของเอกภพทั้งหมด (10¹²⁰ ครั้ง) จะต้องใช้ 798 บิต
    • หากยึดตามระดับอะตอม (10⁸⁰ รายการ) จะอยู่ที่ 532 บิต และสำหรับนาโนบอต 1g (10⁵⁶ รายการ) จะอยู่ที่ 372 บิต
  • สิ่งสำคัญคือ การได้มาซึ่งความสุ่มที่แท้จริง และแนะนำให้ใช้ CSPRNG หรือ แหล่งกำเนิดเลขสุ่มเชิงควอนตัม
    • ควรห้ามใช้ seed ที่พบได้ทั่วไปหรือ ID ค่าคงที่ (เช่น all-zero)

แนวทางแบบกำหนดแน่นอน (Deterministic)

  • วิธี ตัวนับศูนย์กลาง คือให้เซิร์ฟเวอร์เดียวออก ID ตามลำดับ
    • เพื่อแก้ปัญหาการเข้าถึง จึงมีข้อเสนอเป็น โครงสร้างการมอบหมายระหว่างดาวเทียมหรืออุปกรณ์ (Dewey)
  • สคีม Dewey: ID แบบลำดับชั้นรูป A.B.C แสดงผลด้วย Elias omega coding
    • มีการเติบโตแบบ ลอการิทึม หรือเชิงเส้น ตามโครงสร้างต้นไม้
  • สคีม Binary แบ่งพื้นที่ ID ด้วยต้นไม้ทวิภาค และในบางกรณีมีประสิทธิภาพมากกว่า Dewey
  • 2-Adic Valuation รับประกันเอกลักษณ์ทางคณิตศาสตร์ และเป็นรูปแบบดัดแปลงของ Binary
  • สคีม Token แสดงการเติบโตแบบลอการิทึมในโครงสร้างแบบสายโซ่ แต่เมื่อความกว้างเพิ่มขึ้นจะเปลี่ยนเป็นเชิงเส้น

การพิสูจน์ว่าการเติบโตเชิงเส้นหลีกเลี่ยงไม่ได้

  • โดยตั้งอยู่บนสมมติฐานว่า ทุกเส้นทางในการมอบ ID ต้อง ไม่ซ้ำกัน จึงคำนวณจำนวนเส้นทางที่เป็นไปได้
  • เมื่อจำนวนโหนดเป็น n จำนวน ID ที่ต้องใช้จะเพิ่มเป็น $2^{n-1}$
  • ดังนั้น ความยาว ID ต้องอย่างน้อย O(n) หรือก็คือ ในกรณีเลวร้ายที่สุด การเติบโตเชิงเส้นหลีกเลี่ยงไม่ได้
  • ไม่มีอัลกอริทึมใดที่สามารถคงการเติบโตแบบลอการิทึมไว้ได้ในทุกกรณี

การจำลองโมเดลการขยายตัว

  • มีการทดลองด้วยโมเดลการเติบโตหลายแบบ เช่น Random Recursive Tree, Preferential Attachment, Fitness Model
    • ในขนาดเล็ก (2,048 โหนด) Binary ทำได้ดีที่สุด ส่วน Dewey และ Token แตกต่างกันไปตามสถานการณ์
    • ในโมเดล Preferential นั้น Dewey มีประสิทธิภาพสูงสุด
    • ในโมเดล Fitness นั้น Dewey และ Binary ให้ผลใกล้เคียงกัน
  • แม้ในการทดลองระดับ หนึ่งล้านโหนด Dewey และ Token ก็ยังรักษาการเติบโตแบบลอการิทึมไว้ได้
    • ความยาว ID สามารถประมาณได้ในรูป ≈ 6.55 × ln(n)

โมเดลการขยายตัวระดับกาแล็กซีและเอกภพ

  • การแพร่กระจายระหว่างดาวเคราะห์ ถูกจำลองเป็นแนวคลื่น (front) ที่เคลื่อนที่ด้วยความเร็วคงที่
    • แต่ละดาวเคราะห์จะสร้าง ID ราว 10⁹ รายการ ก่อนจะแพร่ต่อไปยังดาวเคราะห์ถัดไป
  • เมื่อรัศมีของกาแล็กซีมีประมาณ 2,121 ดาวเคราะห์ ความยาว ID จะอยู่ที่ประมาณ 288,048 บิต เมื่อแพร่ทั่วทั้งกาแล็กซี
  • หากพิจารณาการแพร่ระหว่างกาแล็กซีด้วย (ประมาณ 7,816 ขั้น) จะต้องใช้ ประมาณ 2.2 พันล้านบิต (281MB)
  • วิธีแบบกำหนดแน่นอนไม่มีประสิทธิภาพ และ แนวทางแบบสุ่ม (ไม่เกิน 798 บิต) มีประสิทธิภาพเหนือกว่าอย่างมาก

ความปลอดภัยและข้อพิจารณาเพิ่มเติม

  • เพื่อ ป้องกันการปลอมแปลง ID สามารถใช้ ระบบตรวจสอบแบบอิงลายเซ็น ได้
    • ID แบบสุ่มใช้กุญแจสาธารณะเป็น ID ส่วนสคีมแบบกำหนดแน่นอนให้โหนดแม่ลงลายเซ็นให้กับกุญแจของโหนดลูก
  • จำเป็นต้องมี รหัสแก้ไขข้อผิดพลาด และ การจัดการเวอร์ชัน
  • สำหรับ วัตถุที่ไม่สามารถเก็บ ID ได้ (เช่น ดาวเคราะห์) สามารถจัดการด้วยการแมปหลาย ID เข้าด้วยกัน
  • มีการอภิปรายเรื่องการคงอยู่ของ ID เมื่อมีการเปลี่ยนองค์ประกอบ เช่น ปัญหาเรือของ Theseus
  • แนวคิดที่เกี่ยวข้อง: Decentralized Identifiers (DID), Ancestry Labeling Schemes

บทสรุป

  • สคีมแบบกำหนดแน่นอนน่าสนใจในเชิงทฤษฎี แต่ใช้งานจริงได้น้อย
  • การสร้าง ID แบบสุ่ม เป็นแนวทางที่สมจริงและมีประสิทธิภาพ แม้ในระดับจักรวาล
  • การทำให้โอกาสชนกันของ ID “แทบเป็นศูนย์” คือ ทางเลือกที่ปลอดภัยและใช้งานได้จริงที่สุด

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

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

 
mammal 2026-02-20

ลองอ่านต้นฉบับให้ได้นะครับ เขาอธิบายด้วยสูตรและการจำลองให้เห็นภาพ เลยอ่านได้สนุกมากครับ
 
princox 2026-02-20

ถ้าสร้างจากเวลา ก็น่าจะต้องมองว่าเป็นแบบเชิงเส้นสินะครับ..?
คงต้องไปดูต้นฉบับสักหน่อย เป็นเรื่องที่น่าสนใจครับ
 
hmmhmmhm 2026-02-20

ถ้าชนกันขึ้นมานี่คือโชคร้ายระดับจักรวาลเลยสินะ...(?)
 
GN⁺ 2026-02-20
ความเห็นจาก Hacker News

  • บทวิเคราะห์นี้ไม่ยุติธรรมทั้งหมด ตอนออกแบบ UUID มีการคำนึงถึง locality หรือก็คือความเร็วแสง แต่ตอนคำนวณความน่าจะเป็นการชนกลับละเลยประเด็นนั้นไป ในทางปฏิบัติ การชนกันจะมีความหมายก็ต่อเมื่อ UUID สองตัวนั้นเกิด causal contact กันหลังถูกสร้างขึ้น ดังนั้นการใช้ birthday paradox แบบตรงๆ จึงเป็นวิธีที่ไม่ถูกต้อง ถ้าคำนึงถึง locality ขนาด UUID ที่ต้องใช้ก็น่าจะเล็กกว่า 800 บิตตามบทความมาก ยังไม่ได้คำนวณจริงจัง แต่ไม่น่าจะเกิน 256 บิต สิ่งที่ชอบมากเกี่ยวกับ HN คือเป็นไม่กี่แห่งที่มี การถกเถียงเชิงเทคนิคแบบละเอียดจริงจัง แบบนี้เกิดขึ้นอย่างจริงจัง

    • เคยอ่านสมมติฐานเรื่องการขยายตัวของเอกภพที่ทำให้กาแล็กซีถอยห่างกันจนแลกเปลี่ยนข้อมูลกันไม่ได้ ตามสมมติฐานนั้น สิ่งมีชีวิตทรงปัญญาจะต้อง มุ่งไปรวมกันยังบริเวณที่มีความหนาแน่นมวลสูงที่สุด เพื่อความอยู่รอด สุดท้ายก่อนการตายเชิงความร้อนของเอกภพ อาจเกิด “การชุมนุมครั้งใหญ่” ของอารยธรรมต่างดาวก็ได้ ถึงตอนนั้นอาจมี UUID ชนกันจริงๆ ก็ได้ นึกภาพ Vogon ใส่ UUID ให้ทุกแท็ก XML จนสถิติพังเละ
    • ครั้งหนึ่งเคยได้รับ Intel NIC มาทั้งกล่อง แล้วทุกตัวมี MAC address เดียวกันหมด ยังจำได้ว่าต้องเสียเวลาหลายวันกว่าจะหาสาเหตุเจอ
    • เวลาพูดถึงความน่าจะเป็นที่ต่ำมากๆ ก็ควรเผื่อไว้ด้วยว่าเราอาจ เข้าใจจักรวาลวิทยาผิดอยู่ก็ได้ light cone อาจไม่ใช่ขีดจำกัดเชิงเหตุและผลก็ได้
    • ต้องคำนึงถึงทั้งเวลาและ locality เวลาจนกว่าโปรตอนจะสลายและสสารหายไปนั้นมีเพียงประมาณ 10^56 นาโนวินาทีเท่านั้น
    • คำวิจารณ์นี้ตรงประเด็น บทความต้นฉบับเป็นการทดลองทางความคิดที่สนุก แต่ประเมินปัญหาสูงเกินจริงเพราะมองข้ามเรื่อง causality ในความเป็นจริง UUID ชนกันมีความหมายเฉพาะภายในระบบที่สื่อสารกันได้เท่านั้น และระบบแบบนั้นก็ถูกจำกัดด้วย light cone 128 บิต ก็เพียงพอสำหรับระบบที่มนุษยชาติจะสร้างในอีกพันปี และ 256 บิตก็เกินพอแม้ในระดับทั้งเอกภพ

  • เวลาเราคำนวณจำนวนอ็อบเจ็กต์ที่ระบุที่อยู่ได้ ต้องคำนึงด้วยว่าอย่างน้อยต้องมีที่ไหนสักแห่งเก็บที่อยู่ของอ็อบเจ็กต์แต่ละตัวไว้หนึ่งครั้ง ถ้าการเก็บหนึ่งบิตต้องใช้อนุภาค Npb จำนวนหนึ่ง เมื่อจำนวนบิตของที่อยู่เพิ่มขึ้น จำนวนอ็อบเจ็กต์ที่ระบุที่อยู่ได้ก็จะลดลง ดังนั้นจำนวนสูงสุดที่อ้างที่อยู่ได้จึงหาได้จากความสัมพันธ์รูปแบบ Nthg = Np / (Npb * f(Ntng))

  • ครั้งหนึ่งเคยต้องโต้แย้งว่า random ID แบบ 256 บิตนั้นมากพอจนไม่ต้องตรวจสอบการชนกันด้วยซ้ำ เพื่อนร่วมงานอยากเพิ่ม ตรรกะตรวจสอบการชนกัน ที่ซับซ้อนเข้าไป แต่ผมอธิบายว่า 2^256 มีขนาดพอๆ กับจำนวนอะตอมในเอกภพที่สังเกตได้ และโอกาสที่ดาต้าเซ็นเตอร์จะระเบิดเป็นล้านครั้งยังสูงกว่าที่จะเกิดการชนกัน สุดท้ายก็สรุปกันว่าแค่ 128 บิตก็พอแล้ว

    • แต่ถ้าในสภาพแวดล้อมแบบกระจายศูนย์มี ผู้มีส่วนร่วมที่ไม่น่าเชื่อถือ เป็นคนสร้าง ID ก็จำเป็นต้องตรวจสอบ เพราะอาจมีการสร้างการชนกันโดยเจตนาได้ ในทางกลับกัน ถ้าเป็นระบบเดียว ก็ใช้ตัวนับธรรมดาก็พอ และถ้ามีหลายเซิร์ฟเวอร์ ก็แบ่งช่วงด้วย sharded counter ได้
    • จริงๆ แล้วการคำนวณง่ายกว่านั้นอีก ปริมาณข้อมูลทั้งหมดของมนุษยชาติยังไม่ถึง 1 yottabyte ด้วยซ้ำ ตาม birthday paradox ความน่าจะเป็นชนกัน 50% จะเกิดที่ราว 2^128 ค่า ID ขนาด 256 บิตมีขนาด 32 ไบต์ ดังนั้น 2^128 * 32 ไบต์ = 10^16 ยอตตะไบต์ นั่นคือ ความน่าจะเป็นที่จะชนกันต่ำอย่างมหาศาล

  • มีการคำนวณว่าถ้าจะกำหนด ID ให้ทุกอะตอมจะต้องใช้ประมาณ 532 บิต แต่ในความเป็นจริงเราน่าจะอยากให้ ID กับกลุ่มอะตอมด้วย เช่น ไมโครชิป รถยนต์ ฯลฯ จึงอาจต้องใหญ่กว่านั้น

    • จริงๆ แล้วไม่ต้องให้กับทุกอนุภาค แต่ ให้หนึ่ง ID ต่อชนิดของอนุภาค ก็พอ ตามกฎฟิสิกส์ อนุภาคที่เหมือนกันจะแยกออกจากกันไม่ได้
    • ต่อให้คำนึงถึงกลุ่มอะตอม บิตที่ต้องเพิ่มก็คงแทบไม่มี
    • UUIDv∞ จะอยู่ที่อย่างน้อยราว 536 บิตไหมนะ? ถ้าใส่ group ID หรือ timestamp ด้วยก็อาจไปถึง 1024 บิต
    • เวลานิวตริโนเกิดการ oscillate ต้องออก ID ใหม่ทุกครั้งไหม? โชคดีที่อิเล็กตรอนใช้แค่ตัวเดียวก็พอ

  • มีไอเดียใช้ สำรับไพ่ แทน ID ถ้าแทนไพ่ทั้ง 52 ใบด้วยอักขระ Unicode จะอ่านง่าย แก้ด้วยมือยาก และช่วยให้มองเห็นรูปแบบได้ดี ถ้านำสำรับจริงมาสับแล้วให้กล้องอ่าน ก็ยังใช้เป็น random seed ได้ด้วย แนวคิดคล้ายๆ กันมี DiceKeys

    • แต่จุดอ่อนที่สุดคือ “การสับให้ดีจริงๆ”

  • เป็นภาพประกอบและข้อสังเกตที่ยอดเยี่ยม ผมออกแบบฐานข้อมูลโดยยึดตัวระบุแบบสุ่มที่เล็กที่สุดเท่าที่ทำได้เป็นหลัก และมองว่า ตัวระบุสากล แบบนี้คือ ‘golden disk’ เพียงหนึ่งเดียวอย่างแท้จริง ในแวดวงการจัดการข้อมูลวิทยาศาสตร์หรือบรรณารักษศาสตร์ แนวคิดนี้กลับถูกประเมินค่าต่ำเกินไป ปัญหามากมายในองค์กรขนาดใหญ่คงแก้ได้ด้วยการออกแบบตัวระบุที่ดีกว่านี้
    บทความที่เกี่ยวข้อง: Identifiers Deep Dive, Trible Structure

    • อัตลักษณ์ของเอนทิตีอาจนิยามแบบ intrinsic ได้ แล้วทำไม consistency contract ถึงใช้ไม่ได้?

  • ตอนนี้กำลังอ่าน Becky Chambers เรื่อง 『The Galaxy, and the Ground Within』 แถวๆ หน้า 281
    ตัวอย่างข้อความในหนังสือ:

    Received Message
Encryption: 0
From: GC Transit Authority --- Gora System (path: 487-45411-479-4)
To: Ooli Oht Ouloo (path: 5787-598-66)
Subject: URGENT UPDATE

    ชอบซีรีส์นี้มาก การตั้งค่าจักรวาลหลายเผ่าพันธุ์ที่ใช้ ระบบที่อยู่เส้นทางซึ่งตกลงร่วมกันจากส่วนกลาง น่าสนใจมาก

    • ขอแนะนำตัวอย่างคล้ายกันคือ 『A Fire Upon The Deep』 ของ Vernor Vinge วิธีติดป้ายกำกับการสื่อสารระหว่างกาแล็กซีน่าสนใจมาก
    • โดยเฉพาะฉากที่กลัวแนวคิดเรื่องชีสนั้นน่าประทับใจมาก หนังสือเล่มที่สองของซีรีส์ 『A Closed and Common Orbit』 ดีที่สุด

  • เพิ่งไปรู้จัก Snowflake ID มาไม่นาน ใช้กันใน Twitter, Discord, Instagram, Mastodon ฯลฯ เป็นวิธีลดขนาด ID ด้วยการผสม timestamp + random ซึ่งน่าเสียดายที่บทความไม่ได้พูดถึง
    ดูเพิ่มเติมที่ Snowflake ID บนวิกิ, วิดีโอของ Tom Scott
    ถ้าเปลี่ยนบางบิตของ timestamp ใน Snowflake ให้เป็นแบบสุ่ม ก็น่าจะสร้าง ID ได้ 4 พันล้านตัวต่อวินาที

    • จริงๆ แล้ว Snowflake มีโครงสร้างแทบเหมือน UUID v1 ต่างกันแค่ว่ามีขนาดครึ่งเดียว
    • มีไอเดียคล้ายกันคือ DRUUID
    • แต่การที่ทั้งเอกภพจะ ตกลงกันเรื่องนาฬิกาเรือนเดียว นั้นแทบเป็นไปไม่ได้
    • วิธีนี้ก็คล้ายกับ BSON ID เช่นกัน

  • สงสัยว่าจะสร้าง ID จาก ปรากฏการณ์ที่สังเกตได้ ได้ไหม ด้วยคุณสมบัติที่แยกกันได้ด้วยเวลาและระยะทาง จึงอาจรับประกันความไม่ซ้ำได้ เช่น รูปแบบแสงดาว ณ ช่วงเวลาหนึ่งมีเพียงคนเดียวเท่านั้นที่มองเห็น มันคล้ายการใช้ noise เป็น entropy แบบ lava lamp ถ้าสามารถนิยามระบบพิกัดของเอกภพทั้งหมดได้ ก็ดูเหมือนจะสร้าง ID ที่ไม่ซ้ำได้จากการรวม local time + x + y + z + salt

  • วิธี random UUID เหนือกว่ามากในแง่อายุการใช้งาน จำนวนอุปกรณ์ที่ทำงานพร้อมกันได้มีจำกัด และต่างจาก UUID แบบ tree-based ตรงที่เมื่อเลิกใช้อุปกรณ์แล้วก็สามารถนำ ID กลับมาใช้ใหม่ได้ ในทางปฏิบัติ อัลกอริทึมแบบผสมที่ใช้ รากตามตำแหน่ง + บิตย่อยแบบสุ่ม น่าจะใช้งานได้จริงที่สุด