Friday, May 9, 2008

How hash works with block in ruby

There are many different implementations of Fibonacci series in Ruby. One implementation is this.





fibs = Hash.new do |hash,key|
if key < 2
hash[key] = 1
else
hash[key] = hash[key - 1] + hash[key - 2]
end
end

(1..10).each {|i| puts fibs[i] }

# output
1
2
3
5
8
13
21
34
55
89




Ruby is full of surprises and this is one of them. Look at the api for Hash. It will mention that Hash can accept a block. But the api leaves out something very important without which understanding the above code is difficult.




At the time of Hash creation if a block is passed then this is what happens. Ruby will make a call to the block every single time ruby encounters a case where the hash doesn’t have a value for the input key. If the hash has a value for the input key then the block is not invoked. When the block is indeed invoked then ruby passes two parameters. The first param is the hash itself and the second param is the key for which no value was found.




Now it should make it easy to understand how and why the above code is working.


Thursday, May 8, 2008

High Performance Multithreaded Access to Amazon SimpleDB

Simpledb_s3_query_sample_2
We have just released a new code sample.



Written in Java, this new sample shows how Amazon SimpleDB can be used as a repository for metadata which describes objects stored in Amazon S3. The code was written to illustrate best practices for indexing S3 data and for getting the best indexing and query performance from SimpleDB.



Indexing is implemented at two levels. At the first level, multiple threads (implemented using the Java Executor) are used to ensure that a number of S3 reads and a number of SimpleDB writes are taking place simultaneously. At the second level, Amazon SQS is used to coordinate index tasks running on multiple systems, leading to an even higher degree of concurrency.



Bulk queries are implemented using a pair of thread pools. The first pool runs SimpleDB queries and the second retrieves SimpleDB attributes. With the proper balance between the two pools, a Small Amazon EC2 instance was able to make over 300 requests per second.



Check it out!



-- Jeff;




Bad concurrency advice: interned Strings

I just read Thread Signaling from Jacob Jenkov. It is fine as far as it goes to introduce the reader to Object.wait() and Object.notify().

But it has one fatal flaw: it uses a literal java.lang.String for coordinating between threads. Why is this wrong?

Strings are interned by the compiler. To quote the javadocs: All literal strings and string-valued constant expressions are interned. Using a literal string means that any other code anywhere in the JVM, even in other libraries, which use the same String literal value all share the same object for wait() and notify(). This code:

public void dastardly() {
"".notify();
}

will wake up a thread waiting on empty string, including one in utterly unrelated code.

Don't do that. Instead, create a fresh Object for coordinating threads. This age-worn advice for lock objects (synchronize(lock)) applies just as much to objects used to coordinate threads.


Comic for May 8, 2008



Wednesday, May 7, 2008

Crawling is harder than it looks

The best paper award at WWW 2008 went to a paper on large-scale crawling titled "IRLbot: Scaling to 6 Billion Pages and Beyond" (PDF) by Hsin-Tsang Lee, Derek Leonard, Xiaoming Wang, and Dmitri Loguinov.

I have never been that interested in crawling, so I almost missed this talk. But, I am glad I didn't.

The paper is a fascinating look at the difficulty of doing very large scale web crawling, focusing on avoiding web spam and pathological link structures that could trap a crawler, making sure to not overwhelm crawled webservers, and using high performance techniques for duplicate detection.

Some extended excerpts:
The web has changed significantly since the days of early crawlers, mostly in the area of dynamically generated pages and web spam. With server-side scripts that can create infinite loops, high-density link farms, and unlimited number of hostnames, the task of web crawling has changed from simply doing a BFS scan of the WWW to deciding in real time which sites contain useful information and giving them higher priority as the crawl progresses.

The first performance bottleneck we faced was caused by the complexity of verifying uniqueness of URLs and their compliance with robots.txt. As N scales into many billions ... [prior] algorithms ... no longer keep up with the rate at which new URLs are produced by our crawler (i.e., up to 184K per second) ... [A] new technique called Disk Repository with Update Management (DRUM) ... can store large volumes of arbitrary hashed data on disk and implement very fast check, update, and check+update operations using bucket sort ... DRUM can be thousands of times faster than prior disk-based methods.

