pagesift_frontier/frontier/
mod.rs

1//! 爬取前沿的质量规则：哪些 URL 是同一页的不同写法，哪些不值得抓，哪些是陷阱。
2//!
3//! - URL 清洗：去掉跟踪参数（utm_*、fbclid、gclid…）和会话 ID（`;jsessionid=`、PHPSESSID…）。
4//!   参数名单取自 courlan 的跟踪参数规则和 Heritrix 的会话 ID 规则，只收确定是跟踪或会话的名字，
5//!   `ref`、`source`、`id` 这类也可能决定页面内容的参数不动。
6//! - 抓取前过滤：图片、音视频、压缩包、字体、脚本样式这类转不成文本的文件；
7//!   同一段路径连续重复三次以上（Heritrix 的 PathologicalPath 规则，典型是坏掉的相对链接
8//!   `more/` 越叠越长）、路径层级过深、URL 过长。
9//! - 按 URL 模板学习陷阱（自研）：把 URL 归成模板（路径里的数字和长 ID 换成占位符，
10//!   查询只留参数名），记下每个模板抓到的页面有多少是重复内容（全文相同，或者只差数字，
11//!   比如日历的"下一月"、翻到头的空列表页、排序筛选的组合）。一个模板抓了几页、大多是重复，
12//!   就把它降级：它的 URL 排到所有正常 URL 之后。只降级不丢弃，正常页面抓完、上限还没到时
13//!   仍然会抓它们；模板后来抓到新内容，比例下降，又会恢复正常。
14//! - URL 改写规则学习（DUST，Bar-Yossef 等 "Do not crawl in the DUST"，以及 Dasgupta 等
15//!   KDD 2008 的 URL 改写规则去重）：两个 URL 的正文完全相同时，比较它们的差别——多了一个查询参数
16//!   （`print=1`），或者路径末尾多了一段（`index.html`、`more/`）——记成候选规则；同一条规则
17//!   被两对不同的页面证实后生效，之后发现的 URL 先按规则改写再去重，同一页的其他写法不再抓。
18//!   参数规则默认只去掉特定的值（`page=1` 和不带参数相同，不代表 `page=2` 也相同）；
19//!   同一个参数名有两种以上取值都被证实，才去掉整个参数。
20
21use std::collections::{HashMap, HashSet, VecDeque};
22
23use url::Url;
24
25mod clean;
26mod learn;
27#[cfg(test)]
28mod tests;
29
30pub use clean::*;
31pub use learn::*;
32
33/// 广度优先的两层队列：模板降级的 URL 排在降级层，正常层空了才出队。
34/// 正常层按主机分队列（同 Heritrix 的每主机 work queue），主机之间轮流出队，跳过在途请求已满的主机
35/// （同 Scrapy 的 DownloaderAwarePriorityQueue），一个主机排得再长也不会挡住其他主机。
36/// 总长度由调用方按爬取上限控制；满了以后新来的正常 URL 可以挤掉降级层最后面的一个。
37#[derive(Default)]
38pub struct Tiered {
39    normal: HashMap<String, VecDeque<(Url, usize, u64)>>,
40    /// 正常层里还有 URL 的主机，轮流出队的顺序
41    ring: VecDeque<String>,
42    normal_len: usize,
43    low: VecDeque<(Url, usize, u64)>,
44    /// 上次把正常层里已降级的 URL 挪走时，学习器的 generation
45    sorted_at: u64,
46}
47
48fn host_of(u: &Url) -> String {
49    u.host_str().unwrap_or_default().to_string()
50}
51
52impl Tiered {
53    pub fn len(&self) -> usize {
54        self.normal_len + self.low.len()
55    }
56
57    pub fn is_empty(&self) -> bool {
58        self.len() == 0
59    }
60
61    pub fn push(&mut self, learner: &Learner, url: Url, depth: usize) {
62        let key = shape_key(&url);
63        if learner.demoted_key(key) {
64            self.low.push_back((url, depth, key));
65            return;
66        }
67        let host = host_of(&url);
68        let q = self.normal.entry(host.clone()).or_default();
69        if q.is_empty() {
70            self.ring.push_back(host);
71        }
72        q.push_back((url, depth, key));
73        self.normal_len += 1;
74    }
75
76    /// 下一个要抓的 URL，第三项表示是否来自降级层。正常层里模板已降级的顺手挪到降级层。
77    /// `busy(host)` 为真的主机这次跳过（在途请求已到上限）。
78    /// `allow_low` 为 false 时只出正常层：还有正常页面在抓或等重试，它们可能发现新的正常链接，
79    /// 这时候抓降级的 URL 会白白占掉上限。
80    pub fn pop(
81        &mut self,
82        learner: &Learner,
83        allow_low: bool,
84        busy: impl Fn(&str) -> bool,
85    ) -> Option<(Url, usize, bool)> {
86        for _ in 0..self.ring.len() {
87            let host = self.ring.pop_front()?;
88            if busy(&host) {
89                self.ring.push_back(host);
90                continue;
91            }
92            let q = self.normal.get_mut(&host).expect("ring hosts have queues");
93            let mut found = None;
94            while let Some(item) = q.pop_front() {
95                self.normal_len -= 1;
96                if learner.demoted_key(item.2) {
97                    self.low.push_back(item);
98                } else {
99                    found = Some((item.0, item.1, false));
100                    break;
101                }
102            }
103            if q.is_empty() {
104                self.normal.remove(&host);
105            } else {
106                self.ring.push_back(host);
107            }
108            if found.is_some() {
109                return found;
110            }
111        }
112        if !allow_low || self.low.front().is_some_and(|i| busy(&host_of(&i.0))) {
113            return None;
114        }
115        self.low.pop_front().map(|(u, d, _)| (u, d, true))
116    }
117
118    /// 队列满了、又来了一个正常 URL：从降级层末尾挤掉一个，返回被挤掉的 URL（调用方从去重表里删掉它，
119    /// 以后还能再进来）。降级层是空的就返回 `None`，新 URL 不入队。
120    pub fn evict_low(&mut self, learner: &Learner) -> Option<Url> {
121        if self.sorted_at != learner.generation {
122            self.sorted_at = learner.generation;
123            for q in self.normal.values_mut() {
124                let before = q.len();
125                let mut keep = VecDeque::with_capacity(before);
126                for item in q.drain(..) {
127                    if learner.demoted_key(item.2) {
128                        self.low.push_back(item);
129                    } else {
130                        keep.push_back(item);
131                    }
132                }
133                self.normal_len -= before - keep.len();
134                *q = keep;
135            }
136            self.normal.retain(|_, q| !q.is_empty());
137            let normal = &self.normal;
138            self.ring.retain(|h| normal.contains_key(h));
139        }
140        self.low.pop_back().map(|(u, _, _)| u)
141    }
142
143    pub fn iter(&self) -> impl Iterator<Item = (&Url, usize)> {
144        self.ring
145            .iter()
146            .flat_map(|h| self.normal[h].iter())
147            .chain(&self.low)
148            .map(|(u, d, _)| (u, *d))
149    }
150}
pagesift_frontier/frontier/mod.rs

pagesift_frontier/frontier/
mod.rs
