สร้างฐานข้อมูลของตัวเอง

• อธิบายหลักการพื้นฐานและขั้นตอนการใช้งาน ฐานข้อมูลแบบคีย์-ค่า
• เริ่มต้นจากการจัดเก็บแบบถาวรและการค้นหาผ่าน ระบบไฟล์
• เมื่อต้องเพิ่ม แก้ไข และลบข้อมูล พบว่าปัญหา ความไม่มีประสิทธิภาพ เกิดขึ้น
• พัฒนาขึ้นอย่างค่อยเป็นค่อยไปไปสู่โครงสร้างที่มีประสิทธิภาพมากขึ้น เช่น Append-Only File, ดัชนี, การจัดเรียง, และการบีบอัดเซกเมนต์
• เชื่อมโยงไปสู่โครงสร้างสมัยใหม่อย่าง LSM Tree และถูกนำไปใช้ในระบบขนาดใหญ่จริง

---

บทนำ: การเริ่มต้นสร้างฐานข้อมูลของคุณเอง

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

แนวคิดพื้นฐาน: การเก็บข้อมูลถาวรด้วยไฟล์

• จุดประสงค์ของฐานข้อมูลคือการ เก็บข้อมูลอย่างถาวร และค้นหาได้อย่าง มีประสิทธิภาพ ในภายหลัง
• วิธีที่พบบ่อยที่สุดคือการใช้ ระบบไฟล์ เพื่อเขียนแต่ละคู่ key-value ลงในไฟล์
• เมื่อต้องเก็บข้อมูล ตัวอย่างเช่น ใช้รูปแบบ $ db set 1 "Lorem ipsum" เพื่อเติมข้อมูลลงไฟล์
• เมื่อต้องค้นหา ข้อมูลจะถูกสแกนทีละรายการทั้งหมดในไฟล์เพื่อหาค่า key ที่ต้องการ
• การแก้ไข จะเป็นการแทนที่ค่าใหม่ในตำแหน่งเดิมของ key และ การลบ คือการลบระเบียนนั้นออกจากไฟล์

ปัญหา: การแก้ไข In-Place ที่ไม่มีประสิทธิภาพ

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

การปรับปรุง 1: โครงสร้างไฟล์แบบ Append-Only

• ในการแก้ไขและลบข้อมูล ให้คงข้อมูลเดิมไว้ และใช้วิธีเพิ่ม เรคคอร์ดใหม่เฉพาะที่ท้ายไฟล์
• ทุกครั้งที่ข้อมูลเปลี่ยน จะเพิ่มเรคคอร์ดใหม่และปรับวิธีค้นหาให้มองหา key ที่อยู่ล่าสุดเสมอ
• การลบจะแสดงผลด้วยค่า tombstone พิเศษ (เช่น null)
• ข้อดี: เขียนเพิ่มข้อมูลได้อย่างมีประสิทธิภาพโดยไม่ต้องย้ายข้อมูลเดิม
• ข้อเสีย: เรคคอร์ดซ้ำและเครื่องหมายลบทำให้ขนาดไฟล์ค่อย ๆ เพิ่มขึ้น
• ความเร็วในการค้นหายังคงช้าอยู่ (ต้องสแกนทั้งไฟล์)

การปรับปรุง 2: การจัดการขนาดไฟล์และ Compaction

• เพื่อแก้ปัญหาไฟล์ที่โตแบบไม่จำกัด เมื่อไฟล์มีขนาดถึงเกณฑ์ที่กำหนดให้ย้ายไปไฟล์ใหม่ (segment) และ ลบข้อมูลที่ไม่จำเป็น (ซ้ำ/ลบแล้ว) ออกจากไฟล์เดิม เพื่อให้ขนาดลดลง (compaction)
• ระหว่าง compaction ให้เก็บไว้เฉพาะข้อมูลที่ยังจำเป็นจริง และลบเรคคอร์ดเก่าหรือเครื่องหมายลบที่เหลืออยู่ที่ไม่จำเป็น
• พัฒนาสู่โครงสร้างที่จัดการไฟล์หลาย segment และหากจำเป็นจึงรวมไฟล์เหล่านี้เข้าด้วยกัน (merge)

การปรับปรุง 3: ค้นหาเร็วขึ้นด้วย Index

• สร้าง ดัชนีในหน่วยความจำ (hash table) เพื่อเก็บตำแหน่ง (offset) ของไฟล์ต่อ key ทำให้ค้นหาได้เร็วขึ้น
• ตอนค้นหา เราจะดูดัชนีก่อน แล้วอ่านตำแหน่งตรงจากไฟล์ทันที
• trade-off: ความเร็วค้นหาดีขึ้น แต่ดัชนีอยู่ในหน่วยความจำ ดังนั้นเมื่อ key มีจำนวนมากอาจชนขีดจำกัดหน่วยความจำ
• การจัดการดัชนีทำให้ ประสิทธิภาพการเขียน ลดลงบ้าง

