Cỗ máy cất và tìm nằm dưới mọi truy vấnMáy cất dữ liệu ở đâu, tìm lại kiểu gì?The store-and-find engine under every query

Kleppmann mở chương bằng cơ sở dữ liệu đơn giản nhất có thể tưởng tượng: một tệp mà mỗi lần ghi chỉ nối thêm một dòng vào cuối, còn mỗi lần đọc thì quét cả tệp để lấy giá trị mới nhất1. Ghi rẻ đến mức khó tin, nhưng chi phí đọc tăng theo số bản ghi. Muốn đọc nhanh thì phải dựng chỉ mục — một cấu trúc phái sinh từ dữ liệu gốc, không thêm thông tin mới mà chỉ thêm một lối đi ngắn hơn. Và vì lối đi ấy phải được bảo trì, mọi chỉ mục đều bắt việc ghi gánh thêm chi phí — đó là đánh đổi nền tảng mà cả chương xoay quanh1.

Hãy tưởng tượng một cuốn sổ mà bạn chỉ được viết thêm vào dòng cuối, không được tẩy xóa. Viết thì nhanh lắm. Nhưng muốn tìm lại một điều đã ghi thì phải lật từ đầu đến cuối. Vậy nên người ta làm thêm một trang "mục lục" ghi sẵn mỗi thứ nằm ở dòng nào. Tìm nhanh hẳn — đổi lại, mỗi lần viết thêm một dòng, bạn phải sửa mục lục nữa.

Kleppmann opens the chapter with the simplest database imaginable: a file where every write just appends one line to the end, and every read scans the whole file for the latest value1. Writing is absurdly cheap, but read cost grows with the number of records. To read fast you need an index — a derived structure built from the primary data, adding no new information, only a shorter path to it. And because that path must be maintained, every index makes writes pay more — the foundational trade-off the whole chapter turns on1.

Bắt các đoạn log phải sắp xếp theo khóa, ta được SSTable; cho các bản ghi mới đi vào một cây trong bộ nhớ rồi định kỳ đổ xuống đĩa, ta được LSM-tree. Tên gọi đến từ bài của O'Neil và cộng sự năm 1996, mô tả một cấu trúc "hoãn lại và gom lô các thay đổi chỉ mục, dồn thay đổi từ một thành phần trong bộ nhớ xuống một hoặc nhiều thành phần trên đĩa theo cách gợi nhớ merge sort"4. Ở phía đối diện là B-tree, cấu trúc chỉ mục tiêu chuẩn của cơ sở dữ liệu quan hệ — phổ biến tới mức năm 1979 Douglas Comer đã đặt tên bài tổng quan của mình là "The Ubiquitous B-Tree"9. Nó chia dữ liệu thành các trang kích thước cố định và sửa tại chỗ.

Có hai kiểu tủ đựng đồ. Tủ thứ nhất: bạn cứ ném đồ mới vào một cái hộp nhỏ trên bàn, đầy thì đổ cả hộp xuống ngăn dưới, rồi thỉnh thoảng gộp các ngăn lại cho gọn. Tủ thứ hai: mỗi món có sẵn một ô cố định, đổi gì thì mở đúng ô đó ra sửa. Kiểu một ghi nhanh nhưng dọn nhiều; kiểu hai gọn gàng nhưng mỗi lần sửa phải đi tìm ô.

Require the log segments to be sorted by key and you get SSTables; let new records land in an in-memory tree and spill to disk periodically and you get the LSM-tree. The name comes from O'Neil and colleagues in 1996, describing a structure that "defers and batches index changes, cascading the changes from a memory-based component through one or more disk components in an efficient manner reminiscent of merge sort"4. Facing it is the B-tree, the standard index of relational databases — so standard that in 1979 Douglas Comer titled his survey "The Ubiquitous B-Tree"9. It breaks data into fixed-size pages and updates in place.

Cả LSM-tree lẫn B-tree đều có thể dùng làm chỉ mục cho khóa chính lẫn chỉ mục phụ. Khác biệt nằm ở chỗ: khóa của chỉ mục phụ không nhất thiết duy nhất — nhiều bản ghi có thể cùng một giá trị. Kleppmann nêu hai cách xử lý: cho mỗi mục trong chỉ mục trỏ tới một danh sách các bản ghi khớp, hoặc thêm định danh bản ghi vào khóa để khóa trở nên duy nhất1. Từ nền đó mọc ra một họ hình dạng: chỉ mục gom cụm, chỉ mục phủ, chỉ mục nhiều cột, chỉ mục đa chiều, và chỉ mục cho tìm kiếm mờ.

Mục lục không nhất thiết phải theo tên. Bạn có thể làm mục lục theo màu, theo năm, theo chỗ để. Nhưng có một chỗ khác: tên thì mỗi món một tên, còn màu thì nhiều món cùng màu — nên mục lục theo màu phải ghi được nhiều dòng cho một mục.

Both LSM-trees and B-trees can index a primary key or a secondary one. The difference: a secondary index key is not necessarily unique — many records can share a value. Kleppmann gives two ways to handle it: make each index entry point to a list of matching records, or append a record identifier to the key to make it unique1. From that base grows a family of shapes: clustered indexes, covering indexes, multi-column indexes, multi-dimensional indexes, and indexes for fuzzy search.

Ranh giới không nằm ở công nghệ mà ở dạng truy cập. Hệ xử lý giao dịch (OLTP) lấy vài bản ghi mỗi truy vấn, tìm bằng khóa, và làm vậy rất nhiều lần mỗi giây; hệ phân tích (OLAP) quét hàng triệu bản ghi để trả về vài con số tổng hợp1. Bài C-Store phát biểu cùng sự phân đôi ấy từ phía thiết kế: kho theo hàng là hệ tối ưu cho ghi và "đặc biệt hiệu quả với các ứng dụng kiểu OLTP", còn "các hệ hướng tới truy vấn tùy biến trên lượng dữ liệu lớn thì nên được tối ưu cho đọc"19.

Có hai loại việc rất khác nhau. Loại một: "cho tôi xem đơn hàng số 4821" — chỉ cần lấy đúng một tờ. Loại hai: "cả năm nay bán được bao nhiêu tiền" — phải đếm hết cả kho. Cùng là một kho giấy tờ, nhưng cách xếp giấy cho hai việc này phải khác nhau hoàn toàn.

The line isn't drawn by technology but by access pattern. Transaction processing (OLTP) fetches a few records per query, found by key, very many times per second; analytics (OLAP) scans millions of records to return a handful of aggregates1. The C-Store paper states the same split from the design side: row stores are write-optimized and "especially effective on OLTP-style applications", while "systems oriented toward ad-hoc querying of large amounts of data should be read-optimized"19.