Silabus Pelajaran 47 dari 156 · Buat pemblokir
Buat pemblokir

Cocokkan permintaan dengan aturan

Kenapa ini penting Sebuah blocker memeriksa setiap permintaan yang dibuat halaman, seringkali lebih dari seratus per halaman, terhadap puluhan ribu aturan. Jika pemeriksaan itu lambat, setiap halaman terasa lambat, dan orang akan mematikan blocker. Cepat dan benar adalah hal yang membuat perlindungan bisa digunakan.

Dua tugas: jawaban benar, cepat

Bayangkan sebuah perpustakaan dengan 5,000 buku. Untuk mencari satu buku, kamu tidak akan membaca setiap punggung buku dari rak pertama. Kamu pergi ke bagian yang tepat, lalu ke rak yang tepat. Sebuah blocker harus melakukan hal yang sama: langsung lompat ke beberapa aturan yang could cocok, dan periksa hanya itu saja.

Latihan ini dinilai dari keduanya. Tes menghitung berapa kali decide memanggil rule_matches untuk satu permintaan, dan anggarannya adalah 20 checks dengan 5,000 aturan yang dimuat. Kami menghitung jumlah pengecekan daripada mengukur waktu kamu, jadi ponsel lambat dan laptop cepat dinilai dengan cara yang sama.

Langkah 1: wildcards

Wildcard: simbol yang berarti "karakter apa saja". Dalam daftar filter itu adalah *, jadi /beacon/*/hit cocok dengan /beacon/42/hit dan /beacon/abc/hit.

Pisahkan pola di setiap *, lalu cari potongan di teks, sesuai urutan, satu per satu setelah yang sebelumnya:

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) mengembalikan di mana piece dimulai, hanya dilihat dari posisi pos, atau -1 jika tidak ada di sana. Perhatikan bahwa dalam daftar filter ? dan . adalah karakter biasa, jadi jangan gunakan regular expression atau fnmatch, yang menganggap mereka sebagai karakter khusus.

Langkah 2: satu aturan untuk satu permintaan

rule_matches(rule, url, third_party) menjawab ya atau tidak untuk satu aturan:

    Aturan
  • A dengan set third_party tidak pernah cocok dengan permintaan pihak pertama.
  • Aturan domain
  • adco.example cocok dengan host adco.example atau host apa pun yang berakhiran .adco.example. Titik itu penting: notadco.example adalah orang lain.
  • Aturan pola
  • cocok saat wildcard_in(value, url.lower()) bernilai true.

Langkah 3: sebuah indeks, jadi kamu hanya mengecek beberapa aturan

Index: struktur yang dibuat sekali agar kamu bisa menemukan sesuatu tanpa mencari semuanya, seperti indeks di bagian belakang buku. Di sini: sebuah dict dari nama host ke aturan untuk host tersebut.

A dict Python menemukan kunci dalam satu langkah, tidak peduli berapa banyak kunci yang ada. Jadi buat, sekali:

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

Untuk permintaan ke img.adco.example, cari setiap akhiran host: img.adco.example, adco.example, example. Itu berarti tiga pencarian alih-alih 5,000 pengecekan. Tambahkan beberapa aturan pola (pemblokir asli juga mengindeks itu, berdasarkan potongan teks pendek yang harus mereka miliki; kita menyimpannya dalam daftar biasa).

Langkah 4: putuskan, dengan pengecualian yang menang

Cek setiap kandidat. Jika ada aturan yang cocok merupakan pengecualian, jawabannya adalah "allow", titik. Jika tidak, jika ada aturan blok yang cocok, "block"; jika tidak ada yang cocok, "allow". Pengecualian ada karena daftar terkadang menangkap hal yang sebenarnya tidak dibutuhkan situs, seperti cdn.example, yang melayani pustaka tidak berbahaya.

Kesalahpahaman umum

"Lebih banyak aturan berarti pemblokir lebih lambat." Dengan indeks yang bagus, tidak: mencari host di dict biayanya hampir sama dengan 50 aturan atau 50,000. Yang memperlambat pemblokir adalah memeriksa aturan satu per satu.

Coba sendiri Setelah berhasil, ubah decide untuk melakukan loop ke setiap rule di dalam list (tanpa index) dan jalankan tes lagi. Tes budget gagal dengan jumlah sekitar 5,000. Angka itu adalah beban kerja yang dihemat oleh index kamu pada setiap request dari setiap halaman.

Di bahasa lain

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);
}

Go:

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
}

Ringkasan

  • Pola wildcard: bagi di * dan cari bagiannya sesuai urutan.
  • Aturan Domain cocok dengan host atau subdomain apa pun, dibandingkan label demi label.
  • Indeks (dict berdasarkan host) berarti beberapa pencarian alih-alih ribuan pengecekan.
  • pengecualian matching selalu menang daripada aturan blok.
Giliranku

Tulis empat fungsi. wildcard_in(pattern, text): True jika potongan pattern di antara tanda * semuanya muncul di text secara berurutan. rule_matches(rule, url, third_party): True jika satu dict aturan (dari pelajaran terakhir) cocok dengan permintaan. build_index(rules): atur aturan sesukamu agar decide bisa melewati sebagian besar aturan tersebut. decide(index, url, third_party): kembalikan "block" atau "allow", dengan pengecualian yang cocok yang menang, memanggil rule_matches maksimal 20 kali per permintaan saat 5,000 aturan dimuat.

Ada masalah di pelajaran ini? Laporkan · Tanya tentang pelajaran ini

Latihan ini akan segera dibuka

Selesaikan pelajaran sebelumnya agar pelajaran ini terbuka. Seluruh kursus ini gratis, tidak butuh akun, dan kamu bisa baca pelajaran ini sekarang.