Müfredat 156 dersinden 47. · Bir engelleyici oluştur
Bir engelleyici oluştur

İstekleri kurallarla eşleştir

Neden önemli Bir blocker, bir sayfanın yaptığı her isteği, genellikle sayfa başına yüzden fazla isteği, on binlerce kurala karşı kontrol eder. Eğer bu kontrol yavaşsa, her sayfa yavaş hissedilir ve insanlar blockerı kapatır. Hızlı ve doğru olması, korumayı kullanılabilir kılan şeydir.

İki görev: doğru cevap, hızlıca

5,000 kitaplık içeren bir kütüphane düşün. Birini bulmak için ilk raftan itibaren her sırtı okumazsın. Doğru bölüme, sonra doğru rafa gidersin. Bir blocker da aynısını yapmalı: could uyan birkaç kurala doğrudan atlamalı ve sadece onları kontrol etmeli.

Bu egzersiz her ikisine göre puanlanır. Testler, bir istek için decide'nin rule_matches'yi kaç kez çağırdığını sayar ve bütçe, 5.000 kural yüklendiğinde 20 checks'dir. Seni zamanlamak yerine kontrolleri sayıyoruz, bu yüzden yavaş bir telefon ve hızlı bir dizüstü bilgisayar aynı şekilde puanlanır.

Adım 1: joker karakterler

Wildcard: "herhangi bir karakter" anlamına gelen bir semboldür. Filtre listelerinde *, bu yüzden /beacon/*/hit hem /beacon/42/hit hem de /beacon/abc/hit ile eşleşir.

Deseni her * kısmında böl, sonra parçaları metin içinde bul, sırasıyla, her biri bir öncekinden sonra:

wildcard_in("*/collect?*cid=", "https://m.example/collect?x=1&cid=9")
# pieces: "/collect?" then "cid="  -> both found, in order -> True

wildcard_in("a*b", "b then a")
# "a" found at position 7, then no "b" after it -> False

text.find(piece, pos), sadece pos konumundan bakarak piece'nin başladığı yeri veya orada değilse -1'yi döndürür. Filtre listelerinde ? ve .'nin sıradan karakterler olduğunu, bu yüzden onları özel olarak işleyen bir düzenli ifade veya fnmatch kullanmaman gerektiğini unutma.

Adım 2: bir isteğe karşı bir kural

rule_matches(rule, url, third_party) bir kural için evet veya hayır cevabı verir:

  • kuralı third_party seti ile asla bir birinci taraf isteğiyle eşleşmez.
  • alan adı kuralı adco.example, adco.example ana bilgisayarını veya .adco.example ile biten herhangi bir ana bilgisayarı eşleştirir. Nokta önemlidir: notadco.example başkasıdır.
  • A desen kuralı wildcard_in(value, url.lower()) doğru olduğunda eşleşir.

Adım 3: bir indeks, böylece sadece birkaç kuralı kontrol edersin

Index: her şeyi aratmadan bir şeyleri bulmanı sağlayan, bir kitabın arkasındaki indeks gibi bir kez oluşturulan yapıdır. Burada: host adından o host için kurallara bir dict.

A Python dict kaç anahtar tutarsa tutsun bir adımda bir anahtarı bulur. Bu yüzden bir kez oluştur:

index = {"domains": {"adco.example": [rule, ...], ...},
         "patterns": [rule, rule, ...]}

img.adco.example için bir istek geldiğinde, ana bilgisayarın her bitişine bak: img.adco.example, adco.example, example. Bu, 5,000 kontrol yerine üç arama demektir. Birkaç desen kuralını ekle (gerçek engelleyiciler bunları de içermeleri gereken kısa bir metin parçasıyla indeksler; biz onları düz bir listede tutuyoruz).

Adım 4: karar ver, istisnalar kazansın

Her adayı kontrol et. Eğer eşleşen kurallardan herhangi biri bir istisnaysa, cevap "allow", nokta. Aksi takdirde, herhangi bir blok kuralı eşleştiyse "block"; hiçbir şey eşleşmediyse "allow". İstisnalar vardır çünkü listeler bazen bir sitenin gerçekten ihtiyaç duyduğu şeyleri, örneğin zararsız bir kütüphaneye hizmet eden cdn.example gibi şeyleri yakalayabilir.

Yaygın bir yanılgı

"Daha fazla kural, daha yavaş bir engelleyici demektir." İyi bir index ile hayır: bir dict içinde bir host aramak 50 kuralda veya 50,000 kuralda hemen hemen aynı maliyete sahip. Bir engelleyiciyi yavaşlatan şey kuralları tek tek kontrol etmektir.

Kendin dene Geçtikten sonra decide listedeki her kuralı dönmek (indeks yok) için değiştir ve testleri tekrar çalıştır. Bütçe testi yaklaşık 5,000 sayısıyla başarısız oluyor. Bu sayı, indeksinin her sayfanın her isteğinde tasarruf ettiği iş miktarıdır.

Diğer dillerde

JavaScript:

function wildcardIn(pattern, text) {
  let pos = 0;
  for (const piece of pattern.split("*")) {
    if (!piece) continue;
    const at = text.indexOf(piece, pos);
    if (at === -1) return false;
    pos = at + piece.length;
  }
  return true;
}

// Index: a Map from host to rules; look up each ending of the host.
function candidates(index, host) {
  const parts = host.split(".");
  const out = [];
  for (let i = 0; i < parts.length; i++) {
    out.push(...(index.domains.get(parts.slice(i).join(".")) || []));
  }
  return out.concat(index.patterns);
}

Git:

func wildcardIn(pattern, text string) bool {
    pos := 0
    for _, piece := range strings.Split(pattern, "*") {
        if piece == "" {
            continue
        }
        at := strings.Index(text[pos:], piece)
        if at < 0 {
            return false
        }
        pos += at + len(piece)
    }
    return true
}

Özet

  • Wildcard desenleri: * üzerinden böl ve parçaları sırasıyla bul.
  • Domain kuralları ana makineyi veya herhangi bir alt alan adını, etiket etiket karşılaştırarak eşleştirir.
  • Bir index (host tarafından bir dict) binlerce kontrol yerine birkaç arama anlamına gelir.
  • A eşleşen istisna her zaman bir blok kuralından üstün gelir.
Senin sıran

Dört fonksiyon yaz. wildcard_in(pattern, text): pattern içindeki * işaretleri arasındaki parçaların tamamı text içinde sırasıyla göründüğünde True döner. rule_matches(rule, url, third_party): Bir kural sözlüğü (geçen dersten) istekle eşleştiğinde True döner. build_index(rules): decide çoğu kuralı atlayabilsin diye kuralları istediğin gibi düzenle. decide(index, url, third_party): Herhangi bir eşleşen istisnanın kazandığı şekilde "block" veya "allow" döndür, 5,000 kural yüklendiğinde her istek için rule_matches fonksiyonunu en fazla 20 kez çağır.

Bu derste bir sorun mu fark ettin? Bildir · Bu ders hakkında soru sor

Bu alıştırma yakında açılacak

Bu dersi bitirince bu ders açılacak. Kursun tamamı ücretsiz, hesap gerekmiyor ve bu dersi hemen şimdi okuyabilirsin.