Distributed Search Engine Search.minty Dowser Type Engine and Larbin Spider Search.minty.org: Open, Distributed Web Search
Dowser: Dowser is a research tool for the web It clusters results from major search engines, associates words that appear in previous searches, and keeps a local cache of all the results you click on in a searchable database It helps you keep track of.. What you find on the web.
LARBIN: CRAWLER
Open, Distributed Web Searchmurray Walker, Search@minty.org
Consider this an RFC (Request for Comments).
Please add the the wiki
-------------------------------------------------- ------------------------------
AbstractThis article discusses the concepts, goals and ideas for an open source, community-run (distributed) web search service that allows anyone to search, and thus navigate around the internet A key tenet is impartiality and objectivity -. Avoiding bias, corruption and " Spamming "of the service.
...................... ..
IntroductionThe Ability to Find Things on the Internet, And Particularly The World Wide Web, IS OFTEN TAKEN For Grand by The Vast Majority of People Who (Offen Many Times a Day) Are "Searching The Web".
Whilst there is a huge number of tools and technologies available to do this, a tiny handful Dominate the Market:
Google Yahoo Microsoft [1] TheY, Along With Many Other Similar Services, Share a Number of Key Features:
Their algorithms, or rules for deciding which results to display, are "closed" and often tightly guarded secrets. They generate money, selling various forms of advertising around the search results. They are commercial companies whose first priority is to generate value and profit for their shareholders. there are no obligations or requirements for them to be objective, impartial, comprehensive or even accurate. and there is very little anyone can do to measure them against these metrics. Given the power and influence these services have over everyone that uses them , it could be argued there is scope for abuse and at least the possibility for a conflict of interest.Which leads to the idea for an "open" [2] web search service that is free to use - both financially and (more importantly) IN The Sense That It Can Be Used by Anyone, for Any Purpose. This Means That The Technical Code and Information Needed To Run Such A System Are "Open Sourced", But Also That The Service is Provided by TH E Community of Users WITHOUT IMPOSIY Any Restrictions on now service is used.
IT IS Not Known if this IDEA Would Work, or if IT IS SIMPLY A Description of a Hypothetical, Impractical or Impossible Scenario. Hopefully by Reading and Add to the Debate, IT Will Be Possible to Find Out.
The Rest of this Article Discusses Some Issues That Such A Project Might Encounter, And Outlines Very Briefly One Possibly Technical Architecture That Might Be Used To Implement Such A System.
If you would like to Comment, you can do so on the acid wiki.
Assumptions and scpe
This article will discuss only a plain text web search service, including HTML files. This excludes features like image search for the sake of simplicity. Many existing search services, including the "big three" mentioned above, have paid advertisements around the search results. They also all have separate, custom technology for delivering such advertisements [3]. The ability to do, or technology of, "ad serving" is not discussed here. Custom search services, such as searching for books on Amazon or auctions on ebay, are out of scope. A generic web search service must be able to handle unstructured, plain text data. The primary focus is a search service that requires no manual intervention or classification on a site by site, or page by page basis. Namely, once . it is setup and running, it is fully autonomous Advanced features of existing services, such as viewing cached versions of pages, spell checking, etc. are also out of scope.Resources: Bandwidth, Disk space and CPUConsider an index of around 4 billion items, roughly the size of Google's current web index Taking an average of 30Kb per item or url (only looking at the plain text - including html source)., it would take around 111 Terabytes of data being downloaded to consider Each Document Exactly onCE.
Then consider updates, which could range from quarterly or monthly for resources infrequently used or rarely changed, to weekly, daily or even hourly in the case of very popular or highly dynamic sites, such as news sites.
It is not the goal, at least initially, to store complete copies of everything downloaded. Thus, if a 30Kb item could be reduced to 300 bytes of information, disk space requirements would be around 1000 Gigabytes. It is also possible that in order to produce fast results when a query is run, it would require storing more than 30Kb per item. If it was a ten fold increase, it would put disk storage requirements at close to 1 Petabyte.CPU or raw processing power is even harder to predict, but it breaks down into two distinct areas. There is the task of crawling or indexing pages. This can be done "offline" or in a batch approach. For the sake of argument, if a typical 2Ghz Pentium 4 (r) computer could process 100 urls per second, that computer could do just over 8.5 million urls in a day. (Assuming the data could be downloaded this fast.) It would take that (single) computer about a year and a half to process the 4 billion urls. A Hundred Such Computers Could Do It in Just Under 5 Days.
Then there is the task of returning answers to queries in real time. Again, for the sake of argument, assume our typical 2Ghz Pentium computer could deliver 100 requests per second. Assuming it can scale close to linearly, the CPU resource required here would then Become a Function of How Popular the service became.
Considering a Worsse Case, WHERE Our Benchmark Machine IS Capable of Crawling Only 1 URL PER Second, and answering queries at a rate of 1 Request Per second, IT Could Easily Require Thousands of Computers.
IT is Clear That The Resources Required Are ConsideRable.
Historically, approaches to this problem used a small number of massively powerful computers (the Mainframe approach). More recently, and the technique used by Google, Yahoo and most likely Microsoft, involve many hundreds or thousands of "commodity" computers (cheap, standard , generic machines) working in some degree of parallelism, using the network to communicate.Taking this model one step further, it would appear that a distributed, "peer-to-peer" model could potentially be used to provide these resources. There is The Potential for Hundreds of Thousands of Computers, Distributed Across The Internet All Working Together.
EXInship (Working) Examples of Peer-to-Peer NetWorks:
Traditional file-sharing networks such as Kazaa, which already allow millions of users to search across millions of files, representing terabytes of data, and then download those files simultaneously from multiple sources. Internet Telephony networks, like Skype, which use peer-to- peer networks to route calls for free around the world in real time. Less traditional (newer?) file sharing networks, such as BitTorrent which implement an "open" service similar to the traditional service offered by Akamai. Also Freenet which implements an entirely decentralised Hosting NetWork Where Both Publishers and Consumers Are Anonymous.
Spamming, corruption and abuseBecause it will drive more people to a web site, many people and organisations go to considerable lengths and cost to try and ensure their sites appear as high as possible in search results. This is commonly referred to as "Search Engine Optimisation ".
An example might be trying to ensure your web site appears above those of your competitors - even when the search query was for your competitors name, or product.However this is only the tip of the iceberg when it comes to bias and corruption in search results . for instance, a technique often referred to as "Google Bombing" resulted in Microsoft's website appearing at the top of the results when someone searched for "more evil than satan himself" towards the end of 1999.
And THEN, OF Cours, There Are Laws, Lawyers, Legal Systems and Governments. Consider Liable and Propaganda to Name But Two.
There are a number of ways to address these problems, which are typically coded into the algorithms and rules used by the search service and are often highly guarded secrets. Although the specific implementation details are not public knowledge, many of the concepts are generally well understood And Documented. PageRank (TM), As Used by Google, IS A Good Example of this. Various Forms of Hashing To try Another.
Discussion of these techniques, while a critical and very complex part of any web search solution, are beyond the scope of this document. There are however two problems specific to a distributed web search service worth noting.
Open algorithmThe rules and algorithms used in an open web search service would be available to anyone, including those wanting to corrupt it. This is often cited as a key reason for keeping these rules secret in existing services.
WITHOUT TRYING, IT IS IMPOSSIBLE TO KNOW IF This Would Indeed Be An Insurmountable Problem.
However, Microsoft and others have argued that proprietary "closed" software is more secure because the source code is not public, and thus it is harder to find and exploit bugs or weakness. Linux takes the opposite approach, and says that making everything open will both promote a more secure design and allow for problems to be found and fixed faster.Without wishing to get involved in this specific debate, it would be fair to say that neither side has categorically proved their case, and most likely never will. Which raises THE Question, Could the Same Be True of the Algorithms Used in Web Search Engines?
There are a number of additional measures that can be used to avoid spamming and corruption. Many sites, including Amazon and slashdot.org, employ community-rating schemes. Yahoo Mail allows users to easily mark emails as spam. Used collectively, this information can Help Identify and Dear With Problems and Can Be a Difficult System To Abuse ON A Consistent and Repetitive Basis.
Corrupt nodes or clientsExisting models such as those used by Google, Yahoo or Microsoft obviously involve a massive number of computers. However, all of Google's computers are under the full control of Google. They can be reasonably sure all their machines are running the same code AND That None of their Machines Are Intend Their Data or Service.
In a distributed, community-driven service, where code would be running on a vast array of different computers around the internet, it would be very easy for someone to obtain the source code for an open, distributed web search service, adjust it to suit their specific purposes (such as always returning porn sites top of the results) and then add this new node or client to the network.A good example of this is when the music industry added corrupt or invalid files to file sharing networks such as Kazaa. Because The File Names and Sizes Matched, Users Thought The Popstar. INSTATION.
Again, IT IS IMPOSSIBLE TO KNOW WITHOUT TRYING WHENER THIS Would Be A Fundamental Problem That Could Not Be Resolved.
That said, and assuming there is more good than evil, one Possible Solution Would Be to Introduce Redundancy and cross Checking.
Imagine There a Number of Independent Machines (Or Nodes IN Our Open, Distributed Network That Visit, Crawl and Analyze A URL or Web Page. Let's Call, "Crawlers". See Fig 1.
.
Having completed their task, the crawlers do nothing more than pass the information "up the chain" to another set of machines (or nodes in the network) that hold the index data for a whole set of urls or pages. These are called "Indexers See Fig 2.
An Indexer would typically get information about a single url from a number of disparate Crawlers. It could compare these various copies, and all being well, each copy would be identical. If one of the copies differed, it would know something was wrong with that crawler.Indexer nodes could be thought of as a collection of lots of little databases. No one node would contain the entire database. It is unlikely any of the nodes on the network would have enough storage available.
In Addui Splitting The Whole Index Across Multiple Indexer Nodes, There Wouldes All Storing The Same Section of The INDEX.
The third type of node is a Searcher node These accept "end user" queries -. For example a search for "car hire in london" The Searcher node breaks this down, and passes it along to a number of different Indexer nodes Each.. Indexer Node Is Responsible for Returning A Partial Set of the Overall Results. See Figage.
The Searcher nodes combine the results from the various Indexer nodes and additionally cross check the results. In this way, a Searcher node can quickly identify an Indexer node that is misbehaving or returning bad results. Such nodes can then be factored out of the current results And not buy infuture.
Obviously, Any Such System Would Be Vastly More Complex. But It Should Be Clear That There Various Ways To DEAL with BADLY-BEHAVED NODES AND ACCORDINGLY.
Making Access EasyWhile It Would Be Important That As Many People As Possible Installed and Ran The Software (And Act As A Node), this is unlikely to Ever be the massity Since Most People Search Via a Web Site.
Consider a portal site that offers the ability to search the web. If it were to contribute sufficient resources to the network, it ought to be able to use the network to power its web search offering. The portal would be contributing resources to the network, which could be used by others.LeechesMost distributed networks have to deal with "leeches" -. people that suck resources from the network without contributing back This problem is related to the problem of spammers and people trying to corrupt the network The most obvious type. Of Leech Would Be A Large Site Operating Many Searcher Nodes But no Indexer OR CRAWLER ANES.
Indexer nodes would quickly spot any one Searcher node that was requesting abnormally high levels of traffic and penalise it accordingly. This would force the Searcher node onto another Indexer node, which would eventually also penalise the Searcher node for its high levels of traffic. As this Progresses, a Greedy Searcher Node FINDS FEWER AND FEWER INDEXER NODES WILLING to Communicate with it.
It would be possible to taint your local node to only act as a Searcher, but in order to send more than a trivial amount of queries, you would need to set up a very high number of these nodes. In addition, because Indexer nodes communicate with both Searcher and Crawler nodes, and because one physical machine ought to be capable of acting as multiple types of nodes simultaneously, an Indexer node that receives high numbers of queries from a discreet location ought also to receive Crawler data from that same location. We Penalise Nodes That Do Not Meet The Criteria.
Which Sites to CRAWL?
How do crawlers know which sites to visit and how offen?
Individual Indexer nodes are aware of a subset of the overall index and also which pages are matching most in current queries. When Crawler nodes are passing information about specific sites to the Indexers, the Indexers can be passing back statistical information about where to crawl next. The Crawler nodes can cross reference the statistical models they receive about a small sub-set of the internet from various Indexer nodes. Then, by a combination of weighting popular urls and randomly picking a starting point from the statistical model, a Crawler can find a Point to begin.
In addition, it ought to be possible to monitor the results end users are clicking on. This would allow sites that get more traffic to be considered more worthy of additional, or more frequent, crawling. It might be most appropriate for the Crawler nodes themselves To Gather this Data. Note That We do Not NEED To Record Every Click, ONLY A Statistical Sample. See Fig 4.
.
Crawler 1 visits www.example.com, indexes the page and passes it onto various Indexer nodes. Www.example.com updates the content of their page Crawler 2 visits www.example.com, indexes and passes on the data to various Indexer nodes . When the various Indexer nodes compare the data about www.example.com from the various Crawlers, they will notice a discrepancy. Pages that include the current time (including seconds), the user name or a "random" headline will all suffer this IT Would Also Be a problem by ipdates to the code or systems of the various nodes where updates.
Once again, it is hard to know if this problem could be solved sufficiently, but a number of techniques may help.When information is received from a Crawler that does not match the existing data for a site, the Crawler is not immediately banned. The Receiving Node Would SIMPLY NOTE A GIVEN CRAWLER HAD PRESENTED POSSIBLY CORRUPT DATA. IF A CRAWLER CONSISTENTLY GIVES BAD DATA for a Given Site (or for all sites) Only the would IT Be Treated as corrupt.
By knowing the time a Crawler visited a page, a node could sort the various different copies of data about a site by time. This would help to spot a typical site update. If there were five versions of information about one site, we would use The Version That Was Most Consistent Across The Available Sample.
Hashing algorithms exist that could be used to spot two documents that are substantially identical except for a small amount of text. If all the various copies of information received about a site differed in a similar way, it would be safe to assume there was no problem .
Final ThoughtsSearcher nodes might expose a vast array of features and configuration abilities. Date ranges, geography, language and profanity might be variables that could be adjusted. A client (including a web site) could mask these from the end user by simply hard-coding VALUES for them.
This is.
Indexer nodes would appear to be doing the most work, so it is possible that this conceptual block might be sub-divided into smaller units, each of which could be a distinct node. Alternatively, the vast majority of nodes would need to be Indexers. It ought to be possible for one physical machine to function as many different types of nodes. Namely, your computer could be a Crawler, Indexer and Searcher node simultaneously. In fact, it is probably better if this is the case.
The Apache HTTP Server, especially version 2, is a very mature multi platform application development framework that is well suited to a project such as this. Despite its name, it need not be limited to the HTTP protocol for communication between nodes.
Next Steps
Maths, Statistics and ProbabilityFrom a theoretical point of view, could this model stand up? Or would it require so many nodes to operate that it would be unfeasible to build? Would the communication overhead be too high?
How do we split the index up across multiple nodes? For instance, it could be split by the words people might search on, leaving a set of Indexer nodes with information on all the urls that mention a word starting with the letter A, another for Words Starting B, ETC. IN Reality, Sub-Dividing by Much More Than THE 26 Letters of The Alphabet Would Be Required - But How Far? Would this work?
Another approach might be to split based on the domains of sites. Thus, one group of Indexer nodes would know all about sites whose domains began "www.ab ..." and another group of Indexer nodes could handle sites beginning "www.ac "
Given that a typical node will not have a huge amount of resources available to it, how many of each type of node (Crawler, Indexer and Searcher) would be required to index 4 billion urls, refreshing them all once per month? And to be handle a sustained rate of 100 queries per second? What mathematical or statistical techniques could be used to analyse sites? Problems here include looking for similar (but maybe not identical) documents and identifying likely spam. Would Bayesian classifiers be of use? Perhaps adapting other DE-Spamming Technologies Would Be Useful?
Weakness and Riskhow Would You Attack Such A NetWork in Order To Improve THE RANKING OF Your Site?
WHERE Are The Weak Spots in The Design?
COULD An Update to the code used by The Nodes Result in a deadlock, such what the entire network failed?
Proof of conceptBy limiting ourselves to a couple of small domains to crawl and index and not worrying too much about the complexities of dealing with spam and abuse, it ought to be possible to implement a working prototype.
Which language to use? This could be contentious at best, but it would be reasonable to assume that it must be an open source language. A strong collection of networking and text analysis tools would be of much use, as would an abundance of programmers willing To Hack.
It could be argued that there is the most value in rapid application development, focusing on building the API's and system design. A language such as Perl might be appropriate for this. From here, faster, more optimised and efficient clones could evolve in other languages .
Feedbacksome Hearty Discussion On The Wiki Might Be in Order. Please try to keep it..
