ความเสี่ยงของคีย์หลักแบบ UUID ใน SQLite

 (andersmurphy.com)
1 คะแนน โดย GN⁺ 4 시간 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • การทำงานของคีย์หลักใน SQLite ทำให้ลำดับการจัดเก็บจริงแตกต่างกันระหว่างตาราง rowid ปกติกับตาราง WITHOUT ROWID และเมื่อใช้ UUID4 แบบสุ่ม เป็น clustered index จะเกิดต้นทุนจากการปรับสมดุล B-tree และการเพจจิงเพิ่มเติม
  • ค่าฐานอ้างอิงของ rowid แบบจำนวนเต็มทำความเร็วการแทรกได้ราว 1 ล้านแถวต่อวินาทีในการทดสอบแทรกทีละ 1 ล้านแถว ขณะที่ UUID4 WITHOUT ROWID ใช้เวลาแทรกช้ากว่า 14–16 เท่า
  • คุณสมบัติที่ไม่มีลำดับของ UUID4 ทำให้แถวถูกแทรกเข้า B-tree แบบสุ่ม และจากผลการโปรไฟล์พบว่าใช้เวลากับการปรับสมดุลต้นไม้และการอ่าน-เขียนมากขึ้น
  • UUID7 WITHOUT ROWID เป็น UUID แบบเรียงตามเวลา จึงลดปัญหาการจัดเรียงของ UUID4 และให้เวลาแทรกที่สมเหตุสมผลกว่า แต่เพราะเป็นคีย์ BLOB ขนาด 16 ไบต์ จึงยังช้ากว่าคีย์จำนวนเต็มขนาด 8 ไบต์
  • UUID4 WITH ROWID ได้ประโยชน์จากความเป็นลำดับของ rowid ที่ซ่อนอยู่ แต่ยังมี write amplification จากการมีดัชนีสองชุดและต้นทุนของการแทรกดัชนีแบบสุ่ม จึงมีประสิทธิภาพต่ำกว่า UUID7 WITHOUT ROWID

clustered index คืออะไร?

  • clustered index คือดัชนีที่กำหนดลำดับการจัดเก็บจริงของแถวในตาราง
  • แถวสามารถเรียงจริงได้เพียงแบบเดียว ดังนั้นแต่ละตารางจึงมี clustered index ได้เพียงหนึ่งตัว
  • clustered index คือตัวตารางเอง ส่วน non-clustered index จะเก็บเพียงคอลัมน์ที่ถูกทำดัชนีและตัวชี้ไปยังตำแหน่งของข้อมูลแถวจริง

Rowid

  • ทุกตาราง SQLite แบบปกติจะมีคีย์หลักจำนวนเต็ม 64 บิตแบบปริยายชื่อ rowid
  • ข้อมูลตารางถูกเก็บในโครงสร้าง B-tree ที่มีหนึ่งเอนทรีต่อหนึ่งแถว โดยใช้ค่า rowid เป็นคีย์
  • rowid ทำหน้าที่เป็น clustered index ของ SQLite โดยพฤตินัย และลำดับการจัดเก็บจริงของแถวจะเป็นไปตามลำดับ rowid
โฆษณา

WITHOUT ROWID

  • SQLite รองรับตาราง WITHOUT ROWID ซึ่งไม่มี rowid แบบปริยาย
  • ในตาราง WITHOUT ROWID คีย์หลักที่ประกาศไว้จะทำหน้าที่เป็น clustered index
  • ตาราง rowid ของ SQLite ถูกทำเป็น B*-Tree ที่เก็บเนื้อหาทั้งหมดไว้ที่ใบ ส่วนตาราง WITHOUT ROWID ใช้ B-Tree ทั่วไปที่เก็บเนื้อหาไว้ทั้งที่ใบและโหนดกลาง

ค่าฐานอ้างอิง: คีย์หลักจำนวนเต็มแบบ rowid

  • ค่าฐานอ้างอิงวัดเวลาแทรกทีละ 1 ล้านแถวในตาราง rowid ปกติที่มีโครงสร้าง id INTEGER PRIMARY KEY, data BLOB
  • จำนวนแถวรวมในตารางผลลัพธ์อยู่ตั้งแต่ 10 ล้านแถวถึง 100 ล้านแถว และเวลาอยู่ในช่วง 692ms ถึง 838ms
  • ประสิทธิภาพฐานอ้างอิงอยู่ที่ประมาณ 1 ล้านการแทรกต่อวินาที

