पाठ्यक्रम 156 में से पाठ 47 · एक blocker बनाएँ
एक blocker बनाएँ

requests को नियमों से मिलाएँ

यह क्यों मायने रखता है एक blocker एक पन्ने की हर एक request, अक्सर हर पन्ने पर सौ से ज़्यादा, दसियों हज़ार नियमों से जाँचता है। अगर वह जाँच धीमी है, तो हर पन्ना धीमा लगता है, और लोग blocker बंद कर देते हैं। तेज़ और सही वही है जो सुरक्षा को इस्तेमाल लायक बनाता है।

दो काम: सही जवाब, जल्दी

5,000 किताबों वाली एक library की सोचें। एक ढूँढने के लिए आप पहली शेल्फ़ से हर किताब की रीढ़ नहीं पढ़ेंगे। आप सही हिस्से में जाते हैं, फिर सही शेल्फ़ पर। एक blocker को भी वही करना चाहिए: सीधे उन कुछ नियमों पर कूदें जो मेल खा सकते हैं, और सिर्फ़ उन्हें जाँचें।

इस अभ्यास को दोनों पर अंक मिलते हैं। Tests गिनते हैं कि एक request के लिए आपका decide कितनी बार rule_matches बुलाता है, और 5,000 नियम load होने पर budget 20 जाँचें है। हम आपका समय मापने के बजाय जाँचें गिनते हैं, इसलिए एक धीमे फ़ोन और एक तेज़ लैपटॉप को एक ही तरह अंक मिलते हैं।

क़दम 1: wildcards

Wildcard: एक चिह्न जो "कोई भी अक्षर" के लिए है। filter lists में यह * है, इसलिए /beacon/*/hit /beacon/42/hit और /beacon/abc/hit से मेल खाता है।

pattern को हर * पर बाँटें, फिर टुकड़ों को टेक्स्ट में ढूँढें, क्रम में, हर एक पिछले के बाद:

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) लौटाता है कि piece कहाँ शुरू होता है, सिर्फ़ स्थान pos से देखते हुए, या -1 अगर वह वहाँ नहीं। ध्यान दें कि filter lists में ? और . साधारण अक्षर हैं, इसलिए एक regular expression या fnmatch इस्तेमाल न करें, जो उन्हें ख़ास मानते हैं।

क़दम 2: एक request के मुक़ाबले एक नियम

rule_matches(rule, url, third_party) एक नियम के लिए हाँ या ना जवाब देता है:

  • third_party सेट वाला एक नियम कभी एक first-party request से मेल नहीं खाता।
  • एक domain नियम adco.example host adco.example या .adco.example पर ख़त्म होने वाले किसी भी host से मेल खाता है। dot मायने रखता है: notadco.example कोई और है।
  • एक pattern नियम तब मेल खाता है जब wildcard_in(value, url.lower()) सही हो।

क़दम 3: एक index, ताकि आप सिर्फ़ कुछ नियम जाँचें

Index: एक बार बनी एक संरचना जो आपको सब कुछ खोजे बिना चीज़ें ढूँढने देती है, एक किताब के पीछे के index की तरह। यहाँ: host नाम से उस host के नियमों तक एक dict।

एक Python dict एक key एक क़दम में ढूँढता है, उसमें कितनी भी keys हों। इसलिए एक बार बनाएँ:

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

img.adco.example को एक request के लिए, host का हर अंत खोजें: img.adco.example, adco.example, example। यह 5,000 जाँचों के बजाय तीन खोजें हैं। कुछ pattern नियम जोड़ें (असली blockers उन्हें भी index करते हैं, टेक्स्ट के एक छोटे टुकड़े से जो उनमें होना ही चाहिए; हम उन्हें एक सादी सूची में रखते हैं)।

क़दम 4: तय करें, अपवाद जीतते हैं

हर उम्मीदवार जाँचें। अगर कोई मेल खाता नियम एक अपवाद है, तो जवाब "allow" है, बस। नहीं तो, अगर कोई रोकने वाला नियम मेल खाया, तो "block"; अगर कुछ मेल नहीं खाया, तो "allow"। अपवाद इसलिए हैं क्योंकि सूचियाँ कभी-कभी वे चीज़ें पकड़ती हैं जिनकी एक साइट को सचमुच ज़रूरत है, जैसे cdn.example, जो एक हानिरहित library देता है।

एक आम ग़लतफ़हमी

"ज़्यादा नियम का मतलब एक धीमा blocker।" एक अच्छे index के साथ, नहीं: एक dict में एक host खोजने की क़ीमत 50 नियमों या 50,000 के साथ लगभग एक जैसी है। जो एक blocker को धीमा करता है वह है नियमों को एक-एक करके जाँचना।

आज़माएँ पास होने के बाद, decide को सूची के हर नियम पर loop करने के लिए बदलें (कोई index नहीं) और tests फिर चलाएँ। budget test लगभग 5,000 की गिनती के साथ विफल होता है। वह संख्या वह काम है जो आपका index हर पन्ने की हर request पर बचाता है।

दूसरी भाषाओं में

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
}

सार

  • Wildcard patterns: * पर बाँटें और टुकड़ों को क्रम में ढूँढें।
  • Domain नियम host या किसी भी subdomain से मेल खाते हैं, label दर label तुलना करके।
  • एक index (host से एक dict) का मतलब हज़ारों जाँचों के बजाय कुछ खोजें।
  • एक मेल खाता अपवाद हमेशा एक रोकने वाले नियम पर जीतता है।
आपकी बारी

चार functions लिखें। wildcard_in(pattern, text): True जब * चिह्नों के बीच pattern के सारे टुकड़े text में क्रम में दिखें। rule_matches(rule, url, third_party): True जब एक नियम dict (पिछले पाठ से) request से मेल खाए। build_index(rules): नियमों को जैसे चाहें व्यवस्थित करें ताकि decide उनमें से ज़्यादातर छोड़ सके। decide(index, url, third_party): "block" या "allow" लौटाएँ, कोई भी मेल खाता अपवाद जीते, 5,000 नियम load होने पर हर request पर ज़्यादा से ज़्यादा 20 बार rule_matches बुलाते हुए।

इस पाठ में कोई समस्या दिखी? बताएँ · इस पाठ के बारे में पूछें

यह अभ्यास जल्द खुलेगा

इससे पहले वाला पाठ पूरा करें और यह खुल जाएगा। पूरा कोर्स मुफ़्त है, कोई खाता नहीं चाहिए, और आप यह पाठ अभी पढ़ सकते हैं।