Showing posts with label distributed search. Show all posts
Showing posts with label distributed search. Show all posts

Sunday, October 12, 2008

Distributed Search Cloud

First let me say a few words about the long hiatus since the last post - the main reason is that a lot happened since then, in particular a lot related to my vision of distributed search :)

I am working on a new startup with a clear mission of advancing distributed search as well as leveraging user inputs as much as possible, but in a massively scalable way.

We have assembled a great core team of really motivated and enthusiastic people and we are also very happy that our investors share our passions for distributed computing and search.

We are still in stealth so I cannot say much about the details yet but I can promise you that pretty soon (within months) you will be able to see what we are up to. In the mean time, feel free to drop me an email at boris-at-edgios-dot-com if you would like to be notified of news, also if you have some comments, ideas and suggestions or are simply interested in a discussion.

In the following posts I will try to shed some light on the state of the art in search, including some perceptions that are not very well grounded in reality :)

Today, let us start with some facts about the scope of computing resources on (hundreds of) millions of user desktops and how these resources relate to the problem of search, which is one of the most complex problems on the Internet today.

Note that the size of the entire Web in terms of storage is not that large - assuming 10kB/page of indexable information, stripped of unnecessary stuff ( HTML formatting etc) , possibly compressed, and using 40B pages (Google index) would result in 400 TB, which is not very much at all. One can fit 400 TB in 100 1U servers fitting in three racks.

Note that such a corpus, together with an accompanying index, would constitute a single search cluster capable of covering the entire Internet but able to serve only dozens or so qps (queries per second). The massive resource increase comes from the need to replicate such a cluster hundreds of times to support query loads of thousands of qps with peaks over 10K (what Google serves).

Note that this replication is not uniform, you will have to replicate popular stuff much more than the rest, and you better be right about the popularity distribution of the queries or else your system will be brought to its knees or if you are really rich, you will have lots of machines sitting there doing nothing.

Problems at Cuil launch were IMHO due to under-provisioning expected query load at launch, both statically (total number of queries) as well as dynamically (not knowing which queries are most popular)

There are several classes of resources available in abundance on user desktops:
  • Bandwidth - with wide adoption of broadband the aggregated bandwidth out there is mind-boggling. For instance, consider crawling,a rough rule of thumb is that one can crawl 1 million pages a day with 1Mbps of bandwidth. That means that a group of, say 100,000 motivated users could theoretically crawl 100 billion pages a day - more than twice the size of Google's index. One might argue that 1Mbps is a lot to ask for crawling, but think how much bandwidth is consumed every night on prime time cable TV hawking the latest (extremely important :) ) entertainment wares (16Mbps+ for digital TV). The rise of YouTube and video on the Internet is also driving rapid increases in bandwidth.
  • RAM - the amount of the aggregate memory is truly staggering. The above group of 100,000 users running an application using 100MB of RAM (not small but also not a big deal these days, thank you MS Vista :) ) would have 10 TB of RAM !! Hint - you can fit a BIIIG index in there :) It is also very handy if you want to make that fresh and incremental ...
  • Disk - assuming 10GB/user, again not a big deal these days when media downloading is ubiquitous, the total storage would be 1000 TB - 1 Petabyte, enough for more than two copies of the entire Web.
  • CPU - 100,000 CPUs and many more cores bring a lot of compute cycles to the table.

So a natural question arises if we could do search effectively with such a cloud, and if so how good could it be?

In short the answer to the first question is YES, and to the second - VERY GOOD. These two answers are, in essence, what my latest startup is about :)

The number 100,000 is chosen simply for illustration, there is nothing special about it. In fact, such a group of users is today not considered very large at all. On the other hand, just try to imagine a cloud with million or ten million users. Its capabilities would be staggering.

Our vision is to build such a cloud and I invite you to join us in this journey.

Saturday, February 24, 2007

Limits of Search

Hello everyone, this blog is intended to be about search and exploring how far it can be pushed. I strongly believe that the ultimate limits of search lie in the distributed approach. I find it fascinating that distributed approach is pretty much neglected and not considered very seriously in modern search. There are, of course, noble exceptions but really only a few.

Since this is my first post on this blog, a little bit about me. My name is Borislav Agapiev and I am the founder of Vast.com, which is an online classifieds search engine in San Francisco. Go check it out if you are in market for a classifieds item or if you simply like browsing ...

I founded the company in 2000 in Portland, Oregon as Omni-Explorer Technologies. I worked on it for several years with my friends and local angel investors from Portland. In 2005 we showed our technology to Naval Ravikant, former founder and CEO of epinions.com. He liked our stuff so he joined the company (as CEO) and helped us close Series A financing and we moved from Portland to SF and the rest is (our) history -:)

Google, of course, these days is the standard of modern search. They truly are a great company and what they have built is pretty amazing.

But the question still remains whether it is even possible for a startup to compete with them. More and more very smart people are starting to say NO. For instance, Bill Burnham, Peter Norvig (Google Head of Research), Louis Monier (former CEO of Altavista, now at Google).

The essence of their argument is that the resources required are too prohibitive. In particular, one needs to have huge resources for :
  • crawling
  • query serving
  • indexing
This argument is of course true, to compete head-on with Google one needs to employ such resources in huge amounts.

I strongly believe the answer to the question is YES, it is possible to build a search engine which will not only be capable of competing with Google, but actually FAR surpassing it.

The trick is always not to compete with the established players on their turf and under their terms but to change both.

The key part of the modern search approach is that it is centralized, in a sense of centralized server farm(s). Within Google, GFS (Google File System) uses a distributed approach in connecting a sea of dumb linux machines by an internal network. The whole system is centralized in a sense that these machines are very tightly coupled through this network.

BTW if you are not familiar with GFS, I strongly urge you to check out GFS paper which is probably the best published account of how Google works.

In the following posts I will try to shed some light on how to build a truly scalable distributed search engine and show that its ultimate limits actually lie far beyond Google (yes, I know it sounds outrageous and out there -: ).

These thoughts are not just concepts and ideas, I am actually working on a new project to show how to do it. We are currently testing alpha and should have something to show pretty soon.

If you are interested or curious about search and its limits, have any comments, thoughts, ideas, musings or whatever feel free to contact me and join us in this journey ...