หนึ่งในความน่าเบื่อของชีวิตคือการที่ทุกคนตั้งชื่อสิ่งต่างๆ ผิดเพี้ยนไปเล็กน้อย และนั่นทำให้ทุกอย่างในโลกเข้าใจยากขึ้นกว่าที่ควรจะเป็นเล็กน้อย คอมพิวเตอร์ไม่ได้มีหน้าที่หลักในการคำนวณทางคณิตศาสตร์ [...] หน้าที่หลักของมันคือระบบจัดเก็บแฟ้ม

Richard Feynman , Idiosyncratic Thinking seminar (1985)

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

ใน บทที่ 3 เราได้พูดถึง data models และ query languages นั่นคือรูปแบบที่คุณใช้ให้ข้อมูลแก่ฐานข้อมูล และ interface ที่คุณใช้ในการขอข้อมูลคืนในภายหลัง ในบทนี้เราจะพูดถึงเรื่องเดียวกันจากมุมมองของฐานข้อมูล: ว่าฐานข้อมูลจะจัดเก็บข้อมูลที่คุณให้ไปได้อย่างไร และมันจะค้นหาข้อมูลนั้นอีกครั้งได้อย่างไรเมื่อคุณขอ

ทำไมคุณในฐานะนักพัฒนาแอปพลิเคชันถึงต้องสนใจว่าฐานข้อมูลจัดการเรื่อง storage และ retrieval ภายในอย่างไร? คุณคงไม่ได้จะ implement storage engine ของตัวเองตั้งแต่ต้น แต่คุณ จำเป็น ต้องเลือก storage engine ที่เหมาะสมกับแอปพลิเคชันของคุณ จากที่มีอยู่มากมาย การจะ configure storage engine ให้ทำงานได้ดีกับ workload ของคุณ คุณต้องมีความเข้าใจคร่าวๆ ว่า storage engine ทำงานเบื้องหลังอย่างไร

โดยเฉพาะอย่างยิ่ง มีความแตกต่างอย่างมากระหว่าง storage engine ที่ถูกปรับให้เหมาะกับ transactional workloads (OLTP) กับ storage engine ที่ถูกปรับให้เหมาะกับ analytics (เราได้แนะนำความแตกต่างนี้ไว้ใน "Operational Versus Analytical Systems" ) บทนี้เริ่มต้นด้วยการสำรวจ storage engine สองตระกูลสำหรับ OLTP: log-structured storage engines ที่เขียน data files แบบ immutable และ storage engine อย่าง B-trees ที่อัปเดตข้อมูลในที่เดิม โครงสร้างเหล่านี้ใช้สำหรับทั้ง key-value storage และ secondary indexes

ใน "Data Storage for Analytics" เราจะพูดถึง storage engine ตระกูลหนึ่งที่ถูกปรับให้เหมาะกับ analytics และใน "Multidimensional and Full-Text Indexes" เราจะดู indexes สำหรับ query ที่ซับซ้อนมากขึ้น เช่น การค้นหาข้อความ

Storage and Indexing for OLTP (การจัดเก็บและการทำ Index สำหรับ OLTP)

ลองนึกถึงฐานข้อมูลที่ง่ายที่สุดในโลก ซึ่ง implement ด้วย bash functions สองฟังก์ชัน:

#!/bin/bash

db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

ฟังก์ชันทั้งสองนี้ implement key-value store คุณสามารถเรียก db_set key value ซึ่งจะเก็บ key และ value ไว้ใน database key และ value สามารถเป็นอะไรก็ได้ (เกือบทุกอย่าง) เช่น value อาจเป็น JSON document จากนั้นคุณสามารถเรียก db_get key ซึ่งจะค้นหาค่าล่าสุดที่เชื่อมโยงกับ key นั้นและส่งกลับมา

และมันก็ใช้งานได้:

$ db_set 12 '{"name":"London","attractions":["Big Ben","London Eye"]}'

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

รูปแบบการจัดเก็บนั้นง่ายมาก: ไฟล์ข้อความที่แต่ละบรรทัดประกอบด้วย key-value pair คั่นด้วย เครื่องหมาย comma (ประมาณว่าเหมือนไฟล์ CSV แต่ไม่สนใจเรื่อง escaping) ทุกครั้งที่เรียก db_set จะต่อท้ายข้อมูลที่ปลายไฟล์ ถ้าคุณอัปเดต key หลายครั้ง version เก่าของ value จะไม่ถูกเขียนทับ—คุณต้องดูค่า key ที่เกิดขึ้นล่าสุดในไฟล์เพื่อหา value ล่าสุด (ด้วยเหตุนี้จึงมี tail -n 1 ใน db_get ):

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'

$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}

$ cat database
12,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

ฟังก์ชัน db_set มีประสิทธิภาพที่ดีพอสมควรสำหรับสิ่งที่เรียบง่ายขนาดนี้ เพราะการต่อท้ายไฟล์โดยทั่วไปแล้วมีประสิทธิภาพมาก เช่นเดียวกับที่ db_set ทำ ฐานข้อมูลจำนวนมากใช้ log ภายใน ซึ่งเป็นไฟล์ข้อมูลแบบ append-only ฐานข้อมูลจริงมีปัญหาที่ต้องจัดการมากกว่านี้ (เช่น การจัดการ concurrent writes การคืนพื้นที่ดิสก์เพื่อให้ log ไม่โต และการจัดการกับ records ที่เขียนไม่สมบูรณ์เมื่อกู้คืนจาก crash) แต่หลักการพื้นฐานก็เหมือนกัน Logs มีประโยชน์อย่างเหลือเชื่อ และเราจะพบเจอมันหลายครั้งในหนังสือเล่มนี้

Note

คำว่า log มักใช้หมายถึง application logs ที่แอปพลิเคชันแสดงข้อความอธิบายสิ่งที่กำลังเกิดขึ้น ในหนังสือเล่มนี้ log ถูกใช้ในความหมายที่กว้างกว่า: ลำดับของ records แบบ append-only บนดิสก์ ไม่จำเป็นต้องอ่านโดยมนุษย์ได้; อาจเป็น binary และมีไว้สำหรับใช้งานภายในของระบบฐานข้อมูลเท่านั้น

ในทางกลับกัน ฟังก์ชัน db_get มีประสิทธิภาพที่แย่มากถ้าคุณมี records จำนวนมากใน database ทุกครั้งที่คุณต้องการค้นหา key, db_get ต้อง scan ไฟล์ database ทั้งหมดตั้งแต่ต้นจนจบ เพื่อหาค่า key ที่ต้องการ ในเชิง algorithm ต้นทุนของการค้นหาคือ O ( n ): ถ้าคุณเพิ่มจำนวน records n ใน database เป็นสองเท่า การค้นหาจะใช้เวลานานเป็นสองเท่า ซึ่งไม่ดีเลย

เพื่อค้นหา value สำหรับ key ที่ต้องการใน database อย่างมีประสิทธิภาพ เราจำเป็นต้องมี data structure ที่แตกต่างออกไป: index ในบทนี้เราจะดูโครงสร้าง index หลากหลายรูปแบบและเปรียบเทียบกัน แนวคิดทั่วไปคือการจัดโครงสร้างข้อมูลในลักษณะเฉพาะ (เช่น เรียงลำดับตาม key) ที่ทำให้ค้นหาข้อมูลที่ต้องการได้เร็วขึ้น ถ้าคุณต้องการค้นหาข้อมูลเดียวกันในหลายวิธี คุณอาจต้องมีหลาย indexes ในส่วนต่างๆ ของข้อมูล

Index เป็น โครงสร้างเพิ่มเติม ที่ถูกสร้างขึ้นจากข้อมูลหลัก ฐานข้อมูลจำนวนมากอนุญาตให้คุณเพิ่มและลบ indexes ได้ และสิ่งนี้ไม่มีผลต่อเนื้อหาของ database มีผลแค่ประสิทธิภาพของ queries การบำรุงรักษาโครงสร้างเพิ่มเติมทำให้เกิด overhead โดยเฉพาะใน writes สำหรับ writes เป็นการยากที่จะเอาชนะประสิทธิภาพของการต่อท้ายไฟล์ เพราะนั่นเป็นการเขียนที่ง่ายที่สุดเท่าที่จะเป็นไปได้ index ทุกชนิดมักจะทำให้ writes ช้าลง เพราะ index ก็ต้องถูกอัปเดตทุกครั้งที่มีการเขียนข้อมูล

นี่คือ trade-off ที่สำคัญในระบบจัดเก็บข้อมูล: indexes ที่เลือกมาอย่างดีจะทำให้ read queries เร็วขึ้น แต่ทุก index กินพื้นที่ดิสก์เพิ่มเติมและทำให้ writes ช้าลง ซึ่งในบางครั้งก็ช้าลงอย่างมาก [ 1 ] ด้วยเหตุนี้ ฐานข้อมูลจึงไม่ทำ index ทุกอย่างเป็นค่าเริ่มต้น แต่ต้องการให้คุณ—คนที่เขียนแอปพลิเคชันหรือบริหารฐานข้อมูล—เลือก indexes ด้วยตนเอง โดยใช้ความรู้เกี่ยวกับรูปแบบ query ทั่วไปของแอปพลิเคชัน จากนั้นคุณสามารถเลือก indexes ที่ให้ประโยชน์สูงสุดแก่แอปพลิเคชัน โดยไม่เพิ่ม overhead ในการเขียนโดยไม่จำเป็น

Log-Structured Storage (การจัดเก็บแบบ Log-Structured)

เริ่มต้น สมมติว่าคุณต้องการเก็บข้อมูลในไฟล์แบบ append-only ที่เขียนโดย db_set ต่อไป และคุณแค่ต้องการเร่งความเร็วในการอ่าน วิธีหนึ่งที่ทำได้คือการเก็บ hash map ไว้ในหน่วยความจำ โดย map ทุก key ไปยัง byte offset ที่สามารถหา value ล่าสุดของ key นั้นได้ ดังที่แสดงใน Figure 4-1 .

Diagram showing how an in-memory hash map indexes keys to byte offsets in a log-structured file storing key-value pairs.

Figure 4-1. Storing a log of key-value pairs in a CSV-like format, indexed with an in-memory hash map (การจัดเก็บ key-value pairs ในรูปแบบ log คล้าย CSV โดยทำ index ด้วย in-memory hash map)

เมื่อใดก็ตามที่คุณต่อท้าย key-value pair ใหม่ลงในไฟล์ คุณก็อัปเดต hash map เพื่อสะท้อน offset ของข้อมูลที่เพิ่งเขียนไป เมื่อคุณต้องการค้นหา value คุณใช้ hash map เพื่อค้นหา offset ใน log file จากนั้นก็ seek ไปยังตำแหน่งนั้นและอ่าน value ถ้าส่วนนั้นของ data file อยู่ใน filesystem cache อยู่แล้ว การอ่านก็ไม่ต้องใช้ disk I/O เลย

แนวทางนี้เร็วกว่ามาก แต่ก็ยังมีปัญหาหลายประการ:

  • คุณไม่มีการคืนพื้นที่ดิสก์ที่ถูกครอบครองโดย log entries เก่าที่ถูกเขียนทับ ถ้าคุณเขียนข้อมูลลง database เรื่อยๆ คุณอาจจะเต็มดิสก์

  • hash map ไม่ได้ถูก persist ดังนั้นคุณต้องสร้างมันขึ้นมาใหม่เมื่อ restart database—เช่น โดยการ scan ไฟล์ log ทั้งหมดเพื่อหา byte offset ล่าสุดของแต่ละ key ซึ่งทำให้ restart ช้าถ้าคุณมีข้อมูลจำนวนมาก

  • hash table ต้อง fit ใน memory โดยหลักการแล้ว คุณสามารถรักษา hash table ไว้บน disk ได้ แต่น่าเสียดายที่การทำให้ on-disk hash map มีประสิทธิภาพทำได้ยาก มันต้องใช้ random access I/O จำนวนมาก การขยายขนาดเมื่อเต็มก็แพง และ hash collisions ก็ต้องใช้ logic ที่ยุ่งยาก [ 2 ]

  • Range queries ไม่มีประสิทธิภาพ ตัวอย่างเช่น คุณไม่สามารถ scan ทุก keys ตั้งแต่ 10000 ถึง 19999 ได้ง่ายๆ—คุณต้องค้นหาแต่ละ key ใน hash map ทีละตัว

The SSTable file format (รูปแบบไฟล์ SSTable)

ในทางปฏิบัติ hash tables ไม่ได้ถูกใช้บ่อยนักสำหรับ database indexes แต่การเก็บข้อมูลในโครงสร้างที่ เรียงลำดับตาม key นั้นพบได้ทั่วไป [ 3 ] ตัวอย่างหนึ่งของโครงสร้างดังกล่าวคือ Sorted Strings Table หรือเรียกสั้นๆ ว่า SSTable ดังที่แสดงใน Figure 4-2 รูปแบบไฟล์นี้ก็จัดเก็บ key-value pairs เช่นกัน แต่รับประกันว่ามันเรียงลำดับตาม key และแต่ละ key ปรากฏเพียงครั้งเดียวในไฟล์

Diagram of an SSTable highlighting a sparse index, which maps specific keys to their byte offsets, enabling efficient block access to sorted key-value pairs.

Figure 4-2. An SSTable with a sparse index, allowing queries to jump to the right block (SSTable ที่มี sparse index ซึ่งทำให้ queries สามารถข้ามไปยัง block ที่ถูกต้องได้)

ตอนนี้คุณไม่จำเป็นต้องเก็บ keys ทั้งหมดไว้ใน memory คุณสามารถจัดกลุ่ม key-value pairs ภายใน SSTable เป็น blocks ขนาดไม่กี่กิโลไบต์ แล้วเก็บ key แรกของแต่ละ block ไว้ใน index index แบบนี้ที่เก็บแค่บาง keys เรียกว่า sparse index นี้ถูกเก็บไว้ในส่วนแยกต่างหากของ SSTable—เช่น ใช้ immutable B-tree, trie, หรือ data structure อื่นๆ ที่ช่วยให้ queries สามารถค้นหา key ที่ต้องการได้อย่างรวดเร็ว [ 4 ]

ใน Figure 4-2 ตัวอย่างเช่น key แรกของ block หนึ่งคือ handbag และ key แรกของ block ถัดไปคือ handsome สมมติว่าคุณกำลังค้นหา key handiwork ซึ่งไม่ปรากฏใน sparse index เนื่องจากการเรียงลำดับ คุณจึงรู้ว่า handiwork ต้องอยู่ระหว่าง handbag และ handsome ซึ่งหมายความว่าคุณสามารถ seek ไปยัง offset ของ handbag และ scan ไฟล์จากตรงนั้นจนกว่าจะเจอ handiwork (หรือไม่เจอ ถ้า key ไม่มีอยู่ในไฟล์) block ขนาดไม่กี่กิโลไบต์สามารถ scan ได้อย่างรวดเร็ว

แต่ละ block ของ records สามารถถูกบีบอัดได้ (แสดงด้วยพื้นที่แรเงาใน Figure 4-2 ) นอกจากจะประหยัดพื้นที่ดิสก์แล้ว การบีบอัดยังลดการใช้ bandwidth I/O โดยแลกกับการใช้ CPU เวลาเพิ่มขึ้นเล็กน้อย

Constructing and merging SSTables (การสร้างและรวม SSTables)

รูปแบบไฟล์ SSTable นั้นดีกว่าสำหรับการอ่านเมื่อเทียบกับ append-only log แต่มันทำให้ writes ยากขึ้น เราไม่สามารถแค่ต่อท้ายที่ปลายไฟล์ได้ เพราะไฟล์จะไม่เรียงลำดับอีกต่อไป (เว้นแต่ keys จะถูกเขียนตามลำดับจากน้อยไปมากโดยบังเอิญ) ถ้าเราต้องเขียน SSTable ใหม่ทั้งหมดทุกครั้งที่มี key ถูกแทรก somewhere ตรงกลาง writes ก็จะแพงเกินไป

