Software Engineer Encyclopedia
0%
Domain 04 · Database Engineering & Data Management · Pillar

Storage Engines من جوه: B-tree وLSM وSSTable وBloom filter وWAL وCompaction

Database Storage Engine Internals

ليه الـ database بيكتب بسرعة أو بيقرأ بسرعة، وليه مش الاتنين ببلاش: pages وB+trees، الـ WAL والـ crash recovery، الـ LSM-trees (memtable ← SSTables ← compaction)، Bloom filters، الـ read/write/space amplification، ومقارنة SQL Server وPostgreSQL وMongoDB (WiredTiger) على مستوى التخزين — مع أثر ده على تصميمك في .NET.

  • Intermediate
  • ~13 min read
  • 13 sections
  • 4 code examples
  • 3 diagrams
  • 6 questions
  • Priority L2 · Essential
  • SQL Server 2022 · PostgreSQL 17 · MongoDB 8 (WiredTiger) · RocksDB/Cassandra as LSM references — concepts stable, details reviewed 2026-11-18

بعد الدرس ده هتقدر

  • تشرح الـ page وإزاي B+tree بيوصل لأي صف في 3–4 قراءات
  • تشرح الـ WAL وليه الـ commit = fsync للـ log مش للـ data pages، وإزاي الـ crash recovery بيشتغل
  • تشرح LSM-tree: memtable، flush لـ SSTables، compaction، tombstones
  • تفهم Bloom filter رياضيًا وعمليًا وليه بيقلل read amplification
  • تقارن read/write/space amplification بين B-tree وLSM وتختار حسب الـ workload
  • تقارن التخزين في SQL Server (clustered index) وPostgreSQL (heap + MVCC + VACUUM) وMongoDB (WiredTiger)
  • تربط ده بقرارات عملية: GUID keys، page splits، fill factor، bloat، write-heavy tables

المتطلبات قبل ما تبدأ

01

ليه مهندس ‎.NET محتاج يعرف ده؟

Why storage internals matter to an application engineer
Basics

انت مش هتكتب storage engine. لكن كل قرار يومي في الـ schema بيتحول لعمليات على القرص: نوع الـ primary key، عدد الـ indexes، حجم الـ rows، الـ updates المتكررة، وطريقة الحذف. الفرق بين جدول بيستحمل 50 ألف insert في الثانية وجدول بيقع عند 2,000 غالبًا قرار من دول — مش الهاردوير.

العرض اللي هتشوفهالسبب على مستوى التخزينالقسم
Inserts بتبطأ مع الوقت والـ index بقى fragmentedrandom GUID key ← page splits في B+treeB+tree
جدول PostgreSQL حجمه 3× البيانات الحقيقيةMVCC dead tuples ← bloat من غير VACUUM كافيPostgreSQL
Commit بطيء على VM رخيصfsync للـ WAL على قرص latency عاليWAL
Cassandra/time-series DB بتاخد كتابة ضخمة بسهولة بس القراءة متقلبةLSM: كتابة sequential، قراءة من كذا SSTableLSM
«مسحنا البيانات والمساحة ما رجعتش»tombstones/dead tuples لحد الـ compaction/VACUUMCompaction
02

الـ page: وحدة كل حاجة

Pages: the unit of I/O
Deep dive

الـ database ما بيقراش «صف»؛ بيقرأ page كاملة (8 KB في SQL Server و PostgreSQL، 4 KB افتراضي في SQLite). كل قراءة/كتابة للقرص وكل حاجة في الـ buffer pool (cache الذاكرة) بالـ pages. عشان كده:

  • صف حجمه 4 KB ← صفين في الـ page. صف حجمه 200 byte ← ~40 صف. Scan لمليون صف صغير = 25 ألف page؛ لمليون صف كبير = 500 ألف page. حجم الصف بيأثر مباشرة على سرعة الـ scans والـ cache.
  • الـ buffer pool (shared_buffers في PostgreSQL) بيحتفظ بالـ pages الأكتر استخدامًا. Query «سريعة» ممكن تكون سريعة لأنها في الـ cache بس — قيس الـ logical vs physical reads.
  • الأعمدة الكبيرة (NVARCHAR(MAX)، JSON، text طويل) بتتخزن off-row/TOAST، وجيبها في SELECT * = I/O زيادة.
