DAĞITILMIŞ DURUM MAKİNELERİ İÇİN YOL TAHMİNİNE DAYALI ÖNBELLEK YÖNETİMİ
PATH PREDICTION BASED PRE-FETCHING FOR DISTRIBUTED STATE MACHINES
- Tez No: 688126
- 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: 2021
- Dil: Türkçe
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Son zamanlarda bulut sağlayıcıları, yalnızca bulut üzerinde işletilmesi gereken işlevselliği belirlemeye odaklanarak sunucusuz hesaplama hizmetleri sunmaya başladı. Bu hizmetlerin geliştirilmesinde sıklıkla kullanılan durum makineleri, tarihsel geçmişleri ve ifade güçleri nedeniyle yazılım geliştirme sürecinde program davranışını modellemek için sıklıkla kullanılan araçlardır. Son yıllarda durum makinesi modelleri hataya dayanıklı bulut hizmetleri sağlamak için bulut bilişim ortamında uygulandı. Sunucusuz hesaplama gibi durum makinelerinin dağıtılmış uygulamalarında, çeşitli kaynaklardan gelen talepleri işlemek için aynı durum makinesinin birden fazla örneği paralel olarak işletilebilir. Dağıtılmış işletim söz konusu olduğunda, dağıtılmış örneklerin önbelleklerini yönetmede büyük zorluklar ortaya çıkmaktadır. Dağıtılmış durum makineleri için önbelleğe alma, sunucusuz bilgi işlem sistemlerinde karşılaşılan çağdaş zorluklardan biridir. Bu çalışmada, dağıtılmış durum makineleri için yola dayalı tahmini önbelleğe alma uygulaması sunulmaktadır. Tahmine dayalı önbelleğe alma, deneyim kalitesi (QoE) ve performansı iyileştirmek için temel bir yaklaşımdır. Bu uygulamalarda durum makinelerinin son işletme geçmişi incelenmiş olup genel önbellek kaçırma sayısını azaltmak için durum makine örneklerinin geçmişleri ortaklaşa biçimde kullanılmıştır. Deneylerde öğrenci kaydını işlemek için öğrenci, ders ve bölüm verilerini işlemekten sorumlu basit bir durum makinesi modellenmiş olup bu modelde, her bir işletmeden önce, veri tabanından farklı bir veri kümesinin önceden getirilmesini gerektiren birden fazla olası yol işletilebilmektedir. Deneylerde ilk olarak tekdüze dağıtım üzerinden rastgele oluşturulmuş sorguları içeren veri kümesi kullanılmıştır. Ardından, daha gerçekçi bir istek dağılımını taklit etmek için yaklaşık 9 saati kapsayan gerçek dünya verilerini içeren bir veri kümesinin durum geçişleri kullanılmıştır. Daha sonra bu basit durum makinesinin üç örneği işletilerek durum makinelerinin farklı düzeylerde geçmiş yol işletme bilgilerini paylaştığı üç farklı tahmnileme yaklaşımı uygulanmıştır. Yol için gerekli olan verileri önceden getirme kararında, işletilecek yolun geçmişte ne sıklıkla işletildiğine ilişkin veriler kullanılmıştır. Kullanılan bir eşik değeri ile belirli sıklıktan fazla işletilen yol(lar)a ait veriler tamamen ya da kısmen önbelleğe alınmaktadır. Rastgele oluşturulmuş sentetik veriler ve gerçek dünya verileri, deneylerdeki durumlara uyarlama ile tekrarlanmıştır. Durum makineleri işletme geçmişlerini aralarında paylaşmasalar bile, önbelleğe alma işleminin sonuçları, belirli eşik değerlerinde önbellek kaçırmalarında önemli bir azalma sağladığını göstermektedir. Farklı örneklerin işletme geçmişi işbirliği içinde kullanıldığında, belirli eşik değerlerinde önbellek kayıplarının sayısında bazı ek iyileştirmeler görülmüştür. Ek olarak gerçek dünya verilerini daha fazla durum makinesi kullanarak test etmek için, bu üç test senaryosu, farklı sayıda durum makinesi kullanılacak şekilde tekrarlanmıştır. Ayrıca, optimal eşik değerindeki değişikliğin görülebilmesi için, farklı geçmiş pencere boyutları da kullanılarak deneyler tekrarlanmıştır. Yapılan deneyler sonucunda hangi durumlarda ve hangi yöntemlerle, önbelleğe getirilecek verilerin tahminlenmesinin verimli olduğu gözlemlenmiştir. Yapılan deneyler dağıtılmış durum makineleri özelinde ve işletilen yol özelinde yapılabilecek tahminleme teknikleri özelinde sunulmuştur.
Özet (Çeviri)
Recently, cloud providers have started offering serverless computing services that involve eliminating the need to specify the entire software stack, focusing solely on determining the functionality that should be executed in the cloud. Since the historical background and expressive power of state machines, they are a frequently used tool to model program behavior in software development. Recently, state machine models have been implemented in the cloud computing environment to provide fault-tolerant cloud services. For distributed applications of state machines like serverless computing, multiple instances of the same state machine can be executed in parallel to handle requests from various sources. When it comes to distributed execution, major difficulties arise in managing the caches of distributed instances. Caching for distributed state machines is one of the contemporary challenges for serverless computing systems. In this project, we have implemented path-based predictive caching for distributed state machines. Predictive caching is a fundamental approach to improving the quality of experience (QoE) and performance. In our application, we review the last execution history of state machines and collaboratively use sample histories to reduce the overall number of cache misses. Experiments were performed on a system running Java SDK 1.8 and Windows 10 64-bits operating system with 16 Intel i7-7700HQ CPU 2.81 GHz cores, 16 GB of RAM, and a 512 GB SSD. The Implementation uses Rabbit MQ sender/receiver, Mongo DB reader/writer and Spring Statemachine framework with version of 2.1.8. In our experiments, we have modelled a simple state machine responsible for processing student, course, and department data to process student enrolment. Our simple state machine has multiple execution paths, each of which requires pre-fetching a different set of data from the database before execution. In this study, two different datasets were used to execute distributed instances of state machines. The first dataset contains randomly generated queries over a uniform distribution. The event frequencies of a second dataset were used to simulate a more realistic request distribution. This dataset contains real world data and includes requests covering approximately 9 hours. Afterwards, we have executed three examples of this simple state machine and used a pre-fetch technique for three different predictors in which the state machines shared different levels of historical path execution information. In our decision, we used a threshold for the proportion of a particular path in the execution history to pre-fetch the data required for the path before the upcoming execution. We have implemented 3 different scenarios where each scenario contains results from 8 different threshold values and performed 10 repetitions of our experiment for each threshold value used in each scenario. The methods to be developed have been developed by testing on samples of different data sets like randomly generated synthetic data sets and real-world data sets. In the first scenario, all of the state machines use their histories to apply the path prediction. They start at the same time using the same data set, without being dependent on each other. Each state machine keeps its history according to the data from the data set and activates caching according to this history. We expect approximately the same results for all state machines. The experimental results support this claim. In the second scenario, one of the state machines keeps the history and shares it with the other machines. The last two state machines do not operate the path estimation method and they use shared history to fetch data into their caches. All state machines perform caching based on the path estimation of the first state machine. We expect more efficient results for the last two state machines. The experimental results up to a threshold of 0.5 support this claim. After the threshold of 0.55 at which it is guaranteed to always pre-fetch the data of a single path into the cache, performance drops. In the third scenario, two-state machines independently keep their histories and share this history with the last state machine. The last remaining state machine combines its history and these two shared histories, and it estimates the path over these three histories. The last state machine uses the results of this compound path estimation to pre-fetch data into its cache. It offers a very limited band of thresholds for both synthetic data and real-world data that improves previous results. The performance enhancement threshold band is quite different for synthetic data and real-world data; 0.3-0.4 and 0.4-0.45, respectively. Additionally, these three test scenarios have been updated to perform with 5 state machines with real-world data. In the first scenario, all of the state machines use their histories to apply the path prediction. We expect approximately the same results for all state machines as in the 3-state machines test result. In the second scenario, one of the state machines keeps the history and shares it with the other machines. The last four state machines do not operate the path estimation method and they use shared history to fetch data into their caches. We expect more efficient results for the last four state machines as in the 3-state machine test result. In the third scenario, four-state machines independently keep their histories and share this history with the last state machine. The last remaining state machine combines its history and these four shared histories, and it estimates the path over these five histories. The performance enhancement threshold band is the same for real-world data; 0.4-0.45 as in the 3-state machine test result. Also, we repeated the last test scenario with 4 state machines with real-world data. The performance enhancement threshold band is the same as in the 3-state machine test result. The third scenario, regardless of the number of state machines, presents a very limited band of threshold values improving previous results. The last scenario was repeated with 3 state machines in order to see the changes in the threshold values by increasing the data size in the database 4 times compared to the previous tests and by keeping the cache size constant. This test step was repeated on historical data sizes 16, 18, 20 22, respectively. There were shifts in the threshold values in the graphs. While the optimal threshold value was around 0.4 in the previous experiments, it was displayed as 0.45 in the last experiment. Finally, the separate histories scenario was renewed with the data estimation method to compare the results of data estimation for the same datasets and eight different threshold values with the results in the path estimation case. The data estimation method is directly dependent on the data size. Although data estimation seems to be efficient for low data sizes, the path estimation method has become a great advantage as the data size increases. We have performed experiments for 3 different scenarios where each scenario was contains results from 8 different threshold values. Instead of sharing relatively larger, combined histories it provided better results to use a history that may better represent the path execution distribution. For relatively low and high threshold values not sharing any history provided better results.
Benzer Tezler
- Exchange rate disconnect puzzle: A research on forecasting exchange rates with nowcasting of macroeconomic variables
Döviz kuru kopukluğu muamması: Makroekonomik değişkenlerin nowcasting öngörüsü ile döviz kuru tahmini üzerine araştırma
KHATAİ ABBASOV
- Burdur ili mermer sektörünün kurumsal ve ekonomik yapısı
İnstitutional and economic structure of marble sector in burdur
AHMET SARITAŞ
- Improvement of face recognition performance through transfer learning: a comprehensive study using identity card biometric photographs and mobile phone selfie images
Transfer öğrenme yoluyla yüz tanım performanslarının geliştirilmesi: Kimlik kartı biyometrik ve cep telefonu özçekim fotoğrafları ile yapılan kapsamlı bir çalışma
YÜSRA ALBARAZİ
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
PROF. DR. KEMAL BIÇAKCI
- Novel data partitioning and scheduling schemes for dynamic federated vehicular cloud
Dinamik federe araç bulutu için yeni bir görev yükü paylaşımı ve iş planlaması şemaları
WISEBORN MANFE DANQUAH
Doktora
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. DENİZ TURGAY ALTILAR
- Auction based scheduling for distributed systems
Dağınık sistemler için ihale tabanlı çizelgeleme
EMRAH ZARİFOĞLU
Yüksek Lisans
İngilizce
2005
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Bölümü
PROF.DR. İHSAN SABUNCUOĞLU
