web search done right
// Stract is an open source web search engine.
// Copyright (C) 2024 Stract ApS
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program. If not, see <https://www.gnu.org/licenses/>.
use chrono::Utc;
use itertools::Itertools;
use std::path::Path;
use std::sync::{Arc, Mutex};
use tracing::debug;
pub use super::indexable_webpage::IndexableWebpage;
pub use super::job::{Job, JobSettings};
use crate::backlink_grouper::BacklinkGrouper;
use crate::config::{GossipConfig, IndexerConfig, IndexerDualEncoderConfig};
use crate::distributed::cluster::Cluster;
use crate::models::dual_encoder::DualEncoder as DualEncoderModel;
use crate::webgraph::remote::RemoteWebgraph;
use crate::Result;
use crate::index::Index;
use crate::rake::RakeModel;
use crate::ranking::SignalComputer;
use crate::webgraph::{self, EdgeLimit, Node, NodeID, SmallEdgeWithLabel};
use crate::webpage::{safety_classifier, Html, Webpage};
const MAX_BACKLINKS: EdgeLimit = EdgeLimit::Limit(1024);
#[derive(Clone)]
pub enum IndexerGraphConfig {
Local { path: String },
Remote { gossip: GossipConfig },
Existing { cluster: Arc<Cluster> },
}
impl From<crate::config::IndexerGraphConfig> for IndexerGraphConfig {
fn from(conf: crate::config::IndexerGraphConfig) -> Self {
match conf {
crate::config::IndexerGraphConfig::Local { path } => IndexerGraphConfig::Local { path },
crate::config::IndexerGraphConfig::Remote { gossip } => {
IndexerGraphConfig::Remote { gossip }
}
}
}
}
#[derive(Clone)]
pub struct Config {
pub host_centrality_store_path: String,
pub page_centrality_store_path: Option<String>,
pub page_webgraph: Option<IndexerGraphConfig>,
pub safety_classifier_path: Option<String>,
pub dual_encoder: Option<IndexerDualEncoderConfig>,
}
impl From<IndexerConfig> for Config {
fn from(config: IndexerConfig) -> Self {
Self {
host_centrality_store_path: config.host_centrality_store_path,
page_centrality_store_path: config.page_centrality_store_path,
page_webgraph: config.page_webgraph.map(IndexerGraphConfig::from),
safety_classifier_path: config.safety_classifier_path,
dual_encoder: config.dual_encoder,
}
}
}
struct DualEncoder {
model: DualEncoderModel,
page_centrality_rank_threshold: Option<u64>,
}
pub(super) enum Webgraph {
Remote(RemoteWebgraph),
Local(webgraph::Webgraph),
}
impl Webgraph {
async fn batch_raw_ingoing_edges_with_labels(
&self,
ids: Vec<NodeID>,
limit: EdgeLimit,
) -> Vec<Vec<SmallEdgeWithLabel>> {
let edges = match self {
Self::Remote(webgraph) => webgraph
.batch_search(
ids.into_iter()
.map(|id| {
webgraph::query::BacklinksWithLabelsQuery::new(id).with_limit(limit)
})
.collect(),
)
.await
.unwrap_or_default(),
Self::Local(webgraph) => {
let mut res = Vec::new();
for id in ids {
res.push(
webgraph
.search(
&webgraph::query::BacklinksWithLabelsQuery::new(id)
.with_limit(limit),
)
.unwrap_or_default(),
);
}
res
}
};
edges
.into_iter()
.map(|edges| {
edges
.into_iter()
.filter(|e| !e.label.is_empty())
.filter(|e| {
let label = e.label.to_lowercase();
let stopwords = [
"click",
"click here",
"here",
"link",
"website",
"webpage",
"page",
"site",
"url",
"web",
"visit",
"more",
"info",
"information",
"read",
"read more",
];
!stopwords.contains(&label.as_str())
})
.collect::<Vec<_>>()
})
.collect()
}
}
impl Webgraph {
async fn new(config: &IndexerGraphConfig) -> Self {
match config {
IndexerGraphConfig::Local { path } => Self::Local(
webgraph::WebgraphBuilder::new(path, 0u64.into())
.open()
.expect("webgraph should open"),
),
IndexerGraphConfig::Remote { gossip } => {
let cluster = crate::start_gossip_cluster_thread(gossip.clone(), None);
let remote = RemoteWebgraph::new(cluster).await;
#[cfg(not(feature = "dev"))]
{
remote.await_ready().await;
}
Self::Remote(remote)
}
IndexerGraphConfig::Existing { cluster } => {
let remote = RemoteWebgraph::new(cluster.clone()).await;
#[cfg(not(feature = "dev"))]
{
remote.await_ready().await;
}
Self::Remote(remote)
}
}
}
}
pub struct IndexingWorker {
host_centrality_store: speedy_kv::Db<NodeID, f64>,
host_centrality_rank_store: speedy_kv::Db<NodeID, u64>,
page_centrality_store: Option<speedy_kv::Db<NodeID, f64>>,
page_centrality_rank_store: Option<speedy_kv::Db<NodeID, u64>>,
page_webgraph: Option<Webgraph>,
safety_classifier: Option<safety_classifier::Model>,
job_settings: Option<JobSettings>,
rake: RakeModel,
dual_encoder: Option<DualEncoder>,
seen_urls: Mutex<bloom::BytesBloomFilter<String>>,
}
impl IndexingWorker {
pub async fn new(config: Config) -> Self {
let host_centrality_rank_store = speedy_kv::Db::open_or_create(
Path::new(&config.host_centrality_store_path).join("harmonic_rank"),
)
.unwrap();
Self {
host_centrality_store: speedy_kv::Db::open_or_create(
Path::new(&config.host_centrality_store_path).join("harmonic"),
)
.unwrap(),
host_centrality_rank_store,
page_centrality_store: config
.page_centrality_store_path
.as_ref()
.map(|p| speedy_kv::Db::open_or_create(Path::new(&p).join("harmonic")).unwrap()),
page_centrality_rank_store: config.page_centrality_store_path.as_ref().map(|p| {
speedy_kv::Db::open_or_create(Path::new(&p).join("harmonic_rank")).unwrap()
}),
page_webgraph: match config.page_webgraph.as_ref() {
Some(graph) => Some(Webgraph::new(graph).await),
None => None,
},
safety_classifier: config
.safety_classifier_path
.as_ref()
.map(|path| safety_classifier::Model::open(path).unwrap()),
job_settings: None,
rake: RakeModel::default(),
dual_encoder: config.dual_encoder.as_ref().map(|dual_encoder| {
let model =
DualEncoderModel::open(&dual_encoder.model_path).unwrap_or_else(|err| {
panic!("failed to open dual encoder model: {}", err);
});
DualEncoder {
model,
page_centrality_rank_threshold: dual_encoder.page_centrality_rank_threshold,
}
}),
seen_urls: Mutex::new(bloom::BytesBloomFilter::new(10_000_000_000, 0.05)),
}
}
pub(super) fn page_centrality_store(&self) -> Option<&speedy_kv::Db<NodeID, f64>> {
self.page_centrality_store.as_ref()
}
pub(super) fn page_webgraph(&self) -> Option<&Webgraph> {
self.page_webgraph.as_ref()
}
/// Returns false if the URL has not been seen before and marks it as seen.
/// Returns true if the URL has been seen before.
pub(super) fn see(&self, url: &String) -> bool {
let mut seen_urls = self.seen_urls.lock().unwrap();
if seen_urls.contains(url) {
true
} else {
seen_urls.insert(url);
false
}
}
pub fn process(&mut self, job: &Job) -> Index {
job.process(self)
}
pub fn set_job_settings(&mut self, job_settings: JobSettings) {
self.job_settings = Some(job_settings);
}
fn prepare(&self, page: &IndexableWebpage) -> Result<Webpage> {
let html = match Html::parse_without_text(&page.body, &page.url) {
Ok(html) => html,
Err(err) => {
return Err(anyhow::anyhow!("error parsing html: {:?}", err));
}
};
if html.is_no_index() {
return Err(anyhow::anyhow!("noindex"));
}
let title = html.title().unwrap_or_default();
if title.is_empty() || title.chars().all(|c| c.is_whitespace()) {
return Err(anyhow::anyhow!("empty title"));
}
Ok(Webpage::from(html))
}
fn set_host_centrality(&self, page: &mut Webpage) -> Result<()> {
let node = Node::from(page.html.url());
let host_node_id = node.clone().into_host().id();
let host_centrality = self
.host_centrality_store
.get(&host_node_id)
.unwrap()
.unwrap_or_default();
let host_centrality_rank = self
.host_centrality_rank_store
.get(&host_node_id)
.unwrap()
.unwrap_or(u64::MAX);
if let Some(host_centrality_threshold) =
self.job_settings.and_then(|s| s.host_centrality_threshold)
{
if host_centrality < host_centrality_threshold {
return Err(anyhow::anyhow!("low host_centrality value"));
}
}
page.node_id = Some(host_node_id);
page.host_centrality = host_centrality;
page.host_centrality_rank = host_centrality_rank;
if !page.host_centrality.is_finite() {
page.host_centrality = 0.0;
}
self.parse_text(page)?;
Ok(())
}
fn parse_text(&self, page: &mut Webpage) -> Result<()> {
page.html.parse_text();
if page.html.empty_all_text() {
return Err(anyhow::anyhow!("empty all text"));
}
if let Some(minimum_clean_words) = self.job_settings.and_then(|s| s.minimum_clean_words) {
match page.html.clean_text() {
Some(clean_text) => {
if clean_text.split_whitespace().count() < minimum_clean_words {
return Err(anyhow::anyhow!("too few clean words"));
}
}
None => {
return Err(anyhow::anyhow!("no clean text"));
}
}
}
Ok(())
}
fn set_page_centralities(&self, page: &mut Webpage) {
let node = Node::from(page.html.url());
if let Some(store) = self.page_centrality_store.as_ref() {
let node_id = node.id();
page.page_centrality = store.get(&node_id).unwrap().unwrap_or_default();
}
page.page_centrality_rank = u64::MAX;
if let Some(store) = self.page_centrality_rank_store.as_ref() {
let node_id = node.id();
page.page_centrality_rank = store.get(&node_id).unwrap().unwrap_or(u64::MAX);
}
if !page.page_centrality.is_finite() {
page.page_centrality = 0.0;
}
}
fn set_keywords(&self, page: &mut Webpage) {
page.keywords = page.html.keywords(&self.rake);
}
fn set_safety_classification(&self, page: &mut Webpage) {
if let Some(model) = self.safety_classifier.as_ref() {
page.safety_classification = Some(model.predict(page).label);
}
}
pub fn set_title_embeddings(&self, pages: &mut [Webpage]) {
if let Some(dual_encoder) = self.dual_encoder.as_ref() {
let (page_indexes, titles): (Vec<_>, Vec<_>) = pages
.iter()
.enumerate()
.filter(|(_, w)| {
dual_encoder
.page_centrality_rank_threshold
.map(|thresh| w.page_centrality_rank <= thresh)
.unwrap_or(true)
})
.map(|(i, w)| (i, w.html.title().unwrap_or_default()))
.unzip();
let title_emb = dual_encoder
.model
.embed(&titles)
.ok()
.and_then(|t| t.to_dtype(candle_core::DType::BF16).ok());
if let Some(title_emb) = title_emb {
for (i, page_index) in page_indexes.into_iter().enumerate() {
if let Ok(emb) = title_emb.get(i) {
pages[page_index].title_embedding = Some(emb);
}
}
}
}
}
pub async fn set_backlinks(&self, pages: &mut [Webpage]) {
if let Some(graph) = self.page_webgraph() {
let ids = pages
.iter()
.map(|w| Node::from(w.html.url()).id())
.collect::<Vec<_>>();
let backlinks = graph
.batch_raw_ingoing_edges_with_labels(ids, MAX_BACKLINKS)
.await;
for (page, backlinks) in pages.iter_mut().zip_eq(backlinks) {
page.set_backlinks(backlinks.clone());
let mut grouper =
BacklinkGrouper::new(self.host_centrality_rank_store.len() as u64);
for backlink in backlinks {
let from = self
.host_centrality_rank_store
.get(&backlink.from)
.unwrap()
.unwrap_or(u64::MAX);
grouper.add(backlink, from);
}
page.set_grouped_backlinks(grouper.groups())
}
}
}
pub fn set_keyword_embeddings(&self, pages: &mut [Webpage]) {
if let Some(dual_encoder) = self.dual_encoder.as_ref() {
let (page_indexes, keywords): (Vec<_>, Vec<_>) = pages
.iter()
.enumerate()
.filter(|(_, w)| {
dual_encoder
.page_centrality_rank_threshold
.map(|thresh| w.page_centrality_rank <= thresh)
.unwrap_or(true)
})
.map(|(i, w)| (i, w.keywords.join("\n")))
.unzip();
let keyword_emb = dual_encoder
.model
.embed(&keywords)
.ok()
.and_then(|t| t.to_dtype(candle_core::DType::BF16).ok());
if let Some(keyword_emb) = keyword_emb {
for (i, page_index) in page_indexes.into_iter().enumerate() {
if let Ok(emb) = keyword_emb.get(i) {
pages[page_index].keyword_embedding = Some(emb);
}
}
}
}
}
pub async fn prepare_webpages(&self, batch: &[IndexableWebpage]) -> Vec<Webpage> {
let mut res = Vec::with_capacity(batch.len());
let mut signal_computer = SignalComputer::new(None);
for page in batch {
let mut webpage = match self.prepare(page) {
Ok(html) => html,
Err(err) => {
debug!("skipping webpage: {}", err);
continue;
}
};
if let Err(e) = self.set_host_centrality(&mut webpage) {
debug!("skipping webpage: {}", e);
continue;
}
self.set_page_centralities(&mut webpage);
self.set_keywords(&mut webpage);
self.set_safety_classification(&mut webpage);
signal_computer.set_current_timestamp(Utc::now().timestamp().max(0) as usize);
webpage.pre_computed_score = signal_computer.precompute_score(&webpage);
res.push(webpage);
}
self.set_title_embeddings(&mut res);
self.set_keyword_embeddings(&mut res);
self.set_backlinks(&mut res).await;
res
}
}
#[cfg(test)]
mod tests {
use file_store::temp::TempDir;
use crate::config::WarcSource;
use super::*;
fn setup_worker(data_path: &Path, threshold: Option<u64>) -> (IndexingWorker, TempDir) {
let temp_dir = TempDir::new().unwrap();
let worker = crate::block_on(IndexingWorker::new(
IndexerConfig {
host_centrality_store_path: temp_dir
.as_ref()
.join("host_centrality")
.to_str()
.unwrap()
.to_string(),
page_centrality_store_path: None,
page_webgraph: None,
safety_classifier_path: None,
dual_encoder: Some(IndexerDualEncoderConfig {
model_path: data_path.to_str().unwrap().to_string(),
page_centrality_rank_threshold: threshold,
}),
output_path: temp_dir
.as_ref()
.join("output")
.to_str()
.unwrap()
.to_string(),
limit_warc_files: None,
skip_warc_files: None,
warc_source: WarcSource::Local(crate::config::LocalConfig {
folder: temp_dir.as_ref().join("warc").to_str().unwrap().to_string(),
names: vec!["".to_string()],
}),
host_centrality_threshold: None,
minimum_clean_words: None,
batch_size: 10,
autocommit_after_num_inserts:
crate::config::defaults::Indexing::autocommit_after_num_inserts(),
}
.into(),
));
(worker, temp_dir)
}
#[test]
fn title_embeddings() {
let data_path = Path::new("../../data/summarizer/dual_encoder");
if !data_path.exists() {
// Skip the test if the test data is not available
return;
}
let (worker, _temp_dir) = setup_worker(data_path, None);
let webpages = vec![
IndexableWebpage {
url: "https://a.com".to_string(),
body: "<html><head><title>Homemade Heart Brownie Recipe</title></head><body>Example</body></html>"
.to_string(),
fetch_time_ms: 0,
},
IndexableWebpage {
url: "https://b.com".to_string(),
body: "<html><head><title>How To Use an iMac as a Monitor for a PC</title></head><body>Example</body></html>"
.to_string(),
fetch_time_ms: 0,
},
];
let webpages = crate::block_on(worker.prepare_webpages(&webpages));
assert_eq!(webpages.len(), 2);
assert_eq!(
webpages[0].html.title(),
Some("Homemade Heart Brownie Recipe".to_string())
);
assert_eq!(
webpages[1].html.title(),
Some("How To Use an iMac as a Monitor for a PC".to_string())
);
assert!(webpages.iter().all(|w| w.title_embedding.is_some()));
let emb1 = webpages[0].title_embedding.as_ref().unwrap();
let emb2 = webpages[1].title_embedding.as_ref().unwrap();
let query = "best chocolate cake";
let query_emb = worker
.dual_encoder
.as_ref()
.unwrap()
.model
.embed(&[query.to_string()])
.unwrap()
.to_dtype(candle_core::DType::F16)
.unwrap()
.get(0)
.unwrap();
let sim1: f32 = query_emb
.unsqueeze(0)
.unwrap()
.matmul(
&emb1
.to_dtype(candle_core::DType::F16)
.unwrap()
.unsqueeze(0)
.unwrap()
.t()
.unwrap(),
)
.unwrap()
.get(0)
.unwrap()
.squeeze(0)
.unwrap()
.to_dtype(candle_core::DType::F32)
.unwrap()
.to_vec0()
.unwrap();
let sim2: f32 = query_emb
.unsqueeze(0)
.unwrap()
.matmul(
&emb2
.to_dtype(candle_core::DType::F16)
.unwrap()
.unsqueeze(0)
.unwrap()
.t()
.unwrap(),
)
.unwrap()
.get(0)
.unwrap()
.squeeze(0)
.unwrap()
.to_dtype(candle_core::DType::F32)
.unwrap()
.to_vec0()
.unwrap();
assert!(sim1 > sim2);
}
#[test]
fn title_embedding_ranks() {
let data_path = Path::new("../../data/summarizer/dual_encoder");
if !data_path.exists() {
// Skip the test if the test data is not available
return;
}
let (worker, _temp_dir) = setup_worker(data_path, Some(100_000));
let mut a = Webpage::test_parse("<html><head><title>Homemade Heart Brownie Recipe</title></head><body>Example</body></html>", "https://a.com").unwrap();
a.page_centrality_rank = 1;
let mut b = Webpage::test_parse("<html><head><title>How To Use an iMac as a Monitor for a PC</title></head><body>Example</body></html>", "https://b.com").unwrap();
b.page_centrality_rank = 1_000_000;
let mut webpages = vec![a, b];
worker.set_title_embeddings(&mut webpages);
assert_eq!(webpages.len(), 2);
assert_eq!(
webpages[0].html.title(),
Some("Homemade Heart Brownie Recipe".to_string())
);
assert!(webpages[0].title_embedding.is_some());
assert!(webpages[1].title_embedding.is_none());
let mut a = Webpage::test_parse("<html><head><title>Homemade Heart Brownie Recipe</title></head><body>Example</body></html>", "https://a.com").unwrap();
a.page_centrality_rank = 1_000_000;
let mut b = Webpage::test_parse("<html><head><title>How To Use an iMac as a Monitor for a PC</title></head><body>Example</body></html>", "https://b.com").unwrap();
b.page_centrality_rank = 1;
let mut webpages = vec![a, b];
worker.set_title_embeddings(&mut webpages);
assert_eq!(webpages.len(), 2);
assert_eq!(
webpages[0].html.title(),
Some("Homemade Heart Brownie Recipe".to_string())
);
assert!(webpages[0].title_embedding.is_none());
assert!(webpages[1].title_embedding.is_some());
}
}