SQLsee the I/O, not just the time
-- SQL Server
SET STATISTICS IO ON;
SELECT TOP (100) * FROM dbo.Orders WHERE CustomerId = 42 ORDER BY OrderDate DESC;
-- Table 'Orders'. Scan count 1, logical reads 4, physical reads 0 ...  <- pages touched

-- PostgreSQL
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM orders WHERE customer_id = 42 ORDER BY order_date DESC LIMIT 100;
-- Buffers: shared hit=4 read=0   <- hit = from cache, read = from disk/OS cache
03

B+tree: ليه أي صف على بعد 3–4 قراءات

B+trees
Deep dive
root: 1000 | 2000200 | 500 | 8001200 | 15002300 | 2800rows 1..199rows 200..499…rows 1200..1499…fan-out ≈ 8 KB / ~16 bytes per key ≈ 400+ → 3 levels ≈ 64M keys, 4 levels ≈ 25B keys
B+tree: internal pages hold keys and child pointers; leaf pages hold rows (clustered) or row locators, linked for range scans
  • Fan-out عالي: كل internal page فيها مئات المفاتيح، فالشجرة قصيرة جدًا. المستويين العلويين غالبًا في الذاكرة دايمًا، فالـ seek = قراءة أو اتنين من القرص.
  • Leaf pages متربطة ← range scan (BETWEEN, ORDER BY) = نزول مرة واحدة وبعدين مشي على الأوراق.
  • Clustered (SQL Server، InnoDB): الأوراق هي الصفوف نفسها مرتبة بالـ clustering key؛ أي nonclustered index بيخزن الـ clustering key كـ pointer. يعني clustering key عريض (GUID 16 byte + أعمدة) بيكبّر كل index.
  • Heap + index (PostgreSQL): الصفوف في heap من غير ترتيب، وكل index (حتى الـ primary key) بيشاور على مكان فيزيائي (ctid).

Page splits ومشكلة الـ random GUID

لو الـ key بيزيد دايمًا (identity/sequence)، الإدخال دايمًا في آخر ورقة: الـ page بتتملي وتتفتح واحدة جديدة — كتابة متتالية سعيدة. لو الـ key عشوائي (Guid.NewGuid() v4)، كل insert بيروح لورقة عشوائية: لو مليانة، تتقسم نصين (page split) ← كتابة أكتر، pages نص فاضية، fragmentation، و cache أسوأ لأن الـ inserts بتلمس pages في كل حتة.

C#sequential-friendly GUIDs in .NET
// .NET 9+: version 7 GUIDs are time-ordered (Unix ms timestamp in the high bits) -> inserts go to the end in PostgreSQL uuid
var id = Guid.CreateVersion7();

// SQL Server compares uniqueidentifier bytes in a different order than RFC/PostgreSQL,
// so v7 is not automatically "sequential" there. Options: NEWSEQUENTIALID() as a column default,
// EF Core's SequentialGuidValueGenerator (default for Guid keys with the SQL Server provider),
// or an int/bigint identity clustering key with the GUID as a unique nonclustered public id.

Fill factor: ممكن تسيب مساحة فاضية في كل page (مثلًا 90%) عشان الـ inserts/updates العشوائية ما تعملش split فورًا — على حساب مساحة وقراءة أكتر. مفيد للـ indexes اللي بتاخد inserts عشوائية بطبيعتها (email مثلًا).

04

الـ WAL والـ crash recovery

Write-ahead logging
Deep dive

المشكلة: تعديل صف = تعديل page في الذاكرة. لو كل commit استنى يكتب كل الـ pages المتعدلة على القرص (عشوائي ومتفرق)، الـ commits هتبقى بطيئة جدًا. ولو ما كتبش ووقع الكهربا، البيانات ضاعت.

الحل: قبل أي تغيير في الـ data pages على القرص، التغيير بيتسجل في log متسلسل (WAL في PostgreSQL، transaction log في SQL Server). الـ commit = الـ log records بتاعته اتعملها fsync. الـ data pages نفسها بتتكتب بعدين على مهلها (checkpoint / background writer).

