ตามหา SQLite ที่เร็วกว่าเดิม

• เมื่อรันอินสแตนซ์ SQLite หลายตัวร่วมกันในสภาพแวดล้อมแบบ serverless และ edge การ รอ I/O แบบ synchronous จะเพิ่ม tail latency และนักวิจัยจาก Helsinki กับ Cambridge ได้ทดลองวิธีลดปัญหานี้ด้วย asynchronous I/O และการแยก storage ออกมา
• io_uring ของ Linux ช่วยให้แอปพลิเคชันทำงานอื่นต่อได้ระหว่างที่มีคำขอ I/O ผ่าน submission queue และ completion queue จึงเป็นพื้นฐานที่ช่วยลดการ block ของเธรด
• ระหว่างการรัน sqlite3_step() หากหน้า B-Tree ที่ต้องใช้ไม่อยู่ในแคช SQLite จะอ่านดิสก์ด้วย synchronous I/O อย่าง POSIX read() ทำให้เธรดหยุดจนกว่า I/O จะเสร็จ
• นักวิจัยไม่ได้แค่เปลี่ยน POSIX call แต่ปรับ VM และ BTree ในโปรเจกต์เขียนใหม่ด้วย Rust ชื่อ Limbo ให้เข้ากับโมเดลการรันแบบ asynchronous
• ใน benchmark ค่า p999 tail latency ลดลงได้สูงสุด 100 เท่า แต่ p90 และ p99 แทบเท่ากับ SQLite และการประเมินกรณี reader/writer หลายตัวพร้อมกันยังเป็นงานในอนาคต

---

งานวิจัยเพื่อทำให้ SQLite เร็วขึ้น

• นักวิจัยจาก University of Helsinki และ Cambridge กล่าวถึงการนำ asynchronous I/O และการแยก storage มาใช้กับ SQLite ใน “Serverless Runtime / Database Co-Design With Asynchronous I/O”
• บทความนี้กลายเป็นพื้นฐานของ Limbo โปรเจกต์เขียน SQLite ใหม่ด้วย Rust
• เนื่องจากเป็นบทความ workshop จึงมีความยาวไม่มาก และโฟกัสอยู่ที่ serverless กับ edge computing
• ประเด็นหลักคือ แม้ SQLite เองจะเร็วอยู่แล้ว แต่ tail latency ในสภาพแวดล้อมแบบ multitenant ยังลดลงได้อีกหากเปลี่ยนโมเดลการรัน

io_uring ลดการรอ I/O อย่างไร

• io_uring ของเคอร์เนล Linux ให้ interface สำหรับ asynchronous I/O
• ชื่อนี้มาจาก ring buffer ที่ user space และ kernel space ใช้ร่วมกัน ซึ่งช่วยลด overhead จากการคัดลอก buffer ระหว่างสองพื้นที่
• แอปพลิเคชันสามารถส่งคำขอ I/O แล้วทำงานอื่นควบคู่ไปได้จนกว่า OS จะแจ้งว่าเสร็จสิ้น
• ลำดับการทำงานมีดังนี้
  • ตั้งค่าพื้นที่หน่วยความจำสองส่วนคือ submission queue และ completion queue ด้วย system call io_uring_setup()
  • แอปพลิเคชันใส่คำขอ I/O ลงใน submission queue แล้วใช้ io_uring_enter() เพื่อบอกให้ OS เริ่มประมวลผล
  • คืน control กลับสู่ user space โดยไม่ block เธรดเหมือน read() และ write()
  • แอปพลิเคชันทำงานอื่นไปก่อน แล้วคอย poll completion queue เป็นระยะเพื่อตรวจว่า I/O เสร็จแล้วหรือไม่

คอขวด synchronous I/O ในการรัน query ของ SQLite

• แอปพลิเคชัน SQLite เปิดไฟล์ฐานข้อมูลด้วย sqlite3_open() และในขั้นตอนนี้จะเรียกใช้ OS I/O ระดับต่ำอย่าง POSIX open
• sqlite3_prepare() แปลงคำสั่ง SQL เช่น SELECT, INSERT ให้เป็นลำดับ คำสั่ง bytecode
• sqlite3_step() รันคำสั่ง bytecode จนกว่าจะสร้างแถวที่ query ต้องอ่านได้ หรือจนกว่าการรันจะจบ
  • หากมีแถวให้อ่าน จะคืนค่า SQLITE_ROW
  • หาก statement เสร็จสมบูรณ์ จะคืนค่า SQLITE_DONE
• ระหว่างรัน จะมีการเรียก backend pager และไล่ผ่าน B-Tree ที่แทน table และ row
• หากหน้า B-Tree ที่ต้องใช้ไม่อยู่ใน page cache ของ SQLite จะเกิดการเข้าถึงดิสก์
  • SQLite ใช้ synchronous I/O อย่าง POSIX read เพื่ออ่านเนื้อหาหน้าจากดิสก์เข้าหน่วยความจำ
  • ระหว่างนี้ sqlite3_step() จะ block kernel thread
  • หากต้องการทำงานพร้อมกันระหว่างรอ I/O แอปพลิเคชันต้องใช้เธรดมากขึ้น

เหตุผลที่อยาก embed SQL ใน serverless และ edge

