พื้นฐานของฐานข้อมูล
(tontinton.com)- เริ่มจากที่เก็บคีย์-ค่าแบบ Bash ง่าย ๆ แล้วค่อย ๆ แสดงให้เห็นว่าเหตุใดฐานข้อมูลจริงจึงต้อง扱 ความทนทาน, ความเป็นอะตอม, isolation และประสิทธิภาพเป็นโจทย์ออกแบบแยกกัน
fsync/fdatasync,flockและ WAL เป็นเครื่องมือพื้นฐานสำหรับปกป้องข้อมูลในสถานการณ์ที่เกิดความขัดข้องและการทำงานพร้อมกัน แต่ยิ่งเพิ่มระดับการรับประกันมากเท่าไร ต้นทุนด้านประสิทธิภาพ ก็ยิ่งสูงขึ้น- Storage engine ใช้โครงสร้างอย่าง B-tree และ LSM tree เพื่อลดค่าใช้จ่ายของ disk I/O และการค้นหา โดยแต่ละแบบมีงานบำรุงรักษาอย่าง vacuum และ compaction ตามมา
- ฐานข้อมูลแบบกระจายได้ความพร้อมใช้งานและการขยายแนวนอนเป็นการแลกเปลี่ยนกับ ความซับซ้อนของระบบกระจาย เช่น CAP theorem, network partition, การปรับความสอดคล้อง และการแก้ไขความขัดแย้ง
- เมื่อเลือกหรือสร้างฐานข้อมูล ต้อง ปรับให้เข้ากับ workload ทั้งการรับประกัน ACID, ระดับ isolation, โครงสร้างการจัดเก็บ, วิธี replication และข้อกำหนดด้าน consistency
ปัญหาพื้นฐานของฐานข้อมูลที่เห็นได้จาก bashdb
bashdbเป็นที่เก็บคีย์-ค่าแบบง่ายที่สร้างจากฟังก์ชัน Bash สองตัวdb_setappend ข้อมูลลงไฟล์ในรูปแบบkey,valuedb_getอ่านค่าล่าสุดโดยผสมgrep,sedและtail
- แม้จะเรียบง่ายสำหรับการเรียนรู้ แต่เพียงการ implement แบบนี้ก็เผยให้เห็นปัญหาที่ฐานข้อมูลระดับ production ต้องแก้
- Durability: หากเครื่อง crash หลัง
db_setสำเร็จ ข้อมูลที่ยังไม่ได้ flush ลงดิสก์อาจหายไป - Atomicity: หาก crash ระหว่างการเขียน ข้อมูลอาจถูกบันทึกเพียงบางส่วนและเสียหายได้
- Isolation: หากการอ่านและการเขียนเข้าถึงรายการเดียวกันพร้อมกัน ฝั่งอ่านอาจเห็นข้อมูลเพียงบางส่วน
- Performance:
db_getค้นหาทั้งไฟล์ทีละบรรทัด จึงเป็นO(n)
- Durability: หากเครื่อง crash หลัง
ACID และความพยายามปรับปรุง bashdb
- ACID เป็นตัวย่อที่รวมคุณสมบัติที่ฐานข้อมูลจำนวนมากพยายามรับประกัน
- Atomicity: หากเกิดความขัดข้องระหว่างการเขียน จะยกเลิกหรือย้อนกลับทั้ง transaction ไม่ให้เหลือสถานะการเขียนบางส่วน
- Consistency: transaction ที่ไม่ถูกต้องต้องไม่ทำให้ฐานข้อมูลเสียหาย
- Isolation: ต้องไม่มี race condition ในการเข้าถึงข้อมูลเดียวกันพร้อมกัน
- Durability: การเขียนที่สำเร็จต้องคงอยู่แม้หลังเหตุการณ์อย่างไฟดับ
- ไม่ใช่ transaction ของฐานข้อมูลทุกตัวจะต้องรับประกัน ACID เสมอไป และในบาง use case อาจลดระดับการรับประกันเพื่อประสิทธิภาพได้
-
ความทนทานกับ
fsync- system call
writeเขียน buffer ลงไฟล์ แต่ไม่ได้หมายความว่าจะถูกบันทึกลง non-volatile storage ทันที - kernel สามารถเก็บ buffer เป็น dirty page ใน page cache แล้วค่อย flush ลงดิสก์ภายหลัง
- อุปกรณ์ดิสก์หรือระบบ RAID ก็อาจมี write cache แยกต่างหากได้
fsyncและfdatasyncเป็น system call สำหรับ flush dirty page ไปยังที่เก็บข้อมูลถาวรfdatasyncflush raw buffer ที่ส่งผ่านwritefsyncflush ทั้งข้อมูลและ metadata ของไฟล์ เช่นmtime- หากต่อท้าย
sync -d databaseหลังdb_setจะเพิ่มความทนทานด้วยพฤติกรรมใกล้เคียงfdatasyncได้ แต่โดยทั่วไป sync ช้ากว่าการ write เอง จึงทำให้ประสิทธิภาพแย่ลง - ความสำเร็จของ
fsync()หมายถึง “write ทั้งหมดนับตั้งแต่ fsync ครั้งล่าสุดไปถึงดิสก์แล้ว” ไม่ใช่หมายถึงเฉพาะ “write หลัง fsync ครั้งล่าสุดที่สำเร็จ” - PostgreSQL เคยเจอปัญหานี้ในปี 2018 และเปลี่ยนพฤติกรรมเป็น panic เมื่อ fsync ล้มเหลว แทนที่จะ retry
- เหตุการณ์นี้รู้จักกันในชื่อ fsyncgate และมีข้อมูลที่เกี่ยวข้องเชื่อมไปยัง บทความวิจัยเรื่อง fsync failures
- MongoDB โดยค่าเริ่มต้นจะ sync ทุก 100ms จึงไม่ได้มีความทนทาน 100%
- system call
-
Isolation กับ
flock- วิธีทำ isolation แบบหลาย process ที่ง่ายที่สุดใน
bashdbคือ lock ไฟล์จัดเก็บก่อนอ่านหรือเขียน flockบน Linux ใช้ lock ไฟล์ และหากใช้ flag-sจะเป็น shared lock ทำให้ reader หลายตัวอ่านพร้อมกันได้bashdbที่ปรับปรุงแล้วใช้ exclusive lock สำหรับการเขียน และ shared lock สำหรับการอ่าน- ข้อเสียคือทุกครั้งที่เขียนจะ lock ฐานข้อมูลทั้งหมด
- การรับประกัน atomicity อย่างง่ายด้วย Bash เพียงอย่างเดียวทำได้ยาก และอาจใช้
mv -Tหรือrenameได้ แต่ยังไม่ได้ทำให้สมบูรณ์ bashdbยังไม่สามารถแก้ปัญหาการค้นหาแบบO(n)ได้
- วิธีทำ isolation แบบหลาย process ที่ง่ายที่สุดใน
บทบาทและคอขวดของ Storage engine
- Storage engine ให้ abstraction สำหรับอ่านและเขียนข้อมูลในที่เก็บข้อมูลถาวร โดยเป้าหมายหลักคือ throughput สูงและ latency ต่ำ
- ข้อจำกัดที่ใหญ่ที่สุดมาจากความแตกต่างของความเร็วของดิสก์เอง
- ในตารางตัวอย่าง latency การอ้างอิง L1 cache อยู่ที่ประมาณ
0.5ns, การอ่านแบบ 4KB random read จาก SSD อยู่ที่150,000nsและ disk seek อยู่ที่10,000,000ns - หากมองการอ้างอิง L1 cache เทียบกับจังหวะหัวใจประมาณ 0.5 วินาที การอ่านแบบ sequential 1MB จาก SSD จะเท่ากับประมาณ 12 วัน และการอ่านแบบ sequential 1MB จากดิสก์จะเท่ากับประมาณ 8 เดือน
- ในตารางตัวอย่าง latency การอ้างอิง L1 cache อยู่ที่ประมาณ
- ดังนั้นการออกแบบ storage engine จึงพัฒนาไปในทิศทางที่ลด disk I/O และ disk seek ให้มากที่สุด
- องค์ประกอบการออกแบบ storage engine ทั่วไปมีดังนี้
- โครงสร้างข้อมูล พื้นฐานสำหรับจัดเก็บรายการลงดิสก์
- transaction แบบ ACID
- cache เพื่อลดการอ่านดิสก์
- ชั้น API เช่น SQL, document, graph
- โครงสร้างข้อมูลของ storage engine แบ่งกว้าง ๆ ได้เป็นโครงสร้างที่แก้ไขได้และโครงสร้างแบบ immutable
- โครงสร้างที่แก้ไขได้สามารถเขียนทับข้อมูลที่เขียนลงไฟล์ไปแล้วในภายหลังได้
- โครงสร้างแบบ immutable จะอ่านข้อมูลที่เขียนลงไฟล์ไปแล้วเท่านั้น
B-tree แบบแก้ไขได้
- เพื่อรักษาประสิทธิภาพที่ดีแม้ข้อมูลเพิ่มขึ้น ต้องสามารถหารายการได้ในเวลาไม่เกิน logarithmic time ไม่ใช่ค้นหาแบบเชิงเส้นเหมือน
bashdb - BST ค้นหาได้แบบ
O(log n)แต่หาก node อยู่ห่างกันมากบนดิสก์ ระหว่างการค้นหาอาจเกิด disk seek จำนวนมาก - B-tree เป็นการ generalize BST โดยหนึ่ง node มีลูกได้มากกว่าสองตัว และใช้ประโยชน์จาก spatial locality
- โดยทั่วไปจะอ่าน page ขนาด 4KB หรือ 8KB จากดิสก์ แล้วเปรียบเทียบ node หลายตัวภายในนั้นแบบต่อเนื่องในหน่วยความจำและ CPU cache
- การเข้าถึงหน่วยความจำและ CPU cache เร็วกว่าดิสก์หลายลำดับขั้น จึงสำคัญที่จะใช้ byte ที่อ่านจากดิสก์มาให้มากที่สุด
- การเข้าถึงหน่วยความจำแบบต่อเนื่องอาจทรงพลังมากด้วย SIMD, instruction pipelining และ prefetching
- B+ tree เก็บค่าไว้เฉพาะที่ leaf node ส่วน node ที่เหลือเก็บเฉพาะ key ทำให้เปรียบเทียบ key ได้มากขึ้นในดิสก์ page เดียว
-
การเรียกคืนพื้นที่และ vacuum
- B-tree ต้องเรียกคืนพื้นที่ว่างที่เกิดจากการกระจายตัวของข้อมูลเพื่อทำ space optimization
- หากอัปเดตเป็นค่าขนาดใหญ่ อาจเขียนทับข้อมูลของ node ถัดไปได้ จึงต้องย้ายรายการไปตำแหน่งอื่นและเกิดช่องว่างใน page เดิม
- หากอัปเดตเป็นค่าขนาดเล็ก จะเหลือช่องว่างที่ส่วนท้าย
- การลบจะสร้างช่องว่างในตำแหน่งที่เคยมีค่าที่ถูกลบ
- กระบวนการเรียกคืนพื้นที่และเขียน page ใหม่เหล่านี้อาจเรียกว่า vacuum, compaction, page defragmentation หรือ maintenance
- โดยทั่วไปจะทำใน background เพื่อหลีกเลี่ยง latency spike ของคำขอผู้ใช้
- PostgreSQL สามารถตั้งค่า auto vacuum daemon ได้
- B-tree มักใช้เป็นโครงสร้างข้อมูลพื้นฐานของ index เช่น index เริ่มต้นของ PostgreSQL และเคยมีกรณีที่ DynamoDB ถูกเรียกแบบติดตลกว่า “distributed B-tree”
LSM tree แบบไม่เปลี่ยนรูป
- LSM tree เป็นโครงสร้างข้อมูลแบบ append-only ที่มีจุดเริ่มจากข้อเท็จจริงว่า disk seek มีต้นทุนสูง
- หากเพิ่มข้อมูลเฉพาะท้ายไฟล์ หัวอ่าน/เขียนของดิสก์แทบไม่ต้องเคลื่อนที่ไกลไปยังตำแหน่งเขียนถัดไป จึงเหมาะกับ workload ที่มีการเขียนมาก
Log Structured Merge treeหรือย่อว่า LSM tree ถูกใช้ใน storage engine ของฐานข้อมูลสมัยใหม่ เช่น RocksDB, Cassandra, ScyllaDB- การทำงานพื้นฐานมีดังนี้
- buffer การเขียนไว้ในโครงสร้างข้อมูลในหน่วยความจำที่สามารถเรียงลำดับได้
- ตัวอย่างคือ
AVL tree,Red Black tree,Skip List - เมื่อถึงขนาดที่กำหนด จะ flush ออกเป็นไฟล์ที่เรียงลำดับแล้วชื่อ
Sorted String Tableหรือ SSTable
- SSTable เก็บข้อมูลที่เรียงลำดับแล้ว จึงลด disk I/O ได้ด้วย binary search และ sparse index
- เพื่อความทนทาน งานที่เขียนลงหน่วยความจำจะถูกบันทึกลงใน Write-Ahead Log หรือ WAL
- เมื่อโปรแกรมเริ่มทำงาน จะอ่าน WAL เพื่อกู้คืนสถานะก่อนการปิดโปรแกรมหรือ crash
- การลบก็ถูก append เหมือนการเขียนทั่วไป โดยเก็บ tombstone แทนค่า
- tombstone จะถูกลบออกในกระบวนการ compaction
-
การอ่านและ compaction ของ LSM tree
- การอ่านของ LSM tree จะค้นหาโครงสร้างข้อมูลในหน่วยความจำก่อน หากไม่พบจึงไล่ค้นหา SSTable บนดิสก์จากไฟล์ใหม่สุดไปหาไฟล์เก่าสุด
- ยิ่งมีการเขียนมาก จำนวน SSTable ที่ต้องตรวจสอบก็ยิ่งเพิ่มขึ้น
- แม้แต่ละไฟล์จะเรียงลำดับแล้ว แต่การไล่ดูไฟล์เล็กจำนวนมากอาจช้ากว่าการดูไฟล์ใหญ่ไฟล์เดียว
- สูตรเปรียบเทียบคือ
log(num_files * table_size) < num_files * log(table_size) - compaction เป็นงานเบื้องหลังที่รวม SSTable ขนาดเล็กหลายไฟล์ให้เป็น SSTable ขนาดใหญ่ไฟล์เดียว และลบ tombstone ออก
- RocksDB ใช้ Leveled Compaction
- SSTable ที่เพิ่ง flush จะอยู่ที่ level 0
- เมื่อมีไฟล์สะสมใน level หนึ่งถึงจำนวนที่กำหนด หลัง compaction แล้วไฟล์ใหม่จะถูกเลื่อนไปยัง level ถัดไป
- การลบ tombstone ต้องทำอย่างระมัดระวัง
- อาจเกิดปัญหา data resurrection ที่รายการที่ถูกลบกลับมาปรากฏอีกครั้งจากการ compaction กับไฟล์ที่เก่ากว่า
- RocksDB จะคง tombstone ไว้จนกว่าจะถึงการ compaction ที่เลื่อนไปยัง level สุดท้าย
- ตัวอย่างจริงที่เขียนด้วย Rust เชื่อมไปยัง โค้ด LSM tree ของ dbeel
-
Bloom filter
- Bloom filter เป็นโครงสร้างข้อมูลเซตเชิงความน่าจะเป็นที่ใช้ตรวจสอบได้อย่างมีประสิทธิภาพว่ารายการหนึ่งไม่อยู่ในเซต
- ผลลัพธ์การค้นหามีสองแบบ
false: รายการนั้นไม่อยู่ในเซตอย่างแน่นอนtrue: รายการนั้นอาจอยู่ในเซต
- Bloom filter ใช้ผลลัพธ์จาก hash function หลายตัวแมปไปยังตำแหน่ง bit ใน bitmap แล้วตั้งค่าเป็น 1
- space complexity ถูกนำเสนอว่าเป็น
O(log n)ต่างจากO(n)ของ set ทั่วไป - สามารถปรับ “ความน่าจะเป็นที่จะมั่นใจว่าไม่มี” ได้ด้วยการจัดสรรหน่วยความจำ bitmap เพิ่มและเพิ่มจำนวน hash function และยังมี เครื่องคำนวณ ด้วย
- LSM tree เก็บ Bloom filter ไว้สำหรับแต่ละ SSTable ทำให้ข้ามการค้นหา SSTable ที่ยืนยันได้ว่าไม่มี key นั้นได้
WAL และการรับประกันทรานแซกชัน
- WAL เป็นวิธีบันทึกงานทั้งหมดของทรานแซกชันลงในไฟล์พิเศษ เพื่อให้อยู่รอดจาก crash ที่เกิดขึ้นกะทันหัน
- เมื่อ process ของฐานข้อมูลเริ่มทำงาน จะอ่านไฟล์ WAL และสร้างสถานะข้อมูลขึ้นใหม่
- ทรานแซกชันที่ไม่มี commit log จะถูกข้ามไป จึงได้ atomicity
- หากข้อมูลของคำขอเขียนถูกบันทึกและ flush ลงใน WAL ก่อนตอบกลับผู้ใช้ เมื่อเริ่มทำงานจึงต้องอ่านได้แน่นอน ทำให้ได้ durability
- WAL อาจมองได้ว่าเป็นรูปแบบหนึ่งของ event sourcing สำหรับเหตุการณ์ของทรานแซกชัน
ระดับ isolation และ concurrency control
- วิธีทำให้เกิด isolation แบ่งได้กว้าง ๆ เป็นสามแบบ
- pessimistic lock: ป้องกันการเข้าถึงข้อมูลที่กำลังถูกเขียนอยู่ในปัจจุบัน
- optimistic lock: แก้ไขสำเนาของข้อมูล แล้ว commit เฉพาะเมื่อข้อมูลต้นฉบับไม่ได้เปลี่ยนระหว่างทรานแซกชัน มิฉะนั้นให้ retry
- MVCC: ไม่เขียนทับข้อมูลเดิม แต่สร้าง version ใหม่ ทำให้ผู้ใช้แต่ละรายเห็น snapshot ณ เวลาหนึ่ง
- ไม่ใช่ทุกแอปพลิเคชันที่ต้องการ isolation แบบสมบูรณ์ หรือ serializable isolation
- ANSI/ISO SQL 92 แบ่งผลลัพธ์ที่อาจเกิดขึ้นเมื่อทรานแซกชันอื่นเปลี่ยนข้อมูลเดียวกันระหว่างทรานแซกชันออกเป็นสามประเภท
- Dirty read: อ่านการอัปเดตของทรานแซกชันอื่นที่ยังไม่ได้ commit
- Non-repeatable read: ระหว่างอ่าน row เดียวกันสองครั้ง ทรานแซกชันอื่น commit ทำให้ค่ามีการเปลี่ยนแปลง
- Phantom read: ระหว่างอ่านชุด row ที่มีเงื่อนไขเดียวกันสองครั้ง มี row ถูกเพิ่มหรือลบออก
- ระดับ isolation ของ ANSI/SQL 92 เรียงจากสูงไปต่ำมีดังนี้
- Serializable: อ่านเฉพาะข้อมูลที่ commit แล้ว และหลีกเลี่ยง phantom read รวมถึงการเขียนหลาย row แบบอิงช่วง
- Repeatable reads: อนุญาตให้เกิด phantom read
- Read committed: อนุญาตให้เกิด non-repeatable read
- Read uncommitted: อนุญาตให้เกิด dirty read
- ระดับ isolation ที่สูงมักมาพร้อมกับการยอมเสียประสิทธิภาพ
- ระดับ isolation ของ ANSI/SQL 92 ถูกวิจารณ์ว่ายังไม่สมบูรณ์
- การใช้งาน MVCC จำนวนมากให้ snapshot isolation ไม่ใช่ serializable isolation
- HyPer ถูกแนะนำให้เป็นอัลกอริทึม serializable MVCC ที่รวดเร็ว
เหตุผลที่ต้องใช้ระบบแบบกระจายและ CAP
- ระบบแบบกระจายเพิ่มความซับซ้อนอย่างมาก จึงควรหลีกเลี่ยงเมื่อโซลูชันแบบไม่กระจายก็เพียงพอ
- เหตุผลทั่วไปที่ต้องกระจายข้อมูลไปหลายเครื่องมีสองข้อ
- ความพร้อมใช้งาน (Availability): แม้เครื่องฐานข้อมูลจะ crash หรือการเชื่อมต่อกับผู้ใช้หลุด ก็ยังสามารถส่งคำขอไปยังเครื่องอื่นได้
- การขยายแนวนอน (Horizontal Scaling): แทนการทำ vertical scaling ด้วยเครื่องเดี่ยวที่ใหญ่ขึ้น ให้เครื่องหลายเครื่องที่เชื่อมต่อผ่านเครือข่ายทำงานเสมือนเป็นเครื่องเดียว
- ระบบแบบกระจายนำความซับซ้อนด้านปฏิบัติการและปัญหา network partition เข้ามา
- ทฤษฎีบท CAP ระบุว่าระบบสามารถรับประกันได้เพียงสองอย่างจากสามอย่างต่อไปนี้
- Consistency: การอ่านได้รับค่าจากการเขียนล่าสุด
- Availability: ทุกคำขอสำเร็จโดยไม่ขึ้นกับความขัดข้อง
- Partition Tolerance: ระบบยังทำงานต่อได้แม้ข้อความระหว่างโหนดสูญหายหรือล่าช้า
- ฐานข้อมูลบนเครื่องเดียวไม่มี network partition และมี consistency แต่เมื่อเครื่องขัดข้อง คำขอใหม่จะล้มเหลว จึงละเมิด availability
- ในกรณีที่เครื่องสองเครื่องมี CPU, หน่วยความจำ และดิสก์แยกกัน และเชื่อมต่อด้วยสายเคเบิล เมื่อเกิดความขัดข้องจะมีทางเลือกแตกต่างกัน
- หากยกเลิกคำขอ จะยอมเสีย availability และรักษา consistency
- หากประมวลผลคำขอต่อเฉพาะบนเครื่องที่ยังทำงานอยู่ จะยอมเสีย consistency และรักษา availability
- ระบบที่ยอมเสีย consistency แล้วค่อยปรับให้ตรงกันภายหลังเรียกว่า eventually consistent
- network partition ยังทำให้การ
JOINอย่างมีประสิทธิภาพทำได้ยาก เพราะต้องรวบรวมข้อมูลที่กระจายอยู่ในคลัสเตอร์ ฝั่ง NoSQL จึงแนะนำ denormalization เพื่อบรรเทาปัญหานี้
การทำ Replication และกรณีของ Amazon Dynamo
- Dynamo paper ฉบับดั้งเดิมของ Amazon ถูกยกเป็นกรณีที่มองว่า availability สำคัญกว่า consistency ในตะกร้าสินค้าของ amazon.com
- หากผู้ใช้เห็นสินค้าชิ้นเดียวกันสองรายการในตะกร้า ก็แค่ลบออกหนึ่งรายการได้
- เป็นการตัดสินว่าอย่างน้อยก็ดีกว่าสถานการณ์ที่ไม่สามารถซื้อสินค้าได้เลย
- การจะได้ availability นั้น แค่ให้หลายโหนดแบ่งกันถือข้อมูลยังไม่พอ แต่แต่ละรายการต้องมีสำเนาอย่างน้อยหนึ่งชุดขึ้นไป
- โหนดที่เก็บสำเนาของรายการเรียกว่า replica และกระบวนการคัดลอกเรียกว่า replication
- เมื่อเพิ่มจำนวน replica จะทำให้ availability สูงขึ้น แต่ก็ต้องใช้ทรัพยากรมากขึ้นสำหรับเก็บสำเนา
- สำเนาข้อมูลไม่จำเป็นต้องเก็บทั้งก้อน อาจแบ่งด้วย erasure coding แล้วกระจายไปยังหลายโหนดได้ และคุณลักษณะด้าน latency ที่เกี่ยวข้องเชื่อมโยงไปยังบทความเรื่อง erasure coding
Consistent Hashing และการจัดวางข้อมูล
- เมื่อมีหลายโหนด จำเป็นต้องมีวิธีทำ load balancing หรือ data partitioning เพื่อกำหนดว่า request สำหรับการจัดเก็บจะให้โหนดใดเป็นผู้จัดการ
- วิธีง่าย ๆ คือ hash ค่า primary key แล้วนำไป modulo ด้วยจำนวนโหนด
- เมื่อมีการเพิ่มหรือลบโหนด
len(nodes)จะเปลี่ยน ทำให้ key เดิมชี้ไปยังโหนดอื่น - ในกรณีนี้ต้อง migrate แทบทุกรายการ จึงมีค่าใช้จ่ายสูง
- เมื่อมีการเพิ่มหรือลบโหนด
- Consistent Hashing วางโหนดไว้บน ring แทนการวางเป็น array เพื่อลดจำนวนรายการที่ต้องย้ายเมื่อเพิ่มหรือลบโหนด
- ใช้ในฐานข้อมูลอย่าง Dynamo และ Cassandra
- ใน consistent hashing จะวาง hash ของชื่อโหนดไว้บน ring และโหนดแรกที่พบหลังจาก hash ของ key ใน request จะเป็นเจ้าของ
- การเลือก replica ทำได้โดยเดินรอบ ring ทวนเข็มนาฬิกา แล้วเก็บสำเนาไว้ที่โหนดถัดไป
- หากโหนดเจ้าของตาย replica node จะประมวลผล request แทนเพื่อคง availability
- วิธีนี้เรียกว่า Leaderless Replication และใช้ในฐานข้อมูลสไตล์ Dynamo อย่าง Cassandra
- จำนวน key ที่ต้องย้ายเมื่อเพิ่มโหนด โดยเฉลี่ยคือ
num_keys / num_nodes - virtual node คือการวางโหนดกายภาพหนึ่งตัวลงบน ring หลายครั้ง เพื่อลดโอกาสที่บางโหนดจะเป็นเจ้าของรายการมากเกินไป
- ตัวอย่างคือการเติม index เป็น suffix ต่อท้ายชื่อโหนด เช่น
"half-0","half-1"
- ตัวอย่างคือการเติม index เป็น suffix ต่อท้ายชื่อโหนด เช่น
- ยังมีวิธีอื่นในการเลือก leader node และ replica node เช่น leader election แต่จะไม่กล่าวถึงในที่นี้
Leaderless Replication และการปรับระดับความสอดคล้อง
- โครงสร้างแบบ leaderless ได้ availability สูงขึ้นแลกกับการลดทอน consistency
- หากโหนดเจ้าของอยู่ในสถานะ down ตอนมี write request ข้อมูลจะถูกเขียนไปยัง replica และหลังจากโหนดเจ้าของกลับขึ้นมาแล้ว อาจอ่านข้อมูลเก่าได้จาก read request
- หากต้องการ consistency ใน request ใด request หนึ่ง ให้ส่ง read request ไปยังหลาย replica และโหนดเจ้าของแบบขนาน แล้วให้ client เลือกข้อมูลที่ใหม่ที่สุด
- write request มักถูกส่งไปยัง replica ทั้งหมดแบบขนาน แต่จะรอ acknowledgement จากบางโหนดเท่านั้น
- หากต้องการปรับ consistency ในระดับ request ให้ตรวจสอบ
R + W > N/2 + 1N: จำนวนโหนดที่มีสำเนาข้อมูลW: จำนวนโหนดที่ต้อง acknowledgement เพื่อให้ write สำเร็จR: จำนวนโหนดที่ต้องตอบกลับเพื่อให้ read สำเร็จ
- request ที่ต้องการโหนดส่วนใหญ่ โดยที่
WหรือRเป็นN/2 + 1เรียกว่า quorum -
การแก้ไข conflict
- กระบวนการเลือก write ที่ใหม่ที่สุดคือ Conflict Resolution
- การเปรียบเทียบ timestamp อย่างเดียวเชื่อถือได้ยากในระบบกระจาย
- แต่ละเครื่องมี hardware clock ของตัวเอง และ clock ไม่ได้แม่นยำสมบูรณ์ จึงเกิด drift ได้
- NTP รับเวลาจากแหล่งเวลาที่แม่นยำกว่า แต่ตัว request เองต้องผ่านเครือข่าย จึงไม่สามารถรู้เวลาที่ใช้จนถึงการตอบกลับได้อย่างแม่นยำ
- Cassandra ใช้ timestamp และเอกสารที่เกี่ยวข้องเชื่อมโยงไปยัง Cassandra data versioning
- Google Spanner ทำให้รับประกัน consistency ตาม clock ได้ด้วยฮาร์ดแวร์เวลาความแม่นยำสูงแบบพิเศษและ API ที่เปิดเผยช่วงความไม่แน่นอนของ timestamp โดยมีงานวิจัยที่เกี่ยวข้องคือ Spanner paper
- ระบบอย่าง Dynamo ลด conflict บางส่วนด้วย Version Vectors
- เพิ่มคู่
(node, counter)ให้แต่ละ version ของรายการ เพื่อค้นหาความสัมพันธ์เชิงเหตุผลระหว่าง version - สามารถหา version ที่ใหม่กว่าอย่างแน่นอน แล้วลบค่าบางส่วนที่เก่าออกได้
- มีข้อมูลเพิ่มเติมเชื่อมโยงไปยัง Dotted Version Vectors
- อาจคืนค่า conflict ทั้งหมดให้แอปพลิเคชันเหมือน Riak KV แล้วให้แอปพลิเคชันแก้ไขตามความรู้ที่มีต่อข้อมูลก็ได้
- เทคนิคต่าง ๆ ที่ลด conflict ในระบบ eventually consistent มักถูกรวมไว้ภายใต้คำว่า Anti Entropy
เทคนิค Anti Entropy
-
Read Repair
- หลังจาก client เลือกค่าล่าสุดจากผล read ของหลายโหนดแล้ว จะส่งค่านั้นกลับไปยังโหนดที่ยังไม่ได้เก็บค่านั้นเพื่อ repair
-
Hinted Handoff
- หาก write request ไปไม่ถึงโหนดเป้าหมาย จะเก็บไว้ที่โหนดอื่นเป็น hint
- เมื่อโหนดเป้าหมายกลับมา available อีกครั้ง จะส่ง hint ที่เก็บไว้ให้
- ใน quorum write วิธีนี้ยังเรียกว่า
Sloppy Quorumและช่วยเพิ่ม availability ของ quorum request
-
Merkle Trees
- read repair แก้ไขเฉพาะข้อมูลที่ถูก query ดังนั้นข้อมูลจำนวนมากอาจยังอยู่ในสภาพไม่ตรงกันเป็นเวลานาน
- การซิงก์ระหว่างโหนดเพื่อหาความแตกต่างทั้งหมดมีค่าใช้จ่าย
O(n)เมื่อมีข้อมูลมาก - Merkle tree เป็นโครงสร้างแบบลำดับชั้นที่เก็บ hash ของช่วงข้อมูลไว้ที่ leaf และ parent เก็บ hash ที่ได้จากการรวม hash ของ child
- หาก root hash เหมือนกัน ข้อมูลของสองโหนดก็เหมือนกัน หากต่างกัน จะเปรียบเทียบ hash ระดับล่างแบบ recursive เพื่อหาข้อมูลที่ไม่ตรงกัน จึงทำให้การซิงก์เร็วขึ้นเป็น
O(log n)
-
Gossip Dissemination
- เป็นวิธีกระจาย event ไปทั่วทั้งคลัสเตอร์อย่างเรียบง่ายและเชื่อถือได้
- โหนดจะส่ง message ไปยังโหนดสุ่มจำนวนที่กำหนด หรือ fanout และโหนดที่ได้รับจะส่งต่อไปยังโหนดสุ่มอีก
Nตัว - เมื่อเห็น gossip message เดิมครบจำนวนครั้งที่กำหนดแล้ว จะไม่ broadcast ต่ออีก
- มีsimulator ที่ช่วยให้เห็นการลู่เข้าของข้อมูลได้
- gossip message มักส่งผ่าน UDP
หัวข้อที่สามารถลงลึกเพิ่มเติมได้
- ฐานข้อมูลยังมีหัวข้ออีกมากนอกเหนือจากสิ่งที่กล่าวถึงที่นี่
- เมื่อเลือกหรือพัฒนาฐานข้อมูล ควรดูควบคู่กันว่า storage engine, ACID, isolation level, distributed replication และวิธีแก้ไข conflict สอดคล้องกับความต้องการจริงอย่างไร
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
มีบั๊กในเมธอด
compact: tombstone ควรถูกข้ามเฉพาะตอน compact ระดับสุดท้าย หรือก็คือระดับที่ใหญ่ที่สุดเท่านั้น และไม่ควรถูกลบออกระหว่างทุกระดับไม่เช่นนั้น tombstone ในระดับบนจะหายไประหว่างกระบวนการ compact ทำให้เอนทรีที่อยู่ในระดับล่างโผล่กลับขึ้นมาอีก
ในฐานข้อมูลแบบ LSM การที่เรคอร์ดลบ/tombstone อยู่ค้างไว้นานเป็นหนึ่งในลักษณะเฉพาะ และฐานข้อมูลบางตัวอย่าง RocksDB ก็ใส่ optimization เพื่อหลีกเลี่ยงสิ่งนี้
รู้จักฟีเจอร์ฝั่ง range deletion อยู่ แต่จำไม่ค่อยได้ว่าเคยอ่านเรื่องการลบคีย์เดี่ยวมากนัก
หลายคนเรียนรู้ฐานข้อมูลผ่านการเรียน SQL แต่ขอแนะนำให้เรียนแบบคอร์สลักษณะนี้และทำความเข้าใจ B-tree
ข้อดีข้อเสียของ RDBMS ส่วนใหญ่จะเข้าใจได้เมื่อรู้จัก B-tree และผลของมันต่อการแทรกคีย์ การค้นหา และการเรียงลำดับ
หลายคนพยายามทำให้ฐานข้อมูลเร็วขึ้นด้วยการเพิ่มดัชนี แต่สุดท้ายก็เป็นเพียงการวางต้นไม้อีกต้นทับบนต้นไม้เดิม ซึ่งเท่ากับบดบังปัญหาพื้นฐาน
บางปัญหาเหมาะกับ B-tree แต่หลายปัญหาไม่เหมาะ
SQL เป็นเพียงอินเทอร์เฟซสำหรับ query ไปยังระบบ B-tree ระยะไกลเท่านั้น
B-tree ไม่ใช่กลยุทธ์ indexing เพียงอย่างเดียว และเป็นที่รู้กันดีว่า index เป็นเครื่องมือที่แลกประสิทธิภาพการเขียนเพื่อเพิ่มประสิทธิภาพการอ่าน
เพราะโดยทั่วไปฐานข้อมูลประมวลผลการอ่านมากกว่าการเขียนมาก
อยากรู้ว่า “การวางต้นไม้อีกต้นทับบนต้นไม้เดิม” นั้นกำลังบดบังปัญหาอะไรกันแน่ และจะไปรับมืออย่างไรโดยไม่แตะ index
สำหรับตารางขนาดพอสมควร index แทบจะเป็นสิ่งจำเป็น
ควรเรียนรู้เรื่อง B-tree และ hash index, ชั้น I/O, process model และสิ่งทำนองนี้
ทุกวันนี้กลยุทธ์ทั่วไปของฐานข้อมูลแบบ column-oriented ก็คุ้มค่าที่จะเรียนด้วย เช่น late tuple materialization, lazy execution, linear scan กับ binary search, instruction pipelining เป็นต้น
เมื่อคุ้นเคยกับสิ่งเหล่านี้แล้ว จะเห็นว่าในงานจริงบางครั้งแค่ไฟล์แบนธรรมดา หรือฐานข้อมูล embedded อย่าง RocksDB ก็เพียงพอ ไม่จำเป็นต้องใช้ DBMS
แน่นอนว่าอาจมี covering index ด้วย
สำหรับคำแนะนำที่ว่า “หากโซลูชันที่ไม่กระจายศูนย์เพียงพอ ก็จงหลีกเลี่ยงระบบกระจายศูนย์” ผมอยากพูดในทางกลับกัน
ระบบปฏิบัติการจริงที่ไม่ใช่เรื่องเล็กน้อยทุกระบบล้วนเป็น ระบบกระจายศูนย์
อย่างน้อยถ้าฐานข้อมูลเป็น replica set ก็ถือว่าเป็นระบบกระจายศูนย์แล้ว ดังนั้นการไม่เรียนรู้ระบบกระจายศูนย์คือการยอมรับความเสี่ยง
https://jepsen.io/ และ https://raft.github.io/ น่าดู
แต่นั่นไม่ได้หมายความว่าสามารถนำสิ่งนี้ไปใช้ได้ทุกที่ และถ้าทำแบบนั้น ความซับซ้อน จะเพิ่มขึ้นมากเกินจำเป็น
พูดแบบนี้ยังหักล้างคำแนะนำให้หลีกเลี่ยงความซับซ้อนที่ไม่จำเป็นไม่ได้ ประเด็นสำคัญไม่ใช่ว่าในเชิงเทคนิคมันกระจายศูนย์หรือไม่ แต่คือจำเป็นจริงหรือเปล่า
การเรียนรู้ระบบกระจายศูนย์ กับการนำมาใช้นั้นต่างกัน
สิ่งสำคัญคือหลังจากเรียนรู้แล้ว ยังมีความยับยั้งชั่งใจที่จะใช้เฉพาะในที่ที่เหมาะสมได้หรือไม่
ทุกวันนี้มีหลายกรณีที่ทุ่มความพยายามมากเพื่อย้ายระบบที่เรียบง่ายและทำงานได้ดีไปสู่โมเดลกระจายศูนย์ที่แข็งแรงกว่า ราวกับว่าต้นทุนแทบไม่มี
แต่เมื่อดูปัญหาที่ต้องการแก้และขนาดของระบบแล้ว ก็ชัดเจนว่าหลายกรณีแค่ Postgres instance เดียวกับ monolith ก็เพียงพอ
คำแนะนำในต้นฉบับน่าจะหมายถึงแบบนั้น
อย่างน้อยก็ไม่จำเป็นต้องเป็นเช่นนั้นเสมอไป
ผมยังจะแนะนำให้เลือกโซลูชันที่เรียบง่ายอยู่ดี
ระบบจำนวนมากแม้แต่กับ “สตอเรจที่เล็กน้อยและเรียบง่าย” ก็ยังจัดเก็บสถานะถาวร สำรองข้อมูล และกู้คืนได้ไม่ถูกต้อง
การพยายามกู้คืนสถานะของสตอเรจกระจายศูนย์ในสถานการณ์ disaster recovery ยิ่งยากกว่า
ควรมีโซลูชันแบ็กอัพที่ใช้งานได้จริงก่อน แล้วค่อยเลือกโซลูชันกระจายศูนย์ก็ได้
การตั้งค่า master ที่มี read-only replica ก็ไม่เหมือนกับ “distributed” ตามที่คนทั่วไปพูดกัน เพราะการเขียนไม่ได้ถูกกระจาย
ในงานจริง distributed มักหมายถึงข้อมูลถูก sharding และเป็นส่วนที่อยากหลีกเลี่ยงอย่างยิ่งถ้าไม่ได้จำเป็นจริง ๆ
อ่านสนุก เพราะไล่ภาพรวมแนวคิดหลายอย่างที่เกี่ยวข้องกับการสร้างฐานข้อมูลได้ดี
ครอบคลุมตั้งแต่ SIMD เพื่อรีดประสิทธิภาพจากเครื่องเดียว ไปจนถึงอัลกอริทึม consensus
ในเมื่อพูดถึงฐานข้อมูล ความน่าเชื่อถือ และระบบกระจายศูนย์แล้ว ก็น่าอ่านเรื่อง formal methods ที่นำไปใช้กับสถานการณ์เหล่านี้และการ implement ภายในฐานข้อมูลได้ด้วย
มีบทความวิจัยน่าสนใจที่ทีม S3 ใช้ TLA+ ทำโมเดล
[0] Use of Formal Methods at Amazon Web Services
https://lamport.azurewebsites.net/tla/formal-methods-amazon....
[1] How Amazon Web Services uses formal methods
https://www.amazon.science/publications/how-amazon-web-servi...
consistency มีทั้ง database consistency และ application consistency
ตัวอย่างเช่น ในระดับตารางเดียวอาจทำ atomicity, isolation, durability ได้ แต่การเขียนข้ามหลายตารางอาจล้มเหลวได้
เมื่อเริ่มจัดการ transaction ที่อัปเดตหลายตารางพร้อมกัน consistency ก็จะสำคัญขึ้น
ทุกตารางต้องถูกอัปเดตพร้อมกัน หรือไม่ก็ต้องไม่มีอะไรถูกอัปเดตเลย
ดีไซน์ที่มี document API แบบ MongoDB, leaderless replication แบบ Cassandra และสถาปัตยกรรม thread-per-core แบบ ScyllaDB นั้นเจ๋งมาก
แถมทั้งหมดเขียนด้วย Rust
ขั้นที่บอกว่า “หนังสือกระตุ้นความอยากรู้อยากเห็นจนลงมือสร้างฐานข้อมูลเล็ก ๆ เอง” ดูเหมือนเป็นสิ่งที่นักพัฒนาหลายคนผ่านกันมาสักครั้ง
คงไม่คิดจะห้ามเป็นพิเศษ ลองทำเองแล้วจะได้เรียนรู้อย่างมากว่าอะไรใช้ไม่ได้จริง
ถ้าหาเวลาได้ ก็เป็นบทเรียนที่มีคุณค่าอย่างยิ่ง
การเคยสร้างฐานข้อมูลเองเป็นสิ่งที่ทำให้ผมเคารพโซลูชันที่มีอยู่มากที่สุด
ส่วนที่ยากไม่ใช่การเขียนและอ่านไบต์ลงดิสก์ให้เร็ว
สิ่งที่ยากจริง ๆ คือการทำให้มันทำงานได้อย่างเสถียรเป็นเวลาหลายปี พร้อมรองรับกรณีการใช้งานที่เราไม่เคยนึกถึงมาก่อน
ถ้าออกแบบ DBMS เฉพาะโดเมน โดยตั้งสมมติฐานว่ากรณีการใช้งานนอกโดเมนถูกห้ามและละเลยได้ จะได้ประสิทธิภาพแบบไหนบ้าง?
เช่น ตอนนี้เราใช้ฐานข้อมูลอเนกประสงค์แม้กับชุดข้อมูลที่โดยแก่นแล้วเป็นแบบเพิ่มอย่างเดียว
แล้วถ้าเป็นฐานข้อมูลที่ไม่มีแนวคิดเรื่องการอัปเดตหรือลบแถวเดิมเลย มีแค่การแทรกกับการลบทั้งตาราง/ชุดข้อมูลล่ะ?
ฐานข้อมูลแบบนั้นจะไม่ต้องใช้ทรานแซกชัน MVCC ได้ไหม? แต่ละตารางเป็น write-ahead log อยู่แล้ว จึงเลี่ยง write-ahead log แยกต่างหากได้หรือเปล่า? จะจัดเก็บได้มีประสิทธิภาพขึ้นไหม? จะทำให้อินเด็กซ์มี atomicity ระดับ chunk แทนระดับทั้งตารางเพื่อลดการล็อกได้ไหม?
atomicity ในเวอร์ชัน Bash น่าจะทำได้ “ง่าย ๆ” โดยคัดลอกไฟล์ไปเป็นไฟล์ชั่วคราว แก้ไข แล้วใช้
sync; mv; syncไม่ใช่หรือ?grepแบบย้อนกลับเพื่อหลีกเลี่ยงรายการซ้ำได้ด้วยไหน ๆ ก็คัดลอกแล้วจะรับประกันการเรียงลำดับไปด้วยก็ได้ แต่การทำแบบนั้นด้วยแค่ “bash” กับยูทิลิตีพื้นฐานดูไม่ค่อยสมเหตุสมผล
สำหรับงานแบบนั้นมี CDB ของ DJB เช่น cdbget, cdbmake ฯลฯ:
https://cr.yp.to/cdb.html
เป็นบทความที่ยอดเยี่ยม
หนังสือ Database Internals ดูน่าสนใจ มีหนังสือคล้าย ๆ กันที่เจาะลึกการทำงานภายในอีกไหม?
https://www.youtube.com/c/cmudatabasegroup
มีทั้งคลาสเบื้องต้นและขั้นสูงออนไลน์ รวมถึงพรีเซนเทชันและบรรยายเกี่ยวกับผลิตภัณฑ์ในอุตสาหกรรมด้วย
มีประโยชน์มาก
สำหรับแหล่งข้อมูลที่เป็นมุมมองวิทยาการคอมพิวเตอร์เชิงทฤษฎีในระดับสูงกว่า และเน้นการนำไปใช้จริงเชิงกายภาพน้อยกว่า หนังสือ “Alice” หรือ “Foundations of Databases” นั้นยอดเยี่ยม
เนื้อหาแน่นและเป็นคณิตศาสตร์มาก แต่ครอบคลุม relational algebra กับ Datalog รวมถึงการแปลง Datalog เป็น relational algebra
ตอนนี้หนังสือเล่มกระดาษหายากแล้ว หนังสือมือสองที่ซื้อมาเย็บเล่มพังและหน้าหลุด แต่ทั้งเล่มมีออนไลน์อยู่ที่: http://webdam.inria.fr/Alice/
https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf
แต่ Database Internals ทันสมัยกว่า
ชอบที่บทความไม่ได้ทำให้ “ฐานข้อมูล” ดูลึกลับ แต่เริ่มด้วยการแสดง implementation จิ๋ว ๆ แบบ บรรทัดเดียวใน Bash
เป็นบทนำที่ยอดเยี่ยม