UPDATE + COMMITtransactionBuffer pooldirty page in memoryWAL / logappend + fsync at commitData fileswritten later by checkpointCrash recoveryredo from last checkpoint; undo uncommittedThe same log feeds replication (log shipping, streaming replicas) and CDC/outbox relays
Commit durability comes from the sequential log; data pages are flushed later; recovery replays the log
  • ليه أسرع؟ الكتابة في الـ log متسلسلة (append)، والـ fsync واحد ممكن يغطي commits كتير مع بعض (group commit).
  • Checkpoint: بيكتب الـ dirty pages ويحدد نقطة «كل اللي قبلها في الـ data files». الـ recovery بيبدأ من آخر checkpoint بس.
  • أثر عملي: transaction واحدة فيها 10,000 insert أسرع بكتير من 10,000 transaction (fsync واحد بدل 10,000) — نفس درس SQLite. و synchronous_commit = off في PostgreSQL أو delayed durability في SQL Server بيسرّعوا مقابل احتمال خسارة آخر لحظات قبل crash — قرار بيزنس مش تقني بس.
  • الـ log هو مصدر الـ replication والـ CDC: Debezium و logical replication بيقروا نفس الـ log ده — وده اللي بيخلي outbox relay بالـ CDC ممكن.
05

LSM-tree: لما الكتابة هي الأولوية

Log-structured merge trees
Deep dive

بدل ما تعدّل pages في مكانها (in-place)، الـ LSM بيعامل التخزين كله كـ append: الكتابات بتروح memtable في الذاكرة (مرتبة) + log للأمان، ولما الـ memtable تتملي بتتكتب مرة واحدة كملف SSTable مرتب ومش بيتغير. مع الوقت ملفات كتير ← compaction بيدمجها في ملفات أكبر ويشيل القديم والمحذوف.

Write k=vCommit log (append)Memtablesorted, in memoryL0 SST #9L0 SST #8L1: larger, non-overlappingL2: 10× larger …flushcompaction mergesand drops tombstonesRead kmemtable → L0 newest→oldest → L1 → L2 … first hit winseach SSTable has a Bloom filter + sparse index: "definitely not here" skips it
LSM write path is sequential; reads may check the memtable and several SSTables (Bloom filters skip most)
  • Updates: مفيش تعديل في مكانه؛ نسخة أحدث بتكتب، والقراءة بتاخد الأحدث. الـ compaction بيشيل القديم.
  • Deletes: بتتكتب tombstone (علامة «اتمسح»). المساحة ما بترجعش لحد ما الـ compaction يعدّي على كل الملفات اللي فيها النسخ القديمة — وده سبب مشاكل «حذفنا ملايين الصفوف والقراءة بقت أبطأ» (القراءة بتعدّي على tombstones كتير).
  • استراتيجيات الـ compaction: leveled (قراءة أسرع، كتابة إضافية أكتر) مقابل size-tiered (كتابة أرخص، مساحة وقراءة أسوأ). أمثلة: RocksDB، Cassandra، ScyllaDB، وكتير من الـ time-series والـ vector stores.
06

Bloom filter: «أكيد مش موجود» أو «يمكن موجود»

Bloom filters
Deep dive

bit array بحجم m و k hash functions. الإضافة: حط 1 في k مواضع. الفحص: لو أي موضع من الـ k = 0 ← أكيد مش موجود. لو كلهم 1 ← يمكن موجود (false positive ممكن، false negative مستحيل).

C#BloomFilter.cs (illustrative; production code uses tuned hashing)
public sealed class BloomFilter
{
    private readonly BitArray _bits;
    private readonly int _k;
    public BloomFilter(int expectedItems, double falsePositiveRate)
    {
        int m = (int)Math.Ceiling(-expectedItems * Math.Log(falsePositiveRate) / (Math.Log(2) * Math.Log(2)));
        _k = Math.Max(1, (int)Math.Round((double)m / expectedItems * Math.Log(2)));
        _bits = new BitArray(m);
    }
    private IEnumerable<int> Positions(string key)
    {
        var h = System.IO.Hashing.XxHash64.HashToUInt64(Encoding.UTF8.GetBytes(key));
        uint h1 = (uint)h, h2 = (uint)(h >> 32);
        for (int i = 0; i < _k; i++) yield return (int)((h1 + (uint)i * h2) % (uint)_bits.Length);   // double hashing
    }
    public void Add(string key) { foreach (var p in Positions(key)) _bits[p] = true; }
    public bool MightContain(string key) => Positions(key).All(p => _bits[p]);
}
// 1M keys at 1% false positives -> ~9.6 bits per key (~1.2 MB) and k = 7 hash functions.
Bits per keyFalse positive rate تقريبًا
5~9%
10~1%
15~0.1%

