Geri Dön

Dı̇namı̇k anahtar gruplama: Dağıtık akan-verı̇ katarı ı̇şleme sı̇stemlerı̇ ı̇çı̇n bı̇r yük dengeleme algorı̇tması

Dynamic key grouping: A load balancing algorithm for distributed stream processing engines

PDF İndir

  1. Tez No: 493921
  2. Yazar: ORHUN DALABASMAZ
  3. Danışmanlar: DOÇ. DR. AHMET BURAK CAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2018
  8. Dil: Türkçe
  9. Üniversite: Hacettepe Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 156

Özet

İçinde bulunduğumuz teknoloji çağıyla beraber teknolojik cihazlar yaşamımızın vazgeçilmez birer parçası olmuştur. Her gün, kullanılan cihazlar, bu cihazlara yazılan uygulamalar ve kullanıcılar da artmaktadır. Bütün bu artışlar, üretilen veri miktarındaki çeşitlilik ve hacim artışını da beraberinde getirmiştir. Üretilen verinin hacmi ve çeşitliliği öyle artmıştır ki, artık tek bir makinenin tek başına altından kalkabilmesine imkân kalmamıştır. Bununla birlikte, gelişen ihtiyaçlar verilerin anlık olarak işlenerek gerçek zamanlı sonuç üretebilmelerini gerekmektedir. Bu kapsamda, bir işi yapabilmek için bilgisayar kümeleri kullanılmaktadır. Verilerin bu kümelere dağıtılarak en kısa sürede işlenerek çıktı üretebilmesini sağlamak amaçlanmaktadır. Bunun sağlanabilmesi içinse, yükün, yani verilerin, kümedeki bütün makinelere mümkün olduğunca dengeli dağıtılması gerekmektedir. Yükün makinelere dengesiz dağıtılması, birtakım makinelerin diğerlerinden daha yoğun çalışacağı ve böylece her makinenin verimli kullanılamayacağı anlamına gelmektedir. Verimliliğin düşmesi, sistemin çalışma süresinin artması ve üretkenliğin azalması anlamına gelmektedir. Bu da gerçek zamanlı sonuç üretemeyeceğimiz anlamına gelmektedir. Yükün makinelere dengeli dağıtılması, verinin içeriğine doğrudan bağlıdır. Veri ne kadar homojen dağılıma sahipse, yük o kadar dengeli dağıtılırken, ne kadar çarpık gelirse o kadar dengesiz dağıtılacaktır. Veriler arası bağlamın olmadığı durumda en iyi yük dağılımını sağlayan Karışık Gruplama (SG) yöntemi kullanılırken, veriler arası bağlamın olduğu durumda ise, verinin içeriğine bağlı olarak çalışan Anahtar Gruplama (KG) yöntemi kullanılmaktadır. SG yönteminde her veri makinelere rastgele dağıtılırken, KG yönteminde her veri karma değerine göre bir makineye atanmaktadır. Bu sayede durumlu verilerin tek bir makinede toplanması ve tek bir sonuç çıkartılması sağlanmaktadır. Ancak KG yöntemi, bir verinin çarpık gelmesi durumunda yükün tek bir makinede yoğunlaşmasını sağlayarak sistemin verimli çalışamamasına sebebiyet vermektedir. Parçalı Anahtar Gruplama (PKG) yöntemi ise her veri için iki karma değerinin hesaplanmasını, yani yükün iki makineye dağıtılmasını sağlamaktadır. Bu sayede çarpık gelen verilerde dahi sistemin performansında gözle görülür iyileşmeler elde edilebilmektedir. Ancak bu yöntem de bazı verilerin çok yoğun geldiği durumlarda sistemin verimsiz olmasına sebebiyet vermektedir. Çünkü yük her ne kadar iki makineye dağıtılsa da çok yoğun gelen veri karşısında yükü sadece iki makineye dağıtabildiğinden, diğer makinelerin yükü daha az olmakta, böylece verimsizlik ve performans kayıpları yaşanabilmektedir. Ayrıca bu yöntemle, herhangi bir veri için hesaplanan iki karma değerinin birbirinden farklı olacağı garanti edilememektedir. Tüm bu koşullarda sistemin verimliliğinin ve performansının, verinin içeriğinden bağımsız olarak sürekli yüksek olması gerekliliği doğmaktadır. Bu çalışma kapsamında, yükün makinelere veri içeriğinden bağımsız olarak her zaman dengeli dağıtılabilmesi için Dinamik Anahtar Gruplama (DKG) yöntemi önerilmiştir. Bu yöntem ile yoğun gelen verilerin tespiti yapılmakta ve yoğun verilerin daha çok makineye dağıtılabilmesi sağlanmaktadır. Bu sayede, özellikle çarpık verilerin çok olduğu durumlarda, sistemin üretkenliğinde ve çalışma zamanında iyileşmeler gözlemlenmiş ve oldukça başarılı sonuçlar alınmıştır.

Özet (Çeviri)

