Michael Friis' Blog

About


Non-trivial Facebook FQL example

This post will demonstrate a few non-trivial FQL calls from Javascript, including batching interdependent queries in one request. The example queries all participants of a public Facebook event and gets their names and any public status updates they’ve posted recently. It then goes on to find all friend-relations between the event participants and graphs those with an InfoVis Hypertree. I haven’t spent time on browser-compatibility in result-rendering (sorry!), but the actual queries work fine across browsers. You can try out the example here. The network-graph more-or-less only works in Google Chrome.

The demo was created for a session I did with Filip Wahlberg at the New Media Days conference. The session was called “Hack it, Mash it” and involved us showing off some of the stuff we do at ekstrabladet.dk and then demonstrating what sort of info can be pulled from Facebook. Amanda Cox was on the next morning and pretty much obliterated us with all the great interactive visualizations the New York Times builds, but that was all right.

Anyway, on to the code. Here are the three queries

var eventquery = FB.Data.query(
	'select uid from event_member ' +
	'where rsvp_status in ("attending", "unsure") ' +
		'and eid = 113151515408991 '
);

var userquery = FB.Data.query(
'select uid, name from user ' +
'where uid in  ' +
	' (select uid from {0})', eventquery
);

var streamquery = FB.Data.query(
	'select source_id, message from stream ' +
	'where ' +
	'updated_time > "2010-11-04" and ' +
	'source_id in ' +
		'(select uid from {0}) ' +
	'limit 1000 '
	, eventquery
);

FB.Data.waitOn([eventquery, userquery, streamquery],
	function () {
		// do something interesting with the data
	}
);

Once the function passed to waitOn executes, all the queries have executed and results are available. The neat thing is that FB.Data bundles the queries so that, even though the last two queries depend on the result of the first one to execute, the browser only does one request. Facebook limits the number of results returned from queries on the stream table (which stores status updates and similar). Passing a clause on ‘updated_time’ seems to arbitrarily increase this number.

So now that we have the uid’s of all the attendees, how do we get the friend-relations between those Facebook users? Generally, Facebook won’t give you the friends of a random user without your app first getting permission from said user. Facebook will tell you whether any two users are friends and this is done by querying the friend table. So I wrote this little query which handily gets all the relations in a set of uids. Assume you’ve stored all the uids in an array:

var uidstring = uids.join(",");
var friendquery = FB.Data.query(
	'select uid1, uid2 ' +
	'from friend ' +
	'where uid1 in ({0}) and uid2 in ({0})'
	, uidstring
);

FB.Data.waitOn([friendquery], function () {
	// do something with the relations, like draw a graph
});

Neat huh? The full script can be found here: http://friism.com/wp-content/uploads/2010/11/nmdscript.js

Facebook Open Graph at ekstrabladet.dk

(This post is a straight-up translation from Danish of a post on the Ekstra Bladet development blog)

Right before the 2010 World Cup started, ekstrabladet.dk (the Danish tabloid where I work) managed to get an interesting implementation of the new Facebook Open Graph protocol up and running. This blog post describes what this feature does for our users and what possibilities we think Open Graph holds. I will write a post detailing the technical side of the implementation shortly.

The Open Graph protocol involves adding mark-up to pages on your site so that Facebook users can ‘like’ them in the same way that you can like fan-pages on Facebook. A simple Open Graph implementation for a news-website might involve markup-additions that let users like individual articles, sections and the frontpage. We went a bit further and our readers can now ‘like’ the 700-800 soccer players competing in the World Cup. The actual liking works by hovering over linkified player-names in articles. You can try it out in this article (which tells our readers about the new feature, in Danish) or check out the action-shot below.

When a reader likes a player, Facebook sticks a notice in that users feed, similar to the ones you get when you like normal Facebook pages. The clever bit is that we at Ekstra Bladet can now — using the Facebook publishing API — automatically post updates to Facebook users that like soccer players on ekstrabladet.dk. For example “Nicklas Bendtner on ekstrabladet.dk” (a Danish striker) will post an update to his fans every time we write a new article about him, and so will all the other players. Below, you can see what this looks like in peoples Facebook feeds (in this case it is Lionel Messi posting to his fans).

Behind the scenes the players are stored using a semantic-web/linked-data datastore so that we know that the “Lionel Messi” currently playing for the Argentinian National Team is the same “Lionel Messi” that will be playing for FC Barcelona in the fall.

Our hope is that we can use the Open Graph implementation to give our readers prompt news about stuff they like, directly in their Facebook news feeds. We are looking at what other use we can make of this privileged access to users feeds. One option would be to give our users selected betting suggestions for matches that involve teams they are fans of (this would be similar to a service we currently provide on ekstrabladet.dk).

