MapReduce, büyük veriyi büyük kümelerde (clusters) işlemek üzere geliştirilmiş bir dağıtık programlama modelidir. Genel yapısı itibariyle MapReduce adından da anlaşılacağı üzere iki ana fonksiyondan oluşur. Birincisi map; bir yığının tüm üyelerini sahip olduğu fonksiyon ile işleyip bir sonuç listesi döndürür. İkincisi reduce; paralel bir şekilde çalışan iki veya daha fazla map fonksiyonundan dönen sonuçları harmanlar ve çözer. Hem map() hem de reduce() paralel bir şekilde çalışırlar, aynı anda aynı sistemde olmaları gerekmez.

Google, web sayfalarını indekslemek için MapReduce kullanır [1] . Birçok programlama dili kullanarak ( Java, C++, Python, Perl, Ruby, C vs. ) MapReduce programı geliştirilebilir.

map() fonksiyonu çok büyük veri kümelerini  bucket  diye adlandırılan iki veya daha fazla kovaya  böler. Sonrasında bir kova belirli mantıkla ayrılmış kayıtları veya bir yazı satırı tutar. Her iş parçacığı (thread), işlemci veya sistem, her mantıksal kaydı işleyerek ara değer kümelerini hesaplamak için map() fonksiyonunu ayrılmış kovalar üzerinde çalıştırır. Birden fazla kovada çalışmış olan bu fonksiyonların sonuçları benzer yapıda olmalıdır ki, sonunda bir araya getirildiğinde bir map() fonksiyonu ile çalıştırılarak sonuç elde edilebilsin. map() fonksiyonunun genel yapısı şu şekildedir:

1
2
3
4
5
6
map(fonksiyon, liste) {
  foreach eleman in liste {
    v = fonksiyon(eleman)
    araSonuc.add(v)
  }
} // map

Örnek-1: map fonksiyon yapısı

Örnek-1’deki yöntem  map() fonksiyonunun yapısını basitçe anlamayı sağlamaktadır. Yöntemde, belirli bir mantık ile çalışacak fonksiyon ve girdi değer listesi parametre olarak verilmektedir. Listedeki tüm değerler fonksiyonda tek tek işlenip ara sonuç listesine eklenir. Bu işlenen ara sonuçlar da yukarıda bahsedildiği üzere ana bir map() fonksiyonunda işlenerek sonuç listesine dönüşecektir.

reduce() fonksiyonu, hafızadan, diskten veya ağ transferi ile elde edilen ara sonuç listelerini işler ve her bir liste değerini sahip olduğu fonksiyon ile uygulamaya sokar. Tüm işlemlerin son sonuçları, çalışan tüm reduce() işlemlerinden elde edilen sonuçların yorumlanıp sıralanması ile elde edilir. Genel yapı itibari ile bir reduce() fonksiyonu şöyledir:

1
2
3
4
5
6
7
reduce(fonksiyon, liste, başlangıç) {
  sonuç = başlangıç
  foreach değer in liste {
    sonuç = fonksiyon(sonuç, değer)
  }
  sonuçÇıktısı.add(sonuç)
}

Örnek-2: reduce fonksiyon yapısı

map() fonksiyonunda olduğu gibi belirli bir mantık ile çalışan fonksiyona, değer listesi ve bir başlangıç değeri parametre olarak verilir. Listenin her bir değeri için fonksiyon çalıştırılır. Fonksiyona da başlangıç değeri eklenir. Son olarak elde edilen sonuç, sonuç çıktı listesine eklenir ve program tamamlanır.

Birden fazla sistem arasında map() ve reduce() fonksiyonları, ortak bir havuz üzerinde eş zamanlı olarak ve birbiriyle iletişim kuracak şekilde çalışmaktadır. İş mantığı (business logic) kullanıcı tarafından belirlenir ve bu iş mantığı, mantıksal kayıt işleme üzerine çalışır, çoklu işlem mantığı ile çalışmamaktadır. Bu çalışma mantığı paralel işlem uygulamaları için çok uyumlu bir yapıdır. MapReduce kümeleri her fonksiyon parçası işlendikçe tekrar tekrar kullanılır ve her seferinde test, inşa (build), uygulamanın tamamını yerleştirme (deploy) işlemlerine gerek kalmadan yeni veri kaynakları sağlanabilir. Aşağıdaki grafikte map ve reduce işlemlerinin genel işleyişi ile ilgili bilgi verilmektedir.

  Resim-1 : MapReduce Genel Yapısı

Sonuç olarak, devasa boyuttaki yapısal olmayan verinin işlenmesi günümüz bilişim dünyasının üzerinde önemle durduğu zor konulardan biridir. Geleneksel yöntemlerle yapılan, belirli algoritmaların ve buluşsal yöntemlerin yönetilmesi çok zordur. Aynı zamanda çok hantal çalışan ve uzun süren programlar ortaya çıkmaktadır. MapReduce paralel sistemler üzerinde verinin işlenmesi ile alakalı çok başarılı çözümler sunmaktadır. Bu çözümlerin üstün tarafları:

-Maliyet Düşürücü olması,

-Daha yüksek programcı verimliliği sağlaması, çünkü iş mantığı  paralelleşme kodundan bağımsız bir şekilde uygulanır ,

-Geleneksel RDBMS (Relational Database Management Systems – İlişkisel Veritabanı Yönetim Sistemleri) tekniklerine ve özel algoritmalara göre daha iyi performansla sonuçlanması,

-Java mimarisi ve geliştirme ortamlarına  uygun araçlar sunması ve bilinen teknikler kullanılarak program geliştirebilmenin kolay olması