استخدامات خارج الـ DB: «هل الـ username ده متاخد؟» قبل ما تضرب الـ DB، تجنب cache penetration (طلبات على مفاتيح مش موجودة)، dedup للـ URLs في crawler، و PostgreSQL نفسه عنده bloom index extension. الحذف مش مدعوم في الـ Bloom العادي (Counting Bloom أو Cuckoo filter لو محتاجه).

07

Read و write و space amplification: المثلث

The amplification trade-off
Deep dive
B+tree (in-place)LSM (append + compaction)
Write amplificationpage كاملة لكل تغيير صغير + WAL؛ page splitsكل بايت بيتكتب أكتر من مرة عبر مستويات الـ compaction (ممكن 10×+) لكن sequential
Read amplificationمنخفض ومتوقع: مسار واحد في الشجرةأعلى: memtable + كذا SSTable (Bloom filters بتقلله)
Space amplificationfragmentation و pages مش مليانةنسخ قديمة و tombstones لحد الـ compaction
Throughput كتابةجيد؛ بيتأثر بالـ random I/Oعالي جدًا (sequential)
Latency قراءةثابتمتقلب أثناء compaction
أنسب لـOLTP عام، قراءات و range queries، transactionsingestion ضخم: logs، events، metrics، time-series، key-value

مفيش engine بيكسب في التلاتة. الـ RUM conjecture بيقول: تحسين اتنين من (Read، Update، Memory/space) بيكون على حساب التالت. القرار يبدأ من الـ workload: نسبة القراءة للكتابة، شكل الـ queries، وحجم البيانات.

08

SQL Server مقابل PostgreSQL مقابل MongoDB على مستوى التخزين

Three engines compared
Deep dive
الجانبSQL ServerPostgreSQLMongoDB (WiredTiger)
تنظيم الصفوفClustered index (B+tree) غالبًا؛ heap ممكنHeap دايمًا؛ كل الـ indexes secondary (ctid)B-tree للـ collection مرتب بـ record id داخلي؛ indexes منفصلة
Updatein-place غالبًا (+ log)نسخة جديدة من الـ tuple (MVCC)؛ القديمة dead لحد VACUUM؛ HOT updates لو مفيش indexed column اتغيرcopy-on-write للـ pages في الذاكرة، checkpoints دورية
Concurrencylocks + اختياري row versioning في tempdb (RCSI/Snapshot)MVCC أصلي: القراءة ما بتعملش block للكتابةMVCC على مستوى الـ document + document-level concurrency
Logtransaction log (.ldf)، VLFsWAL segmentsjournal (WAL) + checkpoints كل ~60 ثانية
Cleanupghost cleanup، index rebuild/reorganizeVACUUM / autovacuum (أساسي!)، bloat monitoringcompaction command لاسترجاع المساحة
ضغطrow/page compression، columnstoreTOAST compression للقيم الكبيرةsnappy/zstd للـ data و prefix compression للـ indexes افتراضيًا

نتايج عملية

  • PostgreSQL + updates كتير على نفس الصفوف (counters، status): dead tuples بتتراكم؛ راقب n_dead_tup، اضبط autovacuum للجدول ده، وفكّر في fillfactor أقل عشان HOT updates تشتغل. عدّاد بيتحدث آلاف المرات في الثانية مكانه Redis، مش صف في PostgreSQL.
  • SQL Server + clustering key: اختار key ضيق ومتزايد وثابت (bigint identity أو sequential GUID) لأنه بيتنسخ في كل index.
  • MongoDB documents كبيرة بتكبر: كل update بيكتب نسخة جديدة من الـ document؛ arrays بتكبر للأبد = documents ضخمة وكتابة أكتر. ده سبب قاعدة «ما تعملش unbounded arrays» في MongoDB.
  • Long-running transactions في الاتنين بتمنع التنظيف (PostgreSQL ما يقدرش يمسح tuples ممكن الـ transaction القديمة تشوفها؛ SQL Server row versions في tempdb بتكبر).
SQLPostgreSQL: is this table bloated?
SELECT relname, n_live_tup, n_dead_tup,
       round(100.0 * n_dead_tup / NULLIF(n_live_tup + n_dead_tup, 0), 1) AS dead_pct,
       last_autovacuum, last_autoanalyze
FROM pg_stat_user_tables
ORDER BY n_dead_tup DESC
LIMIT 10;
10

أخطاء شائعة

