Talk on lock-free hash tables

Cliff Click gave an interesting Google engEdu talk on an implementation of "A Lock-Free Hash Table" for multiprocessor systems with large numbers (>32) of CPUs.

Cliff also has a couple weblog posts ([1] [2]) that cover some of the material from his talk. A brief excerpt:

A Non-Blocking (concurrent, lock-free) HashTable ... [where the] single-threaded performance appears to equal java.util.HashTable, and at high CPU count (750 cpus on a high-end Azul machine) it's about twice as fast as Doug Lea's marvelous java.util.concurrent.ConcurrentHashMap - with 4096-way striping.

I've chosen a power-of-2 closed table - collisions cause re-probing into the table ... I do not need any memory fencing or any locking [even on a resize]. I do need CAS [(Compare-and-swap)] when changing the table.

Early in the talk, I was wondering how Cliff handles deletes. As it turns out, he does not. Old deleted keys are only cleaned up on a resize, which works and nicely dodges delete nastiness.

I seem to be bumping into a lot of interesting work on large scale multiprocessor systems lately. For example, "Evaluating MapReduce for Multi-core and Multiprocessor Systems" (PDF) shows some promising results for using MapReduce to simplify some parallel programming on a single box with 8+ CPUs (rather than on a cluster of boxes), at least for tasks that easily can be translated to a MapReduce problem.

There is also a Google engEdu talk on that MapReduce paper, but the video is hard to hear in parts. However, there were some interesting tidbits in the Q&A, including people questioning the small data sizes used for the tests (almost all under 1G) and whether the extraordinary speedup (~x50) reported on the ReverseIndex task was an issue with the coding of the serial version of the algorithm rather than a true speedup.

Broadening out to issues with programming multiprocessor systems in general, another Google engEdu talk, "Advanced Topics in Programming Languages: The Java Memory Model", provides a nice overview of some tricky issues that may trip up even the best of us when trying to do multithreaded programming.

Finally, that Java memory model talk serves as good motivation for another talk, "Software Transactional Memory", which argues for considering the software transactional memory model -- allowing a series of reads/writes to be marked as one logical action and then using abort and retries to handle most contention -- over error-prone traditional locking. If you have never heard about software transactional memory before (I had not), skimming the Wikipedia page or watching the video might be worthwhile.

Read More

Architecture behind temporary e-mail addresses

Paul Tyma has a fun and detailed post describing the architecture behind Mailinator, a service that provides temporary e-mail addresses.

[Found via Rich Skrenta]

Read More

Amazon versus Alexaholic

An interesting story on TechDirt about how Amazon-owned Alexa took many of the good UI ideas developed by a site called Alexaholic (that was layered on top of and depended on Alexa data), then worked to shut Alexaholic down.

Amazon's Alexa unit, which tries (poorly, some might argue) to track web traffic, has been embroiled in a spat with the site Statsaholic, which until recently was called Alexaholic.

Statsaholic's strategy was to take Alexa's data and present it in a matter that's far more usable than the way Alexa presents it.

Amazon seemed to tolerate, or even encourage, Alexaholic, until it built all of Alexaholic's functionality into its own site, at which point it went on the attack. First it went after the company's domain name, Alexaholic.com, which was arguably infringing on Alexa's trademark. Then Amazon blocked off access to its graphs and data, effectively disabling the renamed Statsaholic.

See also reports on this from Dare Obasanjo and TechCrunch.

See also my Nov 2005 post, "Is Web 2.0 nothing more than mashups?", where I said:

Companies offer web services to get free ideas, exploit free R&D, and discover promising talent. That's why the APIs are crippled with restrictions like no more than N hits a day, no commercial use, and no uptime or quality guarantees.

They offer the APIs so people can build clever toys, the best of which the company will grab -- thank you very much -- and develop further on their own.

Read More

More on a data center in a trailer

Sixteen months ago, there was an interesting rumor that Google is building data centers that fit inside of shipping containers.