เราสามารถแก้ปัญหานี้ได้ด้วยแนวทาง log-structured ซึ่งเป็นลูกผสมระหว่าง append-only log และ sorted file:

  1. เมื่อมี write เข้ามา ให้เพิ่มมันลงใน in-memory ordered map data structure เช่น red–black tree, skip list [ 5 ], หรือ trie [ 6 ] ด้วย data structures เหล่านี้ คุณสามารถแทรก keys ในลำดับใดก็ได้ ค้นหามันอย่างมีประสิทธิภาพ และอ่านกลับมาในลำดับที่เรียงแล้ว data structure ในหน่วยความจำนี้เรียกว่า memtable .

  2. เมื่อ memtable ใหญ่กว่าเกณฑ์ที่กำหนด—โดยทั่วไปไม่กี่เมกะไบต์—ให้เขียนมันลงดิสก์ในลำดับที่เรียงแล้วเป็นไฟล์ SSTable เราเรียกไฟล์ SSTable ใหม่นี้ว่า segment ล่าสุดของ database และมันถูกเก็บเป็นไฟล์แยกต่างหากพร้อมกับ segments ที่เก่ากว่า แต่ละ segment มี index แยกต่างหากของเนื้อหาของตัวเอง ในขณะที่ segment ใหม่กำลังถูกเขียนลงดิสก์ database สามารถ continue เขียนไปยัง memtable instance ใหม่ได้ และหน่วยความจำของ memtable เก่าจะถูกปล่อยเมื่อการเขียน SSTable เสร็จสมบูรณ์

  3. ในการอ่าน value สำหรับ key หนึ่ง ให้ลองค้นหา key ใน memtable และ on-disk segment ล่าสุดก่อน ถ้าไม่เจอ ให้ค้นหาต่อใน segment ที่เก่ากว่าถัดไปจนกว่าจะเจอ key หรือถึง segment ที่เก่าที่สุด ถ้า key ไม่ปรากฏใน segment ใดเลย แสดงว่า key นั้นไม่มีอยู่ใน database

  4. เป็นระยะๆ ให้รันกระบวนการ merging และ compaction ใน background เพื่อรวม segment files และ discard ค่าที่ถูกเขียนทับหรือลบไป

การรวม segments ทำงานคล้ายกับ algorithm mergesort [ 5 ] กระบวนการนี้แสดงใน Figure 4-3 : เริ่มอ่านไฟล์ input ควบคู่กันไป ดู key แรกในแต่ละไฟล์ คัดลอก key ที่น้อยที่สุด (ตาม sort order) ไปยัง output file แล้วทำซ้ำ ถ้า key เดียวกันปรากฏในหลายไฟล์ input ให้เก็บเฉพาะ value ที่ใหม่กว่าเท่านั้น ซึ่งจะสร้างไฟล์ merged segment ใหม่ที่เรียงตาม key เช่นกัน โดยมีหนึ่ง value ต่อหนึ่ง key และใช้ memory น้อยที่สุดเพราะเราสามารถ iterate ผ่าน SSTables ทีละ key ได้

เพื่อให้แน่ใจว่าข้อมูลใน memtable จะไม่หายไปถ้า database crash storage engine จะเก็บ log แยกต่างหากบน disk ที่ทุก write จะถูกต่อท้ายทันที log นี้ไม่ได้เรียงตาม key แต่ไม่เป็นไร เพราะจุดประสงค์เดียวของมันคือการกู้คืน memtable หลังจาก crash ทุกครั้งที่ memtable ถูกเขียนออกไปเป็น SSTable ส่วนที่เกี่ยวข้องของ log ก็สามารถถูก discard ได้

Diagram illustrating the process of merging several SSTable segments, where keys are compared, the most recent values are retained, and the result is a new sorted segment.

Figure 4-3. Merging several SSTable segments, retaining only the most recent value for each key (การรวม SSTable segments หลายๆ ตัว โดยเก็บเฉพาะค่าล่าสุดของแต่ละ key)

ถ้าคุณต้องการลบ key และ value ที่เกี่ยวข้อง คุณต้องต่อท้าย record การลบพิเศษที่เรียกว่า tombstone ลงใน data file เมื่อ log segments ถูกรวม tombstone จะบอกกระบวนการรวมให้ discard ค่าก่อนหน้าทั้งหมดของ key ที่ถูกลบ เมื่อ tombstone ถูกรวมเข้าไปใน segment ที่เก่าที่สุด มันก็สามารถถูก drop ได้

Algorithm ที่อธิบายมาที่นี่คือสิ่งที่ใช้ใน RocksDB [ 7 ], Cassandra, ScyllaDB, และ HBase [ 8 ] ทั้งหมดได้รับแรงบันดาลใจจาก paper ของ Google Bigtable [ 9 ] (ซึ่งแนะนำคำว่า SSTable และ memtable ) algorithm นี้ถูกตีพิมพ์ครั้งแรกในปี 1996 ภายใต้ชื่อ Log-Structured Merge-tree หรือ LSM-tree [ 10 ] ซึ่งต่อยอดจากงานก่อนหน้าเกี่ยวกับ log-structured filesystems [ 11 ] ด้วยเหตุนี้ storage engines ที่ใช้หลักการของการรวมและ compacting ไฟล์ที่เรียงลำดับจึงมักถูกเรียกว่า LSM storage engines .

ใน LSM storage engines ไฟล์ segment จะถูกเขียนในรอบเดียว (ไม่ว่าจะโดยการเขียน memtable หรือการรวม segments ที่มีอยู่) และหลังจากนั้นมันจะ immutable การรวมและ compaction ของ segments สามารถทำได้ใน background thread ในขณะที่การ merge กำลังดำเนินอยู่ เรายังคงให้บริการ reads ได้โดยใช้ input segments ของ merge (เช่นเดิม reads จะค้นหาใน memtable และ segment files ที่ใหม่กว่าก่อน) เมื่อกระบวนการ merge เสร็จสมบูรณ์ เราจะสลับ read requests ให้ใช้ merged segment ใหม่แทน input segments จากนั้น input segment files ก็สามารถถูกลบได้

Segment files ไม่จำเป็นต้องเก็บไว้บน local disk เสมอไป; พวกมันยังเหมาะสำหรับการเขียนไปยัง object storage อีกด้วย SlateDB และ Delta Lake [ 12 ] ใช้แนวทางนี้เป็นตัวอย่าง

การมี immutable segment files ยังช่วยลดความยุ่งยากในการกู้คืนจาก crash ถ้าเกิด crash ขณะที่กำลังเขียน memtable หรือ merging segments ฐานข้อมูลสามารถลบ SSTable ที่ยังไม่เสร็จและเริ่มใหม่ได้ log ที่ persist writes ไปยัง memtable อาจมี records ที่ไม่สมบูรณ์ถ้าเกิด crash ครึ่งทางขณะเขียน record หรือถ้าดิสก์เต็ม; ปัญหาเหล่านี้มักถูกตรวจจับโดยการรวม checksums ไว้ใน log และ discard corrupted หรือ incomplete log entries เราจะพูดถึง durability และ crash recovery เพิ่มเติมใน Chapter 8 .

Bloom filters (Bloom filters)

ในการจัดเก็บแบบ LSM การอ่าน key ที่ถูกอัปเดตครั้งสุดท้ายนานมาแล้ว หรือการพยายามอ่าน key ที่ไม่มีอยู่อาจช้าได้ เนื่องจาก storage engine จะต้องตรวจสอบ segment files หลายตัว เพื่อเร่งความเร็วในการอ่านดังกล่าว LSM storage engines มักจะรวม Bloom filter [ 13 ] ไว้ในแต่ละ segment ซึ่งเป็นวิธีที่รวดเร็วแต่เป็น approximate ในการตรวจสอบว่า key ใด key หนึ่งปรากฏใน SSTable ใด SSTable หนึ่งหรือไม่

Figure 4-4 แสดงตัวอย่างของ Bloom filter ที่ประกอบด้วยสอง keys และ 16 bits (ในความเป็นจริง มันจะมี keys และ bits มากกว่านี้) สำหรับทุก key ใน SSTable เราคำนวณ hash function ให้ได้ชุดของตัวเลข ซึ่งจะถูกแปลเป็น indexes ใน array ของ bits [ 14 ] เราตั้ง bits ที่ตรงกับ indexes เหล่านั้นเป็น 1 และปล่อยส่วนที่เหลือเป็น 0 เช่น key handbag hashes เป็นตัวเลข (2, 9, 4) ดังนั้นเราจึงตั้ง bit ที่สอง, เก้า, และสี่เป็น 1 bitmap จะถูกเก็บเป็นส่วนหนึ่งของ SSTable พร้อมกับ sparse index ของ keys ซึ่งใช้พื้นที่เพิ่มเล็กน้อย แต่โดยทั่วไป Bloom filter มีขนาดเล็กเมื่อเทียบกับส่วนอื่นของ SSTable

เมื่อเราต้องการทราบว่า key ปรากฏใน SSTable หรือไม่ เราคำนวณ hash เดียวกันของ key นั้นเหมือนเดิมและตรวจสอบ bits ที่ indexes เหล่านั้น ตัวอย่างเช่น ใน Figure 4-4 เรากำลังสอบถาม key handheld ซึ่ง hashes เป็น (6, 11, 2) หนึ่งใน bits เหล่านั้นคือ 1 (คือ bit หมายเลข 2) ในขณะที่อีกสองตัวเป็น 0 การตรวจสอบเหล่านี้สามารถทำได้อย่างรวดเร็วมากโดยใช้ bitwise operations ที่ CPU ทุกตัวรองรับ

Diagram illustrating a Bloom filter where keys "handbag" and "handoff" set specific bits, and querying "handheld" shows it is not present due to missing set bits.

Figure 4-4. A Bloom filter provides a fast, probabilistic check on whether a particular key exists in a particular SSTable. (Bloom filter ให้การตรวจสอบแบบรวดเร็วและ probabilistic ว่า key หนึ่งๆ มีอยู่ใน SSTable ที่กำหนดหรือไม่)

ถ้าอย่างน้อยหนึ่ง bit เป็น 0 เราจะรู้ว่า key นั้นไม่มีอยู่ใน SSTable อย่างแน่นอน ถ้า bits ในการสอบถามทั้งหมดเป็น 1 แสดงว่า key นั้นน่าจะอยู่ใน SSTable แต่ก็เป็นไปได้ว่าโดยบังเอิญ bits ทั้งหมดนั้นถูกตั้งเป็น 1 โดย keys อื่นๆ กรณีนี้ที่ดูเหมือนว่า key มีอยู่ทั้งที่จริงๆ แล้วไม่มี เรียกว่า false positive .

ความน่าจะเป็นของ false positives ขึ้นอยู่กับจำนวน keys, จำนวน bits ที่ตั้งต่อ key, และจำนวน bits ทั้งหมดใน Bloom filter คุณสามารถใช้เครื่องมือคำนวณออนไลน์เพื่อหาพารามิเตอร์ที่เหมาะสมสำหรับแอปพลิเคชันของคุณ [ 15 ] ตามหลักคร่าวๆ คุณต้องจัดสรรพื้นที่ Bloom filter 10 bits สำหรับทุก key ใน SSTable เพื่อให้ได้ความน่าจะเป็น false-positive ที่ 1% และความน่าจะเป็นจะลดลงสิบเท่าสำหรับทุกๆ 5 bits เพิ่มเติมที่คุณจัดสรรต่อ key

ในบริบทของ LSM storage engines false positives ไม่ใช่ปัญหา:

  • ถ้า Bloom filter บอกว่า key ไม่มี อยู่ เราสามารถข้าม SSTable นั้นได้อย่างปลอดภัย เพราะเรามั่นใจว่ามันไม่มี key นั้น

  • ถ้า Bloom filter บอกว่า key มี อยู่ เราต้องตรวจสอบ sparse index และ decode block ของ key-value pairs เพื่อตรวจสอบว่า key มีอยู่จริงหรือไม่ ถ้าเป็น false positive เราก็แค่งานที่เกินความจำเป็นเล็กน้อย แต่อย่างอื่นก็ไม่มีอันตราย—เราแค่ค้นหาต่อใน segment ที่เก่ากว่าถัดไป

Compaction strategies (กลยุทธ์การ Compaction)

รายละเอียดสำคัญคือว่า LSM storage เลือกว่าจะทำ compaction เมื่อใดและ SSTables ใดที่จะรวมในการ compaction ระบบ storage ที่ใช้ LSM จำนวนมากอนุญาตให้คุณกำหนดค่ากลยุทธ์ compaction ที่จะใช้ ตัวเลือกทั่วไปบางอย่างมีดังนี้ [ 16 , 17 ]:

Size-tiered compaction (การรวมแบบแบ่งตามขนาด)

SSTables ใหม่และเล็กกว่าจะถูกรวมเข้ากับ SSTables เก่าและใหญ่กว่าตามลำดับ ตัวอย่างเช่น สี่ SSTables ขนาด 256 MB อาจถูก compacted เป็น SSTable ขนาด 898 MB (ผลลัพธ์ไม่ใช่ 1,024 MB เนื่องจากการลบ การเขียนทับ การหมดอายุตาม time-to-live และอื่นๆ) SSTables ที่มีข้อมูลเก่าอาจมีขนาดใหญ่มาก และการรวมมันต้องใช้พื้นที่ดิสก์ชั่วคราวจำนวนมาก ข้อดีของกลยุทธ์นี้คือสามารถรองรับ write throughput ที่สูงมากเนื่องจากข้อมูลส่วนใหญ่ถูกเขียนใหม่เพียงไม่กี่ครั้งในการรวมแบบ sequential ขนาดใหญ่

Leveled compaction (การรวมแบบแบ่งระดับ)

แทนที่จะเขียน SSTables ขนาดใหญ่ leveled compaction จะรักษาขนาด SSTable ให้คงที่และจัดกลุ่มเป็น "levels" ที่เพิ่มขึ้น (เรียกว่า L0, L1 และอื่นๆ) L0 มีข้อมูลที่เพิ่งเขียนล่าสุด ทุกระดับที่เกิน L0 มี SSTables ที่แบ่งตามช่วง key ตัวอย่างเช่น L1 อาจมี SSTables สองตัว: ตัวแรกมี keys a–m และตัวที่สองมี n–z แต่ละ level มีขีดจำกัดขนาดของตัวเอง และแต่ละ level มีขนาดใหญ่กว่า level ที่อยู่ก่อนหน้า (เช่น L2 จะใหญ่กว่า L1) เมื่อ SSTables ของ level ใดรวมกันเกินขีดจำกัดขนาดสูงสุด SSTable หนึ่งตัวหรือมากกว่าจาก level i จะถูกรวมเข้ากับ level i + 1 และถูกลบออกจาก level i แนวทางนี้ช่วยให้ compaction ดำเนินไปแบบ incremental มากขึ้นและใช้พื้นที่ดิสก์น้อยกว่ากลยุทธ์ size-tiered Leveled compaction มีประสิทธิภาพสำหรับ reads มากกว่า size-tiered compaction เพราะ storage engine ต้องอ่าน SSTables น้อยกว่าเพื่อตรวจสอบว่ามี key นั้นหรือไม่

ตามหลักคร่าวๆ size-tiered compaction มีประสิทธิภาพดีกว่าถ้าคุณมี writes เป็นส่วนใหญ่และ reads น้อย ในขณะที่ leveled compaction มีประสิทธิภาพดีกว่าถ้า workload ของคุณเน้น reads เป็นหลัก ถ้าคุณเขียน keys จำนวนน้อยบ่อยครั้งและ keys จำนวนมากไม่บ่อยนัก leveled compaction ก็มีข้อดีเช่นกัน [ 18 ] โชคดีที่การ implement LSM-tree ส่วนใหญ่มีกลยุทธ์ compaction ที่หลากหลายสำหรับ workloads ที่แตกต่างกัน

