Программа курса Урок 47 из 156 · Создайте блокировщик
Создайте блокировщик

Сверяйте запросы с правилами

Почему это важно Блокировщик проверяет каждый запрос страницы, часто более сотни на страницу, на десятки тысяч правил. Если эта проверка медленная, каждая страница кажется медленной, и люди отключают блокировщик. Быстрота и правильность делают защиту удобной.

Две задачи: правильный ответ, быстро

Представьте библиотеку с 5,000 книг. Чтобы найти одну, вы бы не читал каждый корешок с первой полки. Вы идете в нужный раздел, затем на нужную полку. Блокер должен делать то же самое: сразу переходить к тем нескольким правилам, которые could могут подойти, и проверять только их.

Это упражнение оценивается по обоим параметрам. Тесты считают, сколько раз ваш decide вызывает rule_matches для одного запроса, а бюджет составляет 20 checks с загруженными 5,000 правилами. Мы считаем проверки вместо того, чтобы измерять время, поэтому медленный телефон и быстрый ноутбук оцениваются одинаково.

Шаг 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, если его там нет. Заметьте, что в списках фильтров ? и . являются обычными символами, поэтому не используйте регулярное выражение или fnmatch, которые считают их специальными.

Шаг 2: одно правило против одного запроса

rule_matches(rule, url, third_party) отвечает да или нет для одного правила:

    Правило
  • A с установкой third_party никогда не совпадает с запросом первой стороны.
  • Правило домена
  • A adco.example соответствует хосту adco.example или любому хосту, заканчивающемуся на .adco.example. Точка имеет значение: notadco.example это кто-то другой.
  • Правило
  • A совпадает, когда wildcard_in(value, url.lower()) истинно.

Шаг 3: индекс, поэтому вы проверяете только несколько правил

Index: структура, созданная один раз, которая позволяет находить вещи без поиска по всему, как индекс в конце книги. Здесь: словарь из имени хоста в правила для этого хоста.

A Python dict находит ключ за один шаг, сколько бы ключей в нем ни было. Так что создайте один раз:

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, который служит безобидной библиотеке.

A распространенное заблуждение

"Больше правил означает более медленный блокировщик." С хорошим индексом нет: поиск хоста в dict стоит примерно столько же при 50 правилах или 50,000. Что замедляет блокировщик, так это проверка правил по одному.

Попробуйте После прохождения измените decide на loop по каждому правилу в list (без индекса) и запустите тесты снова. Тест на Budget не проходит с количеством около 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
}

Итог

  • Wildcard patterns: разделяйте по * и находите части по порядку.
  • Правила домена соответствуют хосту или любому поддомену, сравниваются метка за меткой.
  • Индекс (словарь по хосту) означает несколько поисков вместо тысяч проверок.
  • A исключение соответствия всегда важнее правила блока.
Твоя очередь

Напишите четыре функции. 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", где любое подходящее исключение побеждает, вызывая rule_matches максимум 20 раз на запрос, когда загружено 5,000 правил.

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.