Fun writing a search engine


Introduction


My interesting project for this quarter was writing a search engine to index blog entries. The experience to do something like this without knowing anything about resources required would probably be risky and stupid. But since this was just an educational project to undertand search technology and to learn java, capacity planning was last thing on my mind.

Based on the resource I had, it was pretty clear to me that I can't build another yahoo or google. Besides who needs another one of those anyway. Also when I started working on this project, google hadn't released thier blog search engine. Needless to say indexing blogs looked pretty interesting. How difficult could it be to build another Technorati anyway ? A few servers running a crawler and a few database servers is all one needs with a nice front end written in pretty php.


Crawling


If search engine was all just about searching a text from a database, then it would be called a database. To build a search engine one needs to solve a few other parts of the puzzle. One of them was the "crawler". If I had done my homework before I started off, I would have found out that there are quite a few crawlers already available for free.

A crawler's job is to crawl around on the internet looking for new URLs, which in this case needs to be RSS/Atom feeds. A unintelligent bot would probably go around in no particular order following new links. The crawler I wrote had a few optimizations which helped it collect a massive amount of URLs very quickly.

  • Supply with very rich seed urls

  • Allow feeds to be harnessed for new sources of feeds

  • Check sites like weblogs.com for new URLs periodically

  • Looking for words like 'rss' or 'atom' in URL and excluding those with 'gif' and 'jpg' would help identify the type of object without downloading it

  • One more thing which I should have done, but didn't was to use the HEAD command to get content type before downloading the complete URL.

  • When a URL is downloaded, it is parsed to look for more href links to other URLs.




Identifying feeds


Writing crawler is simple because there are only as many HTTP versions. RSS is another story. Everyone and their friends are coming out with thier own RSS extentions. Rome is how I got away with it. These guys are going a long way to build a generic RSS reader, and they make it a lot easier to add your own modules to it to read new add-ons.

Unfortunately one thing which I haven't investigated enough is the differences in various feed formats. Rome makes it so transparent that I didn't have to do too much of digging to accept the different formats. However, since it doesn't make sence to crawl multiple feeds(different formats) of the same site, I'll have to do this exercise at some point to figure out which feed format is better for indexing purposes.

As I said before, Rome, allows developers to add their own modules into Rome to support reading of non-standard (or newer) xml tags which are not supported by Rome by default. Form example I noticed some feeds had two versions of 'description', one was longer than the other. When I noticed that Rome was picking the wrong one, I wrote a module to extract the longer description. Similarly I also wrote an iTunes content extracter which helped Rome to understand iTunes content in Feeds.


Spam blogs


There have been studies done on the internet by various organizations and they have all concluded that we live in a very polluted blogging world , where people have been using blogs to skew search engine results.

Weblogs is a good place to see these spam logs in action. Some of the interesting patterns which I used to reduce the effect of spam were

  • Ignore blogs which publish large number of items at a time. Except some new websites most blogs are published one at a time over a long period of time

  • I noticed that spam bloggers are very uncreative when it comes to finding a name for the blog. Most of them have a - in the blog name or blog domain name. Skipping such domains helped a lot in reducing spam.

  • Free blog services are the largest source of spam blogs. Blogspot turned out to be the most annoying one when I analysed this problem

  • If I had some kind of language or pharse analyser, its possible that most of the items in the same feed would look very similar to each other. I didn't have time to do this, but I'm sure one of you guys would do it eventually




Other notes


This writeup is a work in progress.... here are some more notes which I still have to write about

  • You need to know databases very very very well to understand how to optimize searches

  • Mysql is good, but few critical features which it doesn't have could improve your search engine a lot

  • Java is expensive... c/c++ would be better. But Java is very easy to develop in. Google started by using python... so in short its possible

  • There is a lot of crap out there...

  • Its possible that 60 to 70% of the blogs pinging weblogs.com are spam

  • You better be ready to handle UTF8. I learnt it the hard way

  • And even if things are in latin script, not everything is in english

  • If you are planning to index blogs, make sure u understand the languages...

  • But even if you do understand the languages... you should look at all the new words these teens come up with. I swear I didn't recogonize half of them as english untill I really tried hard to understand them. I thought 3l33t was cool... but these are are way ahead

  • Distributed computing is the way to go. One computer itself can't do much

  • Make sure you have plans for scaling ready at hand. You have no idea how fast these things grow.

  • And when you start doing so many HTTP queries, weird things happen on the network. On mine, the router required a reset once every day. I'd never heard of this before... and when I called in to complain about this one year old product, even customer support hadn't heard about it


Comments

Post a Comment

Popular posts from this blog

Creating your first chrome app on a Chromebook

Image
Doing development on Chromebook usually means developing online. There are a lot of sites around for that. But with the APIs getting more mature, its just a matter of time before someone builds a kick-ass IDE which runs natively on Chromebooks without network connectivity. One such tool which I've been exploring for a last few weeks is from Google and called " Chrome Dev Editor " If you have never built and run a chrome app or extension, I'll show you how to do this in 3 easy steps.     Step 1 Launch the app and click on the "+" button to add a new project. Pick a project name and select "JavaScript Chrome App" in the drop down menu.       Step 2 Notice how it automatically adds the minimum code required for it to run. This will be the template you are going to work with. You are almost done, but lets review the files in there to understand why they are there.   manifest.json - This is the most important file. Modify the app name, version number
Read more

Brewers CAP Theorem on distributed systems

Image
Large distributed systems run into a problem which smaller systems don’t usually have to worry about. “ Brewers CAP Theorem ” [ Ref 1 ] [ Ref 2 ] [ Ref 3 ]  defines this problem in a very simple way. It states, that though its desirable to have Consistency, High-Availability and Partition-tolerance in every system, unfortunately no system can achieve all three at the same time . C onsistent : A fully Consistent system is one where the system can guarantee that once you store a state (lets say “x=y”) in the system, it will report the same state in every subsequent operation until the state is explicitly changed by something outside the system. [ Example 1 ] A single MySQL database instance is automatically fully consistent since there is only one node keeping the state. [ Example 2 ] If two MySQL servers are involved, and if the system is designed in such a way that all keys starting “a” to “m” is kept on server 1, and keys “n” to “z” are kept on server
Read more

The pain of Load balancing applications

Introduction Loadbalancing may mean many different things to different people but its all about distributing load. For me its an architecture of how some network services can be scaled by adding multiple servers performing the same tasks. If you had a popular website with static content, and if your server couldn't keep up with the request, all you had to do was setup multiple web servers and use round-robin DNS entries to divide the load into multiple servers. For dynamic web applications like search engines this plays a significant role because the number of users per node can support is much lower. Over time, as applications grew more complex and as web companies found customers outside US they found out the hardware that the only way to optimize network performance was by going local. Loadbalancing POP (points of presence) around the world provide a snappy user experience which has been important and drawing more customers. While, static content on web servers can easily be rep
Read more