08 · Databases
08 · ฐานข้อมูล
This chapter is the floor that turns storage into memory — the layer between raw persistence below and every application above that needs to be told the truth.
ชั้นนี้เปลี่ยนพื้นที่เก็บข้อมูล (storage) ให้กลายเป็นความจำ — คั่นระหว่างความคงอยู่ของข้อมูล (persistence) แบบดิบด้านล่าง กับทุกแอปพลิเคชันด้านบนที่ต้องได้รับความจริง
How does civilization remember reliably?
อารยธรรมจดจำสิ่งต่างๆ ได้อย่างน่าเชื่อถือได้อย่างไร
Before 1970, asking a computer a question it had not been built to answer meant writing a new program, and that program had to know where the answer physically lived: which file, in which order, chained to which other record by which pointer. Reorganize the storage to make one report faster and every program that touched those records broke. Businesses were accumulating data far faster than they could accumulate programmers to chase it around the disk.
ก่อนปี 1970 ถามคำถามที่คอมพิวเตอร์ไม่ได้ถูกสร้างมาให้ตอบ แปลว่าต้องเขียนโปรแกรมใหม่ และโปรแกรมนั้นต้องรู้ว่าคำตอบอยู่ตรงไหนในทางกายภาพ — ไฟล์ไหน เรียงลำดับแบบไหน ผูกกับ record อื่นด้วย pointer ตัวไหน จัดที่เก็บข้อมูลใหม่เพื่อให้รายงานหนึ่งเร็วขึ้น ทุกโปรแกรมที่แตะ record เหล่านั้นพังหมด ธุรกิจสะสมข้อมูลเร็วกว่าที่จะหาโปรแกรมเมอร์มาไล่ตามมันไปทั่วดิสก์ได้ทัน
Then an IBM mathematician at the San Jose Research Laboratory published a paper whose first sentence was a declaration of independence: "Future users of large data banks must be protected from having to know how the data is organized in the machine (the internal representation)" (Codd, CACM 13(6), 1970). Edgar Codd's proposal was to model data as relations — mathematical sets of tuples, with no order, no pointers, no physical trace of the disk in them at all. What a user sees is a table. What a table is made of is nobody's business but the system's.
นักคณิตศาสตร์ของ IBM ที่ San Jose Research Laboratory ตีพิมพ์เปเปอร์ที่ประโยคแรกคือคำประกาศอิสรภาพ: "ผู้ใช้ธนาคารข้อมูลขนาดใหญ่ในอนาคตต้องได้รับการปกป้องจากการต้องรู้ว่าข้อมูลถูกจัดระเบียบอย่างไรในเครื่อง (internal representation)" ("Future users of large data banks must be protected from having to know how the data is organized in the machine (the internal representation)") (Codd, CACM 13(6), 1970) Edgar Codd เสนอให้มองข้อมูลเป็น relations — เซตทางคณิตศาสตร์ของ tuple ไม่มีลำดับ ไม่มี pointer ไม่มีร่องรอยทางกายภาพของดิสก์เหลืออยู่เลย ผู้ใช้เห็นตาราง ส่วนตารางประกอบขึ้นจากอะไรไม่ใช่เรื่องของใครนอกจากระบบเอง
That is the abstraction this floor sells, and the name for it is data independence. Everything else in the chapter exists to make it affordable.
นามธรรม (abstraction) ที่ชั้นนี้ขายคือสิ่งนั้น และชื่อของมันคือ data independence ทุกอย่างที่เหลือในบทนี้มีอยู่เพื่อทำให้มันมีต้นทุนที่จ่ายไหว
It is expensive because a question phrased against an idealized table gives the machine no plan. Codd saw the consequence and stated it precisely: the power of such a query language "lies in its descriptive ability (not its computing ability)" — you describe the answer you want, not the route to it. Somebody must still supply the route. That somebody became the query optimizer, and the technique that made it work was published by Pat Selinger's group in 1979 out of IBM's System R prototype: enumerate the possible access paths, estimate the cost of each from statistics about the data, and pick the cheapest (Selinger et al., SIGMOD 1979). It is an unglamorous idea with an enormous consequence — the reason a modern analyst can write nine lines of SQL over a billion rows and get an answer, while the equivalent hand-written traversal would take a week and be wrong. System R also produced the language: Donald Chamberlin and Raymond Boyce's SEQUEL, in 1974 (SIGFIDET workshop), later renamed SQL because another company already held the trademark on the word.
ราคาของมันสูง เพราะคำถามที่เขียนเทียบกับตารางในอุดมคติไม่ได้บอกแผนการทำงานอะไรกับเครื่องเลย Codd เห็นผลที่ตามมาและพูดไว้ชัดว่า พลังของภาษาคิวรี (query) แบบนี้ "อยู่ที่ความสามารถในการบรรยาย (ไม่ใช่ความสามารถในการคำนวณ)" — คุณบรรยายคำตอบที่ต้องการ ไม่ใช่เส้นทางไปหามัน เส้นทางนั้นยังต้องมีใครสักคนจัดหาให้อยู่ดี คนนั้นกลายเป็น query optimizer เทคนิคที่ทำให้มันทำงานได้ตีพิมพ์โดยกลุ่มของ Pat Selinger ในปี 1979 จากต้นแบบ System R ของ IBM: ไล่ดูเส้นทางการเข้าถึงข้อมูลที่เป็นไปได้ ประเมินต้นทุนของแต่ละเส้นทางจากสถิติของข้อมูล เลือกเส้นทางที่ถูกที่สุด (Selinger et al., SIGMOD 1979) ไอเดียที่ดูไม่หวือหวา แต่ผลของมันใหญ่ — นักวิเคราะห์ยุคนี้เขียน SQL เก้าบรรทัดบนข้อมูลพันล้านแถวแล้วได้คำตอบ ในขณะที่การไล่ค้นด้วยมือแบบเทียบเท่ากันกินเวลาเป็นสัปดาห์และยังผิด System R ให้กำเนิดภาษาด้วย: SEQUEL ของ Donald Chamberlin กับ Raymond Boyce ในปี 1974 (SIGFIDET workshop) ภายหลังเปลี่ยนชื่อเป็น SQL เพราะบริษัทอื่นถือเครื่องหมายการค้าของคำนั้นไปก่อน
The second thing this floor hides is failure. Power dies mid-write; two clerks sell the same seat; a disk returns a page from last Tuesday. The abstraction offered is the transaction: a group of operations that either all happen or none do, that behaves as though no one else were running at the same time, and that once confirmed cannot be lost. Jim Gray set out these guarantees in 1981 (The Transaction Concept, VLDB); Theo Härder and Andreas Reuter gave them the acronym everyone now recites — atomicity, consistency, isolation, durability — in a 1983 survey that credits Gray for the substance (ACM Computing Surveys 15(4)). Note what a transaction really is: not a mechanism for avoiding failure, but a contract about what failure is allowed to look like from above. The machinery underneath fails constantly. The surface it offers admits only two outcomes.
สิ่งที่สองที่ชั้นนี้ซ่อนไว้คือ ความล้มเหลว (failure) ไฟดับกลางคันขณะเขียนข้อมูล เสมียนสองคนขายที่นั่งเดียวกัน ดิสก์คืนหน้าข้อมูลของวันอังคารที่แล้วกลับมา สิ่งที่ยื่นให้แทนคือ ทรานแซกชัน (transaction): กลุ่มของการปฏิบัติการที่เกิดขึ้นทั้งหมดหรือไม่เกิดเลย ทำงานราวกับไม่มีใครอื่นทำงานอยู่พร้อมกัน และเมื่อยืนยันแล้วไม่มีวันสูญหาย Jim Gray วางการรับประกันเหล่านี้ไว้ในปี 1981 (The Transaction Concept, VLDB) ส่วน Theo Härder กับ Andreas Reuter ตั้งชื่อย่อที่ทุกคนท่องกันจนถึงวันนี้ — atomicity, consistency, isolation, durability — ในงานสำรวจปี 1983 ที่ยกเครดิตเนื้อหาให้ Gray (ACM Computing Surveys 15(4)) ทรานแซกชันคืออะไรกันแน่: ไม่ใช่กลไกหลีกเลี่ยงความล้มเหลว แต่เป็น สัญญาว่าความล้มเหลวได้รับอนุญาตให้มีหน้าตาแบบไหนเมื่อมองจากด้านบน กลไกด้านล่างพังอยู่ตลอดเวลา ผิว (surface) ที่มันยื่นให้ยอมรับผลลัพธ์แค่สองแบบ
The mechanism that delivers that contract is the log, and it is the least intuitive idea on this floor. Durability is not achieved by writing the data carefully. It is achieved by writing the intention first, sequentially, to a file that is only ever appended — and only then touching the data pages, whenever it is convenient. If the machine dies, recovery reads the log and replays history: redo what was committed, undo what was not. The canonical treatment is ARIES (Mohan et al., ACM TODS 17(1), 1992), and the pattern escaped the database long ago — filesystems journal, message queues are logs wearing a different hat, and replication in chapter 10 is one machine reading another machine's log. The database's real heart is not the table. It is the append-only record of what it was told to do.
กลไกที่ส่งมอบสัญญานั้นคือ log และเป็นไอเดียที่เข้าใจยากที่สุดในชั้นนี้ ความทนทาน (durability) ไม่ได้มาจากการเขียนข้อมูลอย่างระมัดระวัง แต่มาจากการเขียน เจตนา ก่อน เรียงเป็นลำดับ ลงไฟล์ที่มีแต่การต่อท้าย (append) เท่านั้น ค่อยไปแตะหน้าข้อมูลจริงเมื่อไหร่ก็ได้ที่สะดวก ถ้าเครื่องตาย การกู้คืนอ่าน log แล้วเล่นประวัติศาสตร์ซ้ำ: ทำสิ่งที่ commit แล้วซ้ำอีกครั้ง (redo) ย้อนสิ่งที่ยังไม่ commit กลับ (undo) แนวทางมาตรฐานคือ ARIES (Mohan et al., ACM TODS 17(1), 1992) และแพตเทิร์นนี้หลุดออกจากฐานข้อมูลไปนานแล้ว — filesystem ทำ journal, message queue ก็คือ log ที่สวมหน้ากากคนละแบบ และการทำสำเนา (replication) ในบทที่ 10 ก็คือเครื่องหนึ่งอ่าน log ของอีกเครื่องหนึ่ง หัวใจจริงของฐานข้อมูลไม่ใช่ตาราง แต่คือบันทึกแบบต่อท้ายอย่างเดียว (append-only) ของสิ่งที่มันถูกสั่งให้ทำ
The one place the physical world is allowed to show through is the index, and the shape it takes is dictated by hardware two floors down. Rudolf Bayer and Edward McCreight's B-tree, from a Boeing report in 1970 and Acta Informatica in 1972 (Bayer & McCreight), is deliberately wide and shallow — hundreds of children per node, so that one node fills one disk page and a lookup among billions of rows costs three or four fetches instead of thirty. It is chapter 02's bargain, paid at industrial scale: build the structure now, in space and in write cost, to make a future question cheap. And it is where the abstraction leaks. Two logically identical queries can differ by four orders of magnitude in time because one has an index and the other does not — the surface says what, but the bill is denominated in how.
จุดเดียวที่โลกทางกายภาพได้รับอนุญาตให้โผล่ผ่านมาคือ ดัชนี (index) และฮาร์ดแวร์ที่อยู่สองชั้นด้านล่างเป็นตัวกำหนดรูปทรงของมัน B-tree ของ Rudolf Bayer กับ Edward McCreight จากรายงานของ Boeing ปี 1970 และ Acta Informatica ปี 1972 (Bayer & McCreight) กว้างและตื้นโดยตั้งใจ — แต่ละโหนดมีลูกได้เป็นร้อย หนึ่งโหนดเต็มพอดีหนึ่งหน้าดิสก์ การค้นหาท่ามกลางข้อมูลนับพันล้านแถวจึงเสียแค่สามหรือสี่ครั้งในการดึงข้อมูล แทนที่จะเป็นสามสิบครั้ง นี่คือข้อแลกเปลี่ยน (trade-off) ของบทที่ 02 ที่จ่ายกันในระดับอุตสาหกรรม: สร้างโครงสร้างไว้ตอนนี้ ทั้งพื้นที่และต้นทุนการเขียน เพื่อให้คำถามในอนาคตถูกลง และนี่คือจุดที่ abstraction รั่ว คิวรี (query) สองตัวที่เหมือนกันทุกอย่างในเชิงตรรกะ ใช้เวลาต่างกันได้ถึงสี่ระดับขนาด (order of magnitude) เพราะตัวหนึ่งมี index อีกตัวไม่มี — ผิว (surface) บอกแค่ อะไร แต่บิลคิดเป็น อย่างไร
The people are worth a moment. Codd's employer was slow to build what he described, having a large and profitable investment in the older hierarchical system it would replace (Wade & Chamberlin, IEEE Annals, 2012); the relational model reached customers partly through others, and Codd received the Turing Award in 1981 for a paper his own company had spent a decade arguing with (ACM).
คนในเรื่องนี้คุ้มค่าที่จะแวะดูสักครู่ นายจ้างของ Codd เองช้าที่จะสร้างสิ่งที่เขาบรรยายไว้ เพราะมีเงินลงทุนก้อนใหญ่ที่ยังทำกำไรอยู่ในระบบ hierarchical รุ่นเก่าที่มันจะเข้ามาแทนที่ (Wade & Chamberlin, IEEE Annals, 2012) แบบจำลองเชิงสัมพันธ์ (relational model) ไปถึงมือลูกค้าส่วนหนึ่งผ่านคนอื่น และ Codd ได้รับรางวัล Turing Award ในปี 1981 จากเปเปอร์ที่บริษัทของเขาเองเถียงค้านมานานนับสิบปี (ACM)
Which brings the story to the loosening. Around 2006–2007 two systems built for a scale the relational contract could not reach were published — Google's Bigtable (OSDI 2006) and Amazon's Dynamo (SOSP 2007) — and in June 2009 a San Francisco meetup gave the movement a name it would spend a decade regretting: NoSQL. The trade was explicit: give up joins, give up strong transactions across machines, and buy horizontal scale with the proceeds. What happened next is the interesting part. Having sold the guarantees, the industry discovered how much application code it takes to fake them, and most of these systems have been growing transactions and query languages back ever since. Chapter 10 explains why the guarantees were expensive in the first place — and why they can never be free once the data lives on more than one machine.
เรื่องเดินมาถึงช่วงที่สัญญานั้นคลายตัว ราวปี 2006–2007 ระบบสองตัวที่สร้างมาเพื่อสเกลที่สัญญาเชิงสัมพันธ์ไปไม่ถึงถูกตีพิมพ์ — Bigtable ของ Google (OSDI 2006) กับ Dynamo ของ Amazon (SOSP 2007) — และในเดือนมิถุนายน 2009 งาน meetup ที่ San Francisco ตั้งชื่อให้ขบวนการนี้ ชื่อที่มันจะต้องมานั่งเสียใจไปอีกสิบปี: NoSQL ข้อแลกเปลี่ยนถูกพูดออกมาตรงๆ: ยอมไม่มี join ยอมไม่มีทรานแซกชัน (transaction) ที่แข็งแรงข้ามเครื่อง แล้วเอาสิ่งที่ยอมแลกไปซื้อสเกลแนวนอน สิ่งที่เกิดขึ้นต่อมาคือส่วนที่น่าสนใจ พอขายการรับประกันเหล่านั้นไปแล้ว วงการก็ค้นพบว่าต้องเขียนโค้ดในแอปพลิเคชันมากแค่ไหนถึงจะปลอมมันขึ้นมาใหม่ได้ และระบบพวกนี้ส่วนใหญ่ก็งอกทรานแซกชันกับภาษาคิวรีกลับคืนมาตั้งแต่นั้น บทที่ 10 อธิบายว่าทำไมการรับประกันเหล่านี้ถึงแพงตั้งแต่แรก — และทำไมมันจะไม่มีวันฟรี เมื่อข้อมูลอยู่บนเครื่องมากกว่าหนึ่งเครื่อง
Connections
เชื่อมโยง
Below: chapter 04 supplies the memory hierarchy that gives the B-tree its shape, and chapter 05 supplies the file, the process, and the crash-consistency problem in raw form — the database is what happens when one program takes those duties from the operating system and does them properly. Chapter 02 owns the data structures; chapter 03 explains why compressed columns and encoded pages work at all. Above: chapter 07 lives here permanently, since a schema is the hardest thing in any system to change; chapter 09 puts the client across a network; chapter 10 asks what survives of these guarantees when the machine is really many machines.
ด้านล่าง: บทที่ 04 ให้ลำดับชั้นหน่วยความจำ (memory hierarchy) ที่กำหนดรูปทรงของ B-tree ส่วนบทที่ 05 ให้ไฟล์ โพรเซส (process) และปัญหา crash consistency มาในรูปดิบๆ — ฐานข้อมูลคือสิ่งที่เกิดขึ้นเมื่อโปรแกรมหนึ่งรับหน้าที่เหล่านั้นมาจากระบบปฏิบัติการแล้วทำมันอย่างถูกต้องจริงจัง บทที่ 02 เป็นเจ้าของโครงสร้างข้อมูล บทที่ 03 อธิบายว่าทำไมคอลัมน์ที่บีบอัดแล้วกับหน้าข้อมูลที่เข้ารหัสแล้วถึงทำงานได้ตั้งแต่แรก ด้านบน: บทที่ 07 อยู่ที่นี่ถาวร เพราะสคีมา (schema) คือสิ่งที่แก้ยากที่สุดในระบบใดๆ ก็ตาม บทที่ 09 พา client ข้ามเครือข่ายไป บทที่ 10 ถามว่าการรับประกันเหล่านี้เหลืออะไรอยู่บ้าง เมื่อเครื่องจริงๆ แล้วคือเครื่องหลายเครื่อง
Open questions
คำถามที่ยังเปิดอยู่
Is the relational model a permanent floor or a fifty-year local maximum? Its critics have twice declared it obsolete — for objects in the 1990s, for scale in the 2000s — and it has twice absorbed the challenger. Second: the optimizer is now the least predictable component in most systems, capable of choosing catastrophically on stale statistics; learned optimizers are an active research front, but a mis-estimating model is harder to debug than a mis-estimating formula. Third, and least settled: the log is the one component every modern data system has converged on. If storage, queues, replication and stream processing are all logs underneath, is "the database" still the right unit of thought, or is it the log that is the floor and the database merely one view built over it?
แบบจำลองเชิงสัมพันธ์ (relational model) เป็นชั้นถาวร หรือเป็นแค่จุดสูงสุดเฉพาะที่ (local maximum) ที่อยู่มาได้ห้าสิบปี ผู้วิจารณ์ประกาศว่ามันล้าสมัยมาแล้วสองครั้ง — เรื่อง object ในทศวรรษ 1990 เรื่องสเกลในทศวรรษ 2000 — และมันกลืนคู่แข่งเข้าไปได้ทั้งสองครั้ง ข้อสอง: query optimizer ตอนนี้เป็นส่วนประกอบที่คาดเดาไม่ได้มากที่สุดในระบบส่วนใหญ่ เลือกผิดพลาดร้ายแรงได้จากสถิติที่ล้าสมัย optimizer ที่เรียนรู้ได้ (learned optimizer) เป็นแนวรบวิจัยที่กำลังคึกคัก แต่โมเดลที่ประเมินผิดดีบั๊กยากกว่าสูตรที่ประเมินผิด ข้อสาม และยังไม่ลงตัวที่สุด: log คือส่วนประกอบเดียวที่ระบบข้อมูลสมัยใหม่ทุกตัวมาบรรจบกัน ถ้า storage, queue, replication และ stream processing ล้วนเป็น log อยู่ข้างใต้ "ฐานข้อมูล" ยังเป็นหน่วยคิดที่ถูกต้องอยู่หรือเปล่า หรือว่า log ต่างหากที่เป็นชั้น ส่วนฐานข้อมูลเป็นแค่มุมมองหนึ่งที่สร้างซ้อนอยู่ข้างบน
Go deeper
อ่านต่อ
- E. F. Codd, "A Relational Model of Data for Large Shared Data Banks," Communications of the ACM 13, no. 6 (1970): 377–387 — twelve pages that reorganized an industry; ACM DL.
- Peter Bailis, Joseph M. Hellerstein & Michael Stonebraker, eds., Readings in Database Systems, 5th ed., 2015 — the field's own curated canon, with editorial commentary; free at redbook.io.
- Abraham Silberschatz, Henry F. Korth & S. Sudarshan, Database System Concepts, 7th ed., McGraw-Hill, 2019 — the standard textbook if you want the mechanisms in full.
- E. F. Codd, "A Relational Model of Data for Large Shared Data Banks," Communications of the ACM 13, no. 6 (1970): 377–387 — สิบสองหน้าที่จัดระเบียบทั้งอุตสาหกรรมใหม่; ACM DL.
- Peter Bailis, Joseph M. Hellerstein & Michael Stonebraker, eds., Readings in Database Systems, 5th ed., 2015 — คัมภีร์ที่วงการคัดสรรเอง พร้อมคำอธิบายจากบรรณาธิการ; อ่านฟรีที่ redbook.io.
- Abraham Silberschatz, Henry F. Korth & S. Sudarshan, Database System Concepts, 7th ed., McGraw-Hill, 2019 — ตำราเรียนมาตรฐาน ถ้าต้องการกลไกแบบเต็มรูปแบบ.