Tair (Redis® OSS-Compatible):TairBloom

Genel Bakış

Redis'te benzer işlevselliği Hash, Set veya String içinde depolanan bir bitset kullanarak uygulayabilirsiniz. Ancak bu yöntemler ya çok fazla bellek tüketir ya da sabit bir yanlış pozitif oranını korurken dinamik olarak ölçeklenemez. TairBloom, büyük veri kümelerinde verimli üyelik testleri gerektiren ve küçük bir yanlış pozitif oranına tolerans gösteren kullanım durumları için idealdir. Özel sarmalayıcılara veya yerel uygulamalara ihtiyaç duymadan TairBloom API'sini doğrudan kullanabilirsiniz.

Temel özellikler

• Düşük bellek ayak izi.

• Otomatik ölçeklendirmeyi destekler.

• Otomatik ölçeklendirme sırasında kararlı kalan özelleştirilebilir yanlış pozitif oranı.

Kullanım durumları

En iyi uygulamalar

void recommendedSystem(userid) {
    while (true) {
        // Get a candidate article ID.
        docid = getDocByRandom()
        if (bf.exists(userid, docid)) {
            // The article was probably already recommended, so skip it.
            continue;
        } else {
            // The article was definitely not recommended, so send it.
            sendRecommendMsg(docid);
            // Record the recommendation.
            bf.add(userid, docid);
            break;
        }
    }
}

bool crawlerSystem( ) {
    while (true) {
        // Get a URL to crawl.
        url = getURLFromQueue()
        if (bf.exists(url_bloom, url)) {
            // The URL was probably already crawled, so skip it.
            continue;
        } else {
            // Download the URL content.
            doDownload(url)
            // Add the URL to TairBloom.
            bf.add(url_bloom, url);
        }
    }
}

Çalışma Prensibi

TairBloom, Ölçeklenebilir Bloom Filtresi uygulamasıdır. Otomatik ölçeklendirmeyi destekler ve sabit bir yanlış pozitif oranını korur. Ölçeklenebilir Bloom Filtresi, optimize edilmiş bir bloom filtresi sürümüdür. Aşağıdaki bölümlerde bloom filtrelerinin ve Ölçeklenebilir Bloom Filtrelerinin temel ilkeleri açıklanmaktadır.

• Bloom filtresi

  Bloom filtresi, Burton Bloom tarafından 1970 yılında önerilen alan açısından verimli olasılıksal bir veri yapısıdır. Bir öğenin bir kümeye üye olup olmadığını test etmek için kullanılır.

  Yeni bir bloom filtresi, başlangıçta tüm bitleri 0 olarak ayarlanmış m bitlik bir bit dizisidir. Ayrıca, k'nin m'den küçük bir sabit olduğu k farklı karma işlevi kullanır ve bunlar düzgün rastgele bir dağılım oluşturur. Bloom filtresine bir öğe eklediğinizde, k karma işlevi öğeyi bit dizisindeki k konuma eşler ve bu konumlardaki bitler 1 olarak ayarlanır. Tek bir bit birden fazla öğe tarafından paylaşılabilir. Aşağıdaki şekil, k'nin 3 olduğu bir bloom filtresine X1 ve X2 öğelerinin nasıl eklendiğini gösterir.

  

  Bir öğeyi sorgulamak için aynı k karma işlevi kullanılarak ilgili k bit konumu elde edilir. Bu konumlardaki tüm bitler 1 ise öğenin bloom filtresinde bulunduğu kabul edilir. Herhangi bir bit 0 ise öğe kesinlikle mevcut değildir. Aşağıdaki şekil, Y1 ve Y2'nin bloom filtresinde olup olmadığının nasıl kontrol edileceğini gösterir.

  

  Şekilde gösterildiği gibi, Y2 öğesi bloom filtresine hiç eklenmemiş olmasına rağmen filtre Y2'nin var olduğunu bildirir. Bu bir yanlış pozitiftir. Buna dayanarak bir bloom filtresinin özelliklerini şu şekilde özetleyebiliriz:

  • Bit konumları farklı öğeler tarafından paylaşılabilir.

  • Yanlış pozitifler oluşabilir. Bloom filtresindeki öğe sayısı arttıkça yanlış pozitif olasılığı da artar. Ancak yanlış negatifler oluşmaz. Bir öğe yok olarak bildiriliyorsa kesinlikle yoktur.

  • Öğeler bir bloom filtresine eklenebilir ancak kaldırılamaz. Bunun nedeni bit konumlarının paylaşılabilmesi ve bir öğe için bir biti temizlemenin diğer öğeleri etkileyebilmesidir.

