Programma Les 47 van 156 · Bouw een blocker
Bouw een blocker

Match verzoeken tegen regels

Waarom dit ertoe doet Een blocker controleert elke aanvraag die een pagina doet, vaak meer dan honderd per pagina, tegen tienduizenden regels. Als die controle traag is, voelt elke pagina traag aan, en mensen zetten de blocker uit. Snel en correct is wat bescherming bruikbaar maakt.

Twee taken: juist antwoord, snel

Denk aan een bibliotheek met 5.000 boeken. Om er één te vinden, zou je niet elke rug van de eerste plank lezen. Je gaat naar de juiste sectie, dan naar de juiste plank. Een blocker moet hetzelfde doen: spring direct naar de weinige regels die could kunnen matchen, en controleer alleen die.

Deze oefening wordt op beide beoordeeld. De tests tellen hoe vaak je decide calls rule_matches voor één verzoek, en het budget is 20 checks met 5,000 regels geladen. We tellen checks in plaats van je tijd te meten, dus een trage telefoon en een snelle laptop worden op dezelfde manier beoordeeld.

Stap 1: wildcards

Wildcard: een symbool dat staat voor "elke karakters". In filter lijsten is het *, dus /beacon/*/hit komt overeen met /beacon/42/hit en /beacon/abc/hit.

Splits het patroon bij elke *, zoek dan de stukken in de tekst, in volgorde, elk stuk na het vorige:

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) geeft terug waar piece begint, kijkend alleen vanaf positie pos, of -1 als het daar niet is. Let op dat in filter lijsten ? en . gewone tekens zijn, dus gebruik geen regular expression of fnmatch, die behandelen ze als speciaal.

Stap 2: één regel tegen één verzoek

rule_matches(rule, url, third_party) beantwoordt ja of nee voor één regel:

    De
  • A regel met third_party set komt nooit overeen met een first-party request.
  • De
  • A domeinregel adco.example komt overeen met de host adco.example of elke host die eindigt op .adco.example. De punt is belangrijk: notadco.example is iemand anders.
  • De
  • A patroonregel komt overeen wanneer wildcard_in(value, url.lower()) waar is.

Stap 3: een index, dus controleer je maar een paar regels

Index: een structuur die eenmaal wordt gebouwd en waarmee je dingen kunt vinden zonder alles te doorzoeken, zoals de index achterin een boek. Hier: een dictionary van host naam naar de regels voor die host.

A Een Python dict vindt een sleutel in één stap, ongeacht hoeveel sleutels het bevat. Bouw dus één keer:

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

Voor een verzoek naar img.adco.example, zoek elke eind van de host op: img.adco.example, adco.example, example. Dat zijn drie zoekopdrachten in plaats van 5,000 controles. Voeg de paar patroonregels toe (echte blockers indexeren die ook, door een kort stuk tekst dat ze moeten bevatten; we houden ze in een simpele lijst).

Stap 4: beslis, met uitzonderingen die winnen

Controleer elke kandidaat. Als een passende regel een uitzondering is, is het antwoord "allow", punt. Anders, als een blokregel overeenkwam, "block"; als niets overeenkwam, "allow". Uitzonderingen bestaan omdat lijsten soms dingen vangen die een site echt nodig heeft, zoals cdn.example, wat een onschadelijke bibliotheek dient.

A veelvoorkomende misvatting

"Meer regels betekent een tragere blocker." Met een goede index niet: het opzoeken van een host in een dictionary kost ongeveer evenveel met 50 regels of 50.000. Wat een blocker vertraagt is het één voor één controleren van regels.

Probeer het Nadat je klaar bent, verander je decide naar loop over elke regel in de lijst (geen index) en voer de tests opnieuw uit. De budget test faalt met een aantal van ongeveer 5,000. Dat getal is het werk dat je index bespaart bij elke aanvraag van elke pagina.

In andere talen

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
}

Samenvatting

  • Wildcard patronen: splits bij * en vind de stukken in volgorde.
  • Domain rules match de host of elke subdomain, vergeleken label voor label.
  • Een index (een dict door de host) betekent een paar look-ups in plaats van duizenden checks.
  • A matching exception wint altijd van een block rule.
Jij bent aan de beurt

Schrijf vier functies. wildcard_in(pattern, text): True wanneer de stukken van pattern tussen de * tekens allemaal in text in volgorde verschijnen. rule_matches(rule, url, third_party): True wanneer één regel dict (van de vorige les) overeenkomt met de aanvraag. build_index(rules): organiseer de regels zoals je wilt zodat decide de meeste kan overslaan. decide(index, url, third_party): geef "block" of "allow" terug, waarbij elke passende uitzondering wint, waarbij rule_matches maximaal 20 keer per aanvraag wordt aangeroepen wanneer 5,000 regels zijn geladen.

Een probleem ontdekt in deze les? Meld het · Vraag naar deze les

Deze oefening opent binnenkort

Maak de les ervoor af voordat deze wordt ontgrendeld. De hele cursus is gratis, geen account nodig, en je kunt deze les nu lezen.