Feeds

Facebook rides Unicorn to graph search nirvana

Data-guzzling index tech unfazed by billions of likes

Next gen security for virtualised datacentres

Facebook has given details on "Unicorn," the technology that makes its needle-in-a-haystack query engine Graph Search possible.

The company revealed Unicorn in a post to its Facebook engineering blog on Wednesday.

Unicorn is an inverted index that can theoretically handle queries with "hundreds" of operands (aka, the things wot go into a query), Sriram Sankar, Facebook's lead for search quality and ranking, told The Register.

"The Unicorn infrastructure strength is searching for entities based on attributes about these entities you can get. It is very different from a SQL database," Sankar said. "Unicorn can be used to look up any table, like a hashtable can – but that's not a perfect use of Unicorn. You'd use Unicorn when you have a bunch of keys."

Without Unicorn, Facebook's "screw you, Google & Microsoft" Graph Search tech would be achingly slow.

Anything that can be done in memcache can also be done in Unicorn, Sankar said, though in most use cases memcache would have greater performance.

Unicorn can index "nodes" – anything with a Facebook ID, like a place, person, photo, post – and "edges," which are the actions that can be performed to link these objects, like check-ins, friendships, and tags.

"One way to think of this is if the graph were represented by language, the nodes would be the nouns and the edges would be the verbs. Every user, page, place, photo, post, etc. are nodes in this graph. Edges between nodes represent friendships, check-ins, tags, relationships, ownership, attributes, etc," a trio of Facebook engineers wrote in a blog post on Wednesday.

Typical Facebook searches let you search by the metadata associated with things, like the name of a tagged person. The Unicorn index makes it possible to search across objects and edges, so you can stalk find people nearby who like The Register, for example.

What makes the Unicorn index impressive is it allows Joe Public to query a dataset that consists of billions of different points, and it can do this across multiple nodes without taking a year to spit out the data.

Once a week, Facebook feeds the Unicorn with a giant batch of new information, and the index ingests smaller bits of data throughout the week. 2.5 billion new pieces of content are added to Facebook every day, along with more than 2.7 billion "likes," adding up to tens of billions of new data points and relationships per week.

When Unicorn indexes an object, say a new user with the name Vulture Lohan, it would store Vulture with one id number, Lohan with another, and Vulture Lohan with its own special number.

When a user makes a graph search query, the list of results is winnowed down by static ranking according to relevance at each stage. Most users are likely to make queries that only require a couple of steps, but anything is possible if you can put up with the latency, he said.

"Our infrastructure allows you to do any level of nesting [but] it grows lineally in latency," he said.

The kinds of systems Facebook is developing to deal with its vast kingdom of likes, tedious funny photos, and subtly veiled insults and/or brags posing as status updates, may seem overkill for other companies, but as the amount of data generated by people explodes, these technologies will have more and more relevance.

Big supermarket chains, streaming media companies, and logistics firms would like to get their hands on this kind of tech, we think, and we're fairly sure that Unicorn is the type of index that spooks have either already developed, or are busily trying to replicate.

It's also exactly the type of system that wannabe-social networks will have to build if they want to maintain feature parity with Facebook.

But it could be a while before Zuckerberg releases his Unicorn into the wild: the company has no immediate plans to make the technology open source, Sankar said, though it will publish an academic paper that gives more information on the tech "in due course." ®

The essential guide to IT transformation

More from The Register

next story
The Return of BSOD: Does ANYONE trust Microsoft patches?
Sysadmins, you're either fighting fires or seen as incompetents now
Microsoft: Azure isn't ready for biz-critical apps … yet
Microsoft will move its own IT to the cloud to avoid $200m server bill
US regulators OK sale of IBM's x86 server biz to Lenovo
Now all that remains is for gov't offices to ban the boxes
Death by 1,000 cuts: Mainstream storage array suppliers are bleeding
Cloud, all-flash kit, object storage slicing away at titans of storage
Oracle reveals 32-core, 10 BEEELLION-transistor SPARC M7
New chip scales to 1024 cores, 8192 threads 64 TB RAM, at speeds over 3.6GHz
VMware vaporises vCHS hybrid cloud service
AnD yEt mOre cRazy cAps to dEal wIth
El Reg's virtualisation desk pulls out the VMworld crystal ball
MARVIN musings and other Gelsinger Gang guessing games
prev story

Whitepapers

Implementing global e-invoicing with guaranteed legal certainty
Explaining the role local tax compliance plays in successful supply chain management and e-business and how leading global brands are addressing this.
7 Elements of Radically Simple OS Migration
Avoid the typical headaches of OS migration during your next project by learning about 7 elements of radically simple OS migration.
BYOD's dark side: Data protection
An endpoint data protection solution that adds value to the user and the organization so it can protect itself from data loss as well as leverage corporate data.
Consolidation: The Foundation for IT Business Transformation
In this whitepaper learn how effective consolidation of IT and business resources can enable multiple, meaningful business benefits.
High Performance for All
While HPC is not new, it has traditionally been seen as a specialist area – is it now geared up to meet more mainstream requirements?