In order to determine the legitimacy of a given domain, we use a very simple algorithm based on the number of incoming links from assets that spammers cannot grow to infinity. Our algorithm, which we call Spam Tracking and Avoidance through Reputation (STAR), dynamically allocates the budget of allowable pages for each domain and all of its subdomains in proportion to the number of in-degree links from other domains.

We ran IRLbot on a [single] quad-CPU AMD Opteron 2.6 GHz server (16 GB RAM, 24-disk RAID-5) attached to a 1-gb/s link ... [for a] total active crawling span of 41.27 days. During this time, IRLbot attempted 7,606,109,371 connections and received 7,437,281,300 valid HTTP replies ... IRLbot ended up with N = 6,380,051,942 responses with status code 200 and content-type text/html.

The average download rate during this crawl was 319 mb/s (1,789 pages/s) with the peak 10-minute average rate of 470 mb/s (3,134 pages/s). The crawler received 143 TB of data, out of which 254 GB were robots.txt files, and transmitted 1.8 TB of HTTP requests. The parser processed 161 TB of HTML code.
At very large scale and from a single box, those are pretty remarkable crawling rates, 2k pages/second. The details of the bottlenecks they encountered and how they overcame them made this paper a quite enjoyable read.

I did end with a question about part of the work. The authors say (in 7.1 and Figure 6) that the probability of finding a unique page never dropped below .11 and, earlier (in 1.4) say that "we believe a good fraction of the 35B URLs not crawled in this experiment [contain] useful content." However, they define a unique page as the same URL, so it seems like it could easily be the case that those 35B URLs seen but not crawled could have duplicate or near duplicate content to the 6B crawled.

Update: One topic the IRLbot paper ignored was how frequently we should recrawl a page. Another WWW 2008 paper, "Recrawl Scheduling Based on Information Longevity" (PDF) by Chris Olston and Sandeep Pandey, has a nice overview of that issue and then extends the prior work by focusing on the persistence of a web page. The authors end up arguing that it is not worth recrawling pages that change very rapidly very frequently because it is impossible to ever get the index to match the actual content of the page.

Update: On the question of what content is useful, both in terms of crawling and recrawling, I always find myself wondering how much we should care about pages that never get visited by anyone. Shouldn't our focus in broadening a crawl beyond 6B pages and in recrawling pages in our index depend on how much users seem to be interested in the new content?

Amazon S3 Copy API Ready for Testing

Copying_s3_objects
A few weeks ago we asked our developer community for feedback on a proposed Copy feature for Amazon S3. The feedback was both voluminous and helpful to us as we finalized our plans and designed our implementation.



This feature is now available for beta use; you can find full documentation here (be sure to follow the links to the detailed information on the use of this feature via SOAP and REST). Copy requests are billed at the same rate as PUT requests: $.01 for 1000 in the US, and $.012 for 1000 in Europe.



In addition to the obvious use for this feature -- creating a new S3 object from an existing one -- you can also use it to rename an object within a bucket or to move an object to a new bucket. You can also update the metadata for an object by copying it to itself while supplying new metadata.



Still on the drawing board is support for copying between US and Europe, and a possible conditional copy feature. Both of these items surfaced as a result of developer feedback.



Tool and library support for this new feature is already starting to appear; read more about that in this discussion board thread.



-- Jeff;


Monday, April 28, 2008

Search trails and relevance

Misha Bilenko and Ryen White from Microsoft Research had a paper at WWW 2008, "Mining the Search Trails of Surfing Crowds: Identifying Relevant Websites From User Activity" (PDF), that is a fascinating look at going beyond the first click on search results for improving search results and toward considering all the pages people visit.

An excerpt from the paper:
While query and clickthrough logs from search engines have been shown to be a valuable source of implicit supervision for training retrieval methods, the vast majority of users' browsing behavior takes place beyond search engine interactions.

This paper proposes exploiting a combination of searching and browsing activity of many users to identify relevant resources for future queries. To the best of our knowledge, previous approaches have not considered mining the history of user activity beyond search results, and our experimental results show that comprehensive logs of post-search behavior are an informative source of implicit feedback for inferring resource relevance.

