Dağıtılmış DBMS - Eş Zamanlılık Kontrolü
Eşzamanlılık kontrol teknikleri, işlemlerin ACID özelliklerini ve çizelgelerdeki serileştirilebilirliği korurken birden fazla işlemin aynı anda yürütülmesini sağlar.
Bu bölümde, eşzamanlılık kontrolü için çeşitli yaklaşımları inceleyeceğiz.
Kilitleme Tabanlı Eş Zamanlılık Kontrol Protokolleri
Kilitleme tabanlı eşzamanlılık kontrol protokolleri, veri öğelerini kilitleme konseptini kullanır. Birlocko veri öğesi üzerinde okuma / yazma işlemlerinin gerçekleştirilip gerçekleştirilemeyeceğini belirleyen bir veri öğesi ile ilişkili bir değişkendir. Genel olarak, bir veri öğesinin aynı anda iki işlemle kilitlenip kilitlenemeyeceğini belirten bir kilit uyumluluk matrisi kullanılır.
Kilitleme tabanlı eşzamanlılık kontrol sistemleri, tek fazlı veya iki fazlı kilitleme protokollerini kullanabilir.
Tek fazlı Kilitleme Protokolü
Bu yöntemde, her işlem bir öğeyi kullanmadan önce kilitler ve onu kullanmayı bitirir bitirmez kilidi serbest bırakır. Bu kilitleme yöntemi maksimum eşzamanlılık sağlar, ancak her zaman serileştirilebilirliği zorlamaz.
İki fazlı Kilitleme Protokolü
Bu yöntemde, tüm kilitleme işlemleri ilk kilit açma veya kilit açma işleminden önce gelir. İşlem iki aşamadan oluşmaktadır. İlk aşamada, bir işlem yalnızca ihtiyaç duyduğu tüm kilitleri alır ve herhangi bir kilidi açmaz. Buna genişleyen veyagrowing phase. İkinci aşamada, işlem kilitleri serbest bırakır ve yeni kilit talep edemez. Bu denirshrinking phase.
İki aşamalı kilitleme protokolünü izleyen her işlemin serileştirilebilir olması garanti edilir. Ancak bu yaklaşım, iki çakışan işlem arasında düşük paralellik sağlar.
Zaman Damgası Eşzamanlılık Kontrol Algoritmaları
Zaman damgası tabanlı eşzamanlılık kontrol algoritmaları, serileştirilebilirliği sağlamak için bir veri öğesine eşzamanlı erişimi koordine etmek için bir işlemin zaman damgasını kullanır. Zaman damgası, işlemin başlangıç zamanını temsil eden bir işleme DBMS tarafından verilen benzersiz bir tanımlayıcıdır.
Bu algoritmalar, işlemlerin zaman damgaları tarafından dikte edilen sırayla tamamlanmasını sağlar. Eski işlem sisteme genç olandan önce girdiğinden, daha eski bir işlem daha genç bir işlemden önce yapılmalıdır.
Zaman damgası tabanlı eşzamanlılık kontrol teknikleri, eşdeğer seri programın katılan işlemlerin yaşına göre düzenleneceği şekilde serileştirilebilir programlar oluşturur.
Zaman damgası tabanlı eşzamanlılık kontrol algoritmalarından bazıları -
- Temel zaman damgası sıralama algoritması.
- Konservatif zaman damgası sıralama algoritması.
- Zaman damgası sıralamasına dayalı çok yönlü algoritma.
Zaman damgasına dayalı sıralama, serileştirilebilirliği zorunlu kılmak için üç kuralı izler -
Access Rule- İki işlem aynı veri öğesine aynı anda erişmeye çalıştığında, çakışan işlemler için öncelik eski işleme verilir. Bu, daha genç işlemin önce eski işlemin tamamlanmasını beklemesine neden olur.
Late Transaction Rule- Daha genç bir işlem bir veri öğesi yazdıysa, daha eski bir işlemin bu veri öğesini okumasına veya yazmasına izin verilmez. Bu kural, daha genç işlem zaten taahhüt edildikten sonra eski işlemin gerçekleştirilmesini engeller.
Younger Transaction Rule - Daha genç bir işlem, daha eski bir işlem tarafından zaten yazılmış bir veri öğesini okuyabilir veya yazabilir.
İyimser Eş Zamanlılık Kontrol Algoritması
Düşük çakışma oranlarına sahip sistemlerde, her işlemi serileştirilebilirlik için doğrulama görevi performansı düşürebilir. Bu durumlarda, serileştirilebilirlik testi, commit'den hemen öncesine ertelenir. Çakışma oranı düşük olduğundan, serileştirilemeyen işlemlerin iptal edilme olasılığı da düşüktür. Bu yaklaşıma iyimser eşzamanlılık kontrol tekniği denir.
Bu yaklaşımda, bir işlemin yaşam döngüsü aşağıdaki üç aşamaya bölünmüştür:
Execution Phase - Bir işlem, veri öğelerini belleğe alır ve bunlar üzerinde işlemler gerçekleştirir.
Validation Phase - Bir işlem, değişikliklerini veritabanında gerçekleştirmenin serileştirilebilirlik testini geçmesini sağlamak için kontroller gerçekleştirir.
Commit Phase - Bir işlem hafızadaki değiştirilmiş veri öğesini diske geri yazar.
Bu algoritma, doğrulama aşamasında serileştirilebilirliği zorlamak için üç kural kullanır -
Rule 1- T i ve T j adlı iki işlem verildiğinde , eğer T i , T j'nin yazmakta olduğu veri öğesini okuyorsa , o zaman T i'nin yürütme aşaması, T j'nin kesinleştirme aşamasıyla çakışamaz . T j yalnızca T i yürütmeyi bitirdikten sonra işleyebilir .
Rule 2- T i ve T j adlı iki işlem verildiğinde , eğer T i , T j'nin okuduğu veri öğesini yazıyorsa , o zaman T i’nin kesinleştirme aşaması T j’nin yürütme aşamasıyla çakışamaz . T j , ancak T i zaten taahhüt ettikten sonra çalışmaya başlayabilir .
Rule 3- T i ve T j adlı iki işlem verildiğinde , eğer T i , T j'nin de yazdığı veri öğesini yazıyorsa, o zaman T i’nin kesinleştirme aşaması T j’nin kesinleştirme aşamasıyla çakışamaz . T j , ancak T i zaten taahhüt ettikten sonra işlemeye başlayabilir .
Dağıtık Sistemlerde Eş Zamanlılık Kontrolü
Bu bölümde, yukarıdaki tekniklerin dağıtık bir veritabanı sisteminde nasıl uygulandığını göreceğiz.
Dağıtılmış İki Aşamalı Kilitleme Algoritması
Dağıtılmış iki fazlı kilitlemenin temel prensibi, temel iki fazlı kilitleme protokolü ile aynıdır. Bununla birlikte, dağıtılmış bir sistemde kilit yöneticileri olarak belirlenmiş siteler vardır. Bir kilit yöneticisi, işlem monitörlerinden gelen kilit edinme isteklerini kontrol eder. Çeşitli sitelerdeki kilit yöneticileri arasında koordinasyonu sağlamak için en az bir siteye tüm işlemleri görme ve kilit çatışmalarını tespit etme yetkisi verilmiştir.
Kilit çakışmalarını tespit edebilen sitelerin sayısına bağlı olarak, dağıtılmış iki fazlı kilitleme yaklaşımları üç tipte olabilir -
Centralized two-phase locking- Bu yaklaşımda, bir site merkezi kilit yöneticisi olarak belirlenmiştir. Ortamdaki tüm siteler merkezi kilit yöneticisinin yerini bilir ve işlemler sırasında buradan kilit alır.
Primary copy two-phase locking- Bu yaklaşımda, bir dizi site kilit kontrol merkezleri olarak belirlenmiştir. Bu sitelerin her biri, tanımlanmış bir dizi kilidi yönetme sorumluluğuna sahiptir. Tüm siteler, hangi veri tablosu / parça öğesinin kilidinin yönetilmesinden hangi kilit kontrol merkezinin sorumlu olduğunu bilir.
Distributed two-phase locking- Bu yaklaşımda, her kilit yöneticisinin kendi yerel sitesinde depolanan veri öğelerinin kilitlerini kontrol ettiği bir dizi kilit yöneticisi vardır. Kilit yöneticisinin konumu, veri dağıtımına ve kopyalamaya bağlıdır.
Dağıtılmış Zaman Damgası Eş Zamanlılık Kontrolü
Merkezi bir sistemde, herhangi bir işlemin zaman damgası fiziksel saat okuması ile belirlenir. Ancak, dağıtılmış bir sistemde, herhangi bir sitenin yerel fiziksel / mantıksal saat okumaları, küresel olarak benzersiz olmadıklarından, küresel zaman damgaları olarak kullanılamaz. Dolayısıyla, bir zaman damgası site kimliği ile o sitenin saat okumasının bir kombinasyonundan oluşur.
Zaman damgası sıralama algoritmalarını uygulamak için, her site, her işlem yöneticisi için ayrı bir sıra tutan bir programlayıcıya sahiptir. İşlem sırasında, bir işlem yöneticisi sitenin programlayıcısına bir kilit isteği gönderir. Zamanlayıcı, talebi artan zaman damgası sırasına göre ilgili kuyruğa koyar. İstekler, zaman damgalarına göre, yani en eskisi ilk sıraya göre kuyrukların önünden işlenir.
Çatışma Grafikleri
Diğer bir yöntem de çakışma grafikleri oluşturmaktır. Bu işlem için sınıflar tanımlanmıştır. Bir işlem sınıfı, okuma kümesi ve yazma kümesi olarak adlandırılan iki veri kümesi içerir. İşlemin okuma kümesi, sınıfın okuma kümesinin bir alt kümesiyse ve işlemin yazma kümesi, sınıfın yazma kümesinin bir alt kümesiyse, işlem belirli bir sınıfa aittir. Okuma aşamasında, her işlem, okuma kümesindeki veri öğeleri için okuma isteklerini yayınlar. Yazma aşamasında, her işlem kendi yazma isteklerini yayınlar.
Aktif işlemlerin ait olduğu sınıflar için bir çakışma grafiği oluşturulur. Bu, bir dizi dikey, yatay ve çapraz kenar içerir. Dikey kenar, bir sınıf içindeki iki düğümü birbirine bağlar ve sınıf içindeki çatışmaları belirtir. Yatay kenar, iki sınıftaki iki düğümü birbirine bağlar ve farklı sınıflar arasında bir yazma-yazma çakışmasını belirtir. Köşegen bir kenar, iki sınıftaki iki düğümü birbirine bağlar ve iki sınıf arasındaki yazma-okuma veya okuma-yazma çatışmasını belirtir.
Çatışma grafikleri, aynı sınıfta mı yoksa iki farklı sınıfta mı iki işlemin paralel olarak yürütülebileceğini belirlemek için analiz edilir.
Dağıtılmış İyimser Eş Zamanlılık Kontrol Algoritması
Dağıtılmış iyimser eşzamanlılık kontrol algoritması, iyimser eşzamanlılık kontrol algoritmasını genişletir. Bu uzantı için iki kural uygulanır -
Rule 1- Bu kurala göre, bir işlem yürütüldüğünde tüm sitelerde yerel olarak doğrulanmalıdır. Herhangi bir sitede bir işlem geçersiz bulunursa, iptal edilir. Yerel doğrulama, işlemin yürütüldüğü sitelerde serileştirilebilirliği sürdürmesini garanti eder. Bir işlem yerel doğrulama testini geçtikten sonra global olarak doğrulanır.
Rule 2- Bu kurala göre, bir işlem yerel doğrulama testini geçtikten sonra küresel olarak doğrulanmalıdır. Global doğrulama, iki çakışan işlemin birden fazla sitede birlikte yürütülmesi durumunda, birlikte çalıştıkları tüm sitelerde aynı göreceli sırada taahhüt etmelerini sağlar. Bu, işlemden önce doğrulamadan sonra diğer çakışan işlemi beklemesini gerektirebilir. Bu gereksinim, algoritmayı daha az iyimser hale getirir çünkü bir işlem bir sitede doğrulanır doğrulanmaz tamamlanamayabilir.