การปรับปรุง 4: Sorted String Tables และ Sparse Index

• หากเก็บข้อมูลในสถานะที่คีย์เรียงลำดับอยู่ตลอดเวลา จะได้ประสิทธิภาพสูงสำหรับ การค้นหาระหว่างช่วง (range query)
• จากการเรียงลำดับนี้ จึงสามารถเก็บดัชนีได้เพียงบาง key เท่านั้น (sparse index)
• ปรับความหนาแน่นของดัชนีเพื่อควบคุม trade-off ระหว่างการใช้หน่วยความจำกับประสิทธิภาพการค้นหาได้

รูปแบบการใช้งาน: การผสมผสาน In-Memory และ On-Disk เพื่อความทนทาน

• ข้อมูลใหม่จะถูกบันทึกไว้ก่อนใน รายการเรียงลำดับในหน่วยความจำ และเพิ่มสำเนาลงไฟล์ append-only เพื่อทำหน้าที่สำรอง (backup)
• เมื่อรายชื่อในหน่วยความจำโตขึ้น จะถูกแปลงและจัดเก็บลงไฟล์บนดิสก์แบบเรียงลำดับ (SST) พร้อมอัปเดตดัชนี
• ตอนค้นหา จะตรวจสอบหน่วยความจำก่อน หากไม่พบ ให้ค้นหาบนดิสก์ผ่านดัชนี
• ไฟล์บนดิสก์ถูกจัดการแบบ ไม่แก้ไขได้ (immutable) หมายความว่าการแก้ไข/การลบก็ยังคงทำผ่านการเพิ่มข้อมูลใหม่
• ข้อมูลซ้ำและข้อมูลที่ถูกลบโดยไม่จำเป็นจะถูกจัดการด้วย compaction อย่างต่อเนื่องเพื่อควบคุมขนาดไฟล์

การเกิดของ LSM Tree (Log-Structured Merge Tree)

• โครงสร้างที่พัฒนาขึ้นเหล่านี้จริง ๆ แล้วได้รับการใช้ในชื่อ LSM Tree อย่างแพร่หลาย
• รูปแบบการผสมผสานระหว่าง memtable และ SST (sorted string table) บนดิสก์ ทำให้เร็วและเหมาะกับสภาพแวดล้อมขนาดใหญ่
• ใช้เป็นโครงสร้างข้อมูลหลักในระบบฐานข้อมูลคีย์-ค่าขนาดใหญ่เช่น LevelDB และ Amazon DynamoDB
• แม้มีข้อเสียและความแตกต่างเมื่อเทียบกับโครงสร้างอื่น ๆ (เช่น ระบบฐานข้อมูลเชิงสัมพันธ์ที่อิง B-Tree) แต่มีการยืนยันประสิทธิภาพที่ดีเด่นในการรองรับทราฟฟิกปริมาณสูงและการขยายตัว

บทสรุป

• เริ่มต้นจากไฟล์ฐานข้อมูลแบบพื้นฐาน แล้วค่อย ๆ พัฒนาผ่าน append-only, ดัชนี, การเรียงลำดับ, segment-compaction และแนวคิดการผสมผสานหน่วยความจำ-ดิสก์ สู่การออกแบบฐานข้อมูลที่ดียิ่งขึ้น
• สามารถเรียนรู้การทำงานภายในและการคิดเชิงโครงสร้างของฐานข้อมูลได้โดยตรงผ่านกระบวนการพัฒนาเอง
• โครงสร้าง LSM Tree ทำหน้าที่เป็นองค์ประกอบมาตรฐานในระบบข้อมูลขนาดใหญ่ยุคใหม่
• ยังมีแนวทางสำรวจเพิ่มเติม เช่น โครงสร้าง B-Tree ของฐานข้อมูลเชิงสัมพันธ์ ที่สามารถศึกษาได้อีกต่อไป

[GN⁺]

ความคิดเห็นจาก Hacker News

• รู้สึกชอบมากกับดีไซน์และตัวอย่างในบทความนี้ โครงสร้างที่อ่านง่ายเป็นจุดเด่นมาก และการฝึกฝนแบบนี้เองก็เป็นประสบการณ์ที่สนุกมาก การเริ่มต้นจากศูนย์ทำให้เห็นได้ชัดว่าตัวเองรู้เรื่องอะไรบ้างอย่างแท้จริง
  • ผมเองก็เคยมีท่าทีแบบใจร้อนสมัยก่อนว่า "อย่าทำฐานข้อมูลเอง และอย่าใช้ฐานข้อมูล KV เลย ให้ใช้แค่ SQL" แต่ความคิดนั้นก็มาจากการพยายามออกแบบ DB เองหรือพยายามหลีกเลี่ยง SQL โดยไปใช้แต่ KV จนท้ายที่สุดกลับต้องสร้าง SQL แบบหยาบ ๆ ขึ้นมาเอง จึงยืนยันได้ชัดว่าเรียนรู้ผ่านการลงมือทำมีคุณค่าจริง ๆ
  • อย่างเดียวที่เสียดายคือมีการใช้ lorem ipsum เป็นตัวอย่าง จึงทำให้ผ่านไปแบบไม่ค่อยตั้งใจ ข้อมูลตัวอย่างที่เป็นข้อมูลจริงคงดึงความสนใจกว่าได้มาก ที่เหลือแล้ว บทความนี้ดีมากจริง ๆ
