Storage və retrieval

Database iki əsas işi görür: data verəndə onu saxlayır, sonra soruşanda geri qaytarır. Fəsil 2-də bu işin tətbiq tərəfini, yəni data model-i və query dilini, gördük. Bu fəsildə eyni suala database-in tərəfindən baxırıq: data disk-də necə yerləşir və sorğu gələndə necə tapılır? Developer storage engine yazmayacaq, amma birini seçib tune edəcək və bunun üçün engine-in içini təxmini bilmək lazımdır.

Fəsil iki engine ailəsini izləyir: log-structured və page-oriented. Sonra OLTP ilə OLAP fərqinə və analitika üçün yaranmış column-oriented storage-a keçir.

Dünyanın ən sadə database-i

İki shell funksiyası ilə işlək key-value store yaratmaq olar:

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

db_set faylın sonuna sətir əlavə edir; köhnə dəyər silinmir, db_get isə tail -n 1 ilə sonuncunu götürür. Yazma əladır, çünki append disk-in ən sürətli əməliyyatıdır. Log, yəni append-only qeydlər ardıcıllığı, bir çox real storage engine-in də əsasıdır.

Oxuma isə dəhşətdir: db_get hər dəfə bütün faylı skan edir, yəni O(n). Həll index-dir: əsas data-dan törənən, "harada" sualına cavab verən əlavə struktur. Index-in qiyməti aydındır: hər yazmada index də yenilənməlidir. Yaxşı seçilmiş index oxumanı sürətləndirir, hər index isə yazmanı yavaşladır. Buna görə hansı index-in lazım olduğunu developer seçir.

Hash index-lər

Ən sadə index in-memory hash map-dir: hər key üçün faylda byte offset. Yazma zamanı log-a append edib hash map-i yeniləyirik; oxuma zamanı offset-i tapıb bir seek ilə dəyəri oxuyuruq. Bitcask məhz belə işləyir və key-lərin RAM-a sığdığı, amma hər key-in tez-tez update olunduğu hallarda çox sürətlidir: video view counter kimi.

Disk tükənməsin deyə log segment-lərə bölünür: segment müəyyən ölçüyə çatanda bağlanır, yazma yeni segment-ə keçir. Köhnə segment-lər compaction olunur: hər key-in yalnız sonuncu dəyəri saxlanılır, qalanı atılır. Compaction segment-ləri kiçildir, buna görə bir neçəsini merge edib bir segment yaratmaq olar. Bu iş background-da gedir, merge bitəndə oxumalar yeni segment-ə keçir. Hər segment-in öz hash map-i var; oxuma əvvəl ən yeni segment-ə baxır, tapmasa köhnəyə.

Real implementasiyada bir neçə detal həll olunmalıdır:

• Silmə. Key-i silmək üçün xüsusi qeyd, tombstone, yazılır; merge zamanı tombstone-u görən proses key-in əvvəlki dəyərlərini atır.
• Crash recovery. Hash map yaddaşdadır, restart-da itir. Bütün segment-ləri oxuyub yenidən qurmaq yavaşdır; Bitcask hər segment-in hash map-ini snapshot kimi disk-ə yazır.
• Yarımçıq qeydlər. Yazmanın ortasında crash olarsa, log-da pozulmuş qeyd qalır; checksum ilə aşkarlanır və atılır.
• Concurrency. Yazma ardıcıl olduğu üçün adətən bir writer thread var; segment-lər append-only və immutable olduğundan çoxlu thread paralel oxuya bilər.

Append-only dizayn əsaslıdır: sequential write random write-dan xeyli sürətlidir, immutable segment-lərdə crash və concurrency sadədir. Məhdudiyyətlər isə ciddidir: hash map yaddaşa sığmalıdır, disk-də hash map saxlamaq random I/O-ya görə pis işləyir; range query mümkün deyil, kitty00000-dan kitty99999-a qədər key-ləri tapmaq üçün hamısına ayrı-ayrı baxmaq lazımdır.

