พื้นฐานของฐานข้อมูล

 (tontinton.com)
5 คะแนน โดย GN⁺ 2023-12-16 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

พื้นฐานของ bashdb

  • bashdb ซึ่งเป็นโปรแกรมฐานข้อมูลที่ง่ายที่สุด ประกอบด้วยฟังก์ชัน bash สองตัว
  • ฟังก์ชัน db_set จะเพิ่มข้อมูลลงในไฟล์ และฟังก์ชัน db_get จะค้นหาข้อมูล
  • ปัญหาของ bashdb ได้แก่ ความทนทาน อะตอมมิกซิตี การแยกตัว และประสิทธิภาพ

ปรับปรุง bashdb ให้เป็น ACID

  • ACID คือคุณสมบัติของทรานแซ็กชันฐานข้อมูล ซึ่งหมายถึง อะตอมมิกซิตี ความสอดคล้อง การแยกตัว และความทนทาน
  • เพื่อปรับปรุงความทนทานของ bashdb จึงเพิ่มคำสั่ง sync เข้าไปใน db_set
  • เพื่อการแยกตัว มีการเพิ่มการล็อกไฟล์โดยใช้โปรแกรม flock

ความทนทาน

  • fsync และ fdatasync เป็น system call ที่ใช้ flush write buffer ลงดิสก์
  • คำสั่ง sync จะ flush หน้าหน่วยความจำที่ "สกปรก" ทั้งหมดลงดิสก์ และแฟล็ก -d จะเรียก fdatasync

การแยกตัว

  • ใช้ flock เพื่อให้ bashdb รองรับการแยกตัวระหว่างหลายโปรเซส
  • flock เป็นโปรแกรมลินุกซ์สำหรับการล็อกไฟล์ โดยใช้แฟล็ก -s เพื่ออนุญาตให้อ่านพร้อมกันได้

ข่าวร้าย

  • ยังไม่พบวิธีง่าย ๆ ในการรับประกันอะตอมมิกซิตีด้วย bashdb
  • เพื่อเพิ่มประสิทธิภาพ จำเป็นต้องปรับปรุงอัลกอริทึม O(n)

Storage Engine

  • จุดประสงค์ของ storage engine คือการให้นามธรรมสำหรับการอ่านและเขียนข้อมูลลง persistent storage
  • การออกแบบ storage engine มีเป้าหมายเพื่อลด disk I/O และ disk seek ให้น้อยที่สุด

Mutable B-Tree

  • B-Tree เป็นรูปแบบดัดแปลงของ BST ที่มี spatial locality ซึ่งช่วยลด disk I/O และการ seek
  • B-Tree คือ BST ที่ถูกทำให้เป็นแบบทั่วไปเพื่อให้โหนดมีลูกได้มากขึ้น

Immutable LSM Tree

  • LSM Tree เป็นโครงสร้างข้อมูลแบบ immutable ที่เขียนแบบลำดับต่อเนื่อง ซึ่งเหมาะกับ workload ที่เน้นการเขียน
  • LSM Tree จะบัฟเฟอร์ข้อมูลไว้ในหน่วยความจำ และเมื่อถึงขนาดที่กำหนดจะ flush ออกมาเป็น SSTable ที่เรียงลำดับแล้ว

Bloom Filter

  • Bloom Filter เป็นโครงสร้างข้อมูลเชิงความน่าจะเป็นที่ใช้ตรวจสอบได้อย่างมีประสิทธิภาพว่ารายการหนึ่งไม่มีอยู่ในเซต
  • Bloom Filter ทำงานโดยใช้ฟังก์ชันแฮช และมีความซับซ้อนเชิงพื้นที่เป็น O(log n)

Write Ahead Log

  • WAL เป็นไฟล์พิเศษที่บันทึกการทำงานของทรานแซ็กชันทั้งหมด และใช้สร้างสถานะขึ้นใหม่เมื่อโปรเซสฐานข้อมูลเริ่มทำงาน

การแยกตัว

  • เพื่อให้เกิดการแยกตัว สามารถใช้ pessimistic locking, optimistic locking หรือ MVCC ได้
  • มาตรฐาน ANSI/ISO SQL 92 ได้กำหนดระดับการแยกตัวของการอ่านหลายระดับ

ระบบกระจาย

  • ระบบกระจายเพิ่มความซับซ้อน แต่สามารถกระจายข้อมูลไปยังหลายเครื่องเพื่อให้ได้ความพร้อมใช้งานและการขยายระบบในแนวนอน
  • ตามทฤษฎี CAP ระบบสามารถรับประกันได้เพียงสองในสามอย่างจาก ความสอดคล้อง ความพร้อมใช้งาน และความทนทานต่อการแบ่งเครือข่าย

Consistent Hashing

  • Consistent Hashing เป็นวิธีแบ่งข้อมูลที่ช่วยลดปริมาณรายการที่ต้องย้ายเมื่อมีการเพิ่มหรือลบโหนด

