Map Reduce (Haritalama İndirgeme)

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, map-reduce (haritalama ve indirgeme) yaklaşımını açıklamaktır. Basitçe bir veri kaynağının birden fazla parçaya bölünerek, paralel işlendiği (map) ve ardındna tek bir kaynağa geri indirgendiği sistemlerdir.

Örneğin elimizde bir veri kaynağı olarak iki cümle bulunsun:

C1: “Ali topu at”

C2: “Ali ip atla”

Bu iki cümle için bir haritalama fonksiyonu olarak sayma işlemi tanımlayalım. Basitçe verilen cümledeki kelimelerin frekanslarını saysın:

say ( C1 ) = { (Ali,1) , ( topu, 1) , (at , 1) }

say ( C2 ) = { (Ali,1) , ( ip , 1) , (atla , 1) }

şimdi bu iki sonuç listesi üzerinde bir birleştirme işlemi uygulayalım. Aynı olan elemanların değerlerini toplasın:

birleştir (C1, C2) = { (Ali,2) , ( topu, 1) , (at , 1) , ( ip , 1) , (atla , 1)}

olarak bulunacaktır. İşte bu yaklaşımda sayma fonksiyonu haritalama (map), birleştirme fonksiyonu ise indirgeme (reduce) olarak düşünülebilir.

Buna göre haritalama işlemleri paralel olarak çalıştırılabilir.

Örneğin yukarıdaki örnekte aynı anda birden fazla sayma işlemi gösterilmiştir. Her sayma fonksiyonuna ayrı bir cümle verilip bu cümlelerin sayılması mümkündür. Benzer şekilde bu paralel işlemler ayrı bilgisayarlar hatta dünyanın ayrı uçlarındaki bilgisayarlar bile olabilir. Örneğin bir arama motorunda dolaşılan siteler olduğunu kabul edelim. Her bilgisayar farkıl bir siteyi dolaşarak buradaki kelimeler indekslenebilir.

Ardından indirgeme işlemi gelecektir:

Yukarıdaki şekilde ise bir başlangıç listesine biriktirilen listeler gösterilmiştir. Yani bir önceki adımda sayma fonksiyonunun ürettiği sayılmış listelerin birleştirildiği aşama olarak düşünebilir.

Buradaki problemlerden birisi, haritalama (map) işleminin paralel yapılabilmesi ancak indirgeme (reduce) işleminin paralel yapılamamasıdır. Oysaki özellikle çok büyük miktardaki verilerin işlendiği paralel sistemlerde, bütün listenin sunucular arasında hareket ettirilmesi ve her seferinde bütün listenin işlenmesi oldukça güç olmaktadır. Bu durumda indirgeme (reduce) işleminin de paralel yapılması için bir çözüm önerilmelidir.

Çözüm ise birbirini gerektiren değerlerin beraber işlenmesidir. Örneğin sadece aynı kelimelerin aynı ortamda bulunması, frekanslarının toplanması için yeterlidir. Örneğimizdeki “Ali” kelimeleri toplanırken, kaç tane “ip” kelimesinin bulunduğunun bir önemi yoktur. Bu durumda bütün kelimelerin ayrnı indirgeyicilere dağıtılması söz konusudur. Bu işleme parçalama (partitioning) ismi verilir ve büyük veri kümesi farklı parçalara bölünerek indirgeyiciler (reducer) arasında dağıtılır.

Genelde bu parçalama işlemi için özetleme fonksiyonlar (hash functions) kullanılır.

Örneğin kelimler üzerinden birer anahtar sonuç çıkarılarak bu sonuçlar indirgeyicilere dağıtlır.

Örneğin google bu işlemi simhash ismi verilen bir algoritma ile yapmaktadır.

Yukarıdaki şekilde gösterildiği üzere, veri kaynağından parçalara ayrıldıktan sonra her parça üzerinde haritalama (map) yapılmaktadır. Ardından veriler bir özetleme fonksiyonundan geçirilerek (hash function) anahtarlara göre indirgeyiciler (reducer) arasında dağılım yapılmaktadır.

Neticede, her sonuç ilgili indirgeyicinin üzerinde kalmaktadır.