SSTable-lar və LSM-tree-lər

Sadə dəyişiklik hər iki məhdudiyyəti həll edir: segment-də key-value cütlərini key üzrə sıralanmış saxlamaq. Belə formata Sorted String Table, SSTable, deyilir. Üstünlükləri:

1. Segment-ləri merge etmək mergesort-un son addımı kimi sadə və səmərəlidir: hər segment-dən növbəti key-i oxu, ən kiçiyini çıxar. Eyni key bir neçə segment-dədirsə, ən yeni segment-in dəyəri qalır.
2. Bütün key-lərin index-i lazım deyil. handbag axtarırsınızsa və handbag-in offset-ini bilmirsinizsə, amma handbag-dən əvvəl və sonra gələn key-lərin offset-ini bilirsinizsə, onların arasını skan etmək kifayətdir. Yaddaşdakı index sparse ola bilər: hər bir neçə kilobayt üçün bir key.
3. Skan zamanı oxunan blok sıxıla bilər; bu, həm disk yerinə, həm I/O bandwidth-inə qənaət edir.

Sıralı yazma necə alınır? Yazmalar istənilən sırada gəlir. Yaddaşda sıralı struktur, red-black tree və ya skip list, saxlamaq asandır. Belə yaddaş strukturuna memtable deyilir. Yazma memtable-a gedir; ölçü həddi keçəndə memtable SSTable kimi disk-ə yazılır və yeni memtable başlayır. Oxuma əvvəl memtable-a, sonra ən yeni SSTable-dan ən köhnəyə baxır. Background-da merge və compaction segment-ləri birləşdirir. Crash olsa memtable itir; buna görə hər yazma əvvəlcə ayrıca sıralanmamış log-a da append olunur. Bu write-ahead log memtable bərpası üçündür və memtable disk-ə yazılanda atılır.

Bu ideya LevelDB, RocksDB, Cassandra və HBase-də işləyir. Sıralı segment-lərin merge olunduğu bu struktura LSM-tree, Log-Structured Merge-Tree, deyilir.

İki performans məsələsi var. Mövcud olmayan key-i axtarmaq bahalıdır: memtable-dan ən köhnə segment-ə qədər hər yerə baxılır. Həll Bloom filter-dir: yaddaşda saxlanılan, "bu key dəstdə yoxdur" cavabını qəti verən kompakt struktur. İkincisi compaction strategiyasıdır. Size-tiered compaction-da kiçik və yeni SSTable-lar böyük və köhnələrə merge olunur. Leveled compaction-da key range-i daha kiçik SSTable-lara bölünür və köhnə data ayrı level-lərə köçür; disk yerinə daha qənaətlidir.

B-tree-lər

Ən geniş yayılmış index strukturu LSM deyil, B-tree-dir. 1970-ci ildən bəri relational database-lərin standartıdır və bir çox NoSQL store-da da işləyir. B-tree də key-ləri sıralı saxlayır, amma dizayn fəlsəfəsi fərqlidir: database sabit ölçülü, adətən 4 KB, page-lərə bölünür, hər page ünvanla istinad olunur və page-lər bir-birinə işarə edir, disk-dəki pointer kimi.

Bir page root-dur. İçində key-lər və uşaq page-lərə reference-lər var; hər uşaq key-lərin davamlı bir range-inə cavabdehdir. Axtarış root-dan başlayır, key-in düşdüyü range-in uşağına keçir və leaf page-ə çatanda dəyəri tapır. Bir page-də uşaq reference-lərin sayı branching factor-dur, praktikada bir neçə yüz. Dörd səviyyəli, 4 KB page-li, branching factor 500 olan tree 256 TB saxlayır; axtarış dörd disk oxumasıdır.

Yeniləmə üçün leaf page tapılıb dəyişdirilir və yerində yenidən yazılır. Yeni key əlavə etmək üçün page-də yer yoxdursa, page iki yarıya split olunur və valideyn page yenilənir. Tree balanced qalır: n key üçün dərinlik O(log n).