ถึงแม้จะมีรายละเอียดปลีกย่อยมากมาย แต่แนวคิดพื้นฐานของ LSM-trees—การรักษา SSTables แบบเรียงซ้อนที่ถูกรวมใน background—นั้นเรียบง่ายและมีประสิทธิภาพ เราจะพูดถึงคุณลักษณะด้านประสิทธิภาพโดยละเอียดใน "Comparing B-Trees and LSM-Trees" .

Embedded Storage Engines (Storage Engines แบบ Embedded)

ฐานข้อมูลจำนวนมากทำงานเป็น service ที่รับ queries ผ่าน network แต่ก็มีฐานข้อมูล embedded ที่ไม่เปิดเผย network API แต่เป็น libraries ที่ทำงานใน process เดียวกับ application code ของคุณ โดยทั่วไปจะอ่านและเขียนไฟล์บน local disk และคุณโต้ตอบกับมันผ่าน function calls ปกติ ตัวอย่างของ embedded storage engines ได้แก่ RocksDB, SQLite, LMDB, DuckDB, และ KùzuDB [ 19 ]

Embedded databases ถูกใช้บ่อยมากใน mobile apps เพื่อเก็บข้อมูลผู้ใช้ในเครื่อง ในฝั่ง backend พวกมันเป็นตัวเลือกที่เหมาะสมถ้าข้อมูลเล็กพอที่จะ fit ในเครื่องเดียวและไม่มี concurrent transactions จำนวนมาก ตัวอย่างเช่น ในระบบ multitenant ที่ tenant แต่ละตัวเล็กพอและแยกจากกันโดยสมบูรณ์ (คือคุณไม่จำเป็นต้องรัน queries ที่รวมข้อมูลจากหลาย tenants) คุณสามารถใช้ embedded database instance แยกต่างหากต่อ tenant [ 20 ]

วิธีการจัดเก็บและค้นคืนที่เราพูดถึงในบทนี้ใช้ทั้งใน embedded และ client/server databases ในบท 6 และ 7 เราจะพูดถึงเทคนิคในการ scale ฐานข้อมูลข้ามหลายเครื่อง

B-Trees (B-Trees)

แนวทาง log-structured เป็นที่นิยม แต่มันไม่ใช่รูปแบบเดียวของ key-value storage โครงสร้างที่ใช้กันอย่างแพร่หลายที่สุดสำหรับการอ่านและเขียน database records ตาม key คือ B-tree .

ถูกแนะนำในปี 1970 [ 21 ] และถูกเรียกว่า "ubiquitous" ในเวลาไม่ถึง 10 ปีต่อมา [ 22 ] B-trees ผ่านการทดสอบของกาลเวลาเป็นอย่างดี พวกมันยังคงเป็น index implementation มาตรฐานใน relational databases เกือบทั้งหมด และ nonrelational databases จำนวนมากก็ใช้มันเช่นกัน

เช่นเดียวกับ SSTables B-trees เก็บ key-value pairs เรียงตาม key ซึ่งทำให้การค้นหาแบบ key-value และ range queries มีประสิทธิภาพ แต่นั่นคือจุดสิ้นสุดของความคล้ายคลึง; B-trees มีปรัชญาการออกแบบที่แตกต่างกันมาก

indexes แบบ log-structured ที่เราเห็นก่อนหน้านี้แบ่ง database ออกเป็น segments ขนาดแปรผัน โดยทั่วไปหลายเมกะไบต์หรือมากกว่า ที่ถูกเขียนครั้งเดียวแล้วกลายเป็น immutable ในทางตรงกันข้าม B-trees แบ่ง database ออกเป็น blocks หรือ pages ขนาดคงที่ และอาจ overwrite page ในที่เดิม page โดยทั่วไปมีขนาด 4 KiB แต่ PostgreSQL ปัจจุบันใช้ 8 KiB และ MySQL ใช้ 16 KiB เป็นค่าเริ่มต้น

แต่ละ page สามารถระบุได้ด้วย page number ซึ่งทำให้ page หนึ่งสามารถอ้างถึงอีก page หนึ่ง—คล้ายกับ pointer แต่บน disk แทนที่จะเป็นในหน่วยความจำ ถ้า pages ทั้งหมดถูกเก็บในไฟล์เดียวกัน การคูณ page number ด้วย page size จะให้ byte offset ในไฟล์ที่ตำแหน่งของ page นั้น เราสามารถใช้ page references เหล่านี้เพื่อสร้าง tree ของ pages ดังที่แสดงใน Figure 4-5 .

Diagram showing the lookup process of key 251 in a B-tree index, starting from the root page and navigating through child pages containing keys 200–300 and 250–270.

Figure 4-5. Looking up key 251 by using a B-tree index. From the root page, we first follow the reference to the page for keys 200–300, then the page for keys 250–270. (การค้นหา key 251 โดยใช้ B-tree index จาก root page เราเริ่มต้นตาม reference ไปยัง page สำหรับ keys 200–300 จากนั้นไปยัง page สำหรับ keys 250–270)

หนึ่ง page ถูกกำหนดให้เป็น root ของ B-tree; เมื่อใดก็ตามที่คุณต้องการค้นหา key ใน index คุณจะเริ่มที่นี่ page ประกอบด้วย keys หลายตัวและ references ไปยัง child pages child แต่ละตัวรับผิดชอบช่วงของ keys ที่ต่อเนื่องกัน และ keys ระหว่าง references บ่งบอกว่าขอบเขตระหว่างช่วงเหล่านั้นอยู่ที่ไหน (โครงสร้างนี้บางครั้งเรียกว่า B+ tree แต่เราไม่จำเป็นต้องแยกความแตกต่างจาก B-tree variants อื่นๆ)

ในตัวอย่างใน Figure 4-5 เรากำลังค้นหา key 251 ดังนั้นเราจึงรู้ว่าเราต้องทำตาม page reference ระหว่างขอบเขต 200 และ 300 ซึ่งนำเราไปยัง page ที่มีลักษณะคล้ายกันซึ่งแบ่งช่วง 200–300 ออกเป็นช่วงย่อย ในที่สุดเราก็ลงไปถึง page ที่มี keys แต่ละตัว (a leaf page ) ซึ่งอาจมี value สำหรับแต่ละ key inline หรือมี references ไปยัง pages ที่สามารถหา values ได้

จำนวน references ไปยัง child pages ในหนึ่ง page ของ B-tree เรียกว่า branching factor ตัวอย่างเช่น ใน Figure 4-5 branching factor คือหก ในทางปฏิบัติ branching factor ขึ้นอยู่กับจำนวนพื้นที่ที่ต้องใช้ในการเก็บ page references และขอบเขตของช่วง แต่โดยปกติแล้วมันคือหลายร้อย

ถ้าคุณต้องการอัปเดต value สำหรับ key ที่มีอยู่ใน B-tree คุณค้นหา leaf page ที่มี key นั้นและเขียนทับ page นั้นบน disk ด้วย version ที่มี value ใหม่ ถ้าคุณต้องการเพิ่ม key ใหม่ คุณต้องหา page ที่มีช่วงครอบคลุม key ใหม่และเพิ่มมันลงใน page นั้น ถ้าไม่มีพื้นที่ว่างเพียงพอใน page สำหรับ key ใหม่ page จะถูกแบ่งออกเป็นสอง pages ที่เต็มครึ่ง และ parent page จะถูกอัปเดตเพื่อรองรับการแบ่งช่วง key ใหม่ ดังที่แสดงใน Figure 4-6 .

Diagram illustrating the process of splitting a B-tree page by adding key 334, resulting in the creation of two pages with updated references in the parent node.

Figure 4-6. Growing a B-tree by splitting a page on the boundary key 337. The parent page is updated to reference both children. (การเติบโตของ B-tree โดยการ split page ที่ boundary key 337 page parent ถูกอัปเดตให้อ้างอิง children ทั้งสอง)

ในตัวอย่างนี้ เราต้องการแทรก key 334 แต่ page สำหรับช่วง 333–345 เต็มแล้ว เราจึง split มันเป็น page สำหรับช่วง 333–337 (ซึ่งรวม key ใหม่, 334) และ page สำหรับ 337–345 นอกจากนี้เรายังต้องอัปเดต parent page ให้มี references ไปยัง children ทั้งสอง โดยมี boundary value ที่ 337 คั่นระหว่างกัน ถ้า parent page ไม่มีที่ว่างเพียงพอสำหรับ reference ใหม่ มันอาจต้องถูก split เช่นกัน และการ split สามารถดำเนินต่อไปจนถึง root ของ tree เมื่อ root ถูก split เราจะสร้าง root ใหม่เหนือมัน การลบ keys (ซึ่งอาจต้อง merge nodes) ซับซ้อนกว่า [ 5 ]

algorithm นี้รับประกันว่า tree ยังคง balanced : B-tree ที่มี n keys จะมีความลึก O (log  n ) เสมอ ฐานข้อมูลส่วนใหญ่สามารถ fit ลงใน B-tree ที่ลึกสามหรือสี่ระดับ ดังนั้นคุณไม่ต้องทำตาม page references หลายครั้งเพื่อหา page ที่คุณต้องการ (ต้นไม้สี่ระดับของ pages ขนาด 4 KiB ที่มี branching factor 500 สามารถเก็บได้ถึง 250 TB)

Making B-trees reliable (ทำให้ B-trees มีความน่าเชื่อถือ)

การดำเนินการเขียนพื้นฐานของ B-tree คือการเขียนทับ page บน disk ด้วยข้อมูลใหม่ โดยถือว่าการเขียนทับไม่ได้เปลี่ยนตำแหน่งของ page; references ทั้งหมดไปยัง page นั้นยังคงเมื่อ page ถูกเขียนทับ ซึ่งแตกต่างอย่างสิ้นเชิงกับ log-structured indexes เช่น LSM-trees ที่ต่อท้ายไฟล์เท่านั้น (และในที่สุดก็ลบไฟล์ที่ล้าสมัย) แต่ไม่เคยแก้ไขไฟล์ในที่เดิม

การเขียนทับหลาย pages พร้อมกัน เช่นใน page split เป็นการดำเนินการที่อันตราย ถ้า database crash หลังจากที่เขียนไปแค่บาง pages คุณจะได้ tree ที่เสียหาย (เช่น อาจมี orphan page ที่ไม่ใช่ child ของ parent ใดๆ) ถ้าฮาร์ดแวร์ไม่สามารถเขียนทั้ง page แบบ atomic ได้ คุณก็อาจได้ page ที่เขียนไม่สมบูรณ์ (เรียกว่า torn page [ 23 ])

เพื่อให้ database ทนทานต่อ crash เป็นเรื่องปกติที่ B-tree implementations จะมี data structure เพิ่มเติมบน disk: write-ahead log (WAL) นี่คือไฟล์แบบ append-only ที่การแก้ไข B-tree ทุกครั้งต้องถูกเขียนลงไปก่อนที่จะถูกนำไปใช้กับ pages ของ tree เอง เมื่อ database เริ่มทำงานใหม่หลังจาก crash log นี้จะถูกใช้เพื่อกู้คืน B-tree กลับสู่สถานะที่ consistent [ 2 , 24 ] ใน filesystems กลไกที่เทียบเท่ากันเรียกว่า journaling .

เพื่อปรับปรุงประสิทธิภาพ B-tree implementations โดยทั่วไปจะไม่เขียนทุก page ที่ถูกแก้ไขลง disk ทันที แต่จะ buffer B-tree pages ในหน่วยความจำไว้ก่อนสักระยะ write-ahead log จึงรับประกันว่าข้อมูลจะไม่สูญหายในกรณีที่ crash ตราบใดที่ข้อมูลถูกเขียนไปยัง WAL และ flush ไปยัง disk โดยใช้ fsync system call ข้อมูลจะ durable เพราะ database จะสามารถกู้คืนมันได้หลังจาก crash [ 25 ]

Using B-tree variants (การใช้ B-tree variants)

เนื่องจาก B-trees มีมานานแล้ว จึงมี variants มากมายที่ถูกพัฒนาขึ้นในช่วงหลายปีที่ผ่านมา เพียงแค่ยกตัวอย่างบางส่วน:

  • แทนที่จะเขียนทับ pages และรักษา WAL สำหรับการกู้คืนจาก crash ฐานข้อมูลบางตัว (เช่น LMDB) ใช้ copy-on-write scheme [ 26 ] page ที่ถูกแก้ไขจะถูกเขียนไปยังตำแหน่งอื่น และ version ใหม่ของ parent pages ใน tree จะถูกสร้างขึ้น ชี้ไปยังตำแหน่งใหม่ แนวทางนี้ยังมีประโยชน์สำหรับการควบคุม concurrency ดังที่เราจะเห็นใน "Snapshot Isolation and Repeatable Read" .

  • เราสามารถประหยัดพื้นที่ใน pages โดยไม่ต้องเก็บทั้ง key แต่ใช้การย่อมัน โดยเฉพาะใน pages ภายในของ tree keys ต้องให้ข้อมูลเพียงพอที่จะทำหน้าที่เป็นขอบเขตระหว่างช่วง key การบรรจุ keys มากขึ้นใน page ช่วยให้ tree มี branching factor สูงขึ้นและมีระดับน้อยลง

  • เพื่อเร่งความเร็วการ scan ช่วง key ในลำดับที่เรียงแล้ว B-tree implementations บางตัวพยายามจัดวาง tree เพื่อให้ leaf pages ปรากฏในลำดับ sequential บน disk ซึ่งลดจำนวน disk seeks อย่างไรก็ตาม การรักษาลำดับนั้นทำได้ยากเมื่อ tree โตขึ้น

  • มีการเพิ่ม pointers เพิ่มเติมใน tree ตัวอย่างเช่น แต่ละ leaf page อาจมี references ไปยัง sibling pages ด้านซ้ายและขวา ซึ่งช่วยให้สามารถ scan keys ตามลำดับได้โดยไม่ต้องกลับไปยัง parent pages

Comparing B-Trees and LSM-Trees (การเปรียบเทียบ B-Trees และ LSM-Trees)

ตาม หลักคร่าวๆ LSM-trees เหมาะกับ write-heavy applications มากกว่า ในขณะที่ B-trees เร็วกว่าสำหรับ reads [ 27 , 28 ] อย่างไรก็ตาม benchmarks มักจะ sensitive ต่อรายละเอียดของ workload คุณต้องทดสอบระบบด้วย workload เฉพาะของคุณเพื่อเปรียบเทียบที่มีความหมาย นอกจากนี้ มันไม่ใช่การเลือกอย่างใดอย่างหนึ่งระหว่าง LSM- และ B-trees; storage engines บางครั้งผสมผสานลักษณะของทั้งสองแนวทาง—เช่น การมี B-trees หลายตัวและรวมพวกมันแบบ LSM-style ในส่วนนี้เราจะพูดถึงสั้นๆ เกี่ยวกับสิ่งที่ควรพิจารณาเมื่อวัดประสิทธิภาพของ storage engine

Read performance (ประสิทธิภาพการอ่าน)

ใน B-tree การค้นหา key เกี่ยวข้องกับการอ่านหนึ่ง page ในแต่ละระดับ เนื่องจากจำนวนระดับมักจะค่อนข้างน้อย การอ่านจาก B-tree โดยทั่วไปจึงเร็วและมีประสิทธิภาพที่คาดเดาได้ ใน LSM storage engine การอ่านมักต้องตรวจสอบ SSTables หลายตัวในขั้นตอนต่างๆ ของ compaction แต่ Bloom filters ช่วยลดจำนวน disk I/O operations ที่จำเป็น ทั้งสองแนวทางสามารถทำงานได้ดี และอันไหนเร็วกว่าขึ้นอยู่กับรายละเอียดของ storage engine และ workload

