การชนกันของไทม์สแตมป์ระดับนาโนวินาทีเกิดขึ้นได้บ่อย

 (evanjones.ca)
5 คะแนน โดย GN⁺ 2023-07-23 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ในระบบสมัยใหม่ที่หลายคอร์กายภาพอ่านนาฬิกาพร้อมกัน แม้แต่ ไทม์สแตมป์ระดับนาโนวินาที ก็ซ้ำกันได้ง่าย โดยในการวัดพร้อมกันบนคอร์กายภาพ 4 คอร์ พบว่าประมาณ 5% ของตัวอย่างทั้งหมดเกิดการชนกัน
  • การออกแบบที่ใช้ไทม์สแตมป์ดิบเหมือนเป็น ตัวระบุที่ไม่ซ้ำกัน มีความเสี่ยง และความถี่ของการชนกันจะแตกต่างกันไปตามระบบปฏิบัติการและวิธีการรัน
  • time.Now() ของ Go บันทึกทั้งเวลาสัมบูรณ์และเวลาสัมพัทธ์ตามนาฬิกาแบบ monotonic จึงสามารถตรวจสอบทั้งความต่างระหว่างการเรียกต่อเนื่องกันและการซ้ำกันของไทม์สแตมป์สัมบูรณ์ได้
  • บน Linux แบบเธรดเดียว เวลาเพิ่มขึ้นเสมอ และช่วงเพิ่มขั้นต่ำคือ 32ns แต่เมื่อแยกเป็นหลายเธรด จะพบเวลาสัมบูรณ์เดียวกันได้
  • Mac OS X มีเวลาสัมบูรณ์ที่ ความละเอียดระดับไมโครวินาที จึงเกิดการชนกันมากกว่ามาก และแม้ในเธรดเดียวก็พบอยู่บ่อยครั้งว่านาฬิกาแบบ monotonic ไม่เพิ่มขึ้น

ความถี่ของการชนกันที่ปรากฏเมื่ออ่านพร้อมกัน

  • คำถามหลักคือ ในระบบสมัยใหม่ การชนกันของไทม์สแตมป์ระดับนาโนวินาที เกิดขึ้นจริงบ่อยแค่ไหน
  • เมื่ออ่านนาฬิกาพร้อมกันบนคอร์กายภาพ 4 คอร์ ประมาณ 5% ของตัวอย่างทั้งหมดเกิดการชนกัน
  • แม้ใช้เพียง 2 เธรดบนระบบ 4 คอร์ ก็มีไทม์สแตมป์ซ้ำกันประมาณ 2%
  • ดังนั้น การสมมติว่าสามารถสร้าง ID ที่ไม่ซ้ำกัน ได้ด้วยไทม์สแตมป์ระดับนาโนวินาทีแบบดิบเพียงอย่างเดียวจึงไม่ปลอดภัย

