A bipartite graph model for placement, scheduling and replication in data grids

Abstract

Veri gridleri, büyük veri setleri üreten ve kullanan uygulamalar için coğrafi olarak dağıtılmış kaynaklar sağlar. Halbuki, veri gridlerinde veriye hızlı erişim ve işler için düşük yanıt süresi temin etme durumları, çeşitli sebeplerden dolayı engellenmektedir. Bu sorunları ele almak için, yüksek veri elverişliliği, düşük bant genişliği tüketimi ve indirgenmiş yanıt süresi sağlayan değişik veri çoklama ve iş çizelgeleme stratejileri sunulmuştur. Veri çoklama sayesinde, veri farklı konumlarda çok kopyalı şekilde muhafaza edilmektedir. Ayrıca, grid üzerinde etkili bir şekilde iş çizelgeleme yaparak, sistem verimliliğinin arttırılması amaçlanmıştır. Çoklama stratejileri genelde statik ve dinamik olarak sınıflandırılır. Statik çoklama stratejilerinde, çoklama kararları çoğunlukla grid sistemindeki veri erişim maliyetlerini, bant genişliği özelliklerini ve saklama kısıtlarını kapsayan bir maliyet modeline dayanarak verilir ve çoklama işlemi sistemin tasarlanması sırasında yapılmaktadır. Dinamik çoklama stratejilerinde çoklama işlemi, kullanıcı isteği deseninindeki değişiklikleri sisteme uyarlamak için çalışma zamanında yapılmaktadır. İş çizelgeleme stratejileri, çevrimiçi mod ve toplu mod olmak üzere iki genel kategorinin içinde yer alırlar. Çevrimiçi mod çizelgeleyicisi, bir işi ulaşır ulaşmaz bir makineye atar. Toplu mod yönteminde, bütün grid bilgisini kullanarak, bütün işler aynı anda ele alınır ve çizelgelenir.Biz bu çalışmada, grid sistemindeki işleri ve verileri temsil eden bir `iki kısımlı çizge` modeli önermekteyiz. Veri yerleştirme ve iş çizelgeleme stratejisi elde etmek için bu çizgeyi bölüntülüyoruz. Elde edilen bölüntüler, yerleşkeler arasındaki bant genişliğini ve hoplama bilgisini hesaba katan KL-tabanlı buluşsal bir çizge bölüntüleme yöntemi kullanarak, grid yerleşkelerine atama yapmak için yeniden iyileştirilmektedir. Çoklama, bölüntüleme sürecinden önce seçilen en çok erişilen dosyaların belli bir miktarını kopyalarak gerçekleştirilir. Deneysel sonuçlar göstermektedir ki, bölüntüleme kalitesindeki artış, atama kalitesine olumlu şekilde yansımaktadır. Buna ek olarak, veri çoklama uygulandığında iletişim maliyetinin dikkate değer ölçüde düştüğü gözlemlenmiştir.

Data grids provide geographically distributed resources for applications that generate and utilize large data sets. However, there are some issues that hinder to ensure fast access to data and low turnaround time for the jobs in data grids. To address these issues, several data replication and job scheduling strategies have been introduced to offer high data availability, low bandwidth consumption, and reduced turnaround time for grid systems. Multiple copies of existing data are maintained at different locations via data replication. Data replication strategies are broadly categorized as static and dynamic. In static replication strategies, replication is performed during the system design, and replica decisions are generally based on a cost model that includes data access costs, bandwidth characteristics and storage constraints of the grid system. In dynamic replication strategies, the replication operation is managed at runtime so that the system adapts to the changes in user request patterns dynamically. Job scheduling strategies fall under two main categories: online mode and batch mode. The online mode scheduler assigns tasks to sites as soon as they arrive. In the batch mode, the complete set of jobs are taken into account and scheduled at the same time by using all the grid information.In this thesis, we propose a bipartite graph model for tasks and files in the grid system, and then we partition this graph to obtain a data placement and job scheduling strategy. The obtained parts are further refined in order to be assigned to grid sites by using a KL-based heuristic that takes the bandwidth and hop information between sites into account. Replication is achieved by replicating a certain amount of most accessed files chosen prior to the partitioning process. Experimental results indicate that the increase in the partitioning quality reflects positively on the mapping quality. Morever, it is observed that the communication cost is notably decreased when the data replication is applied. Hence, our results show that by replicating a small amount of data files and placing files onto sites using bipartite graph model, we can obtain performance improvement for scheduling jobs compared to no replication.