سرفصل‌ها درس 47 از 156 · یک مسدودکننده بسازید
یک مسدودکننده بسازید

درخواست‌ها را با قواعد تطبیق دهید

چرا مهم است یک مسدودکننده هر درخواستی را که یک صفحه می‌فرستد، اغلب بیش از صد درخواست در هر صفحه، با ده‌ها هزار قاعده بررسی می‌کند. اگر این بررسی کند باشد، هر صفحه کند به نظر می‌رسد، و آدم‌ها مسدودکننده را خاموش می‌کنند. سریع و درست بودن چیزی است که محافظت را قابل استفاده می‌کند.

دو کار: پاسخ درست، به‌سرعت

کتابخانه‌ای با 5,000 کتاب را در نظر بگیرید. برای پیداکردن یکی، عطف همهٔ کتاب‌ها را از قفسهٔ اول نمی‌خوانید. به بخش درست می‌روید، سپس به قفسهٔ درست. یک مسدودکننده هم باید همین کار را بکند: مستقیم به معدود قواعدی بپرد که ممکن است جور شوند، و فقط آن‌ها را بررسی کند.

این تمرین بر اساس هر دو نمره می‌گیرد. آزمون‌ها می‌شمارند decide شما برای یک درخواست چند بار rule_matches را فرا می‌خواند، و بودجه با 5,000 قاعدهٔ بارگذاری‌شده 20 بررسی است. به‌جای زمان‌گیری بررسی‌ها را می‌شماریم، تا یک تلفن کند و یک لپ‌تاپ سریع به یک شکل نمره بگیرند.

گام 1: نویسه‌های عام

نویسهٔ عام (wildcard): نمادی که به‌جای «هر نویسه‌ای» می‌نشیند. در فهرست‌های فیلتر * است، پس /beacon/*/hit با /beacon/42/hit و /beacon/abc/hit جور است.

الگو را در هر * جدا کنید، سپس تکه‌ها را در متن پیدا کنید، به ترتیب، هر کدام پس از قبلی:

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 اگر آنجا نباشد. توجه کنید که در فهرست‌های فیلتر ? و . نویسه‌های معمولی‌اند، پس از عبارت باقاعده (regular expression) یا fnmatch استفاده نکنید، که با آن‌ها رفتار ویژه دارند.

گام 2: یک قاعده در برابر یک درخواست

rule_matches(rule, url, third_party) برای یک قاعده بله یا نه پاسخ می‌دهد:

  • قاعده‌ای که third_party آن تنظیم شده هرگز با یک درخواست شخص اول جور نمی‌شود.
  • یک قاعدهٔ دامنه adco.example با میزبان adco.example یا هر میزبانی که با .adco.example تمام شود جور است. نقطه مهم است: notadco.example کس دیگری است.
  • یک قاعدهٔ الگو وقتی جور است که wildcard_in(value, url.lower()) درست باشد.

گام 3: یک نمایه، تا فقط چند قاعده را بررسی کنید

نمایه (index): ساختاری که یک بار ساخته می‌شود و به شما امکان می‌دهد چیزها را بدون جست‌وجوی همه‌چیز پیدا کنید، مثل نمایهٔ پشت یک کتاب. اینجا: یک dict از نام میزبان به قواعد آن میزبان.

یک dict در Python یک کلید را در یک گام پیدا می‌کند، هر چند کلید هم که داشته باشد. پس یک بار بسازید:

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

برای درخواستی به img.adco.example، هر پایان میزبان را جست‌وجو کنید: img.adco.example، adco.example، example. این سه جست‌وجو به‌جای 5,000 بررسی است. چند قاعدهٔ الگو را هم اضافه کنید (مسدودکننده‌های واقعی آن‌ها را هم نمایه می‌کنند، با یک تکهٔ کوتاه از متن که باید داشته باشند؛ ما آن‌ها را در یک فهرست ساده نگه می‌داریم).

گام 4: تصمیم، با برنده‌بودن استثناها

هر نامزد را بررسی کنید. اگر هر قاعدهٔ جورشده‌ای استثنا باشد، پاسخ "allow" است، تمام. وگرنه، اگر هر قاعدهٔ مسدودسازی جور شد، "block"؛ اگر هیچ چیز جور نشد، "allow". استثناها وجود دارند چون فهرست‌ها گاهی چیزهایی را می‌گیرند که یک سایت واقعاً به آن‌ها نیاز دارد، مانند cdn.example، که یک کتابخانهٔ بی‌خطر ارائه می‌دهد.

یک تصور نادرست رایج

«قواعد بیشتر یعنی یک مسدودکنندهٔ کندتر.» با یک نمایهٔ خوب، نه: جست‌وجوی یک میزبان در یک dict با 50 قاعده یا 50,000 تقریباً همان هزینه را دارد. چیزی که یک مسدودکننده را کند می‌کند بررسی یکی‌یکی قواعد است.

امتحان کنید پس از قبولی، decide را طوری تغییر دهید که روی همهٔ قواعد فهرست حلقه بزند (بدون نمایه) و آزمون‌ها را دوباره اجرا کنید. آزمون بودجه با شمارشی حدود 5,000 شکست می‌خورد. آن عدد کاری است که نمایهٔ شما در هر درخواست هر صفحه صرفه‌جویی می‌کند.

در زبان‌های دیگر

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
}

خلاصه

  • الگوهای نویسهٔ عام: در * جدا کنید و تکه‌ها را به ترتیب پیدا کنید.
  • قواعد دامنه با میزبان یا هر زیردامنه‌ای جور می‌شوند، برچسب به برچسب مقایسه‌شده.
  • یک نمایه (یک dict بر اساس میزبان) یعنی چند جست‌وجو به‌جای هزاران بررسی.
  • یک استثنای جورشده همیشه بر یک قاعدهٔ مسدودسازی برنده است.
نوبت شما

چهار تابع بنویسید. wildcard_in(pattern, text): True وقتی تکه‌های pattern میان علامت‌های * همه به ترتیب در text ظاهر شوند. rule_matches(rule, url, third_party): True وقتی یک dict قاعده (از درس قبل) با درخواست جور شود. build_index(rules): قواعد را به هر شکلی که دوست دارید سازمان دهید تا decide بتواند از بیشترشان بگذرد. decide(index, url, third_party): "block" یا "allow" را برگردانید، با برنده‌بودن هر استثنای جورشده، و وقتی 5,000 قاعده بارگذاری شده حداکثر 20 بار در هر درخواست rule_matches را فرا بخوانید.

مشکلی در این درس دیدید؟ گزارشش کنید · دربارهٔ این درس بپرسید

این تمرین به‌زودی باز می‌شود

درس پیش از آن را تمام کنید تا این یکی باز شود. کل دوره رایگان است، حساب کاربری لازم نیست، و می‌توانید همین الان این درس را بخوانید.