Range queries นั้นง่ายและเร็วบน B-trees เพราะสามารถใช้ประโยชน์จากโครงสร้างที่เรียงลำดับของ tree ได้ ในการจัดเก็บแบบ LSM range queries ก็สามารถใช้ประโยชน์จากการเรียงลำดับของ SSTable ได้เช่นกัน แต่ต้อง scan ทุก segments พร้อมกันและรวมผลลัพธ์ Bloom filters ไม่ช่วยสำหรับ range queries (เพราะคุณต้องคำนวณ hash ของทุก key ที่เป็นไปได้ในช่วงนั้น ซึ่งไม่สามารถทำได้ในทางปฏิบัติ) ทำให้ range queries มีราคาแพงกว่า point queries ในแนวทาง LSM [ 29 ]

write throughput ที่สูงอาจทำให้เกิด latency spikes ใน log-structured storage engine ถ้า memtable เต็ม สิ่งนี้เกิดขึ้นถ้าข้อมูลไม่สามารถเขียนออกไปยัง disk ได้เร็วพอ อาจเป็นเพราะกระบวนการ compaction ตาม writes ที่เข้ามาไม่ทัน storage engines จำนวนมาก รวมถึง RocksDB ใช้ backpressure ในสถานการณ์นี้: พวกมันระงับ reads และ writes ทั้งหมดจนกว่า memtable จะถูกเขียนออกไปยัง disk [ 30 , 31 ]

ในเรื่องของ read throughput SSDs สมัยใหม่ (โดยเฉพาะ NVMe [Non-Volatile Memory Express] SSDs ที่เชื่อมต่อผ่าน PCIe bus ที่เร็วกว่าแทน SATA bus) สามารถทำ independent read requests จำนวนมากในแบบ parallel ทั้ง LSM-trees และ B-trees สามารถให้ read throughput ที่สูงได้ แต่ storage engines ต้องถูกออกแบบอย่างระมัดระวังเพื่อใช้ประโยชน์จาก parallelism นี้ [ 32 ]

Sequential versus random writes (การเขียนแบบ Sequential เทียบกับ Random)

ด้วย B-tree ถ้า application เขียน keys ที่กระจายทั่ว key space การดำเนินการ disk ที่เกิดขึ้นก็จะกระจายแบบสุ่มเช่นกัน เพราะ pages ที่ storage engine ต้องเขียนทับอาจอยู่ที่ใดก็ได้บน disk ในทางกลับกัน log-structured storage engine จะเขียนไฟล์ segment ทั้งหมดในครั้งเดียว (ไม่ว่าจะเป็นการเขียน memtable หรือ compacting segments ที่มีอยู่) ซึ่งมีขนาดใหญ่กว่า page ใน B-tree มาก

รูปแบบของการเขียนขนาดเล็กจำนวนมากที่กระจายตัว (อย่างที่พบใน B-trees) เรียกว่า random writes ในขณะที่รูปแบบของการเขียนขนาดใหญ่จำนวนน้อย (อย่างที่พบใน LSM-trees) เรียกว่า sequential writes โดยทั่วไป disk มี sequential write throughput ที่สูงกว่า random write throughput ซึ่งหมายความว่า log-structured storage engine โดยทั่วไปสามารถรองรับ write throughput ที่สูงกว่าบนฮาร์ดแวร์เดียวกันเมื่อเทียบกับ B-tree ความแตกต่างนี้ใหญ่เป็นพิเศษบน spinning-disk hard drives; บน SSDs ที่ฐานข้อมูลส่วนใหญ่ใช้ในปัจจุบัน ความแตกต่างน้อยกว่าแต่ยังคงสังเกตเห็นได้

Sequential Versus Random Writes on SSDs (การเขียน Sequential เทียบกับ Random บน SSDs)

บน spinning-disk hard drives (HDDs) การเขียน sequential นั้นเร็วกว่าการเขียน random มาก เนื่องจากการเขียน random ต้องขยับหัวอ่าน disk ไปยังตำแหน่งใหม่โดยใช้กลไกและรอให้ส่วนที่ถูกต้องของแผ่นจานหมุนผ่านใต้หัวอ่าน ซึ่งใช้เวลาหลายมิลลิวินาที—ชั่วนิรันดร์ในมาตรฐานเวลาของคอมพิวเตอร์ อย่างไรก็ตาม SSDs รวมถึง NVMe (หรือ flash memory ที่เชื่อมต่อกับ PCI Express bus) ได้เข้ามาแทนที่ HDDs สำหรับหลาย use cases และไม่อยู่ภายใต้ข้อจำกัดทางกลไกดังกล่าว

ถึงกระนั้น SSDs ก็ยังมี throughput ที่สูงกว่าสำหรับ sequential writes มากกว่า random writes เหตุผลคือ flash memory สามารถอ่านหรือเขียนทีละ page (โดยทั่วไป 4 KiB) แต่สามารถลบได้ทีละ block (โดยทั่วไป 512 KiB) เท่านั้น บาง pages ใน block อาจมีข้อมูลที่ถูกต้อง ในขณะที่ pages อื่นๆ อาจมีข้อมูลที่ไม่ต้องการอีกต่อไป ก่อนที่จะลบ block ตัว controller ต้องย้าย pages ที่มีข้อมูลถูกต้องไปยัง blocks อื่น; กระบวนการนี้ เรียกว่า garbage collection (GC) [ 33 ]

workload การเขียน sequential จะเขียนข้อมูล chunk ที่ใหญ่กว่าต่อครั้ง ดังนั้นจึงมีแนวโน้มว่า block ขนาด 512 KiB ทั้งหมดจะ belong กับไฟล์เดียว เมื่อไฟล์นั้นถูกลบในภายหลัง ทั้ง block สามารถถูกลบได้โดยไม่ต้องทำ GC ใดๆ ในทางกลับกัน ด้วย workload การเขียน random block มีแนวโน้มที่จะมี pages ที่มีข้อมูลถูกต้องและไม่ถูกต้องปนกัน ดังนั้น garbage collector ต้องทำงานมากขึ้นก่อนที่ block จะถูกลบได้ [ 34 , 35 , 36 ] write bandwidth ที่ถูกใช้โดย GC จะไม่พร้อมใช้งานสำหรับ application การเขียนเพิ่มเติมที่เกิดจาก GC ยังก่อให้เกิดการสึกหรอบน flash memory; ดังนั้น random writes ทำให้ drive สึกหรอเร็วกว่า sequential writes

Write amplification (Write Amplification)

สำหรับ storage engine ทุกประเภท หนึ่ง write request จาก application จะกลายเป็น I/O operations หลายครั้งบน disk พื้นฐาน สำหรับ LSM-trees value จะถูกเขียนไปยัง log ก่อนเพื่อความทนทาน จากนั้นอีกครั้งเมื่อ memtable ถูกเขียนไปยัง disk และอีกครั้งทุกครั้งที่ key-value pair เป็นส่วนหนึ่งของ compaction (ถ้า values มีขนาดใหญ่กว่า keys อย่างมาก overhead นี้สามารถลดลงได้โดยการเก็บ values แยกจาก keys และทำ compaction เฉพาะ SSTables ที่มี keys และ references ไปยัง values [ 37 ])

B-tree index ต้องเขียนทุกชิ้นของข้อมูลอย่างน้อยสองครั้ง: ครั้งแรกไปยัง write-ahead log และครั้งที่สองไปยัง tree page เอง นอกจากนี้ การเขียนทั้ง page ออกมาในบางครั้งก็จำเป็น แม้ว่าจะมีแค่ไม่กี่ bytes ที่เปลี่ยนแปลงใน page นั้น เพื่อให้แน่ใจว่า B-tree สามารถกู้คืนได้อย่างถูกต้องหลังจาก crash หรือไฟดับ [ 38 , 39 ]

ถ้าคุณนำจำนวน bytes ทั้งหมดที่เขียนไปยัง disk ใน workload หารด้วยจำนวน bytes ที่คุณต้องเขียนถ้าคุณเพียงแค่เขียน append-only log โดยไม่มี index คุณจะได้ write amplification (บางครั้ง write amplification ถูกนิยามในแง่ของ I/O operations แทนที่จะเป็น bytes) ใน write-heavy applications the bottleneck อาจเป็นอัตราที่ database สามารถเขียนไปยัง disk ได้ ในกรณีนี้ ยิ่ง write amplification สูงเท่าไหร่ จำนวน writes ต่อวินาทีที่มันสามารถรองรับได้ภายใน bandwidth ของ disk ที่มีอยู่ก็ยิ่งน้อยลงเท่านั้น

Write amplification เป็นปัญหาทั้งใน LSM-trees และ B-trees อันไหนดีกว่าขึ้นอยู่กับปัจจัยต่างๆ เช่น ความยาวของ keys และ values ของคุณ และความถี่ที่คุณเขียนทับ keys ที่มีอยู่เทียบกับการแทรก keys ใหม่ สำหรับ workloads ทั่วไป LSM-trees มักจะมี write amplification ที่ต่ำกว่าเพราะไม่ต้องเขียนทั้ง pages และสามารถบีบอัด chunks ของ SSTable [ 40 ] นี่เป็นอีกปัจจัยที่ทำให้ LSM storage engines เหมาะสำหรับ write-heavy workloads

นอกจากจะมีผลต่อ throughput แล้ว write amplification ยังเกี่ยวข้องกับการสึกหรอของ SSDs อีกด้วย storage engine ที่มี write amplification ต่ำกว่าจะทำให้ SSD สึกหรอช้าลง

เมื่อวัด write throughput ของ storage engine สิ่งสำคัญคือต้องรันการทดลองนานพอที่ผลของ write amplification จะชัดเจน เมื่อเขียนไปยัง LSM-tree ที่ว่างเปล่า ยังไม่มีการ compaction เกิดขึ้น ดังนั้น bandwidth ของ disk ทั้งหมดจึงพร้อมสำหรับ writes ใหม่ เมื่อ database โตขึ้น writes ใหม่ต้อง share bandwidth ของ disk กับ compaction

Disk space usage (การใช้พื้นที่ดิสก์)

B-trees อาจเกิด fragmentation เมื่อเวลาผ่านไป; ตัวอย่างเช่น ถ้า keys จำนวนมากถูกลบ ไฟล์ database อาจมี pages จำนวนมากที่ B-tree ไม่ได้ใช้อีกต่อไป การเพิ่มข้อมูลใหม่ใน B-tree สามารถใช้ pages ว่างเหล่านั้นได้ แต่ไม่สามารถคืนให้กับ operating system ได้ง่ายๆ เพราะพวกมันอยู่กลางไฟล์ ดังนั้นพวกมันยังคงกินพื้นที่บน filesystem ฐานข้อมูลจึงจำเป็นต้องมี background process ที่ย้าย pages ไปวางในตำแหน่งที่ดีขึ้น เช่น vacuum process ใน PostgreSQL [ 25 ]

Fragmentation เป็นปัญหาน้อยกว่าใน LSM-trees เนื่องจากกระบวนการ compaction จะเขียนไฟล์ข้อมูลใหม่เป็นระยะๆ อยู่แล้ว และ SSTables ไม่มี pages ที่มีพื้นที่ไม่ได้ใช้ นอกจากนี้ blocks ของ key-value pairs ยังสามารถบีบอัดได้ดีกว่าใน SSTables ซึ่งมักจะส่งผลให้ไฟล์บน disk เล็กกว่าเมื่อเทียบกับ B-trees Keys และ values ที่ถูกเขียนทับยังคงกินพื้นที่จนกว่าจะถูกเอาออกโดยการ compaction แต่ overhead นี้ค่อนข้างต่ำเมื่อใช้ leveled compaction [ 40 , 41 ] Size-tiered compaction (ดู "Compaction strategies" ) ใช้พื้นที่ดิสก์มากกว่า โดยเฉพาะชั่วคราวระหว่างการ compaction

การมีหลาย copies ของข้อมูลบางอย่างบน disk ก็อาจเป็นปัญหาได้เมื่อคุณต้องการลบข้อมูลและมั่นใจว่ามันถูกลบจริงๆ (อาจเพื่อปฏิบัติตามกฎระเบียบการปกป้องข้อมูล) ตัวอย่างเช่น ใน LSM storage engines ส่วนใหญ่ record ที่ถูกลบอาจยังคงมีอยู่ใน levels ที่สูงกว่าจนกว่า tombstone ที่แสดงถึงการลบจะถูก propagate ผ่านทุกระดับของ compaction ซึ่งอาจใช้เวลานาน การออกแบบ storage engine แบบเฉพาะทางสามารถ propagate การลบได้เร็วกว่า [ 42 ]

ในทางกลับกัน ลักษณะ immutable ของ SSTable segment files มีประโยชน์ถ้าคุณต้องการ snapshot ของ database ณ จุดเวลาใดเวลาหนึ่ง (เช่น สำหรับ backup หรือสร้าง copy ของ database สำหรับการทดสอบ) คุณสามารถเขียน memtable และบันทึกว่า segment files ใดมีอยู่ในเวลานั้น ตราบใดที่คุณไม่ลบไฟล์ที่เป็นส่วนหนึ่งของ snapshot คุณก็ไม่จำเป็นต้องคัดลอกมันจริงๆ ใน B-tree ที่ pages ถูกเขียนทับ การทำ snapshot อย่างมีประสิทธิภาพนั้นยากกว่า

Multicolumn and Secondary Indexes (Indexes แบบหลายคอลัมน์และ Secondary Indexes)

จนถึงตอนนี้เราได้พูดถึงเฉพาะ key-value indexes ซึ่งเหมือนกับ primary-key indexes ใน relational model primary key ระบุหนึ่งแถวใน relational table โดยไม่ซ้ำกัน หรือหนึ่ง document ใน document database หรือหนึ่ง vertex ใน graph database records อื่นๆ ใน database สามารถอ้างถึง row/document/vertex นั้นด้วย primary key (หรือ ID) และ index ถูกใช้เพื่อแก้ไข references ดังกล่าว

นอกจากนี้ยังเป็นเรื่องธรรมดาที่จะมี secondary indexes ใน relational databases คุณสามารถสร้าง secondary indexes หลายตัวบน table เดียวกันโดยใช้คำสั่ง CREATE INDEX ซึ่งช่วยให้คุณค้นหาด้วย columns อื่นๆ ที่ไม่ใช่ primary key ตัวอย่างเช่น ใน relational schema ที่แสดงใน Figure 3-1 คุณน่าจะมี secondary index บน column user_id เพื่อให้คุณสามารถค้นหา rows ทั้งหมดที่เป็นของผู้ใช้เดียวกันในแต่ละ table

secondary index สามารถสร้างได้ง่ายจาก key-value index ความแตกต่างหลักคือใน secondary index ค่าที่ถูก index ไม่จำเป็นต้องมีค่าเดียว; กล่าวคือ อาจมีหลาย rows (documents, vertices) ภายใต้ index entry เดียวกัน ปัญหานี้แก้ได้สองวิธี: โดยทำให้แต่ละ value ใน index เป็น list ของ row identifiers ที่ตรงกัน (เหมือน postings list ใน full-text index) หรือโดยทำให้แต่ละ entry มีค่าไม่ซ้ำกันโดยการต่อท้าย row identifier เข้าไป storage engines ที่อัปเดตในที่เดิม เช่น B-trees และ log-structured storage สามารถใช้ทั้งคู่เพื่อ implement index

Storing Values Within the Index (การเก็บ Value ไว้ใน Index)