Web browser toolbars have become increasingly popular ... Examples of popular toolbars include those affiliated with search engines (e.g., Google Toolbar, Yahoo! Toolbar, and Windows Live Toolbar) ... Most popular toolbars log the history of users' browsing behavior on a central server for users who consented to such logging. Each log entry includes an anonymous session identifier, a timestamp, and the URL of the visited Web page. From these and similar interaction logs, user trails can be reconstructed.

Training retrieval algorithms on interaction behavior from navigation trails following search engine result click-through leads to improved retrieval accuracy over training on only result click-through or search destinations ... Our research has profound implications for the design of Web search ranking algorithms and the improvement of the search experience for all search engine users.
Please see also Googler Daniel Russel's JCDL 2007 talk, "What are they thinking? Searching for the mind of the searcher" (PDF), which shows, starting on slide 33, that Google is using their toolbar data to analyze user behavior.

Thanks, Ionut Alex Chitu, for the pointer to Daniel's JCDL talk.

Sunday, April 13, 2008

A first hand look at building an Android application







Dan Morrill builds a simple application on the Android platform.

Views:
267763


286
ratings
Time:
07:57
More in
Science & Technology

Tuesday, April 8, 2008

My wishlist for a great Ajax API

Coming back from The Highland Fling it was interesting to see that people seem not to be quite convinced yet about the necessity of APIs and the large part they are playing in the next few years of web development. I guess this is partly based on experiences with APIs that aren’t properly explained to non-geeks and inconsistent or hard to use. There is just not much fun in trying to find information bit by bit if all you want to do is write some code (unless you have the old school hacker/cracker mind and didn’t consider spending hours looking at hexdumps trying to find a way to get endless lives in a games a waste of time).



During my interview with Paul Boag at I pointed out that designing a good API is as important as designing any other user interface – including your web page. Gareth Rushgrove agreed in his splendid talk How to be a first class web citizen. I also pointed out that there is a lack of clear and easy tutorials and articles on the matter, so I decided to have a go at it now.



Designing a great Ajax API



As an example I will use the recently released Google translation API, point out its good parts and list things I consider missing. I will not go into the part of actually writing the API but instead explain why I consider the missing parts important. This is not an attack towards Google, I just really liked working with this API and wanted to have it a bit easier to use, so no hard feelings, I really take off my hat that you offer an API like that!



Here are the points I consider important when we’re talking about Ajax APIs in JavaScript (Ajax implies that but you’d be surprised how often a REST API is advertised as Ajax):




  • Good documentation

  • Usage examples to copy + paste

  • Modularity

  • Link results to entries

  • Offer flexible input

  • Allow for custom object transportation

  • Cover usability basics



Documentation and presentation



Let’s start with a positive: the documentation of the Google Ajax Language API is great. You have all the information you need on one page including copy and paste examples. This allows you to work through the API online, read it offline and even print it out to read it on a crowded bus without having to take out your laptop.



Tip: If you are offering copy and paste examples – which by all means you should as this is what people do as a first step – make sure they work! I learnt the hard way in my book Beginning JavaScript with DOM Scripting and Ajax that there is nothing more dangerous than showcasing code snippets instead of full examples – people will copy and paste parts of a script, try to run it and either email you that your code is broken or – even worse – complain in book reviews on Amazon. If you offer copy and paste examples make sure all of them work independently.



Google offer explanations what the API is, what you can do with it, a list of all the parameters and what they mean. This is great for a first-glance user. For the hard-core audience they also offer a class reference.



Usage example



The first code example is quite good, you can copy and paste it and if your computer is connected to the Internet it will work – or it would, if the HTML got some fixes.



First of all it lacks a DOCTYPE, which is a bit annoying as it is a very important part of an HTML document. The more important bit is that the encoding is not set. The live example version has both – bit of a nuisance, as especially when we talk about different languages and using traditional Chinese as the example, the correct encoding is a must.



(Note: the irony, seems like wordpress doesn’t do this right for some reason …)


<html>
<head>
<script type="text/javascript" src="http://www.google.com/jsapi"></script>
<script type="text/javascript">

google.load("language", "1");

