بخشی از مقاله
افزايش کنترل همروندي تراکنش ها در سيستم هاي توزيع شده با روش مهر زمان
چکيده : يکي از مهمترين بحث ها در سيستم هاي توزيع شده ، بررسي کنترل همروندي تراکنش ها در اجراي همزمان آنها مي باشد. در نتيجه عدم نظارت بر کنترل همروندي تـراکنش هـا ممکـن اسـت جامعيـت و سازگاري داده ها با مشکلاتي مواجه شود. در اين مقاله ابتدا بـه بررسـي کنترل همروندي تراکنشها پرداخته و مشکلات بوجـود آمـده در نتيجـه عدم نظارت بر کنترل همروندي را مورد بررسي قرار مي دهـيم ، و بـراي حفظ جامعيت و سازگاري داده ها از خاصيت معـروف ACID، برقـراري اجــراي منفــرد ( Isolation ) را در همرونــدي تــراکنش هــا مطــرح مي کنيم . در محور اصلي اين مقاله نيز الگوريتم هاي مختلفي که براي کنترل همروندي تراکنش هـا بکـار مـي رود، را از سـه ديـدگاه بررسـي مي کنيم و با توجه به اينکه در بيشتر سيستم هاي توزيع شـده از روش قفـل کـردن اسـتفاده مـي شـود، روش قفـل گـذاري ( Locking ) و مهر زماني ( Timestamp ) را از اين ديدگاهها مقايسه کرده و در آخـر نيز با استفاده از نتايج تجربـي نشـان مـي دهـيم کـه اسـتفاده از روش مهر زماني کارايي بالاتري خواهد داشت .
واژه هاي کليدي: برخورد ، همروندي ، تجزيه ، مهر زماني ، قفل .
١- مقدمه
سيستم هاي توزيع شده و تراکنش ها در بيشتر کاربردها مورد اسـتفاده قرار مي گيرنـد. بـراي جلـوگيري از اجـراي نادرسـت و دسـتيابي غلـط سيستم هاي توزيع شده ، مديريت سيستم هاي توزيع شده بايـد توسـط زمانبند (Scheduler) دستيابي همزمان آنها را نظارت ، بررسي و کنترل نمايد. حفظ و نگه داشتن سازگاري سيستم هاي توزيع شده و جامعيت داده ها زماني که اجازه مي دهيم چندين تراکنش عنصر داده يکساني را در يک زمان مورد دستيابي قرار دهد به عنوان همروندي تراکنش هـا شناخته مي شود.
٢- کنترل همروندي
همچنان که ذکر شد مهمترين بحث در سيستم هاي توزيع شده همزماني تراکنش هاي موجود مي باشد. ايده هاي مختلفي براي افزايش مکانيزم هاي کنترل همروندي صورت گرفته است ، که Locking و Timestamp شامل اين ايده ها مي باشد. همه اين مکانيزم ها به اين جهت مورد بررسي قرار مي گيرند که بتوانيم جامعيت پايگاه داده و سازگاري داده ها را در سطح بالايي حفظ کنيم . جامعيت سيستم هاي توزيع شده به اين معناست که با اعمال مجموعه اي از محدوديت ها (قواعد و قوانين ) باعث شويم وضعيت سيستم هاي توزيع شده در يک حالت صحيح و پايدار قرار گيرد.
در اين مقاله با استفاده از چهار خاصيت ACID براي حفظ جامعيت و کنترل همروندي براي تضمين Isolation خواهيم پرداخت . کنترل همروندي، اجازه دستيابي افراد بطور همزمان به موجوديتهاي مشترک مي باشد يعني يک عنصر داده اي همزمان توسط چندين تراکنش مورد دستيابي قرار مي گيرد. در نقطه مقابل همزماني ، سريالپذيري مطرح مي شود. اما چرا از سريالپذيري کمتر استفاده مي کنيم . يکي از معايب اجراي سريال اين مي باشد که ميزان گذردهي تراکنش هاي کوچک قابل قبول نمي باشد. دوم اينکه زمان پاسخ براي کاربران که تراکنش مورد نظر را اجرا مي کنند طولاني مي باشد. بنابراين نياز است تا از همزماني و همروندي بين تراکنش ها استفاده شود. اما اين همروندي باعث بوجود آمدن مشکلي به نام Conflict يا برخورد مي شود.
٢-١ بررسي برخورد
براي درک اينکه همروندي تراکنش ها چگونه پياده سازي مي شود، ابتدا مفهومي به نام Conflict يا برخورد را بررسي مي کنيم که در سيستم بايد آنها را تشخيص داده و سپس آنها را برطرف کنيم . هدف از ارائه الگوريتم هاي کنترل همروندي نيز اين مي باشد که اگر سيستم هاي توزيع شده در شرايط Conflict قرار گرفت ، جامعيت داده حفظ شود.
همچنان که مي دانيم هر تراکنش از مجموعه اي از عمليات Write و Read تشکيل يافته است . دو تراکنش موقعي در شرايط Conflict قرار مي گيرند که عمل خواندن با يک عمل نوشتن تراکنش ديگر متعامل شود، يا يک عمل نوشتن با عمل نوشتن تراکنش ديگر متعامل مي شود. شکل ١ مطلب فوق را نشان مي دهد.
در کل مي توانيم بگوييم که T1 و T2 با هم در Conflict |هستند، به شرطي که هر دوي آنها با هم در يک زمان اجرا شوند، يعني اگر T1 قبل ار شروع T2 به اتمام برسد حتي در صورتي که عمل Write و Read آنها با هم در تعامل باشند، برخورد رخ نمي دهد.
همچنان که مطرح شد مهمترين نکته اي که بايد در برخورد در نظر داشته باشيم حفظ جامعيت داده ها مي باشد. اما موقعي که دو تراکنش عنصر داده يکساني را مورد تغيير قرار مي دهند، چهار نوع مشکل ممکن است رخ دهد.
(Lost update) Dirty Write – M1
(Uncommitted data) Dirty Read – M
Non-repeatable read – M
Phantom read –M
شرايط M1 ، M2، M3 و M4 موقعي رخ مي دهد که کنترل همروندي بر روي تراکنش ها صورت نگيرد که در سيستم هاي توزيع شده واقعي يا از همروندي تراکنش ها جلوگيري کرده و يا آنها را کنترل مي کنند.
موقعي که تراکنش ها بصورت همزمان اجرا مي شوند، مهمترين عاملي که بايد در نظر بگيريم تضمين Isolation از خاصيت ACID مي باشد.
فرض کنيم دو کاربر مي خواهند يک عنصر داده را مورد دستيابي و تغيير قرار دهند براي هر کاربر، از بين رفتن تغييرات شخصي آن زماني که کاربر دوم تغييرات متفاوتي را ذخيره مي کند قابل قبول نمي باشد.
هر دو کاربر بايد بتواند بصورت منفرد کار کند بطوريکه فکر کنند فقط يک کاربر در حال کار است و هر تغييرات بايد از ديد کاربران ديگر مجزا باشد. و بنابراين اقداماتي که از طرف مديريت سيستم هاي توزيع شده براي جلوگيري از Conflict بين تراکنش ها صورت مي گيرد به مفهوم برقراري Isolation مي باشد.
٢-٢ معيار دسته بندي الگوريتم هاي همروندي
الگوريتم هاي مختلفي براي تضمين سطوح وکنترل همروندي تراکنش ها وجود دارد که ابتداء يک دسته بندي از اين الگوريتم ها ارائه مي دهيم .
همچنان که ذکر شد سطوح مختلف Isolation در همروندي تراکنشها بايد تضمين شود اما در حالت کلي الگوريتم هاي مختلفي که براي همروندي تراکنش ها طراحي مي شوند داراي خصوصيات زير هستند.
١- Optimistic يا Pessimistic
٢- Non Locking يا Locking
٣- Non versioned يا Versioned
در روش Pessimistic اگر بخواهيم يک عنصر را قفل کنيم ، بر روي آن قفل زده و اجازه نمي دهيم هيچ کس رکورد مورد نظر را تا زماني که تغييرات را انجام داده و ثبت نکرده ايم تغيير دهد. يعني به کاربران ديگر اجازه خواندن را مي دهد، اما اجازه تغييرات نمي دهد. مزاياي اين روش اين مي باشد که براي پياده سازي راحت مي باشد و تضمين مي کند که تغييرات سيستم هاي توزيع شده ماندگار و امن خواهد بود.
اما ايراد اين روش اين است که مقياس پذير (Scalable) نيست .
در روش Optimistic رکورد هاي سيستم هاي توزيع شده را خوانده ، اما آن را قفل نمي کنيم . هر کس مي تواند رکورد مورد نظر را خوانده و تغيير دلخواه را بر روي آن انجام دهد. يعني به فعاليت خود ادامه مي دهند. ولي در لحظه Commit بررسي مي شود اگر خطايي رخ نداده باشد عمل Commit انجام مي گيرد، در غير اين صورت تراکنش مورد نظر abort مي شو اين روش در سيستم هايي که برخورد تراکنش ها حداقل باشد کاربرد دارند.
در روش Locking برروي هر عنصر داده که آن را مورد استفاده قرار مي دهيم ، قفل زده مي شود. اگر تراکنش خاصي نتواند به اجراي خود ادامه دهد abort مي شود. ايراد روش Locking اين مي باشد که حتي زماني که تعداد برخورد ها کم باشد داراي سربار بيشتري مي باشد.
اما روش Non Locking از بوجود آمدن سربار حاصل از Locking جلوگيري مي کند. از تأخيرات بيش از حد جلوگيري مي کند و نرخ abort ها را نيز افزايش مي دهد اين روش زماني که برخوردهاي زيادي در سيستم وجود ندارد مناسب مي باشد. علاوه بر آن در سيستم هاي توزيع شده نيز به خوبي عمل مي کند.
حالت Single Version سيستم هاي توزيع شده بوسيله همه تراکنشها مورد استفاده قرار مي گيرد در اين حالت از هر داده فقط يک نسخه موجود مي باشد. در حالت Multiversion سيستم هاي توزيع شده ، هر داده بصورت چند نسخه نگهداري مي شود. يعني هر داده هنگام ذخيره شدن يک مهر زماني مي خورد و در هنگام ذخيره شدن هاي بعدي نيز با مهر زماني جديد ذخيره مي شود.
اما همچنان که مي دانيم اگر بخواهيم در دنياي واقعي دو عنصر يا دو گزينه را با هم مقايسه کنيم در اولين مرحله بايد معيارهاي مقايسه را داشته باشيم ، تا بتوانيم از روي آنها عمل مقايسه را انجام دهيم . حال در اين مقاله دو روش Timestamp و Locking را به طور خلاصه وار معرفي کرده و مطابق با معيار هاي ذکر شده آنها را با هم مقايسه مي کنيم .
٣- روش قفل (Locking) و مهر زماني (Timestamp)
در اين بخش به بررسي روش قفل کردن و مهر زماني پرداخته و آنها را مطابق با معيار هاي بخش ٢-٢ مقايسه مي کنيم .