Common mistakes
Basics
  • Random GUID v4 كـ clustered key في جدول insert-heavy.
  • Indexes كتير «احتياطي» على جدول write-heavy: كل index = كتابة إضافية لكل insert/update.
  • تعطيل أو تجاهل autovacuum في PostgreSQL، أو transactions مفتوحة لساعات.
  • Delete ضخم مرة واحدة ← log ضخم، locks، وفي LSM tombstones كتير. احذف على دفعات، أو partitions و drop للـ partition.
  • الحكم على الأداء من query تانية مرة (cache دافي) من غير ما تبص على physical reads.
  • افتراض إن «NoSQL أسرع» من غير ما تفهم الـ engine والـ workload.
11

اختبر فهمك

Knowledge check
Basics

ليه الـ commit في database بيعتمد على fsync للـ WAL مش للـ data pages؟

Bloom filter قال «يمكن موجود». إيه المعنى؟

جدول PostgreSQL فيه عمود status بيتحدث 50 مرة لكل صف، وحجمه بيكبر رغم إن عدد الصفوف ثابت. السبب الأرجح؟

12

تمارين محلولة

Worked exercises
Practical
1: احسب عمق B+tree لجدول فيه 500 مليون صف، fan-out 400

الحل: 400¹ = 400، 400² = 160,000، 400³ = 64M، 400⁴ = 25.6B. يبقى 4 مستويات (root + 2 internal + leaf). الـ root والمستوى التاني في الذاكرة غالبًا، فالـ seek = 1–2 قراءة قرص. ده ليه الـ index seek «فوري» حتى على جداول ضخمة، والمشكلة دايمًا في عدد الـ seeks (key lookups) مش في عمق الشجرة.

2: نظام بيستقبل 200 ألف event/ثانية للـ telemetry، والقراءة غالبًا آخر ساعة لكل device. أنهي engine؟

الحل: write-heavy، append-only، قراءات range زمنية على أحدث بيانات، وحذف بالـ retention ← LSM/time-series engine (أو columnar time-series) أنسب من B-tree OLTP. صمّم الـ key بـ (device_id, time) عشان القراءة تبقى range scan، والـ retention بـ partitions زمنية تتشال كاملة (بدل tombstones). وخلي بيانات الـ SaaS الأساسية (tenants، billing) في PostgreSQL/SQL Server.

3: insert rate وقع من 20k/s لـ 3k/s بعد ما الجدول عدّى 200M صف، والـ key = Guid.NewGuid()

الحل: الـ index بقى أكبر من الذاكرة، والـ random keys بيلمسوا pages عشوائية مش في الـ cache ← physical reads + page splits. الحل: key متسلسل (identity أو sequential/v7 GUID حسب الـ engine)، وراجع عدد الـ secondary indexes. قِس قبل وبعد بـ page splits/sec (SQL Server) أو buffer reads.

13

أسئلة إنترفيو

Interview questions
Basics
(Mid) إيه الفرق بين B-tree و LSM-tree؟
B-tree بيعدّل pages في مكانها وبيدّي قراءة ثابتة ومنخفضة التكلفة؛ LSM بيكتب sequential في memtable و SSTables مش بتتغير وبيدمجها بالـ compaction، فبيدّي كتابة أسرع بكتير مقابل read و space amplification أعلى.
(Mid) ليه random GUID كـ clustered key مشكلة؟
كل insert بيروح لمكان عشوائي في الشجرة فيعمل page splits و fragmentation ويلمس pages مش في الـ cache؛ وفي SQL Server كمان بيتنسخ في كل nonclustered index (16 byte).
(Senior) PostgreSQL مقابل SQL Server في update-heavy workload؟
PostgreSQL MVCC بيكتب نسخة جديدة لكل update فمحتاج VACUUM ملاحق و HOT updates (fillfactor، ما تعملش index على الأعمدة اللي بتتحدث)؛ SQL Server بيعدّل in-place مع locks (أو versions في tempdb مع RCSI). في الاتنين: transactions قصيرة، وعدادات hot مكانها Redis أو batching.
↗

المراجع والقراءة الإضافية

References & further reading

الدرس بيشرح الفكرة نفسها؛ الروابط دي للتحقق والتعمق والرجوع لتفاصيل الـ API. (محتاجة إنترنت.)

خلصت الدرس وحليت الأسئلة؟ علّم عليه عشان يتحسب في تقدّمك.

محتويات الدرس