So, I've been quiet lately. That's because I got distracted from the
distraction from the distraction and churned out another project real
quick that I got exited about. I've been messing about with usenet of
late and found that there really isn't a lot of good search engines
for it out there. The ones that _are_ out there that don't completely
suck usually cost money to access. Which got me into this rabbit hole
of looking at usenet indexers, and trying to figure out how to index
the usenet myself.
▁▃▄▅▆▇▀█▀▜▍▀█▀▇▆▅▄▃▁
Usenet uses the NNTP protocol▁▃▆██▄▃▃▊▄▄▙ ▕▎ ▟▄▄▜▃▃▄██▆▃▁
and, like gopher, NNTP is ▃▆▀▔▘▗▀ ▗▘ ▋ ▕▎ ▚ ▝▖ ▀▖▝▔▀▆▃
a pretty simple, plain ▄█▛▗▝▘▆▀▘▕▛▔▔▐▎▔▔▔▎▔▔▝▍▔▔▜▎▝▀▆▝▘▖▜█▄
text, human-readable ▄▛▔▘▗▘ ▗▘ ▁▞▁▁▁▟▂▂▂▂▂▂▂▂▙▁▁▁▚▁ ▝▖ ▝▖▝▔▜▄
protocol. So writing ▟▊▞▀▆▀▀▜▀▔▔▐▔▔▔▔▋▔▔▔▕▎▔▔▔▐▔▔▔▔▍▔▔▀▛▀▀▆▀▚▐▙
a client is not all ▗▜▘▞ ▕▘ ▞ ▞ ▕▌ ▕▎ ▐▏ ▚ ▚ ▝▖ ▚▝▛▖
that difficult. ▗▙▌▟▎ ▞ ▐▀▀▀▕▌ ▐▎ ▕▎ ▝▍ ▐▏▀▀▀▍ ▚ ▕▙▐▟▖
▞▞▕▍ ▗▎ ▞ ▐▎ ▐▏ ▕▎ ▕▌ ▕▍ ▊ ▕▍ ▐▏▚▚
No, the problem ▐_______ _______ _______ _______ _______ _______▎▍
with writing an ▐ | | __| ___| | | ___|_ _|▉
indexer is rather ▐ | |__ | ___| | ___| | |▏▐▐
very much a ▐_______|_______|_______|__|____|_______| |___| ▐▐
problem of scale. ▌▌▕▍ ▕▍ ▐▏ ▊ ▐ ▕▎ ▋ ▊ ▕▍ ▐▏ ▐▏▐▐
▚▂▁▌▁ ▌ ▕▍ ▐ ▐ ▕▎ ▋ ▋ ▗▎ ▐ ▁▐▁▂▉
You see, usenet ▐▕▔▜▔▔▜▔▀▀▋▀▀▀▜▀▀▀▀▜▀▀▀▀▜▛▀▀▀▀▛▀▀▀▀▋▀▀▀▜▀▀▔▛▔▔▛▔▎▍
has a lot of posts.▚▚▕▍ ▝▎ ▚ ▐▎ ▐▏ ▕▎ ▕▌ ▕▍ ▊ ▕▍ ▐▏▞▞
Nearly 500 billion ▝▛▛▜▎ ▚▅▄▟▄▄▗▄▙▃▃▃▟▃▃▃▃▃▎▃▃▃▃▍▃▃▃▟▄▖▄▄▙▄▅▞ ▕▛▜▜▘
at this time, with ▝▟▖▚ ▕▖ ▚ ▚ ▕▌ ▕▎ ▐▏ ▞ ▞ ▗▘ ▞▗▙▘
another 171 million ▜▅▚▖▟▃▂▂▖▁▁▐▁▁ ▋ ▕▎ ▐ ▁▁▍▁▁▗▂▂▃▋▗▞▅▛
being added every day. ▀▙▁▖▝▖ ▝▔▔▔▜▔▔▔▜▔▔▔▐▎▔▔▔▛▔▔▔▛▔▔▔▘ ▗▘▗▁▟▀
▀█▆▞▄▖▐▃▂▂▌▂▁▐▎▁▁▁▎▁▁▁▍▁▂▐▂▂▃▊▗▄▚▆█▀
This means you'll have to ▀▜▄▂▃▝▄ ▝▖ ▔▊▔▔▔▎▔▔▞▔ ▗▘ ▄▘▃▂▄▛▀
optimize the crap out of how ▔▀▜█▙▀▇▀▆ ▝▖ ▕▎ ▗▘ ▆▀▇▀▟█▛▀▔
you're storing what you've ▔▀▀▀▇▇▆█▆▁▎▆█▆▇▇▀▀▀▔
indexed, as well as try everything
you can to make it as fast as possible to search through that massive
amount of data. I found this to be a very interesting problem, so I
kept at it. The result is 'UsenetSearch' - yes, very inspiring and
creative name, I know.
link to the code: https://tildegit.org/jns/UsenetSearch
I'll repeat some of the back-story in the readme there below:
"
I got interested in indexing usenet because I was
disappointed with the existing options. There's
horrible things like newznab, nntmux, etc,... all
written in php, and seemingly depend on the
entire body of software ever written by mankind
in the history of the world. I actually tried to
get nntmux running on my bsd server, failed of
course. Why became immediately obvious as soon as
I looked at their code. It's php code, often
shelling out linux-only shell commands. Ugh. I
was so appalled I had to go and write my own
thing. After all, how hard can it be :)
"
( If you are the author of nntmux or newznab I apologize! - It's not
personal ;) -)
Anyway, ok - so how does this thing work... well, probably, for the
most part, I guess it's similar to how most search engines work, but
I will spell it out for those not familar.
The indexer makes a connection to the NNTP server, and requests a
list of all newsgroups. We look for any newsgroups that match the
patterns of newsgroups we care to index. UsenetSearch lets you set
regular expressions for newsgroup names to index, rather than having
to explicitly list specific ones. If none are set, we are indexing
all of usenet (Hope you've got a lot of storage!!)
For every newsgroup,we ask for all subject headers - starting at the
last indexed post. At this time we are only indexing subject headers.
I might support body indexing or storing dates and such in the future
but I'm really trying to get the storage costs down to a minimum here
obviously.
These posts then get split up in batches that are fed into a thread
pool where we start doing the indexing magic in parallel. Time to put
that CPU to work!
Every subject line gets filtered, then tokenized. So, how does
tokenization work you ask? What is it? Well, basically we're trying
to generate every possible search string that would match the subject
line. So this means every possible combination of sequential words.
Ok, here's an example, say you wanted to tokenize the phrase:
" gophers are cute "
The generated tokens would be:
- gophers are cute
- gophers are
- gophers
- are cute
- are
- cute
So you can see, a 3 word sentence generated us 6 tokens. As you can
imagine, this can blow up pretty quickly in size for long pieces of
text. So we also do a bunch of extra token filtering after we do the
initial tokenization. We remove duplicate tokens, some tokens may
just be dropped, for others we may only care to store them if they
are an exact match to the subject. I tried to make all that filtering
configurable via the usenetsearch configuration file, such that the
end-user may make their own tradeoffs in search result quality versus
storage consumption. Another important thing is that we can limit the
recursion depth of the tokenization algorithm. The algorithm itself
basically is just a loop within a loop, where the outer loop removes
a word from the start and the inner loop removes a word from the end
- each time storing a token of the entire string as it goes through.
The actual C++ implementation of this splits the string by whitespace
into a vector of strings, and then makes use of iterators to take
subsets of word tokens. - So instead of: 'removing a word from the
left', you can simply increment the outer iterator, and instead of
'removing a word from the right', you simply decrement the inner
vector iterator.
Anyway, then each token gets hashed. We don't ever actually store the
subjects themselves, just the hashes of the subjects. This is because
a hash is a fixed size. It doesn't matter how long a sentence is, the
hash of the sentence will be a predictable number of bytes. This may
improve storage efficiency when the subjects are longer than the hash
but may also harm it if the subjects are shorter. In reality, usually
they are longer. But much more important than that, storing things
with a predictable size in a file, makes it so you can easily seek to
a specific entry really quickly without having to do a linear search,
because you can calculate where something is going to be by simply
multiplying it's index with the size of an entry. And what's more, we
can very quickly and efficiently search for a hash, because we can
pre-sort them in a tree structure on disk. That way, we don't have to
search through an entire file of billions of hashes every time. This
is especially important because we're building a reverse-index of
hashes. We're not matching some ID to a hash, we're matching some
hash to an (article) id.
So let's take our example string from before, and look at the hashes:
- gophers are cute : 06e50092d57e0db6219c2ca6b80edbe5
- gophers are : 6f9d9543a11e72dc4f0134fd4874a666
- gophers : de96350d92c5eb383a0de9331933a212
- are cute : 7c4860f2c7ac43aab4345a34d190e2e0
- are : 4015e9ce43edfb0668ddaa973ebc7e87
- cute : 02829fb05c3076ec5a6caebd12477dec
So each of these tokens could be stored on the filesystem like:
./06/e5/00/06.db (contains the 06e50092d57e0db6219c2ca6b80edbe5 hash)
./6f/9d/95/6f.db (contains the 6f9d9543a11e72dc4f0134fd4874a666 hash)
etc... - in other words, you can take the first n digits of the hash
and build a super simple tree from them. Since these are hex digits,
the number of files on the filesystem is always tunable and
predictable - you don't want to end up building such a deep structure
that you run out of inodes. Moreover, using such a scheme one could
also distribute individual top-level folders over multiple different
filesystems which could be useful for scalability reasons.
Anyway, that's the rough outlines of how it works. There's of course
a lot more to it. You don't want 2 threads to write to the same file,
so you have to use file locking, but then you also don't want to end
up in a situation where everything always wants to write to the same
token file because then your program will just be waiting for locks
all the time. You also want to do whatever you can to avoid database
corruption should the daemon get killed uncleanly and what not. Right
now I just have a simple fixed header and footer to check for db file
integrity, although I may add a CRC later.
At some point I may re-purpose some of this code and write a gopher
search engine. That would be a fun project too. But it would be a lot
more complicated, since there you'd have to index (potentially long)
bodies of text, account for endless loops, read robots.txt files, and
so on,... so I might not ever get to it. I've also got a bunch of
gopherclients to finish, a gopher server, a game engine, etc etc etc.
Enough drivel for now :) Catch ya on the flip side!