• เมื่อ serverless computing รันที่ edge แต่ฐานข้อมูลอยู่ในสภาพแวดล้อม cloud จะเกิด ค่าใช้จ่ายจาก network round trip ระหว่าง serverless function กับ cloud
• อีกทางคือวางข้อมูลร่วมไว้ที่ edge แต่แนวทางที่ถูกเสนอว่าเหมาะกว่าคือ embed ฐานข้อมูลเข้าไปใน edge runtime
• Cloudflare Workers ทำรูปแบบนี้ได้แล้ว แต่ expose เป็น KV interface
• KV ไม่ได้เหมาะกับทุก problem domain
  • การ map ข้อมูลแบบ table เข้ากับโมเดล KV ทำให้ประสบการณ์ของนักพัฒนาแย่ลง
  • ยังมีต้นทุนจาก serialization และ deserialization ด้วย
• SQL อาจเหมาะกว่า และ SQLite เป็น embedded database จึงสามารถรวมเข้าไปใน serverless runtime ได้โดยตรง

ทำไมการเปลี่ยน SQLite เป็น io_uring แบบง่าย ๆ จึงยาก

• SQLite ใช้ synchronous I/O ที่อิงกับ POSIX read() และ write() แบบดั้งเดิม
• แม้จะไม่ใช่ปัญหาใหญ่ในแอปพลิเคชันขนาดเล็ก แต่หากรันฐานข้อมูล SQLite หลายร้อยตัวบนเซิร์ฟเวอร์เดียวกัน ก็อาจกลายเป็นคอขวดได้
• ในสภาพแวดล้อมที่ต้องเพิ่มการใช้ทรัพยากรเซิร์ฟเวอร์ให้สูงสุด synchronous I/O จะกลายเป็นข้อจำกัด
• SQLite มีปัญหาด้าน concurrency และ multitenancy
  • I/O เป็น synchronous และมีการ block ทำให้แอปพลิเคชันบนเครื่องเดียวกันต้องแย่งทรัพยากรกัน
  • ผลคือ latency เพิ่มขึ้น
• การแทนที่ POSIX I/O call ด้วย io_uring แบบตรง ๆ ทำได้ยาก
  • แอปพลิเคชันที่ใช้ blocking I/O ต้องถูกออกแบบใหม่ให้เข้ากับโมเดล asynchronous I/O ของ io_uring
  • ไลบรารี SQLite ต้องสามารถคืน control ให้แอปพลิเคชันได้ระหว่างที่ I/O กำลังดำเนินอยู่
• นักวิจัยจึงเลือกแนวทางเขียน SQLite ใหม่ด้วย Rust และใช้ io_uring แทนที่จะเปลี่ยนแค่บาง call ของ SQLite

โมเดลการรันแบบ asynchronous ของ Limbo

• Limbo เป็นโปรเจกต์เขียน SQLite ใหม่ด้วย Rust และปรับองค์ประกอบ VM กับ BTree ให้รองรับ asynchronous I/O
• คำสั่ง bytecode แบบ synchronous ถูกแทนที่ด้วยคำสั่งคู่กันแบบ asynchronous
• ตัวอย่างเช่น คำสั่ง Next จะเลื่อน cursor ไปข้างหน้า และดึงหน้าถัดไปมาหากจำเป็น
  • ในเวอร์ชัน synchronous เดิม หากเกิด disk I/O จะ block จนกว่าจะอ่านหน้าและคืนกลับให้ผู้เรียกได้
  • ในเวอร์ชัน asynchronous หลังส่ง NextAsync แล้วจะคืนค่าทันที
  • จากนั้นผู้เรียกจะเลือก block หรือทำงานอื่นต่อก็ได้
• asynchronous I/O ช่วยกำจัดการ block และปรับปรุง concurrency
• เพื่อเพิ่ม utilization ของทรัพยากรให้สูงขึ้น ยังมีการเสนอ การแยก storage โดยแยก query engine และ storage engine ออกจากกัน
• มีลิงก์คำอธิบายที่เกี่ยวข้องอย่าง Disaggregated Storage - a brief introduction แนบมาด้วย

ผล benchmark และคำถามที่ยังเหลือ

• benchmark จำลอง multitenant serverless runtime
• แต่ละ tenant มี embedded database ของตนเอง
• จำนวน tenant เปลี่ยนตั้งแต่ 1 ถึง 100 โดยเพิ่มทีละ 10
• SQLite ใช้เธรดแยกสำหรับแต่ละ tenant และวัดผลโดยรัน query ในแต่ละเธรด
• query ที่รันคือ SELECT * FROM users LIMIT 100 และทำซ้ำ 1000 ครั้ง
• Limbo ทำการทดลองเดียวกัน แต่ใช้ coroutine ของ Rust
• ผลลัพธ์คือ tail latency ที่ p999 ลดลงได้สูงสุด 100 เท่า
• latency ของ query ใน SQLite ไม่ได้แย่ลงอย่างค่อยเป็นค่อยไปตามจำนวนเธรดที่เพิ่มขึ้น
• งานยังอยู่ระหว่างดำเนินการ และใน paper ยังมีคำถามเปิดอยู่หลายข้อ
  • ใน Future Work กล่าวถึง benchmark เพิ่มเติมที่มี reader และ writer หลายตัว
  • ประโยชน์เด่นชัดเฉพาะหลัง p999
  • ประสิทธิภาพที่ p90 และ p99 แทบเหมือนกับ SQLite
• โค้ดของ Limbo เปิดเป็น โอเพนซอร์ส
• ปัจจุบัน Limbo เป็นโปรเจกต์อย่างเป็นทางการของ Turso และมี บทความแนะนำ เผยแพร่แล้ว