ความเห็นของ GN⁺:

  • ความเข้าใจเกี่ยวกับปัญหาพื้นฐานของฐานข้อมูลและคุณสมบัติ ACID เป็นแกนหลักของวิศวกรรมฐานข้อมูล
  • ตัวอย่าง bashdb ช่วยให้เข้าใจปัญหาที่เกิดขึ้นจริงในระบบฐานข้อมูลได้ดี
  • การออกแบบ storage engine และระบบกระจายเป็นปัจจัยสำคัญที่กำหนดประสิทธิภาพและความน่าเชื่อถือของฐานข้อมูล

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

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

 
GN⁺ 2023-12-16
ความคิดเห็นบน Hacker News

  • สรุปความคิดเห็นแรก:

    • หนึ่งในคุณลักษณะของฐานข้อมูลที่ใช้ LSM คือเรคคอร์ดที่ถูกลบหรือ tombstone อาจคงอยู่เป็นเวลานาน
    • ควรข้าม tombstone เฉพาะในเลเวลสุดท้ายเท่านั้น และไม่ควรข้ามในทุกเลเวล
    • มิฉะนั้น tombstone ในเลเวลบนอาจถูกนำออกไป ทำให้รายการในเลเวลล่างกลับมาปรากฏอีกครั้ง
    • ฐานข้อมูลอย่าง RocksDB พยายามแก้ปัญหานี้ด้วยการเพิ่มประสิทธิภาพ

  • สรุปความคิดเห็นที่สอง:

    • การหลีกเลี่ยงการเรียนรู้ระบบกระจายอาจเป็นเรื่องเสี่ยง
    • ในความเป็นจริง ระบบโปรดักชันที่มีความซับซ้อนทุกระบบล้วนเป็นระบบกระจาย
    • ถ้าฐานข้อมูลเป็นชุดการทำซ้ำข้อมูล ก็ถือว่าเป็นระบบกระจาย
    • หากต้องการเรียนรู้เกี่ยวกับระบบกระจาย ให้ดู jepsen.io และ raft.github.io

  • สรุปความคิดเห็นที่สาม:

    • ในเรื่องความสอดคล้อง มีทั้งความสอดคล้องของฐานข้อมูลและความสอดคล้องของแอปพลิเคชัน
    • คุณอาจทำ ACID (ความเป็นอะตอม ความสอดคล้อง การแยกจากกัน ความคงทน) ได้ในตารางเดียว แต่ล้มเหลวได้เมื่อเขียนข้ามหลายตาราง
    • เมื่อต้องจัดการกับทรานแซกชันที่อัปเดตหลายตารางพร้อมกัน ทุกตารางควรถูกอัปเดตพร้อมกันทั้งหมดหรือไม่ถูกอัปเดตเลย

  • สรุปความคิดเห็นที่สี่:

    • นี่เป็นบทความที่ให้ภาพรวมที่ยอดเยี่ยมของแนวคิดหลากหลายที่เกี่ยวข้องกับการสร้างฐานข้อมูล
    • ครอบคลุมตั้งแต่การใช้ SIMD เพื่อดึงประสิทธิภาพจากเครื่องเดี่ยว ไปจนถึงอัลกอริทึมฉันทามติ
    • มีการกล่าวถึง formal methods ที่ใช้กับความน่าเชื่อถือของฐานข้อมูลและระบบกระจาย
    • มีงานวิจัยที่น่าสนใจเกี่ยวกับวิธีที่ทีม Amazon S3 ใช้ TLA+ ในการทำโมเดล

  • สรุปความคิดเห็นที่ห้า:

    • หลายคนเรียนรู้ฐานข้อมูลผ่านการเรียน SQL แต่การเข้าใจ B-tree จะช่วยให้เข้าใจจุดแข็งและจุดอ่อนของ RDBMS ได้ดีขึ้น
    • ผู้คนพยายามทำให้ฐานข้อมูลเร็วขึ้นด้วยการเพิ่มดัชนี แต่จริง ๆ แล้วนั่นเป็นเพียงการกลบปัญหา
    • บางปัญหาเหมาะกับ B-tree แต่หลายปัญหาไม่เหมาะ
    • SQL เป็นเพียงอินเทอร์เฟซสำหรับคิวรีไปยังระบบ B-tree ระยะไกล

  • สรุปความคิดเห็นที่หก:

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

  • สรุปความคิดเห็นที่เจ็ด:

    • ในเวอร์ชัน Bash ความเป็นอะตอมสามารถทำได้โดยคัดลอกไฟล์ไปยังไฟล์ชั่วคราว จากนั้นแก้ไข แล้วใช้ sync; mv; sync

  • สรุปความคิดเห็นที่แปด:

    • เป็นการออกแบบที่ยอดเยี่ยมมาก โดย document API คล้าย MongoDB, การทำ replication แบบไม่มี leader คล้าย Cassandra และสถาปัตยกรรม one-core-per-thread คล้าย ScyllaDB
    • ทั้งหมดนี้ถูกพัฒนาด้วย Rust

  • สรุปความคิดเห็นที่เก้า:

    • หนังสือชื่อ 'Database Internals' ดีอย่างน่าทึ่ง และให้การสำรวจภายในระบบอย่างลึกซึ้ง
    • ผู้แสดงความคิดเห็นถามว่ามีหนังสือคล้ายกันอีกหรือไม่

  • สรุปความคิดเห็นที่สิบ:

    • หนังสือ 'Database Design and Implementation' ก็เป็นงานอ่านที่ยอดเยี่ยมมากเช่นกัน พร้อมตัวอย่างจำนวนมากที่เขียนด้วย Java
    • สำหรับงานวิจัยจริง แนะนำผลงานของ Andy (Pavlo), Viktor Leis, Thorsten Grust และ Thomas Neumann