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 -> Falsetext.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_partytidak pernah cocok dengan permintaan pihak pertama. Aturan domain -
adco.examplecocok dengan hostadco.exampleatau host apa pun yang berakhiran.adco.example. Titik itu penting:notadco.exampleadalah 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.
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.
Browser ini memblokir cookie untuk learn.floati.life, jadi pelajaran yang sudah kamu selesaikan di sini tidak bisa dibuka berurutan. Izinkan cookie untuk situs ini dan muat ulang.