key ใน index คือสิ่งที่ queries ใช้ค้นหา ข้อมูลอื่นๆ อาจถูกเก็บใน index นอกเหนือจาก keys ขึ้นอยู่กับประเภทของ index:

  • ถ้าข้อมูลจริง (row, document, vertex) ถูกเก็บโดยตรงภายในโครงสร้าง index เรียกว่า clustered index ตัวอย่างเช่น ใน MySQL InnoDB storage engine primary key ของ table จะเป็น clustered index เสมอ และใน SQL Server คุณสามารถระบุ clustered index หนึ่งตัวต่อ table [ 43 ]

  • อีกทางเลือกหนึ่ง value อาจเป็น reference ไปยังข้อมูลจริง: ไม่ว่าจะเป็น primary key ของ row ที่เกี่ยวข้อง (InnoDB ทำแบบนี้สำหรับ secondary indexes) หรือ reference โดยตรงไปยังตำแหน่งบน disk ในกรณีหลัง สถานที่ที่เก็บ rows เรียกว่า heap file และมันเก็บข้อมูลโดยไม่เรียงลำดับเฉพาะ (มันอาจเป็น append-only หรืออาจติดตาม rows ที่ถูกลบเพื่อเขียนทับด้วยข้อมูลใหม่ในภายหลัง) ตัวอย่างเช่น Postgres ใช้แนวทาง heap file [ 44 ]

  • จุดกึ่งกลางระหว่างสองแบบคือ covering index หรือ index with included columns ซึ่งเก็บ บาง columns ของ table ไว้ใน index นอกเหนือจากการเก็บทั้ง row ใน heap หรือใน primary-key clustered index [ 45 ] ซึ่งช่วยให้บาง queries สามารถตอบได้โดยใช้ index เพียงอย่างเดียว โดยไม่ต้องแก้ไข primary key หรือค้นหาใน heap file (ในกรณีนี้ index ถูกกล่าวว่า cover query) ซึ่งสามารถทำให้บาง queries เร็วขึ้น แต่การทำซ้ำข้อมูลหมายความว่า index ใช้พื้นที่ disk มากขึ้นและทำให้ writes ช้าลง

indexes ที่พูดถึงมาจนถึงตอนนี้ map เพียง key เดียวไปยัง value ถ้าคุณต้องการ query หลาย columns ของ table (หรือหลาย fields ใน document) พร้อมกัน ดูที่ "Multidimensional and Full-Text Indexes" .

เมื่ออัปเดต value โดยไม่เปลี่ยน key แนวทาง heap file สามารถอนุญาตให้เขียนทับ record ในที่เดิมได้ ถ้า value ใหม่ไม่ใหญ่กว่า value เก่า สถานการณ์ซับซ้อนมากขึ้นถ้า value ใหม่ใหญ่กว่า เพราะมันอาจต้องถูกย้ายไปยังตำแหน่งใหม่ใน heap ที่มีพื้นที่เพียงพอ ในกรณีนั้น indexes ทั้งหมดต้องถูกอัปเดตให้ชี้ไปยังตำแหน่ง heap ใหม่ของ record หรือต้องทิ้ง forwarding pointer ไว้ในตำแหน่ง heap เก่า [ 2 ]

Keeping Everything in Memory (การเก็บทุกอย่างในหน่วยความจำ)

data structures ที่ได้พูดถึงมาจนถึงตอนนี้ในบทนี้ล้วนเป็นคำตอบสำหรับข้อจำกัดของ disks เมื่อเทียบกับ main memory แล้ว disks จัดการได้ยากกว่า ทั้ง magnetic disks และ SSDs ข้อมูลต้องถูกวางอย่างระมัดระวังถ้าคุณต้องการประสิทธิภาพที่ดีสำหรับ reads และ writes เรายอมรับความยุ่งยากนี้เพราะ disks มีข้อได้เปรียบที่สำคัญสองประการ: มัน durable (เนื้อหาไม่สูญหายเมื่อปิดเครื่อง) และมีต้นทุนต่อกิกะไบต์ที่ต่ำกว่า RAM

เมื่อ RAM ถูกลง ข้อโต้แย้งเรื่องต้นทุนต่อกิกะไบต์ก็ลดน้อยลง datasets จำนวนมากก็ไม่ได้ใหญ่นัก ดังนั้นจึงเป็นไปได้ที่จะเก็บพวกมันทั้งหมดในหน่วยความจำ potentially กระจายข้ามหลายเครื่อง สิ่งนี้นำไปสู่การพัฒนา in-memory databases .

บาง in-memory key-value stores เช่น Memcached มีไว้สำหรับ caching เท่านั้น ซึ่งการสูญเสียข้อมูลเมื่อเครื่อง restart เป็นเรื่องที่ยอมรับได้ แต่ in-memory databases อื่นๆ มุ่งมั่นเพื่อความทนทาน ซึ่งสามารถทำได้ด้วยฮาร์ดแวร์พิเศษ (เช่น battery-powered RAM) หรือโดยทั่วไปคือการเขียน log ของการเปลี่ยนแปลงไปยัง disk การเขียน periodic snapshots ไปยัง disk หรือการจำลองสถานะในหน่วยความจำไปยังเครื่องอื่นๆ

ซึ่งช่วยให้ database โหลดสถานะของมันใหม่ ไม่ว่าจะจาก disk หรือผ่าน network จาก replica (เว้นแต่จะใช้ฮาร์ดแวร์พิเศษ) เมื่อมันถูกรีสตาร์ท ถึงแม้จะเขียนไปยัง disk ระบบเหล่านี้ยังคงถูกพิจารณาว่าเป็น in-memory databases เพราะ disk ถูกใช้เป็น append-only log เพื่อความทนทานเท่านั้น และ reads ให้บริการจากหน่วยความจำทั้งหมด การเขียนไปยัง disk ยังมีข้อดีในด้านการดำเนินงาน: ไฟล์บน disk สามารถ backup, ตรวจสอบ, และวิเคราะห์โดย utilities ภายนอกได้ง่าย

ผลิตภัณฑ์เช่น VoltDB, SingleStore, และ Oracle TimesTen เป็น in-memory databases ที่มี relational model และผู้ขายอ้างว่าพวกมันสามารถให้การปรับปรุงประสิทธิภาพอย่างมากโดยการลบ overheads ทั้งหมดที่เกี่ยวข้องกับการจัดการ on-disk data structures [ 46 , 47 ] RAMCloud เป็น open source in-memory key-value store ที่มีความทนทาน (ใช้ log-structured approach สำหรับข้อมูลทั้งในหน่วยความจำและบน disk) [ 48 ] Redis และ Couchbase ให้ความทนทานที่อ่อนแอโดยการเขียนไปยัง disk แบบ asynchronous

ที่น่าสนใจคือ ข้อได้เปรียบด้านประสิทธิภาพของ in-memory databases ไม่ได้เกิดจากการที่ไม่ต้องอ่านจาก disk แม้แต่ disk-based storage engine อาจไม่ต้องอ่านจาก disk ถ้าคุณมีหน่วยความจำเพียงพอ เพราะ operating system ก็ cache disk blocks ที่เพิ่งใช้ในหน่วยความจำอยู่แล้ว แต่พวกมันเร็วกว่าเพราะหลีกเลี่ยง overheads ของการเข้ารหัส in-memory data structures ในรูปแบบที่สามารถเขียนไปยัง disk [ 49 ]

นอกจาก ประสิทธิภาพแล้ว อีก use case ที่น่าสนใจของ in-memory databases คือการให้ data models ที่ยากที่จะ implement ด้วย disk-based indexes ตัวอย่างเช่น Redis มี interface คล้าย database สำหรับ data structures ต่างๆ เช่น priority queues และ sets เนื่องจากมันเก็บข้อมูลทั้งหมดในหน่วยความจำ การ implement จึงค่อนข้างง่าย

Data Storage for Analytics (การจัดเก็บข้อมูลสำหรับ Analytics)

โดยทั่วไป data model ของ data warehouse จะเป็น relational เพราะ SQL มักจะเหมาะกับ analytical queries มีเครื่องมือวิเคราะห์ข้อมูล graphical จำนวนมากที่สร้าง SQL queries, แสดงผลลัพธ์, และช่วยให้นักวิเคราะห์สำรวจข้อมูล (ผ่าน operations เช่น drill-down และ slicing and dicing )

เมื่อมองจากภายนอก data warehouse และ relational OLTP database ดูคล้ายกัน เพราะทั้งคู่มี SQL query interface อย่างไรก็ตาม ภายในของระบบอาจดูแตกต่างกันมาก เพราะถูกปรับให้เหมาะกับรูปแบบ query ที่แตกต่างกันอย่างมาก ผู้ผลิตฐานข้อมูลจำนวนมากในปัจจุบันมุ่งเน้นสนับสนุน workloads สำหรับ transaction processing หรือ analytics อย่างใดอย่างหนึ่ง แต่ไม่ใช่ทั้งสองอย่าง

ฐานข้อมูลบางตัว เช่น Microsoft SQL Server, SAP HANA, และ SingleStore รองรับทั้ง transaction processing และ data warehousing ในผลิตภัณฑ์เดียวกัน อย่างไรก็ตาม ฐานข้อมูลแบบ hybrid transactional and analytical processing (HTAP) (ที่แนะนำใน "Data Warehousing" ) เหล่านี้กำลังกลายเป็น storage และ query engines ที่แยกจากกันสองตัวมากขึ้นเรื่อยๆ ซึ่งบังเอิญสามารถเข้าถึงได้ผ่าน SQL interface ทั่วไป [ 50 , 51 , 52 , 53 ]

Cloud Data Warehouses (Data Warehouses บนคลาวด์)

ผู้ผลิต data warehouse ที่มีชื่อเสียง เช่น Teradata, Vertica, และ SAP HANA มีทั้งการติดตั้ง on-premises ภายใต้ใบอนุญาตเชิงพาณิชย์และโซลูชันบนคลาวด์ แต่เมื่อลูกค้าจำนวนมากขึ้นย้ายไปยังคลาวด์ data warehouse แบบ cloud-only ใหม่ เช่น Google Cloud BigQuery, Amazon Redshift, และ Snowflake ก็ถูกนำมาใช้อย่างกว้างขวางเช่นกัน ซึ่งแตกต่างจาก data warehouse แบบดั้งเดิม cloud data warehouses สามารถใช้ประโยชน์จาก scalable cloud infrastructure เช่น object storage และ serverless computation platforms

Cloud data warehouses มักจะ integrate กับบริการคลาวด์อื่นๆ ได้ดีกว่า ตัวอย่างเช่น cloud warehouses จำนวนมากรองรับการ ingestion log อัตโนมัติและมีการ integrate ง่ายกับ data processing frameworks เช่น Google Cloud Dataflow หรือ AWS Kinesis warehouses เหล่านี้ยัง elastic มากขึ้นเพราะพวกมันแยก query computation ออกจาก storage layer [ 54 ] ข้อมูลถูก persist ใน object storage แทนที่จะเป็น local disks ซึ่งทำให้ง่ายต่อการปรับความจุ storage และทรัพยากร computing สำหรับ queries อย่างอิสระ ดังที่เราเห็นใน "Cloud Native System Architecture" .

Open source data warehouses เช่น Apache Hive, Trino, และ Apache Spark ก็ได้วิวัฒนาการไปพร้อมกับคลาวด์เช่นกัน เมื่อ data storage สำหรับ analytics ได้ย้ายไปยัง data lakes บน object storage open source warehouses ก็เริ่มแยกส่วนประกอบ [ 55 ] ส่วนประกอบต่อไปนี้ ซึ่งก่อนหน้านี้ถูกรวมอยู่ในระบบเดียว เช่น Hive ตอนนี้มักถูก implement เป็นส่วนประกอบแยกต่างหาก:

Query engine (Query Engine)

Query engines เช่น Trino, Apache DataFusion, และ Presto แยกวิเคราะห์ SQL queries, ปรับให้เหมาะสมเป็น execution plans, และดำเนินการกับข้อมูล การดำเนินการมักต้องการงานประมวลผลข้อมูลแบบ parallel และ distributed บาง query engines มีการ execution task ในตัว ในขณะที่บางตัวเลือกใช้ execution frameworks ของบุคคลที่สาม เช่น Spark หรือ Flink

Storage format (รูปแบบการจัดเก็บ)

รูปแบบการจัดเก็บกำหนดว่า rows ของ table ถูกเข้ารหัสเป็น bytes ในไฟล์อย่างไร ซึ่งโดยทั่วไปแล้วจะถูกเก็บใน object storage หรือ distributed filesystem [ 12 ] ข้อมูลนี้สามารถเข้าถึงได้ไม่เพียงแค่โดย query engine แต่ยังรวมถึงแอปพลิเคชันอื่นๆ ที่ใช้ data lake ตัวอย่างของรูปแบบการจัดเก็บดังกล่าวคือ Parquet, ORC, Lance, และ Nimble; เราจะพูดถึงพวกมันเพิ่มเติมในหัวข้อถัดไป

Table format (รูปแบบ Table)

ไฟล์ที่เขียนใน Parquet และรูปแบบการจัดเก็บที่คล้ายกันโดยทั่วไปจะ immutable เมื่อเขียนแล้ว เพื่อรองรับการเพิ่มและลบ row รูปแบบ table เช่น Apache Iceberg หรือ Databricks Delta format สามารถใช้ได้ รูปแบบ table ระบุรูปแบบไฟล์ที่กำหนดว่าไฟล์ใดประกอบเป็น table พร้อมกับ schema ของ table รูปแบบดังกล่าวยังมีคุณสมบัติขั้นสูง เช่น time travel (ความสามารถในการ query table ณ จุดเวลาก่อนหน้า), GC, และแม้แต่ transactions

Data catalog (Data Catalog)

เช่นเดียวกับที่รูปแบบ table กำหนดว่าไฟล์ใดประกอบเป็น table data catalog กำหนดว่า table ใดอยู่ใน database Catalogs ใช้เพื่อสร้าง, เปลี่ยนชื่อ, และลบ tables ซึ่งแตกต่างจาก storage และ table formats data catalogs เช่น Snowflake Polaris และ Databricks Unity Catalog มักจะทำงานเป็น standalone service ที่สามารถ query ได้โดยใช้ REST interface Apache Iceberg ก็มี catalog ซึ่งสามารถรันภายใน client หรือเป็น process แยกต่างหาก Query engines ใช้ข้อมูล catalog เมื่ออ่านและเขียน tables โดยแล้ว catalogs และ query engines ถูกรวมเข้าด้วยกัน แต่การแยกพวกมันได้ทำให้ระบบ data discovery และ data governance (ที่พูดถึงใน "Data Systems, Law, and Society" ) สามารถเข้าถึง metadata ของ catalog ได้เช่นกัน

Column-Oriented Storage (การจัดเก็บแบบ Column-Oriented)

ดังที่ได้กล่าวถึงใน "Stars and Snowflakes: Schemas for Analytics" data warehouses โดย convention มักใช้ relational schema ที่มี fact table ขนาดใหญ่ซึ่งมี foreign-key references ไปยัง dimension tables ถ้าคุณมีข้อมูลนับล้านล้าน rows และ petabytes ใน fact tables ของคุณ การจัดเก็บและ query พวกมันอย่างมีประสิทธิภาพกลายเป็นความท้าทาย Dimension tables มักจะเล็กกว่าและจัดการได้ง่ายกว่า (หลายล้าน rows) ดังนั้นในส่วนนี้เราจะ focus กับการจัดเก็บ facts

แม้ว่า fact tables มักจะกว้างเกินหนึ่งร้อย columns แต่ data warehouse query ทั่วไปเข้าถึงเพียงสี่หรือห้า columns ในครั้งเดียว ( SELECT * queries ไม่ค่อยจำเป็นสำหรับ analytics) [ 52 ] ยกตัวอย่าง query ใน Example 4-1 : มันเข้าถึง rows จำนวนมาก (ทุกครั้งที่มีคนซื้อผลไม้หรือลูกอมในช่วงปี 2024) แต่มันต้องการเข้าถึงเพียงสาม columns ของตาราง fact_sales : date_key , product_sk , และ quantity query ไม่สนใจ columns อื่นๆ ทั้งหมด

Example 4-1. การวิเคราะห์ว่าผู้คนมักจะซื้อผลไม้สดหรือลูกอมมากกว่ากัน ขึ้นอยู่กับวันในสัปดาห์
SELECT
  dim_date.weekday, dim_product.category,
  SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
  JOIN dim_date    ON fact_sales.date_key   = dim_date.date_key
  JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
  dim_date.year = 2024 AND
  dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
  dim_date.weekday, dim_product.category;

เราจะดำเนินการ query นี้อย่างมีประสิทธิภาพได้อย่างไร?

