Kurrikulum Leson 47 van 156 · Bou 'n bloker
Bou 'n bloker

Pas versoeke teen reëls af

Hoekom dit saak maak 'n blocker kontroleer elke enkele versoek wat 'n bladsy maak, dikwels meer as honderd per bladsy, teen tien duisende reëls. As daardie kontrole stadig is, voel elke bladsy stadig, en mense skakel die blocker af. Vinnig en korrek is wat beskerming gebruikbaar maak.

Twee take: regte antwoord, vinnig

Dink aan 'n biblioteek met 5,000 boeke. Om een te vind, sou jy nie elke rug van die eerste rak lees nie. Jy gaan na die regte afdeling, dan na die regte rak. 'n Blocker moet dieselfde doen: spring reguit na die min reëls wat could pas, en tel net daardie een.

Hierdie oefening word op albei gegradeer. Die toetse tel hoeveel keer jou decide die rule_matches vir een versoek aanroep, en die begroting is 20 checks met 5,000 reëls gelaai. Ons tel checks in plaas daarvan om jou tyd te meet, so 'n stadige foon en 'n vinnige skootrekenaar word dieselfde gegradeer.

Stap 1: wildcards

Wildcard: 'n simbool wat staan vir "enige karakters". In filterlyste is dit *, so /beacon/*/hit pas by /beacon/42/hit en /beacon/abc/hit.

Verdeel die patroon by elke *, dan vind die stukke in die teks, in volgorde, elk een na die 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) gee terug waar piece begin, deur net vanaf posisie pos te kyk, of -1 as dit nie daar is nie. Let daarop dat in filterlyste ? en . gewone karakters is, so moenie 'n regular expression of fnmatch gebruik wat hulle as spesiaal behandel nie.

Stap 2: een reël teen een versoek

rule_matches(rule, url, third_party) antwoord ja of nee vir een reël:

  • A-reël met third_party-stel pas nooit by 'n eerste-party versoek nie.
  • -domeinreël adco.example pas by die gasheer adco.example of enige gasheer wat op .adco.example eindig. Die punt maak saak: notadco.example is iemand anders.
  • Die
  • A patroonreël pas wanneer wildcard_in(value, url.lower()) waar is.

Stap 3: 'n indeks, sodat jy net 'n paar reëls nagaan

Index: 'n struktuur wat een keer gebou word sodat jy dinge kan vind sonder om alles deur te soek, soos die indeks agter in 'n boek. Hier: 'n dict van host name na die reëls vir daardie host.

A Python dict vind 'n sleutel in een stap, ongeag hoeveel sleutels dit hou. Bou dus een keer:

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

Vir 'n versoek na img.adco.example, soek elke einde van die host op: img.adco.example, adco.example, example. Dit is drie soektogs in plaas van 5,000 kontroles. Voeg die paar patroonreëls by (reële blokkeerders indeks ook dié deur 'n kort stukkie teks wat hulle moet bevat; ons hou hulle in 'n eenvoudige lys).

Stap 4: besluit, met uitsonderings wat wen

Kontroleer elke kandidaat. As enige passende reël 'n uitsondering is, is die antwoord "allow", punt. Andersins, as enige blokreël gepas het, "block"; as niks gepas het nie, "allow". Uitsonderings bestaan omdat lyste soms dinge vang wat 'n webwerf regtig nodig het, soos cdn.example, wat 'n onskadelike biblioteek bedien.

A algemene wanbegrip

"Meer reëls beteken 'n stadiger bloker." Met 'n goeie indeks, nie: om 'n host in 'n dict op te soek kos ongeveer dieselfde met 50 reëls of 50,000. Wat 'n bloker vertraag, is om reëls een vir een te kontroleer.

Probeer dit Nadat jy dit geslaag het, verander decide om oor elke reël in die lys te loop (geen indeks nie) en hardloop die toetse weer. Die budget-toets faal met 'n telling van ongeveer 5,000. Daardie nommer is die werk wat jou indeks op elke versoek van elke bladsy bespaar.

In ander tale

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

Ga:

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
}

Opsomming

  • Wildcardpatrone: splits by * en vind die stukke in volgorde.
  • Domain-reëls pas by die gasheer of enige subdomein, vergelyk label vir label.
  • 'n indeks ('n dict by host) beteken 'n paar soektogs in plaas van duisende kontroles.
  • 'n ooreenstemmende uitsondering wen altyd oor 'n blokreël.
Jou beurt

Skryf vier funksies. wildcard_in(pattern, text): Waar as die dele van pattern tussen * tekens al in text in volgorde verskyn. rule_matches(rule, url, third_party): Waar as een reël dict (van die vorige les) by die versoek pas. build_index(rules): organiseer die reëls op enige manier wat jy wil sodat decide die meeste daarvan kan ooslaan. decide(index, url, third_party): gee "block" of "allow" terug, met enige bypassende uitsondering wat wen, en roep rule_matches hoogstens 20 keer per versoek wanneer 5,000 reëls gelaai is.

Sien jy 'n probleem in hierdie les? Rapporteer dit · Vra oor hierdie les

Hierdie oefening open binnekort

Voltooi die lesie voor dit en hierdie een sal ontvanklik wees. Die hele kursus is gratis, geen rekening nodig nie, en jy kan hierdie les nou lees.