MapReduce’un teknik açıdan ne olduğunu ve çalışma mantığını anlattıktan sonra genel yapı itibari ile ne olduğu ve ne olmadığından bahsedilebilir. MapReduce, elde bulunan büyük miktardaki veriyi paralel bir şekilde birçok makine üzerinde çalıştırma imkanı sağlayan programdır. MapReduce programının kullanışlı olması için belirli şartlar gerekir. Bunlar;

  • Verinin bir alt kümesi çalıştırılıp elde edilen sonuç diğer bir alt küme sonucu ile birleştirilir.
  • En son elde edilen sonuç ilk veri kümesinden daha küçüktür.
  • Eldeki veri kümesi hariç hesaplama yapmak için başka bir veriye veya araca gerek kalmaz.
  • Tüm performansı etkilemeden veri kümesini bağımsız parçalara ayırabilmek gerekir.

MapReduce bağımsız çalışabilen alt kümelere ayrılabilmelidir diye belirtilmişti. Aksi taktirde MapReduce çalıştırılamaz. Örneğin; MapReduce kullanarak Fibonacci dizisi çözülemez. Çünkü Fibonacci dizisinde mevcut değeri hesaplamak için bir önceki değere ihtiyaç duyulur. Bunun anlamı birbirinden bağımsız çalışacak alt hesaplama birimlerine ayrılamaz. Doğal olarak art arda birbirine bağımlı hesaplamalar içerdiği için MapReduce istenen şekilde çalışamaz.

Örnek MapReduce Uygulamaları

Dağıtık GREP

Grep komutu linux işletim sistemlerinde bir dosyada belirli kelime veya kelime gruplarını aramak için kullanılır. Dağıtık grep ise çok sayıdaki dosyadan verilen bir kalıbı arama işlemidir. Örneğin; bir web yöneticisi dağıtık grep (distributed grep) kullanarak web sunucu loglarında arama yapabilir. Yaptığı arama sonucunda verilen kalıp ile eşleşen en çok talep edilen sayfaları bulabilir. Map fonksiyonu bu işlemde aşağıdaki çıktıları üretir;

  • Eğer kalıp ile eşleşen bir satır yok ise boş liste döner
  • Eğer kalıp ile eşleşen satır var ise bir anahtar değer çifti (satır,1) üretir.

Reduce fonksiyonu  (satır,[1,1,1…]) girdisini alır ve (satır,n) şeklinde çıktı üretir. n, 1’lerin toplam sayısını belirtir.

Mekan Sorgulama İşlemi

Mekan tabanlı servislerin ilerlemesi ile birlikte, çok büyük miktarda mekan tabanlı üretilmeye başlamıştır. Mekansal sorguları (en yakın komşu sorguları ve ters en yakın komşu sorguları) çalıştırmak için çok fazla bilgisayar kaynağına ihtiyaç duyulmaktaydı. Daha sonra bu sorgunun da paralel bir şekilde çalıştırılabileceği gözlemlendi.

Örneğin Google Maps, haritadaki karoları yorumlarken, verilen kavşağa bağlı olan tüm yolları bulurken ve verilen adrese ait en yakın özelliği bulurken MapReduce kullanır.

LIDAR Verisini Izgaraya Ayırma İşlemi

LIDAR (light detection and ranging) havada lazer ile profil oluşturma işlemidir. Dijital yükselti modeli (digital elevation model- DEM) veya 3 boyutlu (3D) gösterimde her (x,y) pozisyonu tekil bir yükselti değeri ile ifade edilir. DEM karolarla gösterilebilir. Bu şekiller de yeryüzü yükselti bilgisini oluşturur. DEM’ler bilimsel ve mühendislik uygulamalarında menzil belirlemede, hidrolik modellemede, arazi analizinde ve altyapı tasarımında kullanılır. Yerel karolara ayırma algoritması (local gridding algorithm) LIDAR ölçümlerinden elde edilen yükselti bilgisini kullanır.

Yukarıda verilen örnek uygulamalar MapReduce kullanılan birçok programdan sadece birkaçını içermektedir. Örnekler çoğaltılabilir.

Kaynaklar

  1. 1 “How Google Works”. baselinemag.com. “As of October, Google was running about 3,000 computing jobs per day through MapReduce, representing thousands of machine-days, according to a presentation by Dean. Among other things, these batch routines analyze the latest Web pages and update Google’s indexes.”
  2. Spatial Queries http://en.wikipedia.org/wiki/Spatial_query
  3. Nearest Neighbor Search http://en.wikipedia.org/wiki/Nearest_neighbor_search
  4. Voronoi-based Geospatial Query Processing with MapReduce“, Akdogan, A. and Demiryurek, U. and Banaei-Kashani, F. and Shahabi, C.,In:Cloud Computing Technology and Science (CloudCom), 2010 IEEE Second International Conference, pp. 9-16, 2010.
  5. LIDAR http://en.wikipedia.org/wiki/LIDAR
  6. Evaluation of MapReduce for Gridding LIDAR Data“, Sriram Krishnan, Chaitanya Baru, Christopher Crosby, In: Cloud Computing Technology and Science (CloudCom), 2010 IEEE Second International Conference, pp. 33-40, 2010
  7. ESRI, “The ESRI Grid Format”, http://en.wikipedia.org/wiki/ESRI_grid
  8. MapReduce: Simplified data processing on large clusters“, Dean, J. and Ghemawat, S., Communications of the ACM, 51{1}, 107-113, 2008
  9. The Limitation of MapReduce: A Probing Case and a Lightweight Solution“, Zhiqiang Ma and Lin Gu
  10.  David DeWitt; Michael Stonebraker. “MapReduce: A major step backwards”. databasecolumn.com.
  11.  Greg Jorgensen. “Relational Database Experts Jump The MapReduce Shark”. typicalprogrammer.com.
PAYLAŞ

YORUM YOK