Büyük Veride Analiz İşlemlerinde MapReduce Kullanımı

Önceki yazımda da anlattığım gibi eğer elimizde oldukça büyük hacimli veriler varsa şu anki ilişkisel veritabanı yönetim sistemleri ile bu verileri saklayabilmemiz ve analiz edebilmemiz mümkün değil. Google tarafından 2004 yılında yayımlanan bir sistem ile bu işlemleri gerçekleştirebilmemiz mümkün hale gelmiştir. Bu sisteme ise MapReduce adını vermişler. Tanımsal olarak MapReduce, büyük veri kümeleri üzerinde dağıtık ve paralel bir şekilde işlem yapmayı sağlayan bir programlama modelidir.  Bu sistem aslen 1960′lı yıllarda geliştirilen fonksiyonel programlamadaki map ve reduce fonksiyonlarından esinlenmiştir. Veriler işlenirken bu iki fonksiyon kullanılır.

• Map(): Filtreleme ve sıralama işlemlerini gerçekleştirir. Örneğin elimizde öğrencilerin bilgileri varsa, adlarına göre ayrı ayrı kuyruklar oluşturup bunlar üzerinde sıralama işlemleri gerçekleştirebiliriz.
• Reduce(): İşlemin sonuçlarının birleştirilmesini ve dökümünü sağlar. Şekildeki gibi her bir kuyruktaki şekilleri sayarak isimlerine göre frekanslarının bulunmasını sağlar. 

MapReduce sistemi, dağıtık sunucuları harekete geçirir, çeşitli görevleri paralel olarak çalıştırılmasını sağlar, sistemin çeşitli parçaları arasındaki veri akışını kontrol eder, ve tüm bu işlemleri sistemde redundancy ve hata toleransı sağlayarak gerçekleştirir. 

MapReduce modeli fonksiyonel programlamada yaygın olarak kullanılan map ve reduce fonksiyonlarından esinlenmiştir fakat MapReduce çatısı altında aynı işleri yürütmezler. Ayrıca, MapReduce Framework’ünün en önemli fonksiyonları, asıl map ve reduce fonksiyonları değildir, fakat çeşitli uygulamalarda bu fonksiyonların çalışma motoru optimize etmesiyle, ölçeklenebilirliğe ve hata toleransına ulaşılabilir.

MapReduce çok sayıda bilgisayar (node/düğüm) kullanarak büyük veri kümeleri arasında paralelleştirilebilir problemleri çözmeye yarar. Çok sayıdaki bilgisayarların hepsi aynı yerel ağı kullanıyorlarsa ve benzer donanımlara sahiplerse cluster(küme), coğrafi olarak farklı alanlara yayılmışlarsa ve farklı donanım konfigürasyonlarına sahiplerse grid olarak adlandırılırlar.


İşlenilen veri, veritabanındaki gibi (yapılandırılmış) veya dosya sistemindeki gibi (yapılandırılmamış) bir ortamda bulunabilir. MapReduce’un kalıcı girdi ve çıktıları genellikle dağıtık bir dosya sisteminde saklanır. Geçici veriler ise genellikle yerel diskte saklanır ve reducer’lar tarafından uzaktan getirilir. MapReduce, yerel verileri kendisine daha yakın konumdaki kaynaklarda işleyerek veri aktarımında oluşan gecikmeleri optimize edebilir ve hız artışı sağlayabilir.

Map adımı:

İlk (ana) düğüm girdiyi alır, daha küçük alt problemlere böler ve işçi düğümlere iletir. İşçi düğüm çok seviyeli ağaç yapısının ilk düğümlerinde bulunuyorsa bu işlemi çocuklara aktarmak suretiyle tekrar gerçekleştirebilir. İşçi düğümler ise küçülen problemi işler ve ana düğüme geri iletir.

Reduce Adımı:

Ana düğüm tüm alt problemlerden gelen çözümleri toplar ve birleştirerek belirli bir biçimde dökümünü sağlar.

MapReduce, dağıtık olarak map ve reduction işlemlerinin çalıştırılabilmesine olanak tanır. Her bir map işlemini diğerlerinden bağımsız olarak yürütür. Aslında bu paralellik bağımsız veri kaynakları sayısı ve bu veri kaynaklarının yakınında bulunan işlemci sayısına oranla sınırlıdır. Benzer olarak indirgen kümeleri (reducer), aynı anda aynı anahtarı kullanan map işleminin bütün çıktılarını alarak reduction evresini gerçekleştirebilirler. Bu süreci işleyen, daha sıralı çalışan algoritmalar da var fakat genelde verimsiz çalışıyorlar. MapReduce ise, elimizde yetersiz sunucular olsa bile daha geniş veri kümelerinde uygulanabilir. Örneğin geniş bir sunucu kümesiyle bir petabyte’lık bir veride, MapReduce kullanılarak birkaç saat içerisinde sıralama işlemi tamamlanabilir. Paralelliğin sağlanması ile eğer girdi verisi hala elimizde ise, işlem esnasında herhangi bir sunucu çökse bile, yapılan iş tekrar zamanlanabilir.

MapReduce’un işlem sırası:

