Serializability: إمتى التداخل يبقى صح؟
عندنا معيار واحد للصح: النتيجة تساوي تشغيل الترانزاكشنز ورا بعض بترتيب ما. الدرس ده بيعلّمك تحكم على أي Schedule بالورقة والقلم: تحدد التعارضات، وترسم الـ Precedence Graph، وتعرف ليه الداتابيز بتهتم كمان بإمكانية الـ Rollback.
- تعرّف Serializability وتفرّقها عن Serial
- تحدد الـ Conflicts في أي Schedule: RW و WR و WW
- ترسم Precedence Graph وتحكم من الـ Cycles
- تفرّق بين Recoverable و Cascadeless و Strict
1. Serializable مش Serial
Serial يعني فعلاً اتنفذوا ورا بعض. Serializable يعني اتداخلوا، بس محدش يقدر يفرّق بين النتيجة ونتيجة تشغيل ورا بعض. ده الهدف الذهبي: كل التوازي، ونفس صحة التشغيل المتسلسل.
ليه أي ترتيب يكفي؟ لأن لو أحمد وسارة طلبوا في نفس اللحظة، مش فارق مين اتحسب الأول، المهم إن الحسبة تبقى كأن واحد بس اشتغل في الوقت ده.
Serializable = “النتيجة شكلها كأن الترانزاكشنز اشتغلوا ورا بعض”، حتى لو اتداخلوا فعلاً.
2. الـ Conflicts
عشان نحكم على Schedule، مش هنجرّب كل الداتا الممكنة. هنبص على العمليات اللي ترتيبها بيفرق.
| النوع | الشكل | ليه الترتيب بيفرق |
|---|---|---|
| Read-Write (RW) | R1(x) ... W2(x) |
لو اتقلبوا، T1 هتقرا قيمة T2 بدل القيمة القديمة |
| Write-Read (WR) | W1(x) ... R2(x) |
لو اتقلبوا، T2 هتقرا القيمة القديمة بدل قيمة T1 |
| Write-Write (WW) | W1(x) ... W2(x) |
لو اتقلبوا، القيمة النهائية تتغير |
| Read-Read | R1(x) ... R2(x) |
مش تعارض: القرايتين مش بيأثروا على بعض |
أي عمليتين مش متعارضتين وجنب بعض، تقدر تبدّل مكانهم والنتيجة مش هتتغير. ده المفتاح كله.
مثال: R1(x) W1(x) R2(x) W2(x) R1(y) W1(y)
R1(y) W1(y)علىy، و T2 مالهاش دعوة بـy. فنقدر نزقّهم لقدّام فوقW2(x)وR2(x).- النتيجة:
R1(x) W1(x) R1(y) W1(y) R2(x) W2(x)= T1 ثم T2. Serializable ✓
3. الـ Precedence Graph
التبديل باليد متعب. الطريقة المنظمة هي رسم بياني:
النظرية: الـ Schedule Conflict Serializable لو وبس لو الـ Graph مفيهوش Cycle. ولو مفيهوش، أي Topological Sort للـ Graph بيدّيك ترتيب Serial مكافئ.
مثال 1: الـ Lost Update
R1(x) R2(x) W1(x) W2(x)
| العمليتين | نوع التعارض | السهم |
|---|---|---|
R1(x) قبل W2(x) |
RW | T1 → T2 |
R2(x) قبل W1(x) |
RW | T2 → T1 |
W1(x) قبل W2(x) |
WW | T1 → T2 |
فيه سهم T1 → T2 وسهم T2 → T1: ده Cycle. يبقى مش Serializable، وده بالظبط الـ Lost Update اللي شفناه: مفيش ترتيب ورا بعض يدّي النتيجة دي.
مثال 2: تلات ترانزاكشنز
R1(x) W2(x) R3(y) W1(y) R2(z) W3(z)
| العمليتين | نوع التعارض | السهم |
|---|---|---|
R1(x) قبل W2(x) |
RW | T1 → T2 |
R3(y) قبل W1(y) |
RW | T3 → T1 |
R2(z) قبل W3(z) |
RW | T2 → T3 |
الأسهم: T1 → T2 → T3 → T1. Cycle، فمش Serializable، رغم إن مفيش أي عنصر اتكتب مرتين!
عشان تحكم على Schedule: هات كل زوج عمليات متعارضة، ارسم سهم من الأقدم للأحدث، ودوّر على Cycle. مفيش Cycle = Serializable.
4. View Serializability
فيه Schedules Serializable فعلاً بس مش Conflict Serializable. السبب الأشهر: الـ Blind Write، يعني كتابة من غير قراية قبلها.
R1(x) W2(x) W1(x) W3(x)
الـ Graph فيه T1 → T2 (RW) و T2 → T1 (WW)، فيه Cycle. لكن T3 كتبت x في الآخر من غير ما تقرا، فالقيمة النهائية هي بتاعة T3 في كل الأحوال، والنتيجة نفس الترتيب Serial T1 → T2 → T3.
View Serializability أوسع (بتقبل Schedules أكتر)، بس التأكد منها مشكلة NP-complete. علشان كده مفيش داتابيز حقيقية بتستخدمها. كل الأنظمة بتضمن Conflict Serializability، لأن التأكد منها سهل، ولأن الـ Locks والـ Timestamps بيضمنوها تلقائياً.
| Conflict Serializable | View Serializable | |
|---|---|---|
| التعريف | ممكن نوصل لـ Serial بتبديل عمليات مش متعارضة | نفس القرايات ونفس آخر كتابة زي Serial |
| التأكد | سهل: Cycle في Graph | NP-complete |
| بيستخدموه | كل الداتابيز | النظرية بس |
5. Recoverability: الـ Rollback لازم يبقى ممكن
Serializability بتتكلم عن الترانزاكشنز اللي بتنجح. بس فيه ترانزاكشنز بتعمل ABORT (Error، أو Deadlock، أو الكود عمل ROLLBACK). والسؤال: لو واحدة اتلغت، نقدر نلغي أثرها؟
UPDATE t SET x = 50;من غير COMMIT1- 2
SELECT x; -- 50 INSERT INTO log VALUES (50);قرت 50 - 3
COMMIT;اتثبتت ROLLBACK;x رجعت 104
UPDATE t SET x = 50;من غير COMMIT1- 2
SELECT x; -- 50قرت 50 ROLLBACK;x رجعت 103- 4
ROLLBACK; -- اتجبرتاتلغت هي كمان
دوس ▶ شغّل، أو امشي خطوة خطوة بالأسهم.
| النوع | الشرط | بيمنع |
|---|---|---|
| Recoverable | لو Tj قرت من Ti، يبقى Tj ماتعملش COMMIT قبل Ti | الـ COMMIT على داتا اتلغت |
| Cascadeless (ACA) | محدش يقرا إلا حاجة اتعملها COMMIT | الـ Cascading Aborts |
| Strict | محدش يقرا ولا يكتب فوق حاجة إلا لما اتعملها COMMIT أو ABORT | لازم عشان الـ Rollback يبقى مجرد “رجّع القيمة القديمة” |
كل نوع جوه اللي قبله: Strict ⊂ Cascadeless ⊂ Recoverable. والداتابيز الحقيقية بتعمل Strict: الـ Locks على الكتابة بتفضل لحد الـ COMMIT، والقراية بتشوف آخر حاجة اتعملها COMMIT بس. وده بالظبط ليه READ COMMITTED هو الحد الأدنى العملي.
Serializability بتضمن إن الناجحين صح، والـ Strictness بتضمن إن الفاشلين يتلغوا من غير ما يجروا حد معاهم.
6. أسئلة الإنترفيو
فكّر في إجابتك الأول، وبعدين افتح السؤال.
01الفرق بين Serial و Serializable؟
Serial: الترانزاكشنز اتنفذت فعلاً ورا بعض من غير تداخل. Serializable: اتداخلت، بس النتيجة مساوية لتشغيلها ورا بعض بترتيب ما. الداتابيز بتسعى للتاني لأنه بيدّي توازي وصحة مع بعض.
02إمتى عمليتين يبقوا متعارضين (Conflicting)؟
لما يكونوا من ترانزاكشنين مختلفين، وعلى نفس العنصر، وواحدة منهم على الأقل كتابة. يعني RW و WR و WW. القرايتين مع بعض مش تعارض.
03إزاي تعرف إن Schedule هو Conflict Serializable؟
ترسم Precedence Graph: نقطة لكل ترانزاكشن، وسهم من Ti لـ Tj لكل عملية في Ti متعارضة مع عملية بعدها في Tj. لو مفيش Cycle يبقى Conflict Serializable، والـ Topological Sort بيدّيك الترتيب المكافئ.
04ليه الداتابيز مش بتستخدم View Serializability رغم إنها أوسع؟
لأن التأكد منها NP-complete. Conflict Serializability تأكيدها سهل (Cycle detection)، والـ Locks والـ Timestamps بيضمنوها تلقائياً. والفرق بينهم بيظهر بس في حالات Blind Writes.
05يعني إيه Cascading Abort؟ وإزاي بيتمنع؟
ترانزاكشن تتلغى، فكل ترانزاكشن قرت من كتابتها اللي لسه ماتثبتتش لازم تتلغى، وهكذا في سلسلة. بيتمنع لو محدش يقرا إلا داتا اتعملها COMMIT (Cascadeless)، والداتابيز بتضمن ده بإنها تمسك الـ Write Locks لحد الـ COMMIT (Strict 2PL) أو بالـ MVCC.