-: Well, let me first start by thinking about
a high level algorithmic approach
to how to identify documents relative to a keyword.
The most basic search algorithm I know is TF-IDF
where we take the frequency of a term within a document
and divide it by the frequency of the term
over all of the documents
to get a measure of how "special" that term is
to that document.
Woman: Yep, can you think of any problems
that might present
in the context of searching the entire web?
-: Yeah, at least two come to mind.
One is that this is really easy to game;
so just load up a page with the keyword you want,
and make sure it's a relatively obscure keyword,
and you win.
So, maybe this could be part of the solution
but certainly something more sophisticated is needed.
The other problem is computing the denominator.
Computing document frequency across the entire Internet
seems like an intractable problem,
or at least one that would require so many resources
that we would should question if we really need it.
Woman: Right, so,
let's see what other ideas you can come up with.
-: Well, let me work backwards
from what we need to present to the user.
So ultimately, we need some sort of inverted index
that maps keywords to a list of relevant documents
sorted by some measure of relevance.
So, what might that measure be?
Well, we've all heard of "PageRank",
it's how Google started.
As I recall that's based in part on backlinks;
they were using links to a page
and the anchor text of those links
as measures of a site's popularity.
Coming from academia, they just saw backlinks
as the same thing as citations for research papers,
which is kind of how they measure success
in the academic world.
But I digress.
Let me just start writing down things
we might want to measure
and bake into whatever generates that inverted index.
So, backlinks is one.
What else can I think of?
Obviously the words actually on the page
should count for something,
but there may be other signals
that give us hints on how much to weight those terms.
Like what position within the document it's in;
if it's mentioned right at the beginning,
then it's probably relevant to the page.
Words that appear in bold or in a big font
might also be more important.
The title of the page is a big signal too;
words in the title should count for a lot.
I suppose that's something that could be gamed,
but if the title is what's presented
to user in the search results,
it kind of has to be relevant to the page
if the page owner expects
to get relevant user traffic in return.
The length of the document might also be a signal,
or it may be more generally
how often the term appears in the document.
Hey, that's term frequency;
maybe we can at least keep that part of it.
The idea is to make sure that we don't rank pages
that just have the keyword on it and nothing else.
I think there are meta-tags
people can insert into their HTML
to explicitly tell search engines
what keywords they want to target,
but that seems really prone to gaming,
so I'm not sure we'd really want to use that
in this day and age.
Just thinking out loud, these all look like features
that could ultimately be fed into a neural network
that learns how to rank documents
based on user interaction with search results.
That might play a role later on in the design
but first let's worry about extracting
and storing all of this data at scale.
OK, so we'll start with that repository of web pages
that came from our crawler.
Presumably this is compressed somehow,
so as not to take up ridiculous amounts of storage
or at least less ridiculous amounts of storage.
Now we need to build up an index
that maps keywords found in each page
to the document it was found in,
its position within the document,
and whether it's a header or a title,
and the other signals that we talked about a minute ago.
Basically, this is a big key/value object store
where the keys are keywords, or more compactly keyword ID's.
So, that can be distributed.
I think that's kind of what BigTable was made for at Google,
but any modern NoSQL database should do.
In the end, we want an inverted index
that maps keywords to a ranked list of documents,
so if we can keep that sorted by keyword
as we go somehow that will save us some trouble,
but we could do it later if we had to.
As for the indexer itself,
I think that's why Google invented MapReduce
in order to parallelize the processing of documents
in the web repository.
A more modern alternative today would be Apache Spark,
which is faster
and gives us more flexibility and built-in tools.
Woman: How do we go about
extracting keywords from documents?
Do we just build up a map of every word in the document
and go from there?
-: No, there would be a whole world of complexity
in normalizing those keywords that I skipped over.
We need to deal with capitalization, punctuation,
spacing, synonyms, and stoplists.
That's probably just a start.
We could also build up "N-Grams" of words
that represent phrases potentially.
There's a whole world of search algorithms out there
that frankly, I'm only vaguely aware of,
but at least I know those problems exist
and need to be addressed.
I think generally these challenges are addressed
in the process of building up a forward index
that maps documents to keywords as an intermediate step,
but I'm lumping all that
into this more general "Indexer" box that I drew here.
Woman: OK, so a more traditional approach
would be to split that up into a forward index
and I guess what you're describing
as the beginnings of an inverted index.
But I get that you're just thinking out loud here for now,
so keep going.
-: All right, so the other thing we need to think about
is PageRank, assuming that's still a thing.
So, we need to extract any links to other pages
and store those somewhere,
so we can later build up a mapping of pages
and how many backlinks they have across the entire web.
Those links need to match up with the URLs
we originally crawled,
so the same logic we used to normalize URLs in the crawler
would need to be applied here as backlinks are extracted.
I don't remember all the details of PageRank
but I think it weights each link
by how many other links appear on the page
that it came from;
that provides some defense against link farms
and stuff like that.
Now, we said the anchor text of those backlinks
mattered as well.
We could treat those as just another entry in the index,
where the anchor text is the keyword
and the page it links to in the document.
But ultimately we need a database of links
between two documents, so whatever computes PageRank
can add up all the links to a given document
and later use that as a signal to our search algorithm.
All right, I ran out of space on the whiteboard,
so let me move over here.
At this point the two main pieces we have is a big index
that maps keywords to documents and various signals
of that keyword's relevance to the document.
We also have something computing PageRank
given a database of all the links
between documents on the web,
so now we just need to tie it all together.
That index contains a bunch of rows for each keyword
mapping them to documents
and how they were formatted and positioned
within the document and stuff.
So, something will need to score
all of those relevance signals within the document
into some sort of score that we can later use for ranking.
If the forward index isn't already sorted by keyword,
we'll probably want to do that now,
so we can more quickly figure out
how to rank each document the keyword appeared in.
Actually if we are using Spark,
it might figure out how to optimize that on its own
without us having to explicitly sort things.
So finally, we'll have some sort of ranking stage
that takes each keyword,
the measure of that keyword's relevance
within each document,
and the document's PageRank score
to come up with a final ranking of the documents
for a given keyword.
You could imagine even more features being fed
into the ranking that I haven't imagined yet.
I think this is where the term "learning to rank" came from,
so potentially deep learning could be employed
to learn the best way to combine PageRank,
and features from the documents themselves,
and whatever else we dream up to produce the best rankings.
And although I'm drawing, scoring, sorting,
and ranking all within the same box,
they could be split out into their own stages
if it made sense to scale them independently,
which it probably does.
Finally, we have what's needed
to write out our inverted index.
Our front-end web servers can query that inverted index
to provide search results to our happy searchers
who found what they are looking for.
Woman: All right, this is workable and not too far off
from how Google was originally designed in fact.
They had more complexity
on how to keep the forward index sorted,
but as you pointed out Spark and other modern tools
and databases would manage a lot of that for us today.
You were right to focus on the high-level architecture first
because that's the hard part.
In the minute or so that we have left,
talk more about how you'd scale all of this
to billions and billions of pages and users.
-: Well I talked a little about
using distributed storage and analytics;
originally at Google
that would have been BigTable and MapReduce.
Today the web repository might be a "data lake"
built on cloud storage
and pretty much everything in a rectangle here
would be implemented in Spark or something similar,
which can scale across a cluster as needed.
The other databases would be a NoSQL data store
of some sort that can also be scaled horizontally.
It's possible that some of the operations we're doing
could be consolidated to operate on fewer databases
than I'm showing here conceptually;
maybe there is no intermediate backlinks data store at all
and the normalizer just takes data streaming
from the indexer directly.
Now, given the massive volume of search traffic,
we'd have many front-end servers
distributed across different racks, data centers,
and regions, using DNS tricks to geo-route users
to the closest data center
and load balancers to distribute the load
amongst the servers in each data center.
The inverted index would be cached in Redis or something,
so those servers would have fast access to them locally.
Woman: OK, well very good.
There's a lot more we could talk about
in terms of operations
and keeping this thing working reliably,
but we have to move on.
So, good job!