İnternette dolaşırken denk gelmiştim. Okumanızı tavsiye ederim.
---
NoSQL ile alakalı makaleler okurken, Google indexleme, arama, inceleme süreçleri hakkında çeşitli dökümanlar okudum. Kodrellada yazmayı düşündüğüm bir konuyla uyuşunca Googleun bu kusursuz yapısı hakkında araştırmalarımı paylaşmak istedim. Yazı bu konu hakkında ki acemiliğimden dolayı, yanlış terim kullanımları, hatalı tanımlamalar içerebilir.
NoSQL kısaca ilişkisel olmayan veritabanı. Günümüzde semantizm, kişiyi, kullanıcıyı tanımak bu kadar popülerken, İlişkisel olmayan veritabanı niye bu aralar gündemde dedim ben de önce, Googleun bir nevi NoSQL tipini, kendi altyapısında nasıl kullandığını anlayınca, NoSql ve aşağı da tanımladığım diğer kavramlara daha bir ilgi duyar oldum. Okumanız önerilir..
Öncelikle NoSQL hakkında kavramları inceleyelim;
Map-Reduce kavramı
Map ; Bu katman gelen işi ilgili birimlere dağıtır ve çıktıyı verir.
Reduce ; Bu katman ise Maptan gelen çıktıları tek bir işlem sonucu olarak verir.
Hasan Özgan hoca blogunda, Map ve Reduce için; aslında fonksiyonel programlamada sıkça kullanılan iki fonksiyondur. Excel buna güzel bir örnektir. demiş.
Ayrıca blogunda Googleun tüm interneti nasıl indirip, taradığı hakkında güzel bir yorumda bulunmuş.
Burada ilginç bir döngü var? Internet mozaik bir yapıdadır. Ve dağınıktır. Bu dağınık yapıyı Googleın yaptığı gibi indekslemek (tabiri caizse tüm interneti indirmek isterseniz), dünyanın en büyük ve en iyi ilişkilsel veritabanını kanalize olmuş Oracle bile yetersiz kalacaktır.
2008 yılında çeşitli kuruluşların sağladığı bilgiye göre 200 milyondan fazla websitesi var. Alan adı değil, yayında olan 200 milyon. O da bundan 4 yıl öncesi, her yıl katlanarak büyüdüğünü anlatmaya gerek yok.
Her site ortalama 10 sayfa içerikden ibaret olsa(kelime sayısı farketmeksizin, 10 farklı url), ki bunların %9′u haber portalları, %6′sı 2008 rakamlarına göre bloglar, Wikiler, Döküman-Makale portalları, Kurum-Kuruluşların(forumlar, ansiklopedi tarzı siteler) bilgi kaynakları vs vs olduğunu düşünürsek ortalama 10 değil, baya bir fazla çıkacaktır. Fakat en basitinden 10′ar sayfa olduğunu varsayarsak 2 milyar sayfa olduğu anlamına gelir.
2 milyar sayfa arasından birbirinden içerik çalan, ya da içeriğinin bir kısmı özgün, diğer kısmı alıntı olan, Veyahut aldığı içeriği kurallara uyarak kısa özetler ve ana siteye bağlantı vererek yapan, Tamamen özgün içerik üreten sitelerin belirlenmesi, Bu sitelerin bu davranışlarının doğal olup olmadığı, %100 özgün olsa da kullanıcılar tarafından tercih edilip edilmemesi, Buna göre sıralanması, Sitenin genel konusuyla ilişkilendirilmesi, Kullanıcıya en iyi sonucu verebilmesi için sürekli olarak bu değerlerin kıstas edilmesi gibi yüzlerce unsurun bir yapıda bulunması günümüzün en kral veritabanı Oracleın bile kaldıramayacağı türden bir sonuç ortaya çıkarıyor. Dev internet sitelerinin kendi teknolojileriyle çalışma yapmamaları, ve bu çalışmalar sonucunda ürünlerini piyasaya çıkarmamaları kaçınılmaz.
İşte burda ilişkisel olmayan veritabanlarının önemi artıyor. Çünkü birbiriyle ilişkili olan ve yukarıda ki işlemlerin daha yüzlercesini 2 milyar sayfa arasında sorgulatmak, kontrol etmek, Aynı anda aynı veriyi isteyen yüzbinlerce kullanıcıya sunmak gerçekten çok zor. İmkansız değil elbette fakat çok ciddi maliyetler, daha yavaş bir yapı ve çok daha fazla uğraş gerektirecek yöne götürüyor. Bu yöntemle yüzlerce, üstün özellikli olmasa da bu dev işlemi gerçekleştiren bilgisayarlara ihtiyaç doğuyor. İşlemcisi, Rami düşük olsa da, sorgulama, karşılaştırma kısacası ilişiklikten uzak olduğu için ihtiyaca tam cevap veriyor.
Aynı şekilde google veriyi tek bir makinada tutmayarak, bir makinanın göçmesi durumunda (ki böylesine bir sistem de çok olağan) birbiriyle ilişkilendirdiği diğer makinalardan devam ettirerek, sistemin sürekli çalışmasını sağlıyor.
Yine Hasan Ozgan hocanın yazısına dönersek;
Google, startup döneminde, bir mühendislik şirketi gibi davrandı ve ihtiyaçlarını iyi analiz etti. 10.000$lık sunucular almak yerine 500$lık ucuz makineler satın aldı. Ve bu makinelerin kısa ömürlü ve her an patlayacağını bilerek kodlarını yazdı. Ve BigTable denilen (Hadoop bunun açık kaynak halidir) Map ve Reduce fonksiyonları ile sorgulamayı sağlayan bir mimari kurdu. Bu mimarinin en önemli özelliği; makinelerden biri göçse bile, sistemin çalışmaya devam etmesidir. Her kaydın 3-5 ayrı sunucuda kopyası bulunmaktadır. Bu şekilde web için en uygun devasa bir Mosaic oluşturdular.
Googleun işi internet için oluşturduğu bu dev Mozaiği, istenene göre en doğru şekilde kullanıcıya sunmak. Bunu yaparken Özgün içerik ayrımını SimHash (Benzerlik Özeti) kavramıyla bilinen yöntemlerin üstüne kendi geliştirdiği, eklediği yöntem ve metodlarla yapıyor. Tamamen farklı bir yapıda kullanılabilir, fakat bu işin ana mantığı Sim hash Benzerlik özeti yapısı.
Yapay zeka konularında doğrultunun eksisinin belirlenmesi, doğruya yakınlığının hesaplanması önemlidir. Çünkü amaç Yapay zekanın en doğru sonucu üretmesidir. Simhash yöntemi de bu işi metodlar ve komutlarla hesaplayıp, her veriye bir tanım vererek doğru depolamayı amaçlamaktadır.
Örneğin aşağıda ki cümle Google örümcekleri tarafından indexlenmiş olsun.
Bilgi ve makaleler Bu yazı sonucunda çeşitli makaleler araştırılmaya devam edecek ve konu hakkında daha fazla bilgi, makaleler edinilecek..
İkinci iş olarak bu yazının özgünlüğünü kıyaslamak isteyeceği için, Öncelikle bu verinin kendi hafızasında olup olmadığını sorgulaması gerekmektedir. Bu adımdan sonra, yazdığımız cümlenin hafıza da olmadığını varsayarsak, Önce benim yönteme göre sonra Simhash benzerlik özeti yöntemine göre aşağıda ki şekillerde depolayacaktır.
Aşağıda olayı daha iyi anlayabilmeniz için basit bir tablo hazırladım(benim saçma yöntemim), bu tabloda site, ve içeriği özgün olduğu için veriyi nasıl kaydedeceği anlatılmıştır.
Örnek tablomuz;
Bu yazının yayınlandığı websitesi
www.kodrella.com
Bu yazının olduğu sitenin meta-tagları
keywords : bilgisayar, programlama, bilgisayar kavramları, teknoloji, popüler haberler
description : bilgisayar ve programlama hakkında çeşitli makalelerin yayınladığı güncel teknoloji sitesi.
h1-h2-b : bilgisayar, programlama, bilgisayar
Şimdi googleun aldığı cümle başka bir yerde kalıp halinde kullanılıp kullanılmadığını anlamak için cümleye özel bir tanım vermesi gerekir. Son zamanlarda popüler olan QR Code benzeri bir yöntem kullanılarak iş oldukça hızlandırılabilir.
Yazdığımız yazı tamamen benzersiz olduğu için, benzersiz bir tanım vermesi gerekir.
Öncelikle her kelimeyi ayrı ayrı olarak tanımlayıp site alanına + olarak ekleyelim.
Yazı,(1)
Sonucunda,(1)
Çeşitli,(1)
Makaleler(3),
araştırılmaya,(1)
devam,(1)
edecek,(1)
konu,(1)
hakkında,(1)
fazla,(1)
bilgi(2),
edinilecek(1)
*Bu, ve, ile, daha gibi daha önce tanımlanmış olan çeşitli bağlaçları almayarak hem zamandan tasarruf edip, hem en doğru veriyi depolayabilir bu yüzden, bu tür bağlaçları baştan sisteme kabul etmiyoruz.
Her bir kez tekrarlanan değer için 1, bir kez tekrarlanan için 0 rakamlarını cümle sırasına göre diziyoruz.
000111000000110
Tabii yüzmilyonlarca site, milyarlarca sayfa arasından aynı yapıya sahip onbinlerce cümle olacağından, birçok cümle aynı rakamsal karşılığı alacaktır. Bu da sistemin mantıksız bir yapıya kurulduğunun kanıtı.
Benim kendi yöntemimle çözmeye çalıştığım işi Sim Hash algoritması aşağıda ki şekilde Şadi Evren ŞEKER hocanın anlatımıyla ekledim.
Sim hash algoritması, iki dosyayı birer vektör olarak görür ve bu vektorler (yöney, vector) arasındaki cosinüs (cosine) bağlantısını bulmaya çalışır.
Yukarıdaki şekilde temsil edildiği üzere iki dokümanın ayrı ayrı birere vektör olması durumunda, aralarında cos (x) olarak gösterilen bir açı ile bağlantı bulunması mümkündür.
Algoritma, öncelikle işlediği metindeki kelimelerin ağırlıklarını (weight) çıkarmakta ve buna göre kelimeleri sıralamaktadır.
Sıralanan her kelimeye, b uzunluğunda, yegane (unique) değer döndüren bir fonksiyon kullanılır. Örneğin her kelime için farklı bir hash sonucu döndüren fonksiyon kullanılır.
b boyutundaki bir vektörün ağırlık değeri hesaplanırken, her kelimedeki 1 değeri için +1 ve 0 değeri için -1 değeri ağırlığa eklenir.
Son olarak üretilen ağırlık vektöründeki + değerler 1, 0 ve değerler ise 0 olarak çevirilir.
Örnek
Yukarıdaki algoritmanın çalışmasını bir örnek üzerinden anlatalım. Algoritmanın üzerinde çalışacağı metin aşağıdaki şekilde verilmiş olsun:
www bilgisayar kavramları com bilgisayar kavramlarının anlatıldığı bir bilgisayar sitesidir ve com uzantılıdır
Yukarıdaki bu metni, algoritmanın anlatılan adımlarına göre işleyelim:
İlk adımımız, algoritmadaki kelimelerini ağırlıklarının çıkarılmasıdır. Bu adımı çeşitli şekillerde yapmak mümkündür ancak biz örneğimizde kolay olması açısından kelimefrekanslarını (tekrar sayısı, frequency) kullanacağız. Buna göre metindeki kelimelerin tekrar sayılarına göre sıralanmış hali aşağıda verilmiştir:
bilgisayar 3 com 2 kavramları 1 kavramlarının 1 anlatıldığı 1 bir 1 www 1 sitesidir 1 ve 1 uzantılıdır 1
Yukarıda geçen her kelime için bir parmak izi (fingerprint) değeri üretiyoruz. Bu değerin özelliği, kelimeler arasında yegane (unique) bir değer bulmaktır. Bu değer, herhangi bir hash fonksiyonu üzerinden de üretilebilir. Biz örneğimizde kolalık olması açısından her kelime için rast gele bir değer kendimiz atayacağız. Ancak gerçek bir uygulamada rast gele değerlerin kullanılması mümkün değildir. Bunun sebebi, aynı kelimenin tekrar gelmesi halinde yine aynı değerin üretilmesi zorunluluğudur. Bu yazıdaki amaç algoritmayı anlatmak olduğu için birer hash sonucu olarak rast gele değerler kullanılacaktır.
bilgisayar 10101010 com 11000000 kavramları 01010101 kavramlarının 10100101 anlatıldığı 11101110 bir 01011111 www 11110001 sitesidir 10101110 ve 00001111 uzantılıdır 00100010
3. adımda, yukarıdaki değerleri topluyoruz. Toplama işlemi sırasında 1 değerleri için +1 ve 0 değerleri için -1 alıyoruz.
10101010
11000000
01010101
10100101
11101110
01011111
11110001
10101110
00001111
00100010
2 0 2 -4 0 2 2 0
Son olarak, yukarıdaki değerleri ikilik tabana çeviriyoruz: 10100110 bu değer bizi simhash sonucumuz olarak bulunuyor.
Örneğin yeni bir dosyayı daha işlemek istediğimizde, bu dosyadaki kelime yoğunluğuna göre yukarıda bulduğumuz simhash değerine yakın bir değer çıkmasını bekleriz.
Diyelim ki yeni bir dosyada da sadece bilgisayar kavramları com yazıyor olsun. Bu yazının sim hash değerini bularak karşılaştırmaya çalışalım:
bilgisayar 10101010 com 11000000 kavramları 01010101
10101010
11000000
01010101
1 1 -1 -1 -1 1 1 1
Değerin ikilik tabana çevrilmiş hali : 11000111
Orjinal dokümandan çıkardığımız simhash değeri ile farklı olan bit sayısı 3′tür. Bunun anlamı yukarıdaki bilgisayar kavramları com yazısının orjinal yazıya 3 mesafesinde yakın olduğudur.
Son olarak google birebir bu yöntemi kullanmıyor tabii ki, fikir benzerliği var fakat, googleun çok daha ileri yöntemler kullanıyor. Zaman zaman yabancı websitelerinde, google kendi bloglarında bunlardan bahsediyor..
Kaynak:
http://www.kodrella.com/google-ozgun...nasil-yapiyor/