ในฐานข้อมูล OLTP ส่วนใหญ่ storage จะถูกจัดวางในรูปแบบ row-oriented : ค่าทั้งหมดจากหนึ่ง row ของ table จะถูกเก็บติดกัน Document databases ก็คล้ายกัน: ทั้ง document มักถูกเก็บเป็นลำดับ bytes ที่ต่อเนื่องกัน คุณสามารถเห็นสิ่งนี้ในตัวอย่าง CSV ใน Figure 4-1 .

เพื่อประมวลผล query เช่นใน Example 4-1 คุณอาจมี indexes บน fact_sales.date_key และ/หรือ fact_sales.product_sk ที่บอก storage engine ว่าจะหา sales ทั้งหมดสำหรับวันที่หรือผลิตภัณฑ์ที่กำหนดได้ที่ไหน แต่แล้ว row-oriented storage engine ก็ยังต้องโหลด rows ทั้งหมดเหล่านั้น (แต่ละ row ประกอบด้วยมากกว่า 100 attributes) จาก disk เข้าสู่หน่วยความจำ, parse พวกมัน, และกรอง rows ที่ไม่ตรงตามเงื่อนไขออก ซึ่งอาจใช้เวลานาน

แนวคิดเบื้องหลัง column-oriented (หรือ columnar ) storage นั้นง่าย: แทนที่จะเก็บค่าทั้งหมดจากหนึ่ง row ด้วยกัน ให้เก็บค่าทั้งหมดจากแต่ละ column ด้วยกันแทน [ 56 ] ถ้าแต่ละ column ถูกเก็บแยกกัน query ต้องอ่านและ parse เฉพาะ columns ที่ใช้ใน query นั้น ซึ่งสามารถประหยัดงานได้มาก Figure 4-7 แสดงหลักการนี้โดยใช้เวอร์ชันขยายของ fact table จาก Figure 3-5 .

Note

Column storage เข้าใจง่ายที่สุดใน relational data model แต่มันใช้ได้กับข้อมูล nonrelational เช่นกัน ตัวอย่างเช่น Parquet เป็น columnar storage format ที่รองรับ document data model [ 57 ] โดยอ้างอิงจาก Google Dremel [ 58 ] โดยใช้เทคนิคที่เรียกว่า shredding หรือ striping [ 59 ]

Diagram comparing traditional row-based storage and columnar storage layout for relational data.

Figure 4-7. Storing relational data by column rather than by row (การจัดเก็บข้อมูล relational โดยแยกตาม column แทนที่จะเป็น row)

การจัดวางแบบ column-oriented อาศัยแต่ละ column ในการเก็บ rows ในลำดับเดียวกัน ดังนั้น ถ้าคุณต้องการประกอบทั้ง row ขึ้นมาใหม่ คุณสามารถนำ entry ที่ 23 จากแต่ละ column แต่ละตัวมารวมกันเพื่อสร้าง row ที่ 23 ของ table

ในทางปฏิบัติ columnar storage engines ไม่ได้เก็บทั้ง column (ซึ่งอาจมีหลายล้านล้าน rows) ในครั้งเดียว แต่พวกมันแบ่ง table เป็น blocks ของหลายพันหรือหลายล้าน rows และภายในแต่ละ block พวกมันเก็บค่าจากแต่ละ column แยกกัน [ 60 ] เนื่องจาก queries จำนวนมากจำกัดอยู่ที่ช่วงวันที่ที่แน่นอน จึงเป็นเรื่องปกติที่จะทำให้แต่ละ block มี rows สำหรับช่วง timestamp ที่กำหนด จากนั้น query ต้องโหลดเฉพาะ columns ที่ต้องการใน blocks ที่ทับซ้อนกับช่วงวันที่ที่ต้องการเท่านั้น

Columnar storage ถูกใช้ใน analytical databases เกือบทั้งหมดในปัจจุบัน [ 60 ] ตั้งแต่ cloud data warehouses ขนาดใหญ่ เช่น Snowflake [ 61 ] ไปจนถึง single-node embedded databases เช่น DuckDB [ 62 ] และระบบ product analytics เช่น Pinot [ 63 ] และ Druid [ 64 ] มันถูกใช้ใน storage formats เช่น Parquet, ORC [ 65 , 66 ], Lance [ 67 ], และ Nimble [ 68 ] และใน-memory analytics formats เช่น Apache Arrow [ 65 , 69 ] และ Pandas/NumPy [ 70 ] ฐานข้อมูล time-series บางตัว เช่น InfluxDB IOx [ 71 ] และ TimescaleDB [ 72 ] ก็อ้างอิงจาก column-oriented storage เช่นกัน

Column compression (การบีบอัด Column)

นอกจากการโหลดจาก disk เฉพาะ columns ที่จำเป็นสำหรับ query แล้ว เรายังสามารถลดความต้องการ disk throughput และ network bandwidth ได้โดยการบีบอัดข้อมูล โชคดีที่ column-oriented storage มักจะเหมาะกับการบีบอัดเป็นอย่างมาก

ลองดู sequences ของค่าสำหรับแต่ละ column ใน Figure 4-7 มีการซ้ำกันพอสมควร ซึ่งเป็นสัญญาณที่ดีสำหรับการบีบอัด ขึ้นอยู่กับข้อมูลใน column เทคนิคการบีบอัดที่แตกต่างกันสามารถใช้ได้ [ 73 ] เทคนิคหนึ่งที่ได้ผลดีเป็นพิเศษใน data warehouses คือ bitmap encoding ดังที่แสดงใน Figure 4-8 .

Diagram illustrating bitmap indexes for a column with various values and their corresponding run-length encoding, highlighting how repetitive data can be efficiently compressed.

Figure 4-8. Compressed, bitmap-indexed storage of a single column (การจัดเก็บ column เดียวแบบบีบอัดและทำ bitmap index)

บ่อยครั้งที่จำนวนค่าที่แตกต่างกันใน column มีน้อยเมื่อเทียบกับจำนวน rows (ตัวอย่างเช่น ร้านค้าปลีกอาจมีธุรกรรมการขายหลายพันล้านรายการ แต่มีสินค้าแตกต่างกันเพียง 100,000 รายการ) ตอนนี้เราสามารถนำ column ที่มีค่าแตกต่างกัน n ค่าและแปลงเป็น n bitmaps แยกกัน: หนึ่ง bitmap สำหรับแต่ละค่าที่แตกต่างกัน โดยมีหนึ่ง bit ต่อหนึ่ง row bit จะเป็น 1 ถ้า row มีค่านั้น และ 0 ถ้าไม่มี

หนึ่ง ตัวเลือกคือการเก็บ bitmaps โดยใช้หนึ่ง bit ต่อหนึ่ง row อย่างไรก็ตาม bitmaps เหล่านี้มักจะมี 0 เป็นจำนวนมาก (เราเรียกว่ามัน sparse ) ในกรณีนั้น bitmaps สามารถถูก run-length encoded เพิ่มเติม ซึ่งเกี่ยวข้องกับการนับ 0 หรือ 1 ที่ต่อเนื่องกันและเก็บ counts ดังที่แสดงที่ด้านล่างของ Figure 4-8 เทคนิคเช่น roaring bitmaps สลับระหว่างการแสดง bitmap สองแบบ โดยใช้แบบที่ compact ที่สุด [ 74 ] ซึ่งทำให้การเข้ารหัส column มีประสิทธิภาพอย่างน่าทึ่ง

Bitmap indexes เช่นนี้เหมาะอย่างยิ่งสำหรับ queries ที่พบได้ทั่วไปใน data warehouse ตัวอย่างเช่น:

WHERE product_sk IN (31, 68, 69)

โหลดสาม bitmaps สำหรับ product_sk = 31 , product_sk = 68 , และ product_sk = 69 และคำนวณ bitwise OR ของสาม bitmaps ซึ่งสามารถทำได้อย่างมีประสิทธิภาพมาก

WHERE product_sk = 30 AND store_sk = 3

โหลด bitmaps สำหรับ product_sk = 30 และ store_sk = 3 และคำนวณ bitwise AND สิ่งนี้ใช้ได้เพราะ columns มี rows ในลำดับเดียวกัน ดังนั้น k th bit ใน bitmap ของ column หนึ่งตรงกับ row เดียวกับ k th bit ใน bitmap ของอีก column หนึ่ง

Bitmaps ยังสามารถใช้เพื่อตอบ graph queries เช่น การหาผู้ใช้ทั้งหมดของ social network ที่ถูกติดตามโดย user X และที่ติดตาม user Y ด้วย [ 75 ]

Note

อย่าสับสนระหว่าง column-oriented databases กับ wide-column (หรือที่เรียกว่า column-family ) data model ซึ่ง row สามารถมีหลายพัน columns และไม่จำเป็นต้องให้ทุก rows มี columns เหมือนกัน [ 9 ] แม้จะมีชื่อที่คล้ายคลึงกัน แต่ wide-column databases เป็น row-oriented เพราะพวกมันเก็บค่าทั้งหมดจาก row ไว้ด้วยกัน Google Bigtable, Apache Accumulo, และ HBase เป็นตัวอย่างของระบบที่ใช้ wide-column model

Sort order in column storage (ลำดับการเรียงในการจัดเก็บแบบ Column)

ในการจัดเก็บแบบ column store ลำดับที่เก็บ rows ไม่ได้สำคัญเสมอไป วิธีที่ง่ายที่สุดคือเก็บตามลำดับที่ถูกแทรก เนื่องจากการแทรก row ใหม่ก็แค่ต่อท้ายแต่ละ columns อย่างไรก็ตาม เราสามารถเลือกที่จะกำหนดลำดับได้ เหมือนที่เราทำกับ SSTables ก่อนหน้านี้ และใช้มันเป็นกลไกการทำ index

ข้อควรทราบ: การเรียงลำดับแต่ละ column อย่างอิสระนั้นไม่สมเหตุสมผล เพราะเราจะไม่รู้ว่าชิ้นส่วนใดใน columns เป็นของ row เดียวกัน เราสามารถสร้าง row ขึ้นมาใหม่ได้ก็ต่อเมื่อเรารู้ว่า k th item ใน column หนึ่งเป็นของ row เดียวกับ k th item ในอีก column หนึ่ง

ข้อมูลต้องถูกจัดเรียงทั้ง row ในครั้งเดียว แม้ว่ามันจะถูกเก็บตาม column ก็ตาม ผู้ดูแลฐานข้อมูลสามารถเลือก columns ที่ใช้ในการเรียงลำดับ table โดยใช้ความรู้เกี่ยวกับ queries ที่พบบ่อย ตัวอย่างเช่น ถ้า queries มักจะอ้างถึงช่วงวันที่ เช่นเดือนที่แล้ว มันอาจสมเหตุสมผลที่จะให้ date_key เป็น sort key แรก จากนั้น query สามารถ scan เฉพาะ rows จากเดือนที่แล้ว ซึ่งจะเร็วกว่าการ scan ทุก rows มาก

column ที่สองสามารถกำหนดลำดับการเรียงของ rows ที่มีค่าเดียวกันใน column แรก ตัวอย่างเช่น ถ้า date_key เป็น sort key แรกใน Figure 4-7 มันอาจสมเหตุสมผลให้ product_sk เป็น sort key ที่สองเพื่อให้ sales ทั้งหมดสำหรับผลิตภัณฑ์เดียวกันในวันเดียวกันถูกจัดกลุ่มในการจัดเก็บ ซึ่งจะช่วย queries ที่ต้องการ group หรือ filter sales ตามผลิตภัณฑ์ภายในช่วงวันที่ที่กำหนด

ข้อดีอีกอย่างของลำดับการเรียงคือมันช่วยในการบีบอัด columns ถ้า primary sort column ไม่มีค่าที่แตกต่างกันมากนัก หลังจากการเรียง มันจะมี sequences ยาวๆ ที่ค่าเดียวกันถูกซ้ำหลายครั้งติดต่อกัน run-length encoding ง่ายๆ แบบที่เราใช้สำหรับ bitmaps ใน Figure 4-8 สามารถบีบอัด column นั้นลงเหลือไม่กี่กิโลไบต์—แม้ว่า table จะมีหลายพันล้าน rows

ผลการบีบอัดนั้นแรงที่สุดใน sort key แรก sort keys ที่สองและสามจะยุ่งเหยิงมากขึ้น ดังนั้นจะไม่มี runs ของค่าที่ซ้ำกันยาวขนาดนั้น columns ที่อยู่ถัดลงไปในลำดับความสำคัญของการเรียงจะปรากฏในลำดับที่สุ่มเป็นส่วนใหญ่ ดังนั้นพวกมันอาจบีบอัดได้ไม่ดีนัก อย่างไรก็ตาม การมีสองสาม columns แรกเรียงลำดับก็เป็นผลดีโดยรวม

Writing to column-oriented storage (การเขียนไปยัง Column-Oriented Storage)

เราเห็นใน "Characterizing Transaction Processing and Analytics" ว่า reads ใน data warehouses มักประกอบด้วย aggregations เหนือ rows จำนวนมาก Column-oriented storage, compression, และการเรียงลำดับทั้งหมดช่วยให้ read queries เหล่านั้นเร็วขึ้น

Writes ใน data warehouses มักจะเป็น bulk imports ของข้อมูล ซึ่งมักผ่านกระบวนการ ETL ด้วย columnar storage การเขียนแต่ละ row ตรงกลางของ sorted table จะไม่มีประสิทธิภาพอย่างมาก เพราะคุณต้องเขียน columns ที่ถูกบีบอัดทั้งหมดใหม่ตั้งแต่ตำแหน่งที่แทรกเป็นต้นไป อย่างไรก็ตาม การเขียน bulk หลาย rows พร้อมกันจะ amortize ต้นทุนของการเขียน columns เหล่านั้นใหม่ ทำให้มีประสิทธิภาพ

แนวทาง log-structured มักใช้ในการดำเนิน writes เป็น batch writes ทั้งหมดไปที่ row-oriented, sorted, in-memory store ก่อน เมื่อ writes สะสมมากพอ พวกมันจะถูกรวมกับ column-encoded files บน disk และเขียนไปยังไฟล์ใหม่เป็น bulk เนื่องจากไฟล์เก่ายังคง immutable และไฟล์ใหม่ถูกเขียนในครั้งเดียว object storage จึงเหมาะสมสำหรับการเก็บไฟล์เหล่านี้

Queries ต้องตรวจสอบทั้ง column data บน disk และ writes ล่าสุดในหน่วยความจำ และรวมทั้งสองเข้าด้วยกัน query execution engine ซ่อนความแตกต่างนี้จากผู้ใช้ จากมุมมองของนักวิเคราะห์ ข้อมูลที่ถูกแก้ไขด้วย inserts, updates, หรือ deletes จะสะท้อนทันทีใน queries ที่ตามมา Snowflake, Vertica, Apache Pinot, Apache Druid, และฐานข้อมูลอื่นๆ อีกมากมายทำแบบนี้ [ 61 , 63 , 64 , 76 ]

Query Execution: Compilation and Vectorization (การดำเนินการ Query: การ Compile และ Vectorization)

SQL query ที่ซับซ้อนสำหรับ analytics จะถูกแบ่งออกเป็น query plan ที่ประกอบด้วยหลายขั้นตอน เรียกว่า operators ซึ่งอาจถูกกระจายข้ามหลายเครื่องสำหรับการดำเนินการแบบ parallel ผู้วางแผน query สามารถทำการ optimizations ได้มากมายโดยการเลือก operators ที่จะใช้ ลำดับการดำเนินการ และตำแหน่งที่จะรันแต่ละ operator

ภายในแต่ละ operator query engine อาจต้องทำสิ่งต่างๆ กับค่าใน column เช่น การหา rows ทั้งหมดที่ค่าอยู่ในชุดค่าที่กำหนด (อาจเป็นส่วนหนึ่งของ join) หรือการตรวจสอบว่าค่ามากกว่า เช่น 15 query engine อาจต้องดูหลาย columns สำหรับ row เดียว—เช่น การหาธุรกรรมการขายทั้งหมดที่สินค้าคือ "bananas" และร้านค้าคือร้านที่สนใจ