We have already expanded what our readers can like to bands playing at this years Roskilde Festival (see this article) and we would like to expand further to stuff like consumer products, brands and vacation destinations. We could then use access to liking users feeds to advertise for those product or do affiliate marketing (although I have to check Danish law and Facebook terms before embarking on this). In general, Facebook Open Graph is a great way for us to learn about our readers’ wants and desires and it is a great channel for delivering personalized content in their Facebook feeds.

Are there no drawbacks? Certainly. We haven’t quite figured out how to best let our readers like terms in article texts. Our first try involved linkifying the terms and sticking a small Facebook thumb-icon after it. Some of our users found that to ruin the reading experience however (even if you don’t know Danish, you might be able to catch the meaning of the comments below this article). Now the thumb is gone, but the blue link remains. As a replacement for the thumb, we are contemplating adding a box at the bottom of articles, listing the terms used in that article for easy liking.

Another drawback is the volume of updates we are pushing to our users. During the World Cup we might write 5 articles with any one player appearing in them over the course of a day and our readers may be subscribed to updates from several players. Facebook does a pretty good job of aggregating posts, but it is not perfect. We are contemplating doing daily digests to avoid swamping peoples news feeds.

A third drawback is that it is not Ekstra Bladet that is accumulating information about our readers, but Facebook. Even though we are pretty good at reader identity via our “The Nation!” initiative, we have to recognize that the audience is much larger when using Facebook. Using Facebook also gives us superb access to reader social graph and news feeds, something we could likely not built ourselves. A mitigating factor is that Facebook gives us pretty good APIs for pulling information about how readers interact with content on our site.

Stay tuned if you want to know more about our Facebook Open Graph efforts.

Transatlantic Facebook application performance woes

Someone I follow on Twitter reported having problems getting a Facebook application to perform. I don’t know what they are doing so this post is just guessing at their problem, but the fact is that — if you’re not paying attention — you can easily shoot yourself in the foot when building and deploying Facebook apps. The diagram below depicts a random fbml Facebook app deployed to a server located in Denmark being used by a user also situated in Denmark. Note that Facebook doesn’t yet have a datacenter in Europe (they have one on each coast in the US).

fbservers

The following exchange takes place:

  1. User requests some page related to the application from Facebook
  2. Facebook realizes that serving this request requires querying the application and sends a request for fbml to the app
  3. The app gets the request and decides that in order to respond, it has to query the Facebook API for further info
  4. The Facebook API responds to the query
  5. The application uses the query results and the original request to create a fbml response that is sent to Facebook
  6. Facebook gets the fbml, validates it and macroexpand various fbml tags
  7. Facebook sends the complete page to the user

… so that adds up 6 transatlantic requests pr. page requested by the user. Assuming a 250ms ping time from the Danish app-server to the Facebook datacenter this is a whopping 1.5s latency on top of whatever processing time your server needs AND the time taken by Facebook to process your API request and validate your fbml.

So what do you do? Usually steps 3 and 4 can be eliminated through careful use of fbml and taking advantage of the fact that Facebook includes the ids of all the requesting users friends. Going for an iframe app is also helpful because it eliminates one transatlantic roundtrip and spares Facebook from having to validate any fbml. A very effective measure if you insist on fbml, is simply getting a server stateside — preferably someplace with low ping times to Facebook datacenters. There are plenty of cheap hosting options around, Joyent will even do it for free (I’m not affiliated in any way).

Using WCF to power Facebook feedstory forms

UPDATE: I think Facebook has changed the API so that links in full stories have to be split into src and href parts.

Several parts of the Facebook developer API requires application developers to furnish JSON web services that feed data to various actions. These include feed forms (“I want to stick something on my wall”) and the publisher to name a few. This post will descripe how that JSON can be generated through Windows Communication Foundation web services. You can see this code in action in the simple Louisefy application. Note that alternatives certainly exists (I recommend Json.NET), but now that we have WCF, why not use it?

(As Rune points out in a comment below, you can use the object-hierachy in the code to generate compliant JSON even if you’re using Json.NET instead of WCF).

As far as feed forms go, the developes pre-register a range of templates for the kind of stories they want their users. A set of templates that get fed to Feed.registerTemplateBundle might look like the following:

List oneLiners = new List() {
	"{*actor*} is <a href=\"{*linkurl*}\">{*linktitle*}</a> {*target*}s Facebook",
};
List shortTmplts = new List() {
	new Dictionary() {
		{"template_title","{*actor*} is <a href=\"{*linkurl*}\">{*linktitle*}</a> {*target*}s Facebook"},
		{"template_body","."}
	},
};
Dictionary fullTmplts = new Dictionary() {
	{"template_title","{*actor*} is <a href=\"{*linkurl*}\">{*linktitle*}</a> {*target*}s Facebook"},
	{"template_body","{*swf*}"}
};