UUID4 WITHOUT ROWID

  • การทดสอบ UUID4 ใช้ตาราง WITHOUT ROWID ที่มีโครงสร้าง id BLOB PRIMARY KEY, data BLOB และแทรกค่า random-uuid4-bytes เป็นคีย์หลัก
  • เวลาในตารางผลลัพธ์คือ 2649ms ที่ 10 ล้านแถว และ 12586ms ที่ 100 ล้านแถว
  • ประสิทธิภาพการแทรกช้ากว่าค่าฐานอ้างอิง rowid แบบจำนวนเต็มประมาณ 14–16 เท่า

โปรไฟล์

  • diffgraph แบบ normalized ใช้เปรียบเทียบสแนปช็อตการโปรไฟล์ของ INTEGER และ UUID4 และแสดงความแตกต่างในรูปแบบ flamegraph
  • มุมมองแบบ normalized จะปรับจำนวน sample รวมของทั้งสองโปรไฟล์ให้เท่ากัน เพื่อดูความต่างเชิงสัมพัทธ์เป็นเปอร์เซ็นต์
  • เฟรมสีน้ำเงินหมายถึงเวลาของฟังก์ชันนั้นในโปรไฟล์ที่สองคือ UUID4 ลดลงเมื่อเทียบกับ INTEGER ส่วนเฟรมสีแดงหมายถึงเพิ่มขึ้นใน UUID4
  • ความเข้มของสีแสดงการเปลี่ยนแปลงสัมพัทธ์ของจำนวน sample ของเฟรมนั้นเอง หรือก็คือ self time delta
  • ใน diffgraph พบว่าใช้เวลากับการปรับสมดุลต้นไม้และการอ่าน-เขียนมากขึ้น
  • เพราะ UUID4 ไม่มีลำดับ คีย์จึงถูกจัดเรียงในลำดับสุ่ม และ SQLite ต้องปรับสมดุล B-tree อย่างต่อเนื่อง
โฆษณา

UUID7 WITHOUT ROWID

  • UUID7 เป็น UUID แบบเรียงตามเวลา และเป็นแนวทางที่ช่วยตัดปัญหาการจัดเรียงของ UUID4 ได้
  • การทดสอบ UUID7 ก็รันบนตาราง WITHOUT ROWID ที่มีโครงสร้าง id BLOB PRIMARY KEY, data BLOB
  • เวลาในตารางผลลัพธ์คือ 1372ms ที่ 10 ล้านแถว และ 1258ms ที่ 100 ล้านแถว
  • UUID7 WITHOUT ROWID กลับมาอยู่ในระดับที่สมเหตุสมผลกว่า UUID4 WITHOUT ROWID แต่ก็ยังช้ากว่าค่าฐานอ้างอิง
  • คีย์หลัก UUID แบบ BLOB มีขนาด 16 ไบต์ ขณะที่คีย์หลักจำนวนเต็มมีขนาด 8 ไบต์

UUID4 WITH ROWID

  • การทดสอบ UUID4 WITH ROWID ใช้ตาราง id BLOB PRIMARY KEY, data BLOB โดยไม่ใช้ WITHOUT ROWID
  • ในโครงสร้างนี้ rowid ที่ซ่อนอยู่เป็น clustered index และข้อดีของ rowid คือความเป็นลำดับ
  • ข้อเสียคือจะเกิดดัชนีสองชุดในตาราง และนำไปสู่ write amplification
  • เวลาในตารางผลลัพธ์คือ 2003ms ที่ 10 ล้านแถว และ 7119ms ที่ 100 ล้านแถว
  • UUID4 WITH ROWID มีประสิทธิภาพไม่ดีเท่า UUID7 WITHOUT ROWID และแม้จะไม่ใช่ clustered index ก็ยังต้องสร้างดัชนีต่อเนื่องจากการแทรกแบบสุ่ม