วิธีทดสอบและความแตกต่างตามระบบปฏิบัติการ

  • โปรแกรมทดสอบ เขียนด้วย Go
  • time.Now() ของ Go บันทึกทั้ง เวลาสัมบูรณ์ และ เวลาสัมพัทธ์ตามนาฬิกาแบบ monotonic ในแต่ละครั้งที่เรียก
    • การทดสอบเปรียบเทียบความต่างสัมพัทธ์ระหว่างไทม์สแตมป์ต่อเนื่องกัน
    • ตรวจสอบการซ้ำกันของไทม์สแตมป์สัมบูรณ์เองด้วย

  • Linux

    • ในเธรดเดียว ทั้งเวลาสัมบูรณ์และเวลาแบบ monotonic เพิ่มขึ้นเสมอ
    • ช่วงเพิ่มขั้นต่ำของระบบที่วัดได้คือ 32ns
    • ระหว่างเธรด มีกรณีที่เวลาสัมบูรณ์ตรงกับเธรดอื่นทุกประการประมาณ 5%

  • Mac OS X

    • เวลาสัมบูรณ์มี ความละเอียดระดับไมโครวินาที จึงเกิดการชนกันจำนวนมากในการทดสอบเดียวกัน
    • แม้ในเธรดเดียว ก็พบอยู่บ่อยครั้งว่านาฬิกาแบบ monotonic ไม่เพิ่มขึ้น

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

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

 
GN⁺ 2023-07-23
ความเห็นจาก Hacker News

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

    • รู้สึกเหมือนบังเอิญกลายเป็นนักเดินทางข้ามเวลานิดๆ เพราะจำได้ว่าราว 10 ปีก่อนหรือมากกว่านั้น ในงานพบปะสายเทคมีคนคนหนึ่งสร้าง UUID มากกว่า 1000 ตัวต่อมิลลิวินาที แล้วเจอปัญหาเรื่องความเป็นเอกลักษณ์ และตอนนั้นก็บ่นว่าไม่ค่อยพอใจกับตัวเลือกที่มี
      หาในอินเทอร์เน็ตไม่ค่อยเจอว่า UUIDv7 เก่าแค่ไหน
    • ยังไม่เข้าใจตั้งแต่ต้นว่าทำไมต้องมี องค์ประกอบเวลา
      มันแค่กินบิตใน UUID และแทบไม่ได้ช่วยเรื่อง entropy เลย
    • มันเข้ากับ ลำดับการจัดเรียง ในฐานข้อมูลยอดนิยมอย่าง PostgreSQL ได้ดีด้วย
      แม้ยังไม่ได้รวมอยู่ในตัวหลัก แต่ก็มีส่วนขยาย pg ดีๆ หลายตัวที่ให้ uuidv7 ใช้งาน นอกเหนือจากการทำเองในระดับแอปพลิเคชัน
    • ปัญหาของ UUID คือมันอ่านยากโดยสิ้นเชิง
      ไม่ใช่แค่เข้าใจยาก แต่แม้แต่การแยกให้ออกด้วยตาเปล่าว่าแต่ละอันต่างกันก็ยังยากมาก
      เพราะอย่างนั้น ในบางกรณี ตัวระบุ ที่ไม่ใส่ข้อมูลหรือสัญญาณรบกวนใดๆ เลยนอกจากข้อมูลขั้นต่ำที่จำเป็นก็มีประโยชน์
    • ขึ้นอยู่กับกรณีใช้งาน บางครั้งก็ไม่จำเป็นต้องรองรับระดับ “มิลลิวินาทีเดียวกัน” ด้วยซ้ำ และยังประหยัดรอบการทำงานได้อีกเล็กน้อย
      ไม่ว่าจะรูปแบบไหน เคาน์เตอร์เพิ่มค่าที่อาจล้นได้ร่วมกับบิตสุ่มเล็กน้อยก็มักเพียงพอ และถ้าออกแบบดี ทั้งสองอย่างก็ทำได้แบบไม่ต้องมี branch

  • เกี่ยวกับเรื่องนี้ เมื่อก่อนเคยเป็นผู้จัดการโปรแกรมที่ดูแล บันทึกเหตุการณ์ความปลอดภัย ของ Windows
    บนระบบหลายคอร์ เมื่อมีงานเกิดขึ้นพร้อมกันหรือห่างกันน้อยมาก การจัดตารางเธรดอาจส่งผลอย่างมากต่อสิ่งที่สังเกตเห็น
    เช่น quantum ของเธรดอาจหมดก่อนที่จะไปถึง system call ที่ใช้ดึง timestamp หรือก่อนจะส่งต่อบัฟเฟอร์ไปเข้า queue ของอีเวนต์เพื่อประทับ timestamp ในภายหลัง
    ในความเป็นจริง บนระบบประมวลผลหลายตัวของ Windows ยุค 2000 การที่รายการใน event log เรียงลำดับสลับกัน นั้นพบได้บ่อยมาก และก็ไม่ควรเชื่อความแม่นยำของ timestamp ใน log ละเอียดเกินไป
    ขอบเขตล่างที่ปลอดภัยจริงๆ แทบจะเป็น 1 วินาที และเท่าที่จำได้ บางคอมโพเนนต์ยังมีการตัดทิ้งหรือปัดเศษ timestamp ด้วย

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

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

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

    • ถ้าเป็นอุปกรณ์ที่ทำงานที่ 1GHz ขึ้นไป ก็เป็นไปได้มากพอที่นาฬิกาจะเพิ่มค่าทุกนาโนวินาที
      แต่นั่นไม่ได้แปลว่ามัน แม่นยำ ถึงระดับนั้น และในระบบหลายคอร์ นาฬิกาของแต่ละคอร์ก็อาจไม่ได้ซิงก์กันถึงระดับนั้น
      ARMv8 รับประกันว่านาฬิกาจะเพิ่มค่าที่อย่างน้อย 1GHz แต่ Intel และ ARM รุ่นก่อนหน้านั้นซับซ้อนกว่า
    • มันเป็นระดับนาโนวินาทีจริงๆ

  • BEAM VM ของ Erlang/Elixir แสดงความต่างนี้ได้ชัดเจนมาก คือความต่างระหว่าง monotonic increasing กับ strictly monotonic increasing
    https://www.erlang.org/doc/apps/erts/time_correction.html#mo...
    “ในลำดับของค่าที่เพิ่มขึ้นแบบ monotonic ค่าทุกค่าที่มีค่าก่อนหน้าจะต้องมากกว่าหรือเท่ากับค่าก่อนหน้านั้น”
    ใช้งานได้ผ่านฟังก์ชัน https://www.erlang.org/doc/man/erlang.html#monotonic_time-0
    https://www.erlang.org/doc/apps/erts/time_correction.html#st...
    “ในลำดับของค่าที่เพิ่มขึ้นแบบเคร่งครัด ค่าทุกค่าที่มีค่าก่อนหน้าจะต้องมากกว่าค่าก่อนหน้านั้น”
    ค่าที่เป็น strictly monotonic บ่งบอกถึงการซิงก์หรือการประสานงานบางรูปแบบ และมีต้นทุนด้านประสิทธิภาพเมื่อมีโปรเซสพร้อมกันจำนวนมาก
    ความสามารถนี้มีให้ผ่านฟังก์ชัน https://www.erlang.org/doc/man/erlang.html#unique_integer-1 และในเอกสารก็เตือนว่า ค่าที่เพิ่มขึ้นแบบเคร่งครัดนั้นโดยเนื้อแท้แล้วมีต้นทุนการสร้างสูงและสเกลได้ไม่ดี จึงควรส่งตัวแก้ไข monotonic เข้าไปเฉพาะเมื่อจำเป็นจริง ๆ

    • แม้แต่ค่าอ้างอิงของ Erlang เองก็ไม่ได้สร้างด้วย ตัวสร้างแบบ global strict monotonic แต่ภายในประกอบด้วยคู่ของตัวระบุแบบ monotonic ทั่วไปกับ PID ของโปรเซสที่ร้องขอ
      พูดอีกแบบคือคล้าย UUIDv1 หรือ https://en.wikipedia.org/wiki/Snowflake_ID
      เราต้องการตัวระบุแบบ global strict monotonic จริง ๆ ก็ต่อเมื่อต้องการผู้ชนะของ first/last write ที่สอดคล้องกันทันทีเท่านั้น
      แต่ถ้าใช้ first/last write winner แบบ eventually consistent ได้ เช่น เหตุการณ์การเขียนถูกใส่เข้าไปใน event store หรือคิวที่ทำให้เป็นเส้นตรงด้วย ID แล้วสามารถเก็บไว้เฉพาะรายการที่มีลำดับความสำคัญของ ID สูงสุดในหมู่การเขียนที่ “พร้อมกัน” และทิ้งรายการอื่นระหว่างการประมวลผลหรือขณะอ่านได้ ผมจะพิจารณาคู่ (nodeID, seq) ที่บีบอัดแล้วก่อน
      ถ้าจำเป็นต้องจัดลำดับเหตุการณ์แบบ global โดยเฉพาะ ก็น่าพิจารณารูปแบบ Snowflake ID อย่าง (timestampMajor, nodeID, timestampMinor, seq)

  • FreeBSD ไม่มี CLOCK_MONOTONIC_RAW พอคอมเมนต์ทิ้งแล้วก็ดูเหมือนจะใช้ได้
    ผมเข้าใจว่าถ้ามีการชนกัน ก็น่าจะต้องเห็น timestamp บางค่าซ้ำ แต่กลับสร้างการชนกันไม่ได้
    clock_getres(CLOCK_REALTIME, ...)=1 ns, clock_getres(CLOCK_MONOTONIC, ...)=1 ns แสดงแบบนั้น และในตัวอย่าง 30 ค่า ความต่างก็ยังเพิ่มขึ้นเรื่อย ๆ อยู่ราว 29~71ns

    • ประเด็นสำคัญคือได้รัน พร้อมกันบน 4 คอร์ แบบที่ผู้เขียนทำหรือเปล่า

  • สุดท้ายแล้วมันคงลงไปถึงปัญหาระดับ สถาปัตยกรรมชุดคำสั่ง ใช่ไหม
    CPU ที่ทำงานที่ 3GHz จะได้ 3 clock cycle ต่อนาโนวินาที
    ดูมีโอกาสไม่น้อยที่ด้วยการ optimize ของคอมไพเลอร์ การเรียก assembly เพื่ออ่าน clock register จะถูกวางติดกัน
    ถ้าการเรียก time.Now() ต่อเนื่องกันเกิดขึ้นภายใน 3 clock cycle จะยุติธรรมไหมที่จะคาดหวังความละเอียดระดับนาโนวินาทีที่ไม่ซ้ำกันจริง ๆ

    • x86_64 บน Linux ใช้ RDTSC และปรับแก้ด้วยค่าที่อ่านจาก VDSO ดังนั้นจึงอาจเกิดขึ้นได้เร็วมากจริง ๆ
    • แม้แต่การอ่าน cycle counter register บนชิปรุ่นใหม่ก็ยังใช้เวลาราว 20 cycle
      ต่อให้การชนกันจะค่อนข้างพบได้น้อย แต่ถ้าเกิดวันละไม่กี่ครั้ง มันก็แย่กว่า “แทบไม่มีวันเกิดขึ้นเลย” มาก

  • ทำให้นึกถึงตำนานเกี่ยวกับ Lotus Notes
    เมื่อก่อนว่ากันว่าใช้ timestamp ความละเอียด 1 วินาทีเป็น ID ที่ไม่ซ้ำกัน
    ถ้าเกิดชนกันก็แค่บวกเพิ่ม 1 วินาที และสุดท้ายการชนก็เยอะมากจนรายการต่าง ๆ มี เวลาในอนาคต

  • เวลาที่แม่นยำอย่างสมบูรณ์เป็น ปัญหาด้านความปลอดภัย
    ผู้ออกแบบ CPU ใส่ clock jitter โดยตั้งใจมานานมากแล้ว เพื่อป้องกันการคาดเดาได้สมบูรณ์ ตั้งแต่สมัย Alpha ของ DEC
    บน x86 เอง ถ้ารัน 3~4 ครั้งแล้วเก็บค่าไว้ในรีจิสเตอร์ก่อนค่อยมาดูตอนจบ ก็น่าจะเห็นได้ว่าความต่างของเวลาไม่ได้เท่ากันเป๊ะ

    • สงสัยว่ามีแหล่งอ้างอิงไหม
      ผมหาค้นไม่ค่อยเจอ แต่ถ้าหมายรวมถึง x86 ยุคแรก ๆ ด้วย ก็แปลกใจที่มีการตระหนักถึงปัญหาความปลอดภัยของนาฬิกาที่แม่นยำตั้งแต่เร็วขนาดนั้น
      ส่วนตัวคิดว่าก่อนช่วงมิลเลนเนียมนี้คงยังไม่รู้ปัญหาประเภทนั้น และคงเดาว่า clock jitter ที่สังเกตได้อธิบายได้ด้วยสิ่งอย่าง interrupt
      ไม่ได้บอกว่าคุณผิด แค่อยากรู้เพิ่ม

  • เคยเห็นคนตกใจกับการชนกันของ timestamp ระดับมิลลิวินาทีหรือไมโครวินาทีมากเกินไป
    แบบที่จำได้ชัดและเกลียดที่สุดคือการประกอบ timestamp จาก system call สองครั้ง
    อันหนึ่งใช้สำหรับหลักบน อีกอันหนึ่งใช้สำหรับหลักล่าง แต่เพราะโปรเซสอาจถูกแย่ง CPU หลังจากอ่านหลักบนแล้ว ตอนที่หลักล่างขยับจาก 99x ไปเป็น 00x ก็อาจสร้าง timestamp ที่ย้อนกลับไปก่อนเวลาของเหตุที่ทำให้สร้างเอนทิตีนั้นได้
    แบบนี้ทำให้โค้ดบางส่วนพังอย่างอลังการ และอย่างน้อยผมเคยเห็น ลูปไม่รู้จบ มาแล้วสองครั้ง
    ถ้าไม่จำใส่ใจไว้เสมอว่าต้องหลีกเลี่ยงสิ่งนี้ การทดสอบก็จะผ่าน 99.5% แล้วต้องอาศัยคนที่มีเซนส์จับแพตเทิร์นดีมากมาสังเกตว่า “เทสต์เดิมแดงสัปดาห์ละครั้งมาตลอดเดือนครึ่ง”
    นั่นนานเกินกว่าที่ระเบิดเวลาเชิงตรรกะจะถูกปล่อยให้มีชีวิตอยู่ในโค้ด CI/CD ก่อนถูกแก้

    • ตัวอย่างที่จำได้ที่สุดคือในบทสนทนาฝ่ายซัพพอร์ต ผมบอกว่า “ดูเหมือนจะมี race condition” แล้วได้รับคำตอบว่า “สองอีเวนต์นั้นเกิดขึ้น เวลาเดียวกันเป๊ะ ดังนั้นจึงไม่น่าใช่ race condition”