The FBML markup to get a feed form that lets users publish on their friends feeds would look like this:

<form fbtype="multiFeedStory" action="http://link.to/myfeedhandler.svc">
Start typing names of your friends:
<fb:multi-friend-input />
<input type="submit" label="Louisefy your friends feeds" />
</form>

The code for the actual feedhandler follows below, with the web.config stuff at the very bottom. I really like the terse, declarative syntax — there’s not a single hint that this all becomes JSON at some point. Note that if you need to pass arguments to your feedhandler, they’re very easy to map in the UriTemplate. I generally find WCF services to be fiendishly complex to get up and running because of the dearth of good tutorials and documentation — but once you get them going, it’s pure joy.

[ServiceContract]
[AspNetCompatibilityRequirements(RequirementsMode = AspNetCompatibilityRequirementsMode.Allowed)]
public class feedHandler
{
	[WebInvoke(ResponseFormat = WebMessageFormat.Json,
	BodyStyle = WebMessageBodyStyle.Bare,
	Method = "POST",
	UriTemplate = "/friendsfeed")
	]
	[OperationContract]
	public FeedResponse GetResponse()
	{
		return new FeedResponse
		{
			method = "multiFeedStory",
			content = new Content
			{
				feed = new Feed
				{
					template_id = "1234",
					template_data = new TemplData
					{
						swf = "",
						linktitle = "Louisefying",
						linkurl = "http://apps.facebook.com/louisefy/",
						images = new FeedImage[]
						{
							new FeedImage
							{
								src = "http://foo.bar/my.png",
								href = "http://apps.facebook.com/louisefy"
							}
						},
					}
				},
				next = "http://apps.facebook.com/louisefy",
			}
		};
	}
}

[DataContract]
public class FeedResponse
{
	[DataMember]
	internal string method;

	[DataMember]
	internal Content content;
}

[DataContract]
class Content
{
	[DataMember]
	internal string next;
	[DataMember]
	internal Feed feed;
}

[DataContract]
class Feed
{
	[DataMember]
	internal string template_id;

	[DataMember]
	internal TemplData template_data;
}

[DataContract]
class TemplData
{
	[DataMember]
	internal FeedImage[] images;

	[DataMember]
	internal string swf;

	[DataMember]
	internal string linkurl;

	[DataMember]
	internal string linktitle;
}

[DataContract]
class FeedImage
{
	[DataMember]
	internal string src;

	[DataMember]
	internal string href;

}

web.config:

<system.serviceModel>
	<behaviors>
	  <endpointBehaviors>
		<behavior name="Popcorn.feedHandlerAspNetAjaxBehavior">
		  <webHttp />
		</behavior>
	  </endpointBehaviors>
	</behaviors>
	<serviceHostingEnvironment aspNetCompatibilityEnabled="true" />
	<services>
	  <service name="Popcorn.feedHandler">
		<endpoint address="" behaviorConfiguration="Popcorn.feedHandlerAspNetAjaxBehavior"
		  binding="webHttpBinding" contract="Popcorn.feedHandler" />
	  </service>
	</services>
</system.serviceModel>

Server based real-time face detection in Flex

This post will demonstrate the feasability of face detection in web cam feeds grabbed by a flash/flex application. It’s inspired by a prototype of Martin Speelmans, informed by my work with Flash and web cams and my experiments with OpenCV. The basic premise is that a flex application running in a users browser grabs web cam shots, compresses them and sends them to a server. The server decompresses the picture, does face detection on it, and sends the result back to the client. All fast enough to give the user a relatively smooth experience. A fairly impressive Actionscript 3 face detection implementation exists, but my guess is that — barring a quantum leap in Adobe compiler technology — it’s gonna be a few years before fast, reliable Actionscript 3 face detection is feasible in Flash Player. Silverlight may be a different story, but it doesn’t support web cams yet.

The first prototype was implemented in Flash since I refused to program in XML (which you tend to to in Flex) as a matter of principle. When it turned out that Flash doesn’t support web services, I relented and changed to Flex. The parameter marshalling code that Flex Builder generates turned out to be too slow for low latency operation tough and was dumped in favour of a HttpService. The server part is implemented in ASP.Net, with C# calling EmguCV wrapped OpenCV. The code is at the bottom of the post.