สำหรับ data warehouse queries ที่ต้อง scan หลายล้าน rows เราต้องกังวลไม่เพียงแค่ปริมาณข้อมูลที่ต้องอ่านจาก disk แต่ยังรวมถึง CPU time ที่ต้องใช้ในการดำเนินการ operators ที่ซับซ้อนด้วย operator ที่ง่ายที่สุดก็เหมือน interpreter สำหรับ programming language ในขณะที่ iterating ผ่านแต่ละ row มันจะตรวจสอบ data structure ที่แสดงถึง query เพื่อหาว่าต้องทำ comparisons หรือ calculations ใดบน columns ไหน น่าเสียดายที่วิธีนี้ช้าเกินไปสำหรับวัตถุประสงค์ analytics หลายอย่าง แนวทางทางเลือกสองแบบสำหรับการดำเนินการ query ที่มีประสิทธิภาพได้เกิดขึ้น [ 77 ]:

Query compilation (การ Compile Query)

query engine รับ SQL query และสร้าง code สำหรับการดำเนินการ code จะ iterate ผ่าน rows ทีละตัว ดูค่าต่างๆ ใน columns ที่สนใจ ทำ comparisons หรือ calculations ที่จำเป็น และคัดลอกค่าที่ต้องการไปยัง output buffer ถ้าเงื่อนไขที่ต้องการเป็นไปตามที่กำหนด จากนั้น query engine จะ compile code ที่สร้างขึ้นเป็น machine code (มักใช้ compiler ที่มีอยู่ เช่น LLVM) และรันมันบนข้อมูลที่เข้ารหัสแบบ column ที่ถูกโหลดเข้าสู่หน่วยความจำ แนวทางการสร้าง code นี้ คล้ายกับ just-in-time (JIT) compilation approach ที่ใช้ใน Java Virtual Machine (JVM) และ runtimes ที่คล้ายกัน

Vectorized processing (การประมวลผลแบบ Vectorized)

query ถูก interpreted ไม่ใช่ compiled แต่มันถูกทำให้เร็วโดยการประมวลผลหลายค่าจาก column ใน batch แทนที่จะ iterate ผ่าน rows ทีละตัว ชุดของ predefined operators ที่ตายตัวถูก built-in ใน database; เราสามารถส่ง arguments ให้พวกมันและรับผลลัพธ์เป็น batch กลับมา [ 50 , 73 ]

ตัวอย่างเช่น เราสามารถส่ง column product_sk และ ID ของผลิตภัณฑ์ (สมมติว่า "bananas") ไปยัง equality operator และรับ bitmap กลับมา (หนึ่ง bit ต่อหนึ่งค่าใน input column ซึ่งเป็น 1 ถ้าตรงกับ ID นั้น) จากนั้นเราสามารถส่ง column store_sk และ ID ของร้านค้าที่สนใจไปยัง equality operator เดียวกัน และรับ bitmap อีกตัว สุดท้ายเราสามารถส่ง bitmaps สองตัวไปยัง bitwise AND operator ดังที่แสดงใน Figure 4-9 ; ผลลัพธ์จะเป็น bitmap ที่มี 1 สำหรับทุกการขายกล้วยในร้านค้าเฉพาะ

Diagram showing a bitwise AND operation between two bitmaps representing product and store IDs, resulting in a compressed bitmap for sales data.

Figure 4-9. A bitwise AND between two bitmaps lends itself to vectorization. (bitwise AND ระหว่าง bitmaps สองตัวเหมาะกับ vectorization)

ทั้งสองแนวทางแตกต่างกันมากในแง่ของการ implement แต่ทั้งคู่ถูกใช้ในทางปฏิบัติ [ 77 ] ทั้งคู่สามารถให้ประสิทธิภาพที่ดีมากโดยการใช้ประโยชน์จากคุณลักษณะของ CPUs สมัยใหม่:

  • ชอบการเข้าถึงหน่วยความจำแบบ sequential มากกว่า random access เพื่อลด cache misses [ 78 ]

  • ทำงานส่วนใหญ่ใน tight inner loops (เช่น มี instructions จำนวนน้อยและไม่มี function calls) เพื่อให้ CPU instruction processing pipeline ไม่ว่างและหลีกเลี่ยง branch mispredictions

  • ใช้ ประโยชน์จาก parallelism เช่น multiple threads และ single-instruction, multiple data (SIMD) instructions [ 79 , 80 ]

  • ดำเนินการโดยตรงกับข้อมูลที่บีบอัดโดยไม่ต้องถอดรหัสเป็น in-memory representation แยกต่างหาก ซึ่งประหยัดค่าใช้จ่ายในการจัดสรรและคัดลอกหน่วยความจำ

Materialized Views and Data Cubes (Materialized Views และ Data Cubes)

เราเคยพบ materialized views มาก่อนใน "Materializing and Updating Timelines" : ใน relational data model พวกมันเป็นวัตถุคล้าย table ที่มีเนื้อหาเป็นผลลัพธ์ของ query materialized view คือสำเนาจริงของผลลัพธ์ query ที่เขียนไปยัง disk ในขณะที่ virtual view เป็นเพียงทางลัดสำหรับการเขียน queries เมื่อคุณอ่านจาก virtual view SQL engine จะขยายมันเป็น query พื้นฐานของ view แบบทันทีทันใดแล้วประมวลผล query ที่ขยายแล้ว

เมื่อข้อมูลพื้นฐานเปลี่ยนแปลง materialized view ต้องถูกอัปเดตตาม ฐานข้อมูลบางตัวสามารถทำได้โดยอัตโนมัติ และยังมีระบบเช่น Materialize ที่เชี่ยวชาญในการบำรุงรักษา materialized view [ 81 ] เราจะกลับมาที่หัวข้อนี้ใน "Maintaining materialized views" การอัปเดตดังกล่าวหมายถึงงานมากขึ้นใน writes แต่ materialized views สามารถปรับปรุง read performance ใน workloads ที่ต้องดำเนินการ queries เดิมซ้ำๆ

Materialized aggregates เป็น ประเภทของ materialized view ที่มีประโยชน์ใน data warehouses ดังที่ได้กล่าวไว้ก่อนหน้านี้ data warehouse queries มักเกี่ยวข้องกับ aggregate function เช่น COUNT , SUM , AVG , MIN , หรือ MAX ใน SQL ถ้า aggregates เดียวกันถูกใช้โดยหลาย queries การคำนวณผ่าน raw data ทุกครั้งอาจเป็นการสิ้นเปลือง ทำไมไม่ cache counts หรือ sums ที่ queries ใช้บ่อยที่สุดล่ะ? Data cube (หรือที่เรียกว่า OLAP cube ) ทำสิ่งนี้โดยการสร้างกริดของ aggregates ที่จัดกลุ่มตามมิติต่างๆ [ 82 ] Figure 4-10 แสดงตัวอย่าง

Diagram showing a two-dimensional data cube with date keys along one axis and product keys along the other, illustrating the aggregation of sales data by summing net prices across various combinations.

Figure 4-10. Two dimensions of a data cube, aggregating data by summing (สองมิติของ data cube รวมข้อมูลโดยการ sum)

สมมติว่าตอนนี้แต่ละ fact มี foreign keys ไปยัง dimension tables เพียงสองตาราง ใน Figure 4-10 สิ่งเหล่านี้คือ date_key และ product_sk คุณสามารถวาดตารางสองมิติ โดยมีวันที่อยู่ตามแกนหนึ่งและผลิตภัณฑ์ตามอีกแกนหนึ่ง แต่ละ cell มี aggregate (เช่น SUM ) ของ attribute (เช่น net_price ) ของ facts ทั้งหมดที่มีชุดวันที่–ผลิตภัณฑ์นั้น จากนั้นคุณสามารถใช้ aggregate เดียวกันตามแต่ละ row หรือ column และได้รับสรุปที่ถูกลดหนึ่งมิติ (ยอดขายตามผลิตภัณฑ์ไม่ว่าจะวันที่ใด หรือยอดขายตามวันที่ไม่ว่าจะเป็นผลิตภัณฑ์ใด)

โดยทั่วไป facts มักมีมากกว่าสองมิติ ใน Figure 3-5 มีห้ามิติ: date, product, store, promotion, และ customer มันยากกว่ามากที่จะจินตนาการว่า hypercube ห้ามิติจะมีลักษณะอย่างไร แต่หลักการยังคงเหมือนเดิม: แต่ละ cell มียอดขายสำหรับชุดวันที่–ผลิตภัณฑ์–ร้านค้า–โปรโมชัน–ลูกค้าเฉพาะ ค่าเหล่านี้สามารถสรุปซ้ำๆ ตามแต่ละมิติได้

ข้อดีของ materialized data cube คือ queries บางอย่างเร็วมากเพราะพวกมันถูก precomputed อย่างมีประสิทธิภาพ ตัวอย่างเช่น ถ้าคุณต้องการทราบยอดขายรวมต่อร้านค้าเมื่อวานนี้ คุณแค่ต้องดู totals ตามมิติที่เหมาะสม—ไม่ต้อง scan หลายล้าน rows

ข้อเสียคือ data cube ไม่มีความยืดหยุ่นเท่ากับการ query ข้อมูลดิบ ตัวอย่างเช่น ไม่มีวิธีคำนวณสัดส่วนของยอดขายที่มาจากสินค้าที่มีราคามากกว่า $100 เพราะราคาไม่ใช่หนึ่งในมิติ data warehouses ส่วนใหญ่จึงพยายามเก็บ raw data ให้มากที่สุดและใช้ aggregates เช่น data cubes เป็นเพียงการเพิ่มประสิทธิภาพสำหรับ queries บางอย่าง

Multidimensional and Full-Text Indexes (Indexes แบบหลายมิติและ Full-Text)

B-trees และ LSM-trees ที่เราเห็นในครึ่งแรกของบทนี้รองรับ range queries เหนือ attribute เดียว ตัวอย่างเช่น ถ้า key คือ username คุณสามารถใช้พวกมันเป็น index เพื่อค้นหาชื่อทั้งหมดที่ขึ้นต้นด้วย L ได้อย่างมีประสิทธิภาพ แต่บางครั้งการค้นหาด้วย attribute เดียวนั้นไม่เพียงพอ

ประเภทของ multicolumn index ที่พบบ่อยที่สุดเรียกว่า concatenated index ซึ่งรวมหลาย fields เป็น key เดียวโดยการต่อ column หนึ่งเข้ากับอีก column หนึ่ง (คำจำกัดความของ index ระบุลำดับที่ fields ถูก concatenated) เหมือนกับสมุดโทรศัพท์กระดาษแบบเก่า ที่ให้ index จาก ( lastname , firstname ) ไปยังหมายเลขโทรศัพท์ เนื่องจากการเรียงลำดับ index สามารถใช้ค้นหาทุกคนที่มีนามสกุลเฉพาะ หรือทุกคนที่มี lastname–firstname รวมกันที่กำหนด อย่างไรก็ตาม index ไร้ประโยชน์ถ้าคุณต้องการหาทุกคนที่มีชื่อเฉพาะ

ในทางกลับกัน multidimensional indexes ช่วยให้คุณ query หลาย columns พร้อมกัน สิ่งนี้สำคัญเป็นพิเศษสำหรับข้อมูล geospatial ตัวอย่างเช่น เว็บไซต์ค้นหาร้านอาหารอาจมี database ที่มีละติจูดและลองจิจูดของแต่ละร้านอาหาร เมื่อผู้ใช้ดูร้านอาหารบนแผนที่ เว็บไซต์ต้องค้นหาร้านอาหารทั้งหมดภายในพื้นที่แผนที่สี่เหลี่ยมที่ผู้ใช้กำลังดูอยู่ ซึ่งต้องใช้ two-dimensional range query เช่น:

SELECT * FROM restaurants WHERE latitude  > 51.4946 AND latitude  < 51.5079
                            AND longitude > -0.1162 AND longitude < -0.1004;

concatenated index บน columns latitude และ longitude ไม่สามารถตอบคำถามประเภทนั้นได้อย่างมีประสิทธิภาพ index สามารถให้ร้านอาหารทั้งหมดในช่วงละติจูด (แต่ที่ลองจิจูดใดก็ได้) หรือร้านอาหารทั้งหมดในช่วงลองจิจูด (แต่ที่ใดก็ได้ระหว่างขั้วโลกเหนือและใต้) แต่ไม่ใช่ทั้งสอง พร้อมกัน .

ตัวเลือกหนึ่งคือการแปลงตำแหน่งสองมิติเป็นตัวเลขเดียวผ่าน space-filling curve จากนั้นใช้ regular B-tree index [ 83 ] โดยทั่วไปแล้ว specialized spatial indexes เช่น R-trees หรือ Bkd-trees [ 84 ] มักใช้; พวกมันแบ่งพื้นที่เพื่อให้ data points ที่ใกล้เคียงกันมักจะถูกจัดกลุ่มใน subtree เดียวกัน ตัวอย่างเช่น PostGIS implement geospatial indexes เป็น R-trees โดยใช้ Generalized Search Tree indexing facility ของ PostgreSQL [ 85 ] นอกจากนี้ยังสามารถใช้กริดของสามเหลี่ยม สี่เหลี่ยมจัตุรัส หรือหกเหลี่ยมที่มีระยะห่างสม่ำเสมอ [ 86 ]

อย่างไรก็ตาม multidimensional indexes ไม่ได้มีไว้สำหรับตำแหน่งทางภูมิศาสตร์เท่านั้น ตัวอย่างเช่น ในเว็บไซต์ ecommerce คุณสามารถใช้ three-dimensional index บนมิติ ( red , green , blue ) เพื่อค้นหาผลิตภัณฑ์ในช่วงสีที่กำหนด หรือใน database ของการสังเกตการณ์สภาพอากาศ คุณสามารถมี two-dimensional index บน ( date , temperature ) เพื่อค้นหาการสังเกตการณ์ทั้งหมดในปีที่กำหนดที่อุณหภูมิอยู่ระหว่าง 25°C ถึง 30°C อย่างมีประสิทธิภาพ ด้วย one-dimensional index คุณต้อง scan ทุก records จากปีนั้น (โดยไม่คำนึงถึงอุณหภูมิ) แล้วกรองตามอุณหภูมิ หรือกลับกัน two-dimensional index สามารถจำกัดผลลัพธ์ตาม timestamp และอุณหภูมิพร้อมกัน [ 87 ]

Full-Text Search (การค้นหาแบบ Full-Text)

Full-text search ช่วยให้คุณค้นหาชุดของเอกสารข้อความ (หน้าเว็บ, คำอธิบายผลิตภัณฑ์, ฯลฯ) โดยใช้ keywords ที่อาจปรากฏที่ใดก็ได้ในข้อความ [ 88 ] Information retrieval เป็นหัวข้อใหญ่และเฉพาะทางที่มักเกี่ยวข้องกับการประมวลผลเฉพาะภาษา; ตัวอย่างเช่น ภาษาเอเชียหลายภาษาเขียนโดยไม่มีช่องว่างหรือเครื่องหมายวรรคตอนระหว่างคำ ดังนั้นการแบ่งข้อความเป็นคำจึงต้องใช้ model ที่ระบุว่าลำดับตัวอักษรใดประกอบเป็นคำ Full-text search ยังมักเกี่ยวข้องกับการจับคู่คำที่คล้ายกันแต่ไม่เหมือนกัน (การจัดการกับการพิมพ์ผิดหรือรูปไวยากรณ์ต่างๆ ของคำ) และคำพ้องความหมาย ปัญหาเหล่านั้นอยู่นอกเหนือขอบเขตของหนังสือเล่มนี้