Google hired a pair of very bright industrial designers to figure out how to cram the greatest number of CPUs, the most storage, memory and power support into a 20- or 40-foot [shipping container]. We're talking about 5000 Opteron processors and 3.5 petabytes of disk storage that can be dropped-off overnight by a tractor-trailer rig.

Now, it appears that Microsoft may be getting into the act. Windows Live Core architect James Hamilton wrote a paper, "Architecture for Modular Data Centers" (.doc), that shows considerable thought into how you might squeeze a data center into a shipping container.

Extended excerpts from the paper:

[We propose] to no longer build and ship single systems or even racks of systems. Instead, we ship macro-modules consisting of a thousand or more systems.

Each module is built in a 20-foot standard shipping container, configured, and burned in, and is delivered as a fully operational module with full power and networking in a ready to run no-service-required package. All that needs to be done upon delivery is provide power, networking, and chilled water.

Components are never serviced and the entire module just slowly degrades over time as more and more systems suffer non-recoverable hardware errors ... Software applications implement enough redundancy so that individual node failures don't negatively impact overall service availability ... At the end of its service life, the container is returned to the supplier for recycling.

This model brings several advantages: 1) on delivery systems don't need to be unpacked and racked, 2) during operation systems aren't serviced, and 3) at end-of-service-life, the entire unit is shipped back to the manufacturer for rebuild and recycling without requiring unracking & repackaging to ship.

A shipping container is a weatherproof housing for both computation and storage. A "data center," therefore, no longer needs to have the large rack rooms with raised floors that have been their defining feature for years ... The only requirement is a secured, fenced, paved area to place the containers around the central facilities building.

On-site hardware service can be expensive ... [we avoid] these costs ... Even more important ... are the errors avoided by not having service personal in the data center ... human administrative error causes 20% to 50% of system outages.

The macro-module containers employ direct liquid cooling ... No space is required for human service or for high volume airflow. As a result, the system density can be much higher than is possible with conventional air-cooled racks .... High efficiency rack-level AC to DC rectifier/transformers [also may yield] significant power savings.

This architecture transforms data centers from static and costly behemoths into inexpensive and portable lightweights.

There also is a PowerPoint presentation (.ppt) that covers much of the same material as the paper.

[James Hamilton paper and talk found via Mary Jo Foley]

Update: Nick Carr writes about Rackable Systems' Concentro and Sun's Blackbox in his post, "Showdown in the trailer park".

