An enhanced two phase commit protocol for high performance consistency management in replicated state machines
Çoğaltılmış durum makinelerinde yüksek performanslı tutarlılık yönetimi için geliştirilmiş iki fazlı işlem protokolü
- Tez No: 637248
- Danışmanlar: DOÇ. DR. TOLGA OVATMAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 89
Özet
Durum Makineleri, belirli bir olay kümesi kullanılarak, bu olay kümesiyle alakalı hareket setlerinin yaşam döngülerinin net bir şekilde işlenmesini sağlayan bir araçtır. Herhangi bir aksiyonun sonucu belli olduğundan, bu makineler aynı, veya farklı cihazlarda çoğaltılıp, çoklu makinelerin birbirleriyle iletişimi sağlanıp, aynı süreci takip etmeye zorlanabilirler. Buna çoğaltılmış durum makinesi yaklaşımı denir ve bir sistemin tutarlılığını yönetmeye ihtiyaç duyulan çoğaltılmış veri hizmetlerinde sıkça kullanılır. Tutarlılığın sağlanması, ve bu süreçte çakışabilecek aksiyonların hızlı ve etkili bir şekilde çözümlenmesi için, yüksek performanslı bir algoritma kullanılması şarttır. Bu bağlamda kullanılan en yaygın algoritmalardan birisi Two-Phase Commit (2PC) adı verilen iletişim algoritmasıdır. Birbiri ile tutarlı olması gereken kaynaklar üzerinde aynı anda işlem yapmaya çalışan servisler arasındaki mesajlaşma sürecinin kontrolünü sağlamak için iki aşamalı bir prosedür sunar. Kaynak üzerinde değişiklik yapacak bir servis, ilk aşamada diğer tüm kopyaların bu değişime hazır olup olmadığını sorgular, tüm kopyalardan onay aldığında bu değişikliği ilk olarak kopyalarda, sonrasında ise kendinde gerçekleştirir. Tek müşteri ve tek sunucunun olduğu durumlarda, gelen mesajlar basit kurallar çerçevesinde onaylanabilirken, birden fazla müşteri ve sunucunun olduğu, yukarıda bahsedilen kopyalı durum makinelerinin mevcut olduğu senaryoda ise, daha derin kurallar ve mesaj tiplerine bağlı farklı yaklaşımlar sergilenmesi ihtiyacı vardır. İlk aşamadaki mesajlaşma sürecinde, eğer mesajlar arasında herhangi bir öncelik düzeyi yok ise, birden fazla onay isteği gelen durumda, bir servis ilk gelen mesaja onay verip, işlem tamamlanasıya veya iptal edilesiye kadar kalan mesajları reddeder. Fakat mesajlar arasında öncelik tanımlandığında, ve bu önceliğe göre işlemlerin iptal edilmesi gerektiğinde, algoritma için iptal edilen işlem sayısı daha fazla önem taşımaya başlar. Özellikle iptal edilen yazma işlemlerinin kaynakları, sürekli taleplerini yenilediklerinde, dağıtık sistem gittikçe daha fazla mesaj harcamaya başlar, ve bir süre sonra şebeke yavaşlayabilir. Bunun yanında makine sayısının çok olduğu durumlarda, aynı anda farklı makineler, farklı servislere yazabilirim cevabı verebileceğinden, sistemin dengeli hale gelmesi vakit alabilir. Mesajlara öncelik tanımlandığında, mevcut 2PC algoritmasının en büyük dezavantajı aşamalarının birbirini ardı ardına takip etmesi, ve bunun sonucunda bir işlem iptal edildiğinde, süreci en baştan almasının maliyetli hale gelmesidir. Değişikliklerin yapılması gereken nokta, geri dönüşün artık mümkün olmayabileceği, verileri yerel önbelleğe alma gibi aksiyonlardan ne kadar uzak olursa, mesaj iptalinin etkisi de o derece büyük olmaktadır. Bunun yanında sunucular arası iletişim sadece bir noktada olduğundan, sunucular birbirlerinin mevcutta işlediği mesajlara ait öncelik farklarını çok geç tespit edebilmektedir. Bunun sonucunda da gene iletişim maliyeti artmaktadır. Bu problemin sebep olduğu mesaj sayısındaki harcamaların azaltılması ve sunucuların aksiyonları üzerinde birbirine bağımlılığı düşürmek için mevcut 2PC algoritması genişletildi. Bahsedilen 2PC algoritmasına ait iki aşama birbirinden ayrılarak, karar verme, ve yazım aşamaları arasındaki sıra bozulmadığı müddetçe, durum makinesi üzerinde herhangi bir yere konumlanabilir hale getirildi. Bu şekilde birbirinden bağımsız iki aşama, kopyalanmış durum makinelerinin herhangi birinde, bir diğerinden bağımsız şekilde işlenebilir duruma geldi. Sunucular diğer sunuculara mesaj attığında, mesaja yanıt veren sunucu, cevap verirken aynı anda kendi müşterisinden gelen mesajın da işlemesine başlayabilir konumda oldu. İlk aşamada servisler, kendilerine diğer servislerden ve müşterilerden gelen mesajlardaki öncelik tanımlarını kullanarak, hangi mesajların işlenebilir olduğuna karar verir. Bunun gerçekleşebilmesi için, sunucular kendilerine gelen mesajlardaki öncelik değerlerini hafızalarında tutarlar. Bu öncelikleri gönderen kaynaklara ait değerler, kaynakların uygulamaya çalıştığı yazım işlemleri gerçekleştirilesiye kadar, hafızada tutulmaya devam eder. Bu sistemin en büyük avantajı, bir sunucunun öncelik kontrolü sırasında, kendisinin haberdar olmadığı bir önceliği, başka bir sunucuda görüp ona göre karar verebilme yeteneği kazanmasıdır. Sonuç olarak, öncelik kontrolü isteyen mesajlar için, mesajın geldiği sunucudaki mevcut tüm öncelik değerleri ile karşılaştırma yapılır, ve rakamsal olarak büyüklük durumuna göre ilgili mesajın yanıtı hazırlanır. Önceliği düşük olan mesajların ait olduğu sunuculardaki durum makinesi daha ileri gidemez. İkinci aşamada ise, öncelik kontrollerinden başarıyla geçmiş olan servisler, kendi yerel koşullarına dayalı yazım kilitlerini almaya çalışır. Bu noktada kilidi almaya çalışan bir servisin tekrardan diğer servislere gitmesine gerek kalmadan, önceliğe dayalı çözümle yazımı yapacak kişi konumuna gelmesi sağlanır. Yerel kilidi başarıyla alan sunucunun, artık diğer sunuculara ortak kaynakta yapılacak olan değişikliği dikte etme gücü olur. Bu değişiklik hiçbir sunucu tarafından reddedilemez. Değişiklikler başarıyla gerçekleştikten sonra, süreç olağan akışına devam eder. Bu yaklaşım üzerinden, çoğaltılmış durum makineleri iki farklı dağıtık sistem tasarımı içinde, farklı çoğaltma sayıları kullanılarak entegre edildi. Bu sistemlerden ilki Amazon Web Hizmetleri (AWS) üzerinde, diğeri ise yerel bir dağıtık sanal bilgisayar kümesi üzerinde kuruldu. Dağıtık sistemler tasarlanırken, sunucu ve müşteriler'in iletişimi için ara bir mesajlaşma katmanı kullanıldı. Bunun yanında işletim sisteminin bilgisayarların gücünü minimal seviyede etkilemesi için, AWS üzerinde tasarlanan dağıtık makine tasarımı linux tabanlı bir sistem üzerine kuruldu. Müşteriler, algoritma sürecindeki etkilerinin minimal kılınması için, sadece sunuculara çalıştırılmak üzere komut gönderen kaynaklar görevi görmesi sağlandı. Bunun yanında komutların kaynağı gene müşteriler olduğu için, mesajlara öncelik atayacak olan sistemler de gene müşterilerin olduğu katmana entegre edildi. Mesajların içerdiği önceliklerin işlenilmesi süreci ise tamamen sunucu tarafındadır. Sunucu tarafında kopyalanmış durum makinesi, makine'nin akış diyagramı, ve üzerinde işlem yapılacak verilerin koordinasyonu için bir yerel arabulucu katman dizayn edildi. Bu arabulucu sayesinde bir sunucuya gelen komutların tek bir noktadan, kontrollü bir şekilde işlenilmesi, ve deneysel sonuçların daha iyi yorumlanması sağlandı. Ayrıca bu alabulucunun yerel bir kilit kullanarak tüm işlemleri gerçekleştirmesi sağlanarak, farklı sunucular arası paylaşılır bir kilit sistemi zorunluluğu ortadan kaldırıldı. Yerel kilit sayesinde, birden fazla kaynaktan gelen mesajlar aynı anda işlenirken, tutarsızlık oluşturabilecek durumların da ortadan kaldırılması hedeflendi. Deneyler sırasında algoritmalar karşılaştırılırken kullanılan kriterler şu şekildedir: belirlenmiş toplam başarılı mesajlaşma sayısı gerçekleşesiye kadar kaynaklar ve sunuclar arasında toplamda ne kadar mesajlaşma oldu, kaynakların taleplerini yenilemesi zorunda kaldığı durumlar sonucunda çıkan toplam harcanan mesaj sayısı, ve bu süreçte harcanan toplam yaşam döngüsü, toplamda sistemin işlediği mesaj sayısı, ve çalışma süreleri. Tasvir edilmiş performans kriterleri kullanılarak, algoritmalar lineer ve dallı olmak üzere iki adet durum makinesi üzerinde test edildi. Bu tez çalışmasında test sonuçları üzerinden geliştirilen algoritmanın mevcut 2PC karşısındaki durumu incelenmektedir. E2PC algoritmasının özellikle yazım işlemlerinin çok sık olduğu durumlarda, çoklanmış durum makinesi sayısı arttığında daha iyi performans sergilediği görülmüştür. Bunun yanında okuma oranı arttığında ise, farklı yazma yüzdelerine göre, E2PC'nin 2PC'ye nazaran daha fazla mesajlaşma yaptığı görülmüştür.
Özet (Çeviri)
State Machines are used to represent a set of transitions, which makes it a useful tool for representing life-cycle of a specific set of events. By utilizing this property, a state machine can be replicated into several machines and each one of them can communicate with one another in order to keep track of the order of changes. This is called the replicated state machine approach and it is highly used in replicated data services where there is a need to manage the consistency of a system. In order to provide any consistency, it is necessary to use a communication algorithm which provides both high throughput, and less number of failures in the case of conflicting operations. One of the widely known communication protocols used in our context is the two-phase commit (2PC) protocol. It provides a two step algorithm in order to manage the committing actions between different machines for the same resource. First it checks if every machine in a network is ready for writing operation, then if a machine receives a successful message from all other machines, it will then proceed to commit the specific operation to all of them. Finally it applies the commit to its own resource. In the case of no priority between the writing actions between different machines, algorithm gives the commit rights to the first machine which can successfully receive OK from all others. However, when priority comes into action, and it becomes necessary to cancel out transitions with less importance, algorithm starts to cancel out some incoming transitions, and in most cases, if the writing operations are too frequent, it cancels out a writing operation even if it obtains its OK from other machines. Disadvantage of the common 2PC algorithm in the case of priority introduction, due to its phases follow one another without any transitions, when an incoming writing request fails, it has to repeat all the preceding events from that point again. When the distance between the last important point of no-return, such as reading a value into cache, and the point of 2PC protocol becomes further away, this affect is increased and the number of messages for a successful transition is increased. In order to reduce the overhead introduced by this problem, a new algorithm is implemented by enhancing the existing 2PC algorithm. Both steps of the 2PC algorithm mentioned is separated from one another, and can be freely deployed in any place on a state machine, as long as their order is preserved. First step checks and compares the priority between different machines by using their transmitted messages, and prevents the machines from progressing any further if another machine has higher priority. Second step enables machines to commit their transitions to other machines if they have successfully passed the priority race. Using the new approach, an experimental replicated state machine is implemented in two different network environment with different replication numbers. Several different criteria is used to compare 2PC and the enhanced version (E2PC): total number of messages sent between clients and servers until all transitions succeed, number of read and write failures which causes the clients to restart their transition from beginning, number of read and write wasted transition event members, and the number of total executed transition events. Using the metrics above, a branching and linear state machine design is used to evaluate the performance of the both algorithms. In this study, using the results of our experiments, performance of the new algorithm is discussed by comparing the metrics mentioned above. Enhanced 2PC algorithm shows better performance for the paths where writing operations are applied frequently as the number of replicated machines increase.
Benzer Tezler
- Çalışma ilişkilerinin geliştirilmesinde bir hizmet içi eğitim modeli uygulaması
Başlık çevirisi yok
AKIN ARSLAN
- A composed technical debt identification methodology to predict software vulnerabilities
Yazılım zafiyetlerini tahmin etmek için kapsamlı bir teknik borç tanımlama yöntemi
RUŞEN HALEPMOLLASI
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYŞE TOSUN KÜHN
- Radyal pompaların kavitasyon performansının hesaplanması ve iyileştirilmesi
Computation and improvement of the cavitation performance of radial flow pumps
MEHMET KAYA
Doktora
Türkçe
2020
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. ERKAN AYDER
- The effect of screening parameters on miscible and immiscible CO2 EOR applications
Geliştirilmiş petrol kurtarım yöntemlerinden olan karışabilir ve karışamayan CO2 uygulamarında filtreleme parametrelerinin etkileri
UMUT EFE ARSLAN
Yüksek Lisans
İngilizce
2024
Petrol ve Doğal Gaz MühendisliğiOrta Doğu Teknik ÜniversitesiPetrol ve Doğal Gaz Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MEHMET ONUR DOĞAN