With the technological age we are in, technological devices are an indispensable part of our life. Every day, variety of devices, applications and number of users are also increasing. All these increases cause a huge grow of data produced and so the variety of data. The volume and the variety of the produced data is so increased that it is no longer possible for single machine to handle alone. On the other hand, requirements force us to process data in real-time. Therefore, cluster of machines is used for high efficiency, fault-tolerant and robust systems. By using a cluster, we aim to process all data as soon as possible by distributing the data to all nodes in the cluster. In order to achieve this, the data or the load should be distributed to the machines as equally as possible. Unbalanced distribution of the load means that a number of machines will work more intensively than others, and thus each machine will not be used efficiently. Reduced productivity and efficiency leads the increase of latency and decrease of throughput. Therefore, the system cannot produce real-time results. In such systems, balancing the load to the machines is directly connected to the contents of the data. The more homogeneous the data, the more balanced the load is, the more skewed it will be distributed unevenly. Shuffle Grouping (SG) is the best option when there is no relation between the data incoming. On the other hand, when there is a relation between the incoming data, the best option is Key Grouping (KG) which assigns the incoming data to the target machines by examining the data content. While the data is distributed to machines randomly by using Round-Robin with Shuffle Grouping, the data is distributed to machines by calculation a hash value for each data with Key Grouping. Therefore, related data can be gathered in the same machine and there is no need to aggregate from several machines. However, both of the grouping methods may become useless and inefficient depending on the data. When there is a relation between the data incoming, Shuffle Grouping cannot be used efficiently, because Shuffle Grouping does not care about the content of incoming data. On the other hand, when the data is skewed, Key Grouping routes the skewed data to the only one machine and most of the load will be concentrated on single machine. In other words, the more the data is skewed, the more inefficient load balancing occurs. This also leads inefficiency, more latency, less throughput and non-real-time results. Partial Key Grouping (PKG), on the other hand, specifies two target machines by calculating two different hash values and chooses the less loaded one for efficient load balancing. With Partial Key Grouping, every data can be distributed to two different machines. Even if the data is slightly skewed, system may have better performance and better load balancing than Key Grouping. However, if the data is so skewed and some of the data is recurring so many times, even Partial Key Grouping may show bad performance. Highly skewed load would be distributed to only two machines, thus, other machines in the cluster would have far less load to process and this leads to inefficiency and performance issues. On the other hand, this method, Partial Key Grouping, does not guarantee the two calculated hash values for one data will be different. In all these conditions, the efficiency and performance of the system must be consistently high regardless of the content of the data. In this study, Dynamic Key Grouping (DKG) method is proposed to distribute the load to the machines at all times regardless of the data content. With this method, skewed data are detected and can be distributed to more servers. Moreover, improvements were observed in the throughput and latency of the system, especially when the data is highly skewed and very successful results were obtained.

Benzer Tezler

  1. Tez No

    539473

    Analytical models for the scalability of dynamic group key agreement protocols and secure file sharing systems

    Dinamik grup anahtar anlaşma protokollerinin ve güvenli dosya paylaşım sistemlerinin ölçeklenebilirliği için analitik modeller

    GÖKCAN ÇANTALI

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEM ERSOY

    PROF. DR. MEHMET UFUK ÇAĞLAYAN

  2. Tez No

    397920

    Grade of service (GoS) based controller framework for software defined heterogeneous networks (SDHetN)

    Yazılım tanımlı heterojen ağlar için servis derecesi tabanlı kontrolör yapısı

    MÜGE EREL

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. BERK CANBERK

  3. Tez No

    878655

    A hierarchical key assignment scheme: A unified approach for scalability and efficiency, with a specialized implementation in cloud computing

    Hiyerarşik anahtar atama şeması: Ölçeklenebilirlik ve verimlilik için bütünleşik bir yaklaşım ve bulut bilişim için özelleştirilmiş bir gerçekleme

    İBRAHİM ÇELİKBİLEK

    Doktora

    İngilizce

    İngilizce

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilişim Uygulamaları Ana Bilim Dalı

    PROF. DR. ENVER ÖZDEMİR

  4. Tez No

    175160

    Querying sensor fields by using quadtree based dynamic clusters and task sets

    Sensör sahasının Quadtree tabanlı dinamik gruplar ve görev kümeleri ile sorgulanması

    ÇAĞHAN ÇİMEN

    Yüksek Lisans

    İngilizce

    İngilizce

    2003

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDeniz Harp Okulu Komutanlığı

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ERDAL ÇAYIRCI

    YRD. DOÇ. DR. VEDAT COŞKUN

  5. Tez No

    151339

    Virtual topology reconfiguration on optical WDM networks considering traffic grooming

    Trafik groomingi gözönüne alarak optik WDM ağlarda sanal topoloji yeniden düzenleşimi

    İLKER AKGÜN

    Yüksek Lisans

    İngilizce

    İngilizce

    2004

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    Y.DOÇ.DR. FEZA BUZLUCA

Geri Dön