The client goes through the following steps:

  1. Setting up the UI, getting the web cam running, setting up a timer to tick three times a second.
  2. On timer ticks, a shot is grabbed from the web cam.
  3. The picture is scaled to 320×240 pixels. The scaling is handled is by native library code and takes a few milliseconds.
  4. The picture is converted to grayscale. OpenCV facedetection only operates on one colour channel anyway and grayscale images compress better. The colour transformation is handled by more native library code and also takes just a few milliseconds.
  5. The picture is then PNG encoded. An encoder lives in the mx.graphics.codec namespace and at ~150ms for a 320×240 pic, it’s pretty fast. The resulting bytearray is around 60kb.
  6. The bytearray is base64 encoded which takes around 100ms.
  7. Finally the bytearray is sent to the server along with a sequence number. The server returns the sequence number so that the client can make sure it doesn’t use old, out-of-sequence results.

Upon receipt of a post, the server does the following:

  1. The request string is base64 decoded to a bytearray.
  2. A bitmap is created from the bytearray and made into a EmguCV grayscale image.
  3. The faces are indentified with a Haar Cascade detector
  4. The results, along with some performance information and the sequence number, are returned to the client as XML

Total server-side time is around 150ms with almost all of it spent in the face detection call. The client can do whatever it want’s with the face information — my demonstration projects a bitmap on top of detected  faces in the video feed. Total roundtrip time is less than half a second at three frames a second on a non-bandwith constrained connection in the same city as the server. This is probably enough to give relatively passive users the illusion of real-time face detection. I’ve also gotten positive reports from testers in the US where latency is higher.

I experimented with zlib compression instead of PNG encoding but the difference in both space and time was marginal (PNG uses zlib so that shouldn’t be too surprising). Instead of grayscaling the image, I also tried yanking out just one colour channel from the 32bit RGBA pixels, but iterating 320x240x4 bytearrays in Actionscript was dead-slow. Ditching http in favour of AMF and using AMF.Net or FluorineFx on the server may improve latency further.

What is point if all this you ask? A haven’t the foggiest idea really, but it’s good fun. You can certainly use it to create very silly facebook applications. You could conceivably use it to detect the mood of your users by determining whether they are smiling or not. Is this usable in a production scenario? Hard to say. The current server is a 3.5GHz Celeron D — a right riceboy machine. With one user hitting it, the CPU is at 20-30% utlization, suggesting it’ll tolerate a few concurrent users at most. Getting a proper machine and installing Intel Performance Primitives would probably help a lot. If you really meant it, you could run the OpenCV part on a PS3 or on a GPU.

Download the important parts of the code here.

Facebook signature generation in .Net

While the Facebook Developer Toolkit handles most of the needs of your average Facebook application, there is not support for the Post-Remove stuff that happens when users decide to remove your application. When your application is removed by a user, Facebook submits a “Post” in the the general direction of a url you’ve specified. The post contains a “fb_sig_user” with the relevant userid and the naive developer would remove this user from their database. That — however — would make the application vulnerable to an attack where a bad guy would hammer the post-remove form with request containing random userid, causing you to falsely believe these users have removed your application.

Below is some code that computes the proper signature that you can use to compare against the one Facebook sends along with the request. The crypto-parts were lifted from the guts of the Facebook Developer Toolkit. The process of computing the signature is described here.

public static string GenerateSignature(NameValueCollection formParams, string secret)
{
	string[] keys = formParams.AllKeys;
	Array.Sort(keys);
	string prefix = "fb_sig_";

	Dictionary dict = new Dictionary();
	var dictInit = keys.Where(k => k.StartsWith(prefix))
		.Select(k =>
			new { key = k.Substring(prefix.Length), val = formParams.Get(k) });
	foreach (var p in dictInit) { dict.Add(p.key, p.val); }

	var signatureBuilder = new StringBuilder();

	// Sort the keys of the method call in alphabetical order
	List keyList = ParameterDictionaryToList(dict);
	keyList.Sort();

	// Append all the parameters to the signature input paramaters
	foreach (string key in keyList)
		signatureBuilder.Append(String.Format(CultureInfo.InvariantCulture,
			"{0}={1}", key, dict[key]));

	// Append the secret to the signature builder
	signatureBuilder.Append(secret);

	MD5 md5 = MD5.Create();
	// Compute the MD5 hash of the signature builder
	byte[] hash = md5.ComputeHash(
		Encoding.UTF8.GetBytes(signatureBuilder.ToString().Trim()));

	// Reinitialize the signature builder to store the actual signature
	signatureBuilder = new StringBuilder();

	// Append the hash to the signature
	foreach (byte hashByte in hash)
		signatureBuilder.Append(hashByte.ToString("x2", CultureInfo.InvariantCulture));

	return signatureBuilder.ToString();
}

Here’s some code that uses the method:

string sig = GenerateSignature(Request.Form,
	ConfigurationManager.AppSettings["FACEBOOK_SECRET"]);
if (sig == Request.Form["fb_sig"])
{
	string fbuid = Request["fb_sig_user"];
	if (fbuid != null && fbuid.Length > 0)
	{
		// Remove user
	}
}