• Ölçeklenebilir Bloom Filtresi

  Bir bloom filtresine daha fazla öğe eklendikçe yanlış pozitif oranı artar. Yanlış pozitif oranını sabit tutmak için bloom filtresinin boyutu artırılmalıdır. Ancak standart bir bloom filtresi yeniden boyutlandırılamaz. Ölçeklenebilir Bloom Filtresi, yeni bloom filtreleri oluşturup bunları tek bir mantıksal filtrede üst üste yığarak bu sorunu çözer.

  Aşağıdaki şekil, BF0 ve BF1 olmak üzere iki katman içeren bir Ölçeklenebilir Bloom Filtresinin (SBF) temel modelini gösterir. Başlangıçta SBF yalnızca BF0 katmanını içerir. a, b ve c öğeleri eklendikten sonra BF0 katmanının kullanıcı tanımlı yanlış pozitif oranını artık koruyamadığını varsayalım. Bu noktada yeni bir katman (BF1) oluşturulur. Sonraki d, e ve f öğeleri BF1 katmanına eklenir. Benzer şekilde, BF1 katmanı yanlış pozitif oranını karşılayamadığında yeni bir katman (BF2) oluşturulur ve bu işlem devam eder. Daha fazla bilgi için bkz. Ölçeklenebilir Bloom Filtresi.

  

  Önemli

  TairBloom otomatik ölçeklendirme yaptığında yeni katman, önceki katmanın iki katı kapasiteye ve dört katı bellek kullanımına sahip olur.

  Her eklenen katman sorgu süresini artırır çünkü bir sorgunun birden fazla bloom filtresi katmanını taraması gerekebilir. Ölçeklenebilir Bloom Filtresi verileri her zaman en son katmana ekler ve sorgular en son katmandan başlayıp ilk katmana (BF0) doğru geriye doğru devam eder. Sonuç olarak TairBloom'daki otomatik ölçeklendirme işlemleri büyük anahtarlar oluşturabilir ve performansı düşürebilir. Performans düşüşü, öğe sayısı arttıkça artar.

  Pratikte TairBloom otomatik ölçeklendirmesinin tetiklenmesinden kaçınmalı ve bu özelliği bir güvenlik mekanizması olarak görmelisiniz. Otomatik ölçeklendirme olayından sonra yazma hatalarını önlemek ve uzun süreli veri tahliye işlemlerini tetikleyerek örneğin yanıt vermemesine neden olmamak için örnek için yeterli bellek ayırın. Bir anahtarın otomatik ölçeklendirme olayını tetiklemek üzere olup olmadığını kontrol etmek için BF.INFO komutunu kullanabilirsiniz. En son katmandaki items sayısı capacity değerine ulaştığında otomatik ölçeklendirme olayı yakındır.

  Gerçek kapasite önceden belirlenen kapasiteyi aştığında TairBloom, yazma işlemlerinin devam etmesini sağlamak ve üretim kazalarını önlemek amacıyla otomatik ölçeklendirme yapar. TairBloom otomatik ölçeklendirme işlemini tamamladıktan sonra performansı iyileştirmek ve sonraki otomatik ölçeklendirme olayıyla ilişkili riskleri azaltmak için anahtarı mümkün olan en kısa sürede yeniden oluşturun.

Ön Koşullar

Kullanım Notları

• Bu konudaki komutlar bir Tair örneğindeki TairBloom verileri üzerinde çalışır.