• บทความระบุว่า "LSM tree เป็นโครงสร้างข้อมูลที่ใช้โดยปกติใน DynamoDB และให้ประสิทธิภาพยอดเยี่ยมแม้ในสเกลใหญ่…รองรับได้ถึง 80 ล้าน rps" ซึ่งมีโอกาสทำให้เข้าใจผิดได้เล็กน้อย เพราะ LSM ใช้ใน storage engine ระดับโหนด แต่ไม่ได้อธิบายขั้นตอนที่ระบบกระจายทั้งหมดขยายสเกลไปถึง 80 ล้าน rps ในงานเดิมของ Dynamo ผมจำได้ว่า paper เดิมใช้ BerkeleyDB (b-tree หรือ LSM) และใน paper ปี 2012 เขาเปลี่ยนมาเป็น engine ที่เป็น LSM แบบครบถ้วน
• ผมลองคลิกอ่านบทความบางชิ้นในรายการแล้ว เห็นว่าดีไซน์และอนิเมชันสวยมาก ยอดเยี่ยมเลย
• ในส่วน “Sorting in Practice” ตัวอย่างแรกดูเหมือนผิดพลาด ในคำอธิบายเขียนไว้ว่าหลัง sort ในหน่วยความจำแล้ว เขียนลงดิสก์ในสถานะที่ยัง sort อยู่ แต่ในตัวอย่างจริงเมื่อเขียนลงดิสก์กลับไม่คงลำดับ ส่วนตัวอย่าง recap ของ flush (ข้อ 2) ก็เช่นเดียวกัน โดยข้อความเขียนว่าบันทึกไฟล์ในสภาพที่เรียงลำดับแล้ว
• บทความนี้น่าสนใจมาก ช่วงนี้ผมกำลังโมเดลกิจกรรมของนักพัฒนาเป็นระบบ key-value แบบ time-series โดยใช้ผู้พัฒนาเป็น key และ commit เป็น value โดยมีปัญหาคล้าย ๆ กันคือ log โตเร็วขึ้น, index หนักขึ้น, และ range query ช้าลง ระหว่างทำ compaction ก็สงสัยว่าควรตัดข้อมูลใดออกดี รู้สึกว่าการหาจุดสมดุลระหว่างความใหม่กับช่วงเก็บรักษาข้อมูลค่อนข้างยาก
• ช่วง 4 สัปดาห์ที่ผ่านมา ผมทุ่มเทอยู่กับการเขียน triple store ด้วยตัวเอง พอบทความนี้ออกสักช้ากว่านิดเดียวคงช่วยให้เข้าใจ insight บางอย่างเร็วขึ้น คิดถึงจุดนี้เสมอ
• ถ้าผู้เขียนอ่านข้อความนี้ อยากให้เพิ่ม RSS feed ในไซต์ด้วยนะ อยากเพิ่มลง Feedly เพื่ออ่านต่อ
• ถ้าคุณอยากสร้างฐานข้อมูลของตัวเอง แนะนำ หนังสือออนไลน์ฟรี นี้แน่นอน
  • เคยจำได้ว่าเคยมีบทความหนึ่งที่อธิบายแนวคิดพื้นฐานของฐานข้อมูลด้วยตัวอย่าง bash (เช่น "การสร้าง DB ด้วย bash") ที่เคยมีในนี้ แต่ตอนนี้หามันไม่เจอแล้ว ถ้าใครมีลิงก์ช่วยส่งต่อให้หน่อย
• ตอนนี้มีทราฟฟิกมากเกินจนเข้าเว็บไม่ได้
  • คงต้องมีฐานข้อมูลที่เร็วขึ้นแน่ ๆ
• ชอบมากกับแนวทางอธิบายแบบค่อย ๆ ต่อจาก "First Principles" แบบนี้ หากติดตามไปทีละขั้นตอนจะเห็นชัดว่าทุกขั้นมีปัญหาอะไรเกิดขึ้น และเมื่อแก้ปัญหาแล้วก็เกิดปัญหาใหม่เสมอ ทำให้ได้ทางออกที่น่าพอใจในที่สุด