B-tree-nin əsas fərqi odur ki, page-lər yerində yenidən yazılır, LSM-də isə faylla yalnız append olunur. Yerində yazma təhlükəlidir: split zamanı üç page yazılmalıdır, ortada crash olsa pozulmuş index, yetim page qalır. Həll yenə write-ahead log-dur: hər dəyişiklik page-ə tətbiq olunmazdan əvvəl append-only log-a yazılır və crash-dən sonra oradan bərpa olunur. Concurrency üçün page-lər latch-lərlə, yəni yüngül lock-larla, qorunur. Bəzi engine-lər, məsələn LMDB, yerində yazma əvəzinə copy-on-write istifadə edir: dəyişdirilmiş page yeni yerə yazılır və valideynlər ona yönəldilir.

B-tree ilə LSM-tree müqayisəsi

Ümumi qayda: LSM yazmada, B-tree oxumada sürətlidir. Amma yük profili həlledicidir.

Write amplification bir yazmanın disk-ə neçə dəfə yazılmasıdır; SSD-lərdə həm throughput-u, həm ömrü təsir edir. LSM-də compaction disk bandwidth-ini tətbiqin yazmaları ilə bölüşür; yazma sürəti compaction-dan yüksək olarsa, oxunmamış segment-lər yığılır, oxuma yavaşlayır və disk dolur. B-tree-də isə hər key tam bir yerdədir; range lock-ları və transaction izolyasiyası daha sadədir. Buna görə B-tree hələ də çox yükdə yaxşı seçimdir, LSM isə yazma intensiv və böyük data həcmlərində üstündür.

Digər index strukturları

İndiyədək key-value, yəni primary key index-lərinə baxdıq. Secondary index eyni şəkildə qurulur, fərqi key-lərin unikal olmamasıdır: ya hər dəyər sətir ID-lərinin siyahısına işarə edir, ya key-ə sətir ID-si əlavə olunur. Index-in dəyəri ya sətrin özü, ya heap file-a reference ola bilər. Sətrin index-in içində saxlandığı variant clustered index-dir; MySQL InnoDB-də primary key clustered-dir, secondary index-lər isə primary key-ə istinad edir. Aralıq variant covering index-dir: tez-tez lazım olan bir neçə sütun index-in içində saxlanılır və sorğu index-dən kənara çıxmır.

Concatenated index bir neçə sahəni bir key-ə birləşdirir: (last_name, first_name) soyad üzrə, yaxud soyad və ad üzrə axtarışa imkan verir, amma yalnız ad üzrə axtarışa yox. Geospatial 2D range axtarışı R-tree və ya space-filling curve tələb edir. Full-text və fuzzy index-lər isə yazı səhvlərini və sinonimləri nəzərə alır; Lucene term lüğətini automaton kimi saxlayıb edit distance ilə axtarır.

RAM ucuzlaşdıqca in-memory database-lər yaranıb: data tamamilə yaddaşda, durability isə WAL, periodik snapshot və ya replication ilə. Sürətləri disk-dən deyil, data strukturlarını disk formatına encode etmək yükündən qaçmaqdan gəlir.

OLTP və OLAP

Database-lərin ilk illərində yazma biznes transaction-ı demək idi: satış, sifariş, maaş. Bu yük OLTP, online transaction processing, adlanır: hər sorğu az qeyd oxuyur və ya yazır, index ilə tapır, interaktiv latency gözlənilir. Sonra ikinci yük formalaşdı: analitika. "Yanvarda hər mağazanın gəliri nə qədər idi?" kimi sorğular milyonlarla qeydi skan edib bir neçə sütun üzrə aggregate hesablayır. Bu yük OLAP, online analytic processing, adlanır.

1990-cı illərdən şirkətlər analitikanı ayrı data warehouse-a çıxarır, çünki iş üçün kritik OLTP sistemlərinə ağır ad-hoc sorğu buraxmaq risklidir. Data OLTP sistemlərindən ETL ilə köçürülür: extract, transform, load. Warehouse-un üstünlüyü analitik yük üçün optimallaşdırıla bilməsidir; OLTP engine-lər, həm B-tree, həm LSM, bu yükdə pisdir.