• İlk kapasiteyi ve yanlış pozitif oranını önceden planlayın. Hedef anahtarın beklenen kapasitesi 100'den çok daha büyükse TairBloom anahtarını oluşturmak için BF.RESERVE komutunu kullanın. Anahtarı BF.ADD komutuyla oluşturmayın.

  Aşağıdaki liste, BF.ADD komutu ile BF.RESERVE komutunu çalıştırma arasındaki farkları açıklar.

  • BF.ADD (veya BF.MADD): Komut çalıştırıldığında hedef anahtar yoksa Tair, varsayılan olarak 100 kapasiteli ve 0,01 yanlış pozitif oranına (error_rate) sahip bir TairBloom örneği otomatik olarak oluşturur. Gerekli kapasiteniz 100'den çok daha büyükse daha sonra kapasiteyi genişleterek yalnızca daha fazla öğe ekleyebilirsiniz. TairBloom'daki dahili katman sayısı arttıkça sorgu işlemleri birden fazla Bloom filtresini taramak zorunda kalır ve bu durum performansı ciddi şekilde düşürür.

  • BF.RESERVE (veya BF.INSERT): Bu komutu çalıştırdığınızda capacity (ilk kapasite) değerini ayarlamanız gerekir. Bu komut, TairBloom anahtarının ilk katmanındaki kapasiteyi başlatır. Daha az katmana sahip bir TairBloom anahtarı daha hızlı sorgular sağlar.

  Not

  Örneğin, yanlış pozitif oranı 0,01 olacak şekilde 10.000.000 öğe eklemek için BF.ADD komutuyla bir TairBloom anahtarı oluşturmak 176 MB bellek gerektirir. Buna karşılık, anahtarı BF.RESERVE komutuyla oluşturmak yalnızca 16 MB gerektirir.

  Aşağıdaki tabloda, BF.RESERVE komutuyla farklı ilk kapasiteler ve yanlış pozitif oranlarıyla oluşturulan anahtarlar için bellek kullanımı listelenmektedir. Değerler yalnızca referans amaçlıdır.

  Kapasite	Yanlış pozitif oranı: 0,01	Yanlış pozitif oranı: 0,001	Yanlış pozitif oranı: 0,0001
  100.000	0,12 MB	0,25 MB	0,25 MB
  1.000.000	2 MB	2 MB	4 MB
  10.000.000	16 MB	32 MB	32 MB
  100.000.000	128 MB	256 MB	256 MB
  1.000.000.000	2 GB	2 GB	4 GB

  Çok büyük bir kapasiteyle anahtar oluştururken error_rate değerini göz önünde bulundurun. Çok büyük bir kapasiteye ve yüksek doğruluğa (düşük error_rate) sahip bir anahtar, yetersiz örnek belleği nedeniyle başarısız olabilir.

• TairBloom, yeni öğeler eklemenize izin verir ancak mevcut öğelerin silinmesine izin vermez. Sonuç olarak bir TairBloom anahtarının bellek kullanımı yalnızca artar. Bir TairBloom anahtarının aşırı büyümesini ve bellek yetersizliği (OOM) hatalarına neden olmasını önlemek için aşağıdaki önerileri dikkate alın.

  • İş verilerini bölün: İş verilerinizi bölüp iyileştirerek büyük miktarda veriyi tek bir TairBloom anahtarında depolamaktan kaçının. Bu yaklaşım, anahtarın çok büyük hale gelip sorgu performansını etkilemesini önlemenin yanı sıra çoğu sorgu trafiğinin anahtarın bulunduğu Redis örneğine yönlendirilmesini de engelleyerek sıcak anahtar oluşumunu ve erişim eğrilmesini önler.

    İş verilerinizi bölün ve verileri birden fazla TairBloom anahtarına dağıtın. Bir küme örneği kullanıyorsanız TairBloom anahtarlarını kümedeki düğümlere dağıtarak bellek ve trafiği dengeleyebilir ve dağıtılmış bir kümenin avantajlarından tam anlamıyla yararlanabilirsiniz.

  • Periyodik olarak yeniden oluşturun: İş süreçleriniz izin veriyorsa TairBloom anahtarını periyodik olarak yeniden oluşturabilirsiniz. TairBloom anahtarını silmek için DEL komutunu kullanın ve ardından arka uç veritabanından verileri çekerek anahtarı yeniden oluşturun. Bu yaklaşım TairBloom anahtarının boyutunu kontrol etmenize yardımcı olur.

    Başlangıçta birden fazla TairBloom anahtarı oluşturup bunlar arasında dönüşüm yaparak tek tek anahtarların boyutunu da kontrol edebilirsiniz. Bu yaklaşım sık sık yeniden oluşturmayı önler ancak daha fazla bellek tüketir.

Komut Referansı

BF.RESERVE

BF.RESERVE BFKEY 0.01 100

OK

BF.ADD

BF.ADD BFKEY item1

(integer) 1

BF.MADD

BF.MADD BFKEY item1 item2 item3

(integer) 1
    (integer) 1
    (integer) 1

BF.EXISTS

BF.EXISTS BFKEY item1

(integer) 1

BF.MEXISTS

BF.MEXISTS BFKEY item1 item5

(integer) 1
    (integer) 0

BF.INSERT

BF.INSERT bfkey1 CAPACITY 10000 ERROR 0.001 ITEMS item1 item2 item3

(integer) 1
    (integer) 1
    (integer) 1

BF.INFO

BF.INFO bk1

1) "total_items:6,num_blooms:2"
    2) "bytes:4 bits:32 hashes:7 hashwidth:64 capacity:3 items:3 error_ratio:0.01"
    3) "bytes:16 bits:128 hashes:9 hashwidth:64 capacity:10 items:3 error_ratio:0.0025"

SSS