Сверяйте запросы с правилами
Почему это важно Блокировщик проверяет каждый запрос страницы, часто более сотни на страницу, на десятки тысяч правил. Если эта проверка медленная, каждая страница кажется медленной, и люди отключают блокировщик. Быстрота и правильность делают защиту удобной.
Две задачи: правильный ответ, быстро
Представьте библиотеку с 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 -> Falsetext.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 правил.
Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке
Это упражнение откроется скоро
Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.
Этот браузер блокирует cookies для learn.floati.life, поэтому завершенные здесь уроки не могут открыться по порядку. Разрешите cookies для этого сайта и перезагрузите страницу.