Warehouse-larda data model adətən star schema-dır: mərkəzdə fact table, hər sətir bir hadisə, məsələn, bir satış; ətrafda dimension table-lar: məhsul, mağaza, tarix, müştəri. Fact table-ın sütunları ya ölçülə bilən dəyər, ya dimension-a foreign key-dir. Dimension-lar alt-dimension-lara bölünsə, snowflake schema alınır.

Column-oriented storage

Fact table-ın yüz sütunu ola bilər, amma analitik sorğu adətən dörd-beşini oxuyur. Row-oriented storage-da sətrin bütün sütunları bir yerdədir; beş sütun üçün də bütün sətirlər disk-dən oxunur. Column-oriented storage hər sütunu ayrı faylda saxlayır: sorğu yalnız lazımi sütunları oxuyur. Hər sütun faylında sətirlər eyni sırada olmalıdır ki, n-ci sətri hər fayldan n-ci dəyəri götürməklə yığmaq mümkün olsun.

Sütunlar sıxılmağa çox yatımlıdır, çünki dəyərlər təkrarlanır. product_sk sütununda milyardlarla sətir, amma yalnız yüz minlərlə fərqli məhsul var. Bitmap encoding hər fərqli dəyər üçün bir bit sütunu yaradır; dəyər seyrəkdirsə bitmap-lər run-length ilə daha da sıxılır. Sorğu bitmap əməliyyatına çevrilir:

WHERE product_sk IN (30, 68, 69)
-- bitmap(30) OR bitmap(68) OR bitmap(69)

Sıxılmış blok CPU cache-ə sığır və əməliyyatlar bit-lər üzərində tight loop-da gedir; buna vectorized processing deyilir.

Sətirləri sıralamaq da mümkündür, amma hər sütunu ayrı sıralamaq olmaz, çünki sətri yığmaq üçün ümumi sıra lazımdır. Sıralama açarı tez-tez filter olunan sütundur, məsələn, tarix. Sıralanmış sütunda eyni dəyərlər ardıcıl gəlir və run-length encoding milyard sətirli sütunu bir neçə kilobayta endirir.

Zəif tərəf yazmadır: sıxılmış, sıralı sütunun ortasına sətir əlavə etmək bütün faylları yenidən yazmağı tələb edir. Həll tanışdır: LSM-tree. Yazmalar memtable-a gedir, sütunlu segment-lərlə merge background-da olur.

Nəhayət, tez-tez işlənən aggregate-lər materialized view kimi əvvəlcədən hesablanır. Xüsusi forması data cube-dur: hər dimension kombinasiyası üçün hazır cəm. Cube sorğunu sürətləndirir, amma elastikliyi azaldır; warehouse-lar xam data-nı saxlayır, cube-u isə sürətləndirici kimi əlavə edir.

Tapşırıqlar

1. Shell ilə yazılmış sadə database-ə in-memory hash index əlavə edin, sonra 100 MB random key-lərlə yazıb oxumanı ölçün. Key sayı yaddaşa sığmayanda nə olur? Bu hal üçün SSTable yanaşmasının hansı dəyişikliyi həll edir?
2. Bir saniyədə 50 000 random yazma və 5 000 point read alan sistem üçün B-tree və LSM-tree arasında seçim edin. Hansı metrikləri ölçərdiniz və hansı yük profilində qərarınızı dəyişərdiniz? Compaction-ın p99 latency-yə təsirini necə məhdudlaşdırardınız?
3. Satış fact table-ı 20 sütun və 2 milyard sətirdən ibarətdir. "Hər ölkədə hər ay satış cəmi" sorğusu üçün row-oriented və column-oriented storage-da təxmini oxunan byte miqdarını hesablayın; sıralama açarı və bitmap sıxılma nəticəni necə dəyişir?