function initialize() {
var text = document.getElementById("text").innerHTML;
google.language.detect(text, function(result) {
if (!result.error && result.language) {
google.language.translate(text, result.language, "en",
function(result) {
var translated = document.getElementById("translation");
if (result.translation) {
translated.innerHTML = result.translation;
}
});
}
});
}
google.setOnLoadCallback(initialize);

</script>
</head>
<body>
<div id="text">??????????</div>
<div id="translation"></div>
</body>
</html>


Tip: make sure you explain to people that your code examples need an internet connection and other dependencies (like requiring HTTP and thus having to run on a local server). JavaScript historically didn’t have any other dependency than a browser, this is changing lately and can be confusing, especially when you use Ajax behind the scenes like some Flash/Ajax APIs do!



Modularity is good!



The first bit that threw me off to a certain degree was the google.load("langage","1") line, but there is an immediate explanation what it means.



The first script include loads a generic Google Ajax API that has a load() method to add other, smaller APIs build on top of this one. In this case the line means you want to load the language API with the version number 1.



This appears clunky and you will get bad feedback for it (it seems there is nothing better the woo the masses to have a one script include solution) but is actually rather clever.



By modularizing the Ajax code in a base library changes to the core functionality will be easy and by asking the implementer to include the APIs he needs with a version number you can make it the choice of the implementer to upgrade instead of breaking older implementations or having to carry the weight of full backwards compatibility.



Yes, the perfect world scenario is that you’ll never have to change the functionality of your API - just add new features – but in the real world there are constant changes that will make it necessary for you to mess with the original API. There is no such thing as perfect code that is built for eternity. Using a loader function in the base API is also pretty clever, as it means that implementers don’t need to change URLs.



What goes in should come out.



This is where Google created a problem. Both the google.language.detect() and the google.language.translate() methods are quite cool insofar they offer you to send a string and define a callback method when the API returned a value. However, the returning object in both cases gives a result and a status code, but not what was entered. You get all kind of other information (described in the class documentation) but having the original entry would be very useful.



Why? Well the great thing about Ajax is that it is asynchronous, and that is also its weakness. It means that I can send lots of requests in the background in parallel and wait for the results. However, this does not mean that the requests also return in the right order!



This means that if you want to loop through an array of texts to translate, the following is an unsafe way of doing it:



var translations = [ 'one','two','three','four','five','six','seven','eight','nine','ten'];
var gtl = google.language.translate;
for(var i=0,j=translations.length;i<j;i++){
gtl(translations[i],'en','de',function(result) {
if (!result.error) {
var container = document.getElementById('translation');
container.innerHTML += result.translation;
}
});
}


Instead you need to wrap the incrementation of the array counter in a recursive function:



var translations = [ 'one','two','three','four','five','six','seven','eight','nine','ten'];
var gtl = google.language.translate;
var i=0;
function doTranslation(){
var gtl = google.language.translate;
if(translations[i]){
gtl(translations[i], 'en', 'de', function(result) {
if (!result.error) {
var container = document.getElementById('translation');
container.innerHTML += result.translation;
i++;
doTranslation();
}
});
}
}
doTranslation();


This is safer, but we lost the opportunity to have several connections running in parallel and thus getting results faster. If the result of the API call had the original text in it, things would be easier, as we could for example populate a result object and match the right request with the right result that way:



var translations = [ 'one','two','three','four','five','six','seven','eight','nine','ten'];
var gtl = google.language.translate;
var results = {};
for(var i=0,j=translations.length;i<j;i++){
gtl(translations[i],'en','de',function(result) {
if (!result.error) {
results[result.input] = result.translation;
}
});
}


Even easier would be a transaction ID to pass in which could be the counter of the loop. Another option of course would be to allow more flexibility in the data that goes in.



Offering flexible input



Both the matching of the input text with the result and a transaction ID still would mean a lot of requests to the API, which is not really nice as it costs money and clobbers the server and the client alike. An easier option would be to not only allow a string as the text parameter but also an array of strings. The return then would also become an array and a lot of the overhead of calling the translation engine would be done on the server in a single call instead of lots and lots of API calls.



This is not hard to do and most JavaScript framework methods work that way, by checking the type of the first argument and branching accordingly. You can even go further and allow the implementers to send an own bespoke object as a third parameter.