• Map() girdisinin hazırlanması: MapReduce sistemi, Map işlemcilerini tanımlar, her işlemcinin üzerinde çalışacağı K1 girdi anahtarının atamasını yapar, ve işlemciye bu anahtar değeri ile ilişkili bütün girdi verisini iletir.
• Kullanıcının tanımladığı Map() kodunun çalıştırılması: Map() fonksiyonu her bir K1 anahtar değeri için yalnızca bir kez çalışır ve K2 anahtar değerleri tarafından düzenlenecek çıktıyı oluşturur.
• Map çıktısının karıştırılarak (shuffle) reduce işlemcilerine iletilmesi: MapReduce sistemi Reduce işlemcilerini tanımlar ve K2 anahtar değerini, çalıştıracak her işlemciye birer birer atar, ve o anki işlemciye bu anahtar ile ilişkili bütün Map’in oluşturduğu çıktı verisini aktarır.
• Kullanıcının tanımladığı Reduce() kodunun çalıştırılması: Map adımından oluşturulan her K2 anahtar değeri ile ilişkili değer için bir Reduce() fonksiyonu çalıştırılır.
• Son çıktının üretilmesi: MapReduce sistemi bütün Reduce çıktısını toplar ve son ürünü oluşturmak için K2 anahtarı ile sıralar.

Bu 5 adımı mantıksal olarak üstteki gibi bir sıra halinde çalıştığını düşünebiliriz – her adım, başlamak için önceki adımın bitmesini bekler. Ama pratikte ise adımlar tabi ki iç içedir.

Genelde girdi verisi önceden farklı sunuculara dağıtılmış olur ve bazen Map sunucularına yerel olarak temsil edilen veriler atanarak 1. Adım oldukça basitleştirilmiş bir hale getirilir. Benzer olarak 3. Adımda da, Reduce işlemcilerine yerel Map fonksiyonundan oluşturulan veri aktarılarak bu adım hızlandırılabiliyor.

MapReduce'e mantıksal açıdan bakalım

MapReduce’ün Map() ve Reduce() fonksiyonları (anahtar,değer) alacak şekilde yapılandırılmışlardır. Map fonksiyonu veri alanını (data domain) içeren bir çift veri alır ve farklı bir domain çıktı listesini return eder:

• Map(k1,v1) -> list(k2,v2)

Map fonksiyonu girdi veri kümesindeki her çift veriye paralel olarak uygulanabilir. Her Map fonksiyonunun çağrımı için ayrı ayrı birer liste oluşturulur. Sonrasında MapReduce sistemi bütün listelerden aynı anahtarlı veri çiftlerini toplar ve her anahtara bir grup düşecek şekilde gruplar.

Sırayla aynı domaindeki verilerden ayrı bir liste üreten Reduce fonksiyonu daha sonra her gruba paralel olarak uygulanabilir.

• Reduce(k2, list(v2)) -> list(v3)

Her Reduce çağırımı, bir kez çağırıldığı zaman birden fazla değeri geri döndürebilecek kapasitede olsa bile genellikle bir v3 değeri veya bir null değeri döndürür. Bütün fonksiyon çağırımlarından toplanan değerler belirlenen sonuç listesine aktarılır.

Böylece MapReduce sistemi (anahtar,değer) çiftlerinin bulunduğu listeyi değer listesine dönüştürür. Bu davranış, fonksiyonel programlamada keyfi değerlerin bulunduğu bir listeyi alan ve listedeki tüm değerleri sadece tek bir değer olarak düzenleyerek geri döndüren map ve reduce fonksiyonlarından faklıdır.

Örnekler

Aşağıdaki örnek, dökümanlardaki her kelimenin oluşma sıklığını hesaplar:

    function map(String belgeAdi, String belgeIcerigi):
      for each kelime k in belgeIcerigi:
        emit (k, 1)

    function reduce(String kelime, Iterator parcaSayisi):
      kelimeSayisi = 0
      for each parca in parcaSayisi:
        kelimeSayisi += ParseInt(parca)
      emit (kelime, kelimeSayisi)

Burada girdi olarak verilen doküman splitting işleminde önce  satırlara sonra da kelimelere ayrılır. Her kelime bir unique key gibi ele alınır ve ayrı ayrı map fonksiyonu tarafından saydırılır. Sonra shuffling işleminde MapReduce Framework’ü, aynı anahtarlı tüm çiftleri bir araya getirir ve reduce’a iletir. Reducing işleminde aynı anahtarlı kelimeler saydırılır ve nihai sonuç olarak birleştirilir. Böylece bu fonksiyon, sadece girdi değerlerini kullanarak verilen kelimenin toplam görülme sıklığını elde etmiş olur.

Kullanım Alanları

MapReduce dağıtık şablon-temelli (pattern based) aramalarda, dağıtık sıralama işlemlerinde, web tarafından erişilen log istatistiklerinde, belgelerin kümelenmesi işlemlerinde, makine öğreniminde ve istatistiksel makine çevrimi olmak üzere geniş çaplı uygulamalarda kullanılıyor. Çok işlemcili sistemlerde, masaüstü  ağlarında, eyewire uygulaması gibi gönüllü işlem yapma ortamlarında, dinamik bulut sistemlerinde ve mobil tarafında da adapte bir şekilde çalışabiliyor.

MapReduce, Google’da dünyadaki tüm sitelerin indekslerini tamamen yenilemek için kullanılıyordu. Önceden de indeksi güncelleyen ve çeşitli analizler gerçekleştiren programlar kullanıyorlardı. Fakat MapReduce’un üretilmesi ile hepsi rafa kaldırıldı.

Şu an sadece Google değil, Facebook, Twitter, Linkedin, Foursquare gibi çok fazla veri toplayan sosyal ağ uygulamalarında kullanılıyor. Son 2 yılda üretilen verilerin geçen 10 seneden fazla olduğunu düşünürsek, MapReduce sisteminin geleceğinin parlak olduğunu söylemek yanlış olmaz.

MapReduce kütüphaneleri farklı optimizasyon seviyesindeki birçok farklı programlama dili ile yazılmışlardır. Açık kaynaklı popüler implementasyonu ise Apache Hadoop’tur. Sonraki yazımda Hadoop'tan bahsedeceğim, görüşmek üzere... 

Kaynaklar: Wikipedia, Devveri