บทสรุป

  • ใน SQLite การเลือกใช้คีย์หลักแบบ UUID อาจทำให้ประสิทธิภาพการแทรกต่างกันมาก ขึ้นอยู่กับ clustered index และความสามารถในการเรียงลำดับของคีย์
  • ปัญหาของ UUID แบบสุ่มไม่ได้จำกัดอยู่แค่ SQLite แต่ขยายไปถึงฐานข้อมูลอื่นที่ใช้ clustered index ด้วย
  • โค้ดเบนช์มาร์กทั้งหมดเผยแพร่ไว้ใน GitHub repository

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

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

 
GN⁺ 4 시간 전
ความเห็นจาก Lobste.rs

  • ดีเลย ถ้ามีตัวเลขตอนที่คีย์จำนวนเต็มใน ตาราง rowid ไม่ได้เพิ่มขึ้นแบบโมโนโทนิกแต่เป็นแบบสุ่มด้วยก็น่าจะน่าสนใจ
    ประเด็นสำคัญที่บทความตกหล่นคือ ดัชนีพื้นฐานของตาราง rowid เป็น B+tree ส่วนตาราง without rowid เป็น B-tree
    เพราะงั้นโดยทั่วไป ถ้าขนาดเรคอร์ดเฉลี่ยเกินค่าขีดหนึ่ง แบบหลังจะไม่ค่อยเหมาะนัก เพราะโหนดภายในของดัชนีเก็บทั้งเรคอร์ดไว้ และถ้าจำไม่ผิด คู่มือ SQLite แนะนำกฎคร่าว ๆ ไว้ที่ 1/20 ของขนาดเพจ

  • ทุ่มแรงไปมากในการวัดประสิทธิภาพของ UUID แต่กลับไม่ได้พิจารณา natural key
    ไม่ว่าจะเป็นจำนวนเต็ม UUID หรือรูปแบบอื่น surrogate key ก็เพิ่มความซับซ้อน ไม่ได้เพิ่มข้อมูล และยังซ่อนข้อผิดพลาดของการทำ normalization
    ผู้เขียนยก “ป้องกันข้อมูลซ้ำ” เป็นเหตุผลในการใช้ UUID แต่จริง ๆ นั่นไม่ใช่เหตุผล ทุกแถวในทุกตารางของทุกฐานข้อมูลควรมีคีย์อย่างน้อยหนึ่งชุดของคอลัมน์ที่ใช้ระบุแถวนั้นได้อย่างไม่ซ้ำกัน
    ฐานข้อมูลที่ไม่มีคีย์แบบนั้นย่อมมีข้อมูลซ้ำซ้อนและเสี่ยงต่อความไม่สอดคล้องเชิงตรรกะ ถ้าฐานข้อมูลมีคีย์แบบนั้นอยู่แล้วก็ไม่จำเป็นต้องมี surrogate key หากมี natural key อยู่แล้วและมีการบังคับใช้อยู่ การอ้างว่า “จำเป็นเพราะประสิทธิภาพ” จึงต้องมีหลักฐาน เพราะมันหมายถึงต้นทุนเพิ่มและความซับซ้อนที่ไม่จำเป็น

    • อาจเป็นเพราะผมจินตนาการไม่พอ แต่เวลาจัดการข้อมูลที่มาจากโลกจริง ผมว่ามักหายากที่จะเจอ natural key ที่เป็นของจริง
      ค่าที่ดูเหมือนจะไม่ซ้ำกันก็อาจไม่ได้ไม่ซ้ำอย่างที่หวัง หรือค่าที่คิดว่าไม่เปลี่ยนสุดท้ายก็ต้องเปลี่ยน
      ในทางกลับกัน การใช้ surrogate key ทำให้ผมกำหนดตัวตนภายในระบบของตัวเองได้ โดยไม่ต้องพึ่งว่าคนอื่นนิยามความเป็นเอกลักษณ์ไว้อย่างไร หรือส่วนใหญ่มักไม่ได้กำหนดไว้อย่างเหมาะสม
      ก็มีข้อยกเว้นนะ ถ้าผมเป็นคนกำหนดโมเดลทั้งหมดเอง และข้อมูลไม่ได้มาจากสิ่งที่เรียกว่าโลกจริง natural key ก็สมเหตุสมผลกว่า แต่เวลาออกแบบสคีมาสำหรับข้อมูลโลกจริงที่ไม่น่าเคยถูกทำ normalization อย่างสมบูรณ์ surrogate key มักมีประโยชน์มาก
    • surrogate key แบบจำนวนเต็มที่เพิ่มขึ้นทีละลำดับมีประโยชน์เชิงปฏิบัติทันทีค่อนข้างมาก
      การอ้างอิงแถวไหนก็ทำได้ด้วยจำนวนเต็ม ทำให้การเข้าถึงง่ายขึ้นมาก และมนุษย์ก็จำได้ง่าย ใช้ในคิวรีก็สะดวก
      ถ้ามันเพิ่มขึ้นแบบโมโนโทนิก มันก็มีข้อมูลในตัวเองด้วย แม้จะเป็นข้อมูลซ้ำซ้อน แต่ก็เป็นความจริง
      ความเร็วในการค้นหาก็ถูกปรับให้เหมาะได้มากที่สุด แทบเป็นกรณีที่เหมาะที่สุดสำหรับการทำดัชนีด้วย B-tree, bitmap และอื่น ๆ
      ผมคิดว่าที่คนใช้ UUID กันเยอะ ส่วนใหญ่เป็นเพราะความสับสน มักใช้ตรรกะว่าอยากทำให้คีย์อ่านยากและเดาไม่ได้ แต่ผมเลิกพยายามเข้าใจไปแล้วว่าทำไมถึงคิดว่าต้องบังคับสิ่งนั้นกับ primary key แทนที่จะใช้ตัวระบุแยกต่างหากสำหรับจุดประสงค์นั้น
    • คำว่า “ป้องกันข้อมูลซ้ำ” ไม่ได้ปรากฏอยู่ในบล็อกโพสต์ จริง ๆ แล้วบทความไม่ได้อธิบายเลยด้วยซ้ำว่าใช้ UUID ไปทำไม

  • UUID version 7 มี timestamp 48 บิตอยู่ด้านหน้า เลยไม่ได้กระจายแบบสุ่มในลักษณะนี้ ดังนั้นการแบ่งเพจมากเกินไปและการ rebalance ก็น่าจะลดลงด้วย

    • ใช่ บทความพูดถึง UUID7 นี่แหละ

  • คนเขาใช้ UUID เป็น primary key กันจริง ๆ เหรอ? ถ้าจำเป็นต้องใช้ UUID ผมสงสัยว่าการทำแบบนั้นมีข้อดียังไง เมื่อเทียบกับการเก็บเป็นคีย์รอง

    • เพื่อการขยายระบบน่ะ ถ้าต้องสร้าง ID ที่ไม่ซ้ำกันแบบกระจายตัวด้วยความเร็วสูงจากคอมพิวเตอร์จำนวนมากและหลายดาต้าเซ็นเตอร์ทั่วโลก เช่น การอัปโหลดไปยัง S3 คุณคงไม่อยากล็อกจำนวนเต็มที่เพิ่มขึ้นทีละตัวเพียงค่าเดียว เพราะการล็อกและซิงก์กันทั้งโลกมันช้า
      GUID และ UUID แก้ปัญหานี้ได้ในเชิงโครงสร้าง
      v1 และ v6 เข้ารหัส machine ID กับ timestamp ไว้ จึงใกล้เคียงกับจำนวนเต็มที่เพิ่มขึ้นอัตโนมัติแต่มี namespace แยกตามแต่ละเครื่อง
      ความสับสนเกิดจากการที่หลายคนคิดว่า UUID เป็นแบบสุ่ม ซึ่งจริง ๆ ใช่เฉพาะ v4 เท่านั้น และการเลือก v4 ก็มาพร้อมต้นทุนที่น่าเสียดาย
      หลายครั้งเราต้องการ determinism ในระดับหนึ่ง เช่น v3, v5, v7 เพื่อช่วยจัดระเบียบข้อมูล หรือเพื่อการรับประกันด้านประสิทธิภาพและการชนกันของค่า
    • ต่อให้เก็บ UUID แบบสุ่มหรือค่าที่สุ่มกระจายสม่ำเสมอไว้เป็นคีย์รอง การแทรกข้อมูลก็ยังช้าลงอยู่ดี เพราะถึงจะไม่ใช่ clustered index ก็ยังมีการแทรกแบบสุ่มเกิดขึ้นใน B-tree ของดัชนีนั้นอยู่ดี