Transporting a custom object allows implementers write a lot less code



The benefit of a custom object going out and in is that you can add more parameters to the API call that are only specific to the implementation. Most likely this could be a reference to a namespace to avoid having to repeat long method names or global variables. You could start by providing parameters that make sense to any Ajax call in terms of usability.



Thinking Ajax usability



The main thing any Ajax call should offer a user is a timeout. There is nothing more disappointing than getting the promise of a brave new Ajax world with much more interactive interfaces and then getting stuck looking at spinning wheels or worse hitting a link and getting nothing. Right now the language API has nothing like this, and you’d have to roll a solution by hand. You’d also have to check the error status code to see if the data could not be retrieved and call a failure case of the connection that way.



A nice API would offer me these options, most likely all rolled in one parameters object.



My dream translation API



Taking all these into consideration it would be perfect to get the API to offer these options:



google.language.translate(input,parameters);


The parameters would be:




input // string or array
parameters // object with the following properties
sourceLanguage:string,
targetLanguage:string,
transactionId:string,
customparameters:object, // to transport
timeout:integer, // (in milliseconds)
failure:function(result,params), // (method to call when there is a timeout or an error)
success:function(result,params), // (method to call when all is fine)


The returned data from the API should have both the result and the parameters provided. This would make the life of implementers dead easy.



Summary



In summary, here’s what I expect from a great Ajax API:




  • Have a good documentation with immediate copy and paste examples backed up by a full class documentation

  • Build your APIs modular and allow the implementer to choose the version they want to have

  • Provide a hook to link the result of the API methods to the initial data entered. The easiest way is to repeat this data, more sophisticated is to allow for a connection ID.

  • Allow for multiple values to be sent through, it’ll save you API calls and the implementer hacking around the problem of unreliable order of returns.

  • Allow implementers to add an own object to send and get back to allow for namespacing and other data state retention.

  • Allow for a timeout, connections are not to be trusted.



This is a work in progress



I hope you found something here to agree with and if you know things to add, just drop a comment.



Technorati Tags: , , , ,


Saturday, April 5, 2008

Don’t make me click

I’ve always been interested in computer user interface design. Like economics, it’s an exercise in constrained optimisation. An interface is constrained by the limits of the computer like the 2D screen and mouse + keyboard input. Given these constraints, the challenge is to design the most efficient interface that allows users to do what they want to do.


One of the dimensions in which websites and software compete is the quality of their interface. This is particularly important for websites, where competition is only a click away. The key is to recognise that the interface imposes costs on the user. They don’t pay money to use your website, but they do pay with time. They are not interested in your interface per se, but the content or services on your site. Every extra interface complexity is like charging a slightly higher price to users. Think of it as a per-click cost. Every click imposes cognitive costs on users and makes your site more ‘expensive’. If your rivals have a ‘cheaper’ interface, they’ll attract more customers than you. Fewer clicks = less cost to users = more traffic (everything else equal).


It’s not that people dislike thinking per se. People do like thinking about things like sudoku puzzles or crosswords. A lot of people also genuinely like thinking about their work. People are happy to think about things that are related to an objective that they have. What they don’t like is having to think about things peripheral to the objective, like how a user interface works. It’s like walking along a crowded street. You don’t mind walking, but all the other people getting in your way annoy you, because they’re imposing extra costs on achieving your objective. Badly designed interfaces are like crowded streets.


With this in mind, here is an interesting talk called “Don’t make me click” by Aza Raskin at Google about interface design:





Aza’s company, Humanized, has developed some interesting software, including Enso, which is a simple pop-up command line. To activate it you press the caps lock key and then type in special commands. For example you can type “google xyz” and you’ll be taken to the page of Google search results for xyz. Once you get used to it, it’s quicker than opening a browser and doing a search.


Somewhat unrelated, but rather amazing, is this talk at Google by a 12 year old kid about programming. It’s pretty technical, but this kid is incredible. I mean, he’s talking about programming, to people who work at Google. I think he knows more about programming than I know about economics.






Permalink |
No comments yet |
Bookmark/share



Posted in Programming, Software