อย่างไรก็ตาม ในแก่นของมัน คุณสามารถคิดว่า full-text search เป็น multidimensional query อีกประเภทหนึ่ง ในกรณีนี้ แต่ละคำที่อาจปรากฏในข้อความ (a term ) เป็นมิติหนึ่ง เอกสารที่มี term x มีค่าเป็น 1 ในมิติ x และเอกสารที่ไม่มี x มีค่าเป็น 0 การค้นหาเอกสารที่กล่าวถึง "red apples" หมายถึง query ที่มองหา 1 ในมิติ red และพร้อมกัน มองหา 1 ในมิติ apples จำนวนมิติจึงอาจมีขนาดใหญ่มาก

data structure ที่ search engines จำนวนมากใช้เพื่อตอบ queries ดังกล่าวเรียกว่า inverted index นี่คือ key-value structure ที่ key คือ term และ value คือ list ของ IDs ของเอกสารทั้งหมดที่มี term นั้น (the postings list ) ถ้า document IDs เป็นตัวเลขเรียงตามลำดับ postings list สามารถแสดงเป็น sparse bitmap ได้เช่นใน Figure 4-8 ; n th bit ใน bitmap สำหรับ term x คือ 1 ถ้าเอกสารที่มี ID n มี term x [ 89 ]

การค้นหาเอกสารทั้งหมดที่มีทั้ง term x และ y ตอนนี้คล้ายกับ vectorized data warehouse query ที่ค้นหา rows ที่ตรงกับสองเงื่อนไข ( Figure 4-9 ): โหลด bitmaps สองตัวสำหรับ terms x และ y และคำนวณ bitwise AND ของพวกมัน แม้ว่า bitmaps จะถูก run-length encoded สิ่งนี้ก็สามารถทำได้อย่างมีประสิทธิภาพมาก

ตัวอย่างเช่น Lucene, full-text indexing engine ที่ใช้โดย Elasticsearch และ Solr ทำงานแบบนี้ [ 90 ] มันเก็บ mapping จาก term ไปยัง postings list ในไฟล์ที่เรียงลำดับคล้าย SSTable ซึ่งถูกรวมใน background โดยใช้ log-structured approach เดียวกับที่เราเห็นก่อนหน้านี้ในบทนี้ [ 91 ] PostgreSQL GIN index type ก็ใช้ postings lists เพื่อรองรับ full-text search และ indexing ภายใน JSON documents [ 92 , 93 ]

แทนที่จะแบ่งข้อความเป็นคำ อีกทางเลือกคือการหา substring ทั้งหมดที่มีความยาว n ซึ่งเรียกว่า n -grams ตัวอย่างเช่น trigrams ( n  = 3) ของ string hello คือ hel , ell , และ llo ถ้าเราสร้าง inverted index ของ trigrams ทั้งหมด เราสามารถค้นหาเอกสารสำหรับ substring ใดๆ ที่มีความยาวอย่างน้อยสามตัวอักษร Trigram indexes ยังรองรับ regular expressions ใน search queries; ข้อเสียคือพวกมันค่อนข้างใหญ่ [ 94 ]

เพื่อรับมือกับการพิมพ์ผิดในเอกสารหรือ queries Lucene สามารถค้นหาข้อความสำหรับคำที่อยู่ใน edit distance ที่กำหนด ( edit distance ของ 1 หมายถึงตัวอักษรหนึ่งตัวถูกเพิ่ม ลบ หรือแทนที่) [ 95 ] มันทำโดยการเก็บ set ของ terms เป็น finite state automaton เหนือตัวอักษรใน keys คล้ายกับ trie [ 96 ] และแปลงมันเป็น Levenshtein automaton ซึ่งรองรับการค้นหาคำภายใน edit distance ที่กำหนดอย่างมีประสิทธิภาพ [ 97 ]

Vector Embeddings (Vector Embeddings)

Semantic search ก้าว ไปไกลกว่าคำพ้องความหมายและการพิมพ์ผิดเพื่อพยายามเข้าใจแนวคิดของเอกสารและความตั้งใจของผู้ใช้ มันกำลังกลายเป็นส่วนสำคัญของแอปพลิเคชัน AI เช่น retrieval-augmented generation ซึ่งรวมผลการค้นหาเข้ากับ output ของ large language model (LLM) ตัวอย่างเช่น ถ้าหน้าช่วยเหลือของคุณมีหน้าที่ชื่อว่า "canceling your subscription" ผู้ใช้ควรยังสามารถค้นหาหน้านั้นได้เมื่อค้นหา "how to close my account" หรือ "terminate contract" ซึ่งใกล้เคียงในแง่ของความหมายแม้ว่าจะใช้คำที่แตกต่างกันโดยสิ้นเชิง

เพื่อเข้าใจความหมายของเอกสาร—ความหมายของมัน—semantic search indexes ใช้ embedding models เพื่อแปลเอกสารข้อความเป็น vector ของ floating-point values เรียกว่า vector embedding บ่อยครั้งที่ทำโดยใช้ LLMs vector แทนจุดในพื้นที่หลายมิติ และค่า floating-point แต่ละค่าแทนตำแหน่งของเอกสารตามแกนของมิติหนึ่ง Embedding models สร้าง vector embeddings ที่อยู่ใกล้กัน (ในพื้นที่หลายมิตินี้) เมื่อ input documents มีความหมายคล้ายคลึงกัน

Note

เราเห็นคำว่า vectorized processing ใน "Query Execution: Compilation and Vectorization" Vectors ใน semantic search มีความหมายที่แตกต่างกัน ใน vectorized processing vector หมายถึง batch ของ bits ที่สามารถประมวลผลด้วย code ที่ถูก optimize เป็นพิเศษ ใน embedding models vector คือ array ของ floating -point numbers ที่แทนตำแหน่งในพื้นที่หลายมิติ

ตัวอย่างเช่น three-dimensional vector embedding สำหรับหน้า Wikipedia เกี่ยวกับการเกษตรอาจเป็น [0.38, 0.83, 0.41] หน้า Wikipedia เกี่ยวกับผักจะอยู่ใกล้มาก อาจมี embedding เป็น [0.36, 0.64, 0.67] หน้าเกี่ยวกับ star schemas อาจมี embedding เป็น [0.85, 0.10, -0.52] ซึ่งค่อนข้างไกลออกไป เราสามารถบอกได้โดยการดูว่า vectors สองตัวแรกอยู่ใกล้กันมากกว่าตัวที่สาม

Embedding models ใช้ vectors ที่ใหญ่กว่ามาก (มักเกิน 1,000 ตัวเลข) แต่หลักการก็เหมือนกัน เราไม่ได้พยายามเข้าใจว่าตัวเลขแต่ละตัวหมายถึงอะไร; พวกมันเป็นเพียงวิธีที่ model ใช้ชี้ไปยังตำแหน่งในพื้นที่นามธรรมหลายมิติ Search engines ใช้ distance functions เช่น cosine similarity หรือ Euclidean distance เพื่อวัดระยะห่างระหว่าง vectors: cosine similarity วัดค่า cosine ของมุมของ vectors สองตัวเพื่อกำหนดว่าพวกมันใกล้กันแค่ไหน ในขณะที่ Euclidean distance วัดระยะทางเส้นตรงระหว่างสองจุดในพื้นที่

embedding models ในยุคแรกๆ หลายตัว เช่น Word2Vec [ 98 ], BERT [ 99 ], และ GPT [ 100 ] ทำงานกับข้อมูลข้อความ โดยปกติ model ดังกล่าว implement เป็น neural networks นักวิจัยได้พัฒนา embedding models สำหรับ video, audio, และ images ด้วย เมื่อไม่นานมานี้ สถาปัตยกรรม model ได้กลายเป็น multimodal : model ตัวเดียวสามารถสร้าง vector embeddings สำหรับหลาย modalities เช่น ข้อความและรูปภาพ

Semantic search engines ใช้ embedding model เพื่อสร้าง vector embedding เมื่อผู้ใช้ป้อน query query และบริบทที่เกี่ยวข้อง (เช่น ตำแหน่งของผู้ใช้) จะถูกป้อนเข้าสู่ embedding model หลังจาก embedding model สร้าง vector embedding ของ query แล้ว search engine ต้องค้นหาเอกสารที่มี vector embeddings คล้ายกันโดยใช้ vector index

Vector indexes จัดเก็บ vector embeddings ของชุดเอกสาร ในการ query index คุณส่ง vector embedding ของ query เข้าไป และ index จะส่งคืนเอกสารที่มี vectors ใกล้กับ query vector มากที่สุด เนื่องจาก R-trees ที่เราเห็นก่อนหน้านี้ทำงานได้ไม่ดีกับ vectors ที่มีหลายมิติ จึงใช้ specialized vector indexes แทน เช่น:

Flat indexes (Flat Indexes)

Vectors ถูกเก็บใน index ตามที่เป็นอยู่ query ต้องอ่านทุก vector และวัดระยะทางไปยัง query vector Flat indexes มีความแม่นยำ แต่การวัดระยะทางระหว่าง query และแต่ละ vector นั้นช้า

Inverted file (IVF) indexes (Inverted File Indexes)

พื้นที่ vector ถูกจัดกลุ่มเป็น partitions (เรียกว่า centroids ) ของ vectors เพื่อลดจำนวน vectors ที่ต้องเปรียบเทียบ IVF indexes เร็วกว่า flat indexes แต่ให้ผลลัพธ์แบบ approximate เท่านั้น; query และเอกสารอาจตกอยู่ใน partitions ที่แตกต่างกัน แม้ว่าพวกมันจะอยู่ใกล้กันก็ตาม query บน IVF index ต้องกำหนด probes ก่อน ซึ่งก็คือจำนวน partitions ที่จะตรวจสอบ Queries ที่ใช้ probes มากขึ้นจะแม่นยำกว่าแต่ช้าลง เนื่องจากต้องเปรียบเทียบ vectors มากขึ้น

Hierarchical Navigable Small World (HNSW) indexes (HNSW Indexes)

HNSW indexes รักษาหลาย layers ของ vector space ดังที่แสดงใน Figure 4-11 แต่ละ layer แสดงเป็น graph ที่ nodes แทน vectors และ edges แทนความใกล้ชิดกับ vectors ใกล้เคียง query เริ่มต้นด้วยการหา vector ที่ใกล้ที่สุดใน layer บนสุด ซึ่งมีจำนวน nodes น้อย จากนั้น query ย้ายไปยัง node เดียวกันใน layer ถัดไปและทำตาม edges ใน layer นั้น ซึ่งเชื่อมต่อกันหนาแน่นกว่า มองหา vector ที่ใกล้กับ query vector มากขึ้น กระบวนการดำเนินต่อไปจนถึง layer สุดท้าย เช่นเดียวกับ IVF indexes HNSW indexes เป็น approximate

Diagram illustrating the hierarchical layers in a Hierarchical Navigable Small World (HNSW) index, showing the traversal path of a query vector through interconnected nodes across multiple layers.

Figure 4-11. Searching for the database entry that is closest to a given query vector in an HNSW index (การค้นหา entry ใน database ที่ใกล้กับ query vector ที่กำหนดมากที่สุดใน HNSW index)

ฐานข้อมูล vector ยอดนิยมหลายตัว implement IVF และ HNSW indexes Facebook Faiss library มี variations หลายแบบของแต่ละชนิด [ 101 ] และ PostgreSQL pgvector รองรับทั้งสองแบบ [ 102 ] รายละเอียดเต็มของ algorithms IVF และ HNSW อยู่นอกเหนือขอบเขตของหนังสือเล่มนี้ แต่ papers ของพวกมันเป็นแหล่งข้อมูลที่ยอดเยี่ยม [ 103 , 104 ]

Summary (สรุป)

ในบทนี้เราได้พยายามทำความเข้าใจว่าฐานข้อมูลดำเนินการจัดเก็บและค้นคืนข้อมูลอย่างไร สิ่งที่เกิดขึ้นเมื่อคุณเก็บข้อมูลในฐานข้อมูล และสิ่งที่ฐานข้อมูลทำเมื่อคุณ query ข้อมูลนั้นอีกครั้งในภายหลัง

"Operational Versus Analytical Systems" ได้แนะนำความแตกต่างระหว่าง transaction processing (OLTP) และ analytics (OLAP) ในบทนี้เราเห็นว่า storage engines ที่ปรับให้เหมาะกับ OLTP ดูแตกต่างอย่างมากจากที่ปรับให้เหมาะกับ analytics:

  • ระบบ OLTP ถูกปรับให้เหมาะกับ requests ปริมาณสูง ซึ่งแต่ละ request อ่านและเขียน records จำนวนน้อยและต้องการการตอบสนองที่รวดเร็ว Records มักจะเข้าถึงผ่าน primary key หรือ secondary index และ indexes เหล่านี้โดยทั่วไปเป็นการ mapping แบบเรียงลำดับจาก key ไปยัง record ซึ่งรองรับ range queries ด้วย

  • Data warehouses และระบบ analytical ที่คล้ายกันถูกปรับให้เหมาะกับ read queries ที่ซับซ้อนซึ่ง scan จำนวน records มาก โดยทั่วไปพวกมันใช้ column-oriented storage layout พร้อมการบีบอัดที่ลดปริมาณข้อมูลที่ query ต้องอ่านจาก disk และ JIT compilation ของ queries หรือ vectorization เพื่อลดปริมาณ CPU time ที่ใช้ในการประมวลผลข้อมูล

ในฝั่ง OLTP เราเห็น storage engines จากสองสำนักคิดหลัก:

  • แนวทาง log-structured ซึ่งอนุญาตให้ต่อท้ายไฟล์และลบไฟล์ที่ล้าสมัย แต่ไม่เคยอัปเดตไฟล์ที่ถูกเขียนแล้ว โดยทั่วไป log-structured storage engines ให้ write throughput ที่สูง SSTables, LSM-trees, RocksDB, Cassandra, HBase, ScyllaDB, Lucene, และอื่นๆ อยู่ในกลุ่มนี้

  • แนวทาง update-in-place ซึ่งถือว่า disk เป็นชุดของ pages ขนาดคงที่ที่สามารถเขียนทับได้ B-trees ซึ่งเป็นตัวอย่างที่พบบ่อยที่สุดของปรัชญานี้ ถูกใช้ใน relational OLTP databases หลักทั้งหมดและ nonrelational databases จำนวนมาก ตามหลักคร่าวๆ B-trees มักจะดีกว่าสำหรับ reads ให้ read throughput ที่สูงกว่าและ response times ที่ต่ำกว่า log-structured storage

จากนั้นเราดู indexes ที่สามารถค้นหาหลายเงื่อนไขพร้อมกัน: multidimensional indexes เช่น R-trees ที่สามารถค้นหาจุดบนแผนที่ตามละติจูดและลองจิจูดพร้อมกัน และ full-text search indexes ที่สามารถค้นหาหลาย keywords ที่ปรากฏในข้อความเดียวกัน สุดท้าย เราเห็นว่า vector databases ถูกใช้สำหรับ semantic search บนเอกสารข้อความและสื่ออื่นๆ; พวกมันใช้ vectors ที่มีจำนวนมิติมากขึ้นและค้นหาเอกสารที่คล้ายกันโดยการเปรียบเทียบความคล้ายคลึงของ vector

ในฐานะนักพัฒนาแอปพลิเคชัน การมีความรู้เกี่ยวกับภายในของ storage engines ช่วยให้คุณอยู่ในตำแหน่งที่ดีขึ้นมากในการรู้ว่าเครื่องมือใดเหมาะสมที่สุดสำหรับแอปพลิเคชันเฉพาะของคุณ ถ้าคุณต้องการปรับพารามิเตอร์ tuning ของ database ความเข้าใจนี้ช่วยให้คุณจินตนาการได้ว่าค่าที่สูงขึ้นหรือต่ำลงอาจมีผลกระทบอย่างไร

แม้ว่าบทนี้จะไม่สามารถทำให้คุณเป็นผู้เชี่ยวชาญในการ tuning storage engine ใด storage engine หนึ่งโดยเฉพาะ แต่มันหวังว่าจะช่วยให้คุณมีคำศัพท์และแนวคิดเพียงพอที่จะทำความเข้าใจ documentation สำหรับ database ที่คุณเลือก