أبسط داتابيز في الدنيا
تخيل داتابيز عبارة عن فايل بتعمل له append: set key value بتضيف سطر في الآخر، وget key بتدور على آخر سطر للمفتاح ده.
سريعة جدًا — مجرد append. وده نفس اللي بتعمله داتابيزات كتير جوه: log (يعني سجل append-only).
كارثة — O(n): بتلف على الفايل كله.
الحل: Index = بنية إضافية مشتقة من الداتا الأساسية بتساعدك توصل بسرعة. وده trade-off أساسي:
Hash Indexes
خلي في الرام hash map: كل key → الـ byte offset بتاعه في الفايل. ده بالظبط اللي بيعمله Bitcask (الـ engine الافتراضي في Riak). ممتاز لو المفاتيح قليلة تدخل الرام والقيم بتتحدث كتير (زي عداد مشاهدات فيديو).
طب الفايل هيكبر للأبد؟ لأ — نقسم الـ log لـ segments، ولما segment يوصل حجم معين نقفله ونبتدي واحد جديد، وفي الخلفية نعمل compaction (نشيل المفاتيح المكررة ونسيب آخر قيمة) وmerge للسيجمنتات. ولكل segment الـ hash map بتاعه.
تفاصيل التنفيذ
SSTables و LSM-Trees
تعديل صغير بفرق كبير: خلي جوه كل segment المفاتيح مترتبة = Sorted String Table (SSTable). المميزات:
- Merge سهل وفعال زي merge sort، حتى لو الفايلات أكبر من الرام. ولو المفتاح في كذا segment ناخد الأحدث.
- Sparse index: مش محتاج تخزن كل المفاتيح في الرام — مفتاح كل كام كيلوبايت يكفي، لأن الترتيب بيخليك تعرف المفتاح هيبقى بين مين ومين وتمسح حتة صغيرة.
- ممكن تـ compress كل block قبل ما تكتبه — توفير مساحة و I/O.
طب إزاي نخلي المفاتيح مترتبة والكتابات جاية عشوائي؟
القراءة: دور في الـ memtable، بعدين أحدث segment، وبعدين اللي قبله… ولو السيرفر وقع؟ الـ memtable هيضيع، فبنكتب كل write كمان في log منفصل append-only عشان الـ recovery (وبيتمسح بعد الـ flush).
ده اسمه LSM-Tree (Log-Structured Merge-Tree) — مستخدم في LevelDB و RocksDB و Cassandra و HBase (المستوحاة من Bigtable)، وفكرة شبيهة في Lucene (محرك Elasticsearch/Solr) للـ term dictionary.
B-Trees — ملك الداتابيزات
أشهر index من السبعينات، موجود في كل الـ relational DBs وكتير من غيرها. برضه بيخلي المفاتيح مترتبة، بس فلسفة مختلفة تمامًا:
segments متغيرة الحجم (ميجات)، وبيكتب sequential دايمًا.
الديسك متقسم pages ثابتة (غالبًا 4KB)، وبيعدل الصفحة في مكانها.
فيه root page، وكل صفحة فيها مفاتيح وreferences لصفحات أولاد (كل واحدة مسؤولة عن range). بتنزل لحد leaf page. عدد الأولاد للصفحة = branching factor (غالبًا مئات). الشجرة دايمًا balanced: n مفتاح = عمق O(log n). 4 مستويات بصفحات 4KB و branching 500 تشيل لحد 256 تيرابايت!
لو الصفحة اتملت وانت بتضيف: تتقسم نصين والأب يتحدث.
إزاي نخليه يستحمل الـ crash؟
- الكتابة فوق صفحة عملية خطيرة (خصوصًا لو split بيعدل كذا صفحة) — لو وقع في النص الشجرة تبوظ.
- الحل: WAL — Write-Ahead Log (اسمه برضه redo log): أي تعديل يتكتب في log append-only قبل ما يتنفذ على الشجرة.
- الـ concurrency: latches (locks خفيفة) عشان threads ماتشوفش الشجرة في حالة نص-نص.
⚖️ LSM vs B-Tree — المقارنة اللي هتتسأل فيها
| LSM-Tree | B-Tree | |
|---|---|---|
| الكتابة | ✅ أسرع غالبًا (sequential، و write amplification أقل أحيانًا) | كل write = WAL + الصفحة (وأحيانًا الصفحة كلها عشان تغيير بايتات قليلة) |
| القراءة | أبطأ شوية (يلف على memtable وكذا segment) | ✅ أسرع ومتوقعة |
| المساحة | ✅ ضغط أحسن، fragmentation أقل | صفحات فيها مساحة فاضية |
| Write amplification · (write واحد بيتحول لكام كتابة على الديسك) | موجود بسبب الـ compaction المتكرر — مهم على SSD لأنها بتستحمل عدد كتابات محدود | WAL + page |
| العيب الكبير | ❌ الـ compaction ممكن يتداخل مع الطلبات ويعمل tail latency عالي. ولو الكتابة أسرع من الـ compaction الديسك يتملى. لازم تراقب ده بنفسك. | كل مفتاح موجود في مكان واحد بالظبط → ✅ transactions و locks على ranges أسهل |
أنواع Indexes تانية
| النوع | الفكرة |
|---|---|
| Secondary index | على عمود مش primary key، والقيم مش unique → كل entry يشاور على لستة IDs أو المفتاح يبقى (value + row id). مهمة جدًا للـ joins. |
| Heap file | الصفوف نفسها متخزنة في مكان والـ indexes بتشاور عليه — مفيش تكرار. لو القيمة الجديدة أكبر وماتنقلتش لازم forwarding pointer. |
| Clustered index | الصف نفسه متخزن جوه الـ index (InnoDB: الـ primary key clustered والـ secondary بيشاور على الـ PK). Covering index = بيخزن شوية أعمدة جواه فبعض الـ queries تتجاوب من الـ index لوحده. التمن: مساحة وكتابة أكتر. |
| Multi-column (concatenated) | زي دليل التليفون (اسم العيلة، الاسم الأول) — مفيد بالترتيب ده بس. |
| Multi-dimensional | لما عايز تبحث بـ 2 أبعاد مع بعض (lat/long في خريطة مطاعم، أو لون RGB، أو تاريخ + حرارة). B-tree عادي مش هيكفي → R-trees (PostGIS). |
| Full-text / Fuzzy | بحث بالمرادفات والأخطاء الإملائية (edit distance). Lucene بيستخدم حاجة شبه trie اسمها Levenshtein automaton. |
كل حاجة في الرام؟ In-Memory DBs
الرامات رخصت، فداتابيزات كتير بقت كلها في الرام (Memcached للكاش، VoltDB, MemSQL, Redis…). ولو عايز durability: battery-backed RAM، log على الديسك، snapshots دورية، أو replication.
OLTP vs OLAP — عالمين مختلفين
| الخاصية | OLTP (Transaction Processing) | OLAP (Analytics) |
|---|---|---|
| القراءة | عدد صغير من الصفوف بالمفتاح | تجميع على ملايين الصفوف |
| الكتابة | random، low latency من المستخدم | Bulk import (ETL) أو event stream |
| مين بيستخدمه | العميل من خلال الأبلكيشن | المحلل الداخلي (business intelligence) |
| الداتا | أحدث حالة | تاريخ الأحداث على مدار الزمن |
| الحجم | GB → TB | TB → PB |
| الـ bottleneck | Disk seek time | Disk bandwidth |
Data Warehouse
داتابيز منفصلة للتحليلات، read-only، فيها نسخة من داتا كل أنظمة الـ OLTP في الشركة. ليه منفصلة؟ عشان الاستعلامات التحليلية التقيلة ماتضربش أداء النظام اللي العملاء شغالين عليه.
كلهم بيتكلموا SQL في الآخر، بس الـ internals مختلفة جدًا. أمثلة: Teradata, Vertica, Redshift، ومفتوحة المصدر زي Hive و Spark SQL و Impala و Presto.
Star و Snowflake Schemas
Column-Oriented Storage
الـ fact table فيها تريليونات صفوف و100 عمود، بس الكويري الواحدة بتحتاج 4-5 أعمدة بس. في التخزين العادي (row-oriented) هتقرا الصف كله! الحل: خزّن كل عمود في فايل لوحده، والصف رقم k = العنصر k في كل فايل.
Column Compression
الأعمدة فيها تكرار كتير (منتجات قليلة مختلفة على ملايين المبيعات) → ضغط جامد. أشهر طريقة: Bitmap encoding — لكل قيمة مميزة bitmap (بت لكل صف)، ولو الـ bitmaps فاضية كتير نعمل run-length encoding. وبعدها WHERE product_sk IN (30, 68, 69) = عملية OR بين 3 bitmaps — سريعة جدًا.
ترتيب الأعمدة
- ماينفعش ترتب كل عمود لوحده (هتفقد مين بتاع مين) — لازم ترتب الصفوف كلها بمفتاح، وتختار المفتاح حسب الكويريز الشائعة (مثلًا التاريخ ثم المنتج).
- العمود الأول المترتب بيتضغط جامد جدًا بالـ run-length.
- Vertica فكرة حلوة: خزن نفس الداتا مترتبة بأكتر من طريقة على replicas مختلفة (بما إنك عامل replication أصلًا)، والكويري تختار الأنسب — شبه multiple secondary indexes.
الكتابة في column store
Update-in-place مستحيل تقريبًا (ضغط + ترتيب). الحل؟ LSM-trees تاني! الكتابة تروح لـ in-memory store، وكل شوية تتدمج مع الملفات على الديسك. والكويري بتقرا من الاتنين.
Materialized Views و Data Cubes
لو بتعمل نفس الـ aggregations (SUM, COUNT…) كتير، خزّن النتيجة جاهزة = materialized view (نسخة حقيقية مش مجرد كويري متخزنة، فلازم تتحدث مع الكتابة — غالية في OLTP بس منطقية في الـ warehouse). نوع منها: OLAP cube — جدول بأبعاد (تاريخ × منتج × …) وكل خلية فيها مجموع جاهز. سريع جدًا بس أقل مرونة (لو عايز تفلتر بحاجة مش بُعد مش هتنفع).
🧪 Lab
ابني أبسط داتابيز في الدنيا بـ bash (append-only log) وحس بالـ trade-off بنفسك:
db_set () { echo "$1,$2" >> database; }db_get () { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1; }db_set 42 '{"name":"Cairo"}'db_set 42 '{"name":"Giza"}'db_get 42 # بيرجع آخر قيمةوبعدين في Postgres: اعمل جدول فيه مليون صف وقارن EXPLAIN ANALYZE لكويري قبل وبعد CREATE INDEX — وقيس وقت الـ INSERT كمان.