Update: One year later, Microsoft announces their new Chicago data center has an "entire first floor is full of containers ; each container houses 1,000 to 2,000 systems per container ; 150 - 220 containers on the first floor." A total of 200k - 400k servers. Wow, quite a build-out. [Found via James Hamilton and [Nick Carr]

Read More

Skrenta on beating Google

Rich Skrenta writes "How to beat Google, part 1". Some brief excerpts:

Grow a spine people! You have a giant growing market with just one dominant competitor, not even any real #2 ... Get a stick and try to knock G's crown off.

Here are my tips to get started:

A conventional attack against Google's search product will fail ... A copy of their product with your brand has no pull.

Forget interface innovation ... Interface features only get in the way.

Forget about asking users to do anything besides typing two words into a box.

Users do not click on clusters, or tags, or categories, or directory tabs, or pulldowns. Ever. Extra work from users is going the wrong way. You want to figure out how the user can do even less work.

Go read the whole thing. It's a good read.

Personalized search, by the way, requires no extra work from the user, works from just a couple words in a box, adds no interface goo, and could provide a substantially different experience than using Google.

Some of my previous posts -- such as "Perfect Search and the clickstream", "Search without searching", and "Search as a matching engine" -- discuss in some detail why personalized search might be a good path for those who seek to beat Google.

See also my posts, "Kill Google, Vol. 3" and "Kill Google, Vol. 2", which argue for attacking Google's lifeblood, their advertising revenue, instead of focusing on search.

Read More

The end of federated search?

Thinking more about my last post, "Google and the deep web", Google appears to me to be rejecting federated search, instead preferring a local copy of all the world's data on the Google cluster.

Federated search (or metasearch) is when a search query is sent out to many other search engines, then the results merged and reranked.

In more complicated forms, the federated search engine may build a virtual schema that merges all the underlying databases, map the original query to the different query languages of the individual source databases, only query the databases that have a high likelihood of returning good answers, resolve inconsistencies between the databases, and combine multiple results from multiple sources to produce the final answers.

The Googlers on the "Structured Data Meets the Web: A Few Observations" (PS) Dec 2006 IEEE paper make several arguments against this approach succeeding at large scale:

The typical solution promoted by work on web­data integration is based on creating a virtual schema for a particular domain and mappings from the fields of the forms in that domain to the attributes of the virtual schema. At query time, a user fills out a form in the domain of interest and the query is reformulated as queries over all (or a subset of) the forms in that domain.

For general web search, however, the approach has several limitations that render it inapplicable in our context. The first limitation is that the number of domains on the web is large, and even precisely defining the boundaries of a domain is often tricky ... Hence, it is infeasible to design virtual schemata to provide broad web search on such content.

The second limitation is the amount of information carried in the source descriptions. Although creating the mappings from web­form fields to the virtual schema attributes can be done at scale, source descriptions need to be much more detailed in order to be of use here. Especially, with the numbers of queries on a major search engine, it is absolutely critical that we send only relevant queries to the deep web sites; otherwise, the high volume of traffic can potentially crash the sites. For example, for a car site, it is important to know the geographical locations of the cars it is advertising, and the distribution of car makes in its database. Even with this additional knowledge, the engine may impose excessive loads on certain web sites.

The third limitation is our reliance on structured queries. Since queries on the web are typically sets of keywords, the first step in the reformulation will be to identify the relevant domain(s) of a query and then mapping the keywords in the query to the fields of the virtual schema for that domain. This is a hard problem that we refer to as query routing.

Finally, the virtual approach makes the search engine reliant on the performance of the deep web sources, which typically do not satisfy the latency requirements of a web­search engine.

Google instead prefers a "surfacing" approach which, put simply, is making a local copy of the deep web on Google's cluster.

Not only does this provide Google the performance and scalability necessary to use the data in their web search, but also it allows them to easily compare the data with other data sources and transform the data (e.g. to eliminate inconsistencie and duplicates, determine the reliability of a data source, simplify the schema or remap the data to an alternative schema, reindex the data to support faster queries for their application, etc.).

Google's move away from federated search is particularly intriguing given that Udi Manber, former CEO of A9, is now at Google and leading Google's search team. A9, started and built by Udi with substantial funding from Amazon.com, was a federated web search engine. It supported queries out to multiple search engines using the OpenSearch API format they invented and promoted. A9 had not yet solved the hard problems with federated search -- they made no effort to route queries to the most relevant data sources or do any sophisticated merging of results -- but A9 was a real attempt to do large scale federated web search.

If Google is abandoning federated search, it may also have implications for APIs and mashups in general. After all, many of the reasons given by the Google authors for preferring copying the data over accessing it in real-time apply to all APIs, not just OpenSearch APIs and search forms. The lack of uptime and performance guarantees, in particular, are serious problems for any large scale effort to build a real application on top of APIs.

Lastly, as law professor Eric Goldman commented, the surfacing approach to the deep web may be the better technical solution, but it does have the potential of running into legal issues. Copying entire databases may be pushing the envelope on what is allowed under current copyright law. While Google is known for pushing the envelope, yet another legal challenge may not be what they need right now.

Read More

Google and the deep web

A few new papers out of Google cover some of their work on indexing the deep web.

A Dec 2006 article, "Structured Data Meets the Web: A Few Observations" (PS), appears to provide the best overview.

The paper starts by saying that "Google is conducting multiple efforts ... to leverage structured data on the web for better search." It goes on to talk about the scope of the problem as "providing access to data about anything" since "data on the Web is about everything."

The authors discuss three types of structured data, the deep web, accessible structured data such as Google Base, and annotation schemes such as tags.

Of most interest to me was the deep web, described in the paper as follows:

The deep (or invisible) web refers to content that lies hidden behind queryable HTML forms.

These are pages that are dynamically created in response to HTML ­form submissions, using structured data that lies in backend databases. This content is considered invisible because search ­engine crawlers rely on hyperlinks to discover new content. There are very few links that point to deep web pages and crawlers do not have the ability to fill out arbitrary HTML forms.

The deep web represents a major gap in the coverage of search engines: the content on the deep web is believed to be [vast] ... [and] of very high quality.

While the deep Web often has well structured data in the underlying databases, the Google authors argue that their application -- web search -- makes it undesirable to expose the deep Web structure. From the paper:

The reality of web search characteristics dictates ... that ... querying structured data and presenting answers based on structured data must be seamlessly integrated into traditional web search.

This principle translates to the following constraints:

• Queries will be posed ... as keywords. Users will not pose complex queries of any form. At best, users will pick refinements ... that might be presented along with the answers to a keyword query.
• The general search engine [must] detect the correct user intention and automatically activate specialized searches.
• Answers from structured data sources ... should not be distinguished from the other results. While the research community might care about the distinction between structured and un­structured data, the vast majority of search users do not.

The authors discuss two major approaches to exposing the deep Web, virtual schemas and surfacing.

Virtual schemas reformulate queries "as queries over all (or a subset of) the forms" of the actual schemas. The virtual schema must be manually created and maintained. As the paper discusses, this makes it impractical for anything but narrow vertical search engines, since there are a massive number of potential domains on the Web ("data on the Web encompasses much of human knowledge"), the domains are poorly delineated, a large scale virtual schema would be "brittle and hard to maintain", and the performance and scalability of the underlying data sources is insufficient to support the flood of real-time queries.

Therefore, authors favor a "surfacing" approach. In this approach:

Deep web content is surfaced by simulating form submissions, retrieving answer pages, and putting them into the web index.

The main advantage of the surfacing approach is the ability to re­use existing indexing technology; no additional indexing structures are necessary. Further, a search is not dependent on the run­time characteristics of the underlying sources because the form submissions can be simulated off­line and fetched by a crawler over time. A deep web source is accessed only when a user selects a web page that can be crawled from that source.

Surfacing has its disadvantages, the most significant one is that we lose the semantics associated with the pages we are surfacing by ultimately putting HTML pages into the web index. [In addition], not all deep web sources can be surfaced.

Given that Google is approaching the deep web as adding data to their current web crawl, it is not surprising that they are tending toward the more straightforward approach of just surfacing the deep web data to their crawl.

The paper also discusses structured data from Google Base and tags from annotation schemes. Of particular note there is that they discuss how the structured data in Google Base can be useful for query refinement.

At the end, the authors talk about the long-term goal of "a database of everything" where more of the structure of the structured deep web might be preserved. Such a database could "lead to better ranking and refinement of search results". It would have "to handle uncertainty at its core" because of inconsistency of data, noise introduced when mapping queries to the data sources, and imperfect information about the data source schemas. To manage the multitude of schemas and uncertainty in the information about them, they propose only using a loose coupling of the data sources based on analysis of the similarity of their schemas and data.

This specific paper is only one of several on this topic out of Google recently. In particular, "Web-scale Data Integration: You can only afford to Pay As You Go" (PDF) goes further into this idea of a loose coupling between disparate structured database sources. Of most interest to me was the idea implied by the title, that PayGo attempts to "incrementally evolve its understanding of the data it emcompasses as it runs ... [understanding] the underlying data's structure, semantics, and relationships between sources", including learning from implicit and explicit feedback from users of the system.

Another two papers, "From Databases to Dataspaces" (PDF) and "Principles of Dataspace Systems" (PDF) also further discuss the idea of "a data co-existence approach" where the system is not in full control of its data, returns "best-effort" answers, but does try to "provide base functionality over all data sources, regardless of how integrated they are."

Read More