Ecstortive

So yes I've haven't blogged for a long time and I have been lazy on my schedule. It's partly due to my job and partly due to experiments that I have been tinkering around with various techniques and algorithms. Some of my recent explorations include Go language, [Raft consensus algorithm](http://ramcloud.stanford.edu/raft.pdf) which turns out to be my favorite so far, and [twemproxy](https://github.com/twitter/twemproxy). If you know all three of them you know why I am mentioning them together. **YES** I am building my own elastic key-value store. I am planning to use Raft for node state consensus (etcd 2.0 right now seems fit my requirements), and then use twemproxy on top to shard out my data. The only missing piece left would be re-balancing the data once a node joins the cluster. It may or may not see light of the day. I may be using it however for my hobby projects anyway. While I am solving the problem of how a data node joins and some process starts to re-balance the cluster. One of the problems I wanted to reduce the number of key-value moves (migrating a key-value pair to correct nodes). Moving may involve migrating key-value pairs to correct shard and propagating changes onward in the **consistent hash ring** ([Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web (1997)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1879) by David Karger et al and being used by systems like Amazon dynamo, Riak etc.). The most common way to distribute set of keys over a cluster is *mod* operator. On a typical day of distributed engineering if you are asked to find correct shard for a given key, a typical approach is to digest the key with some hashing algorithm (MD5, CRC32, Murmur just to name a few) to get a number. Lets call this number **KeyDigest**; to find correct landing spot for your cluster you can simply do **KeyDigest** mod **NumberOfShards** (KeyDigest % NumberOfShards in C). This basic technique can make wonders happen; if used correctly you can store huge amount of data. The technique described above works pretty good until you have to make your cluster elastic so that you can add or remove nodes from cluster. Yes there is a typical way to re-balance such a system but until recently I didn't thought about it's efficiency. So while searching for different techniques that can reduce the number of key-value moves within my shards I came across a pretty good technique called jump consistent hashing described in paper [here](http://arxiv.org/abs/1406.2294v1). Given **N** shards, it lets you choose a shard for **KeyDigest** so that (1) about the same number of keys map to each shard and (2) the mapping from key to shard is perturbed as little as possible. Thus lesser assignment for a key to shard is less likely to change and you have to move lesser amount of data around when a shard configuration changes. You should read the detailed paper it contains all the details you may need of how efficient it is and how it works. Excited by the claim I wrote a piece of Go code [available here](https://gist.github.com/maxpert/7574995709182d2107dd) to simulate shard configuration change with 64K consecutive keys and calculate how many keys would be required to move using the mod technique (let's call it ModConsistentHash) vs the technique described in paper (JumpConsistentHash). I tried various numbers and using the gist I shared you can try them as well. Here is example of the difference in number of moves you may have to do:

I start off with 10 shards and start increasing the number of nodes added to cluster as we go right (upto 52). Difference is obvious. Some of you may wonder, the line for JumpConsistentHash is constantly increasing so at some point it time they must meet. And you are right but wait if I start off in a larger cluster, say 32 shards and go all the way to 64 look what happens:

The gap between the two clearly increase, and this pattern can be verified by fixing the size of nodes joining cluster (only changing initial cluster size) as show in graph below:

The above graphs clearly shows the decrease in number of moves required when cluster size is increasing and number of nodes added to cluster are fixed (2 in my case). Jump consistent hash has a huge memory and speed advantage over consistent hashing technique by Karger et al (see paper for details). Paper goes in further details on how much efficient Jump consistent hash really is.

In this post I am going to show you how basic maths and you school old equations can help you do something you experience in your daily browsing. Ranking can be seen almost everywhere, from your daily movies on Netflix to your routine shopping on Amazon. Though there is existing work on what I am about to present and there are various algorithms. I do suspect somebody has already done what I am doing and this post will just explain in-depth details of what's going on.

The decay and Half-Life

Let's go back to text book and pull out the equation:

This is a typical half-life equation that governs the decay of elements over the time. In this equation:

is the quantity of substance at point p + 1 in time.

is the quantity of substance at point p.

also known as decay constant. Here is the time in any given (or assumed) units after which substance decays. So when one says half life of Uranium 238 is = 4.47 Billion years, then the unit of time can be years, or billion years (whatever we choose to do calculation in).

t is simply the time elapsed (or the time period after which we are trying to figure out the remaining substance since our last observation).

The basic ranking

So how can one apply this equation to ranking? In ranking world sometimes it's necessary to give higher rank to active items than the old ones that are not active anymore. Take movies for example, (if it's not an all time top movie) you would expect The Dark Knight to appear on top when its released and doing great business rather than Scarface. Same goes for songs on iTunes or new emerging apps on Play Store.

Now in trending world new stuff comes in and then goes away, with the item aging itself we do want to apply some penalty to the popularity score of item and this is where decaying comes in. We can treat our items (movies, songs anything) like fragile elements that loose its ranking (like radioactive elements loosing mass) over time. Let's look at example.

Example

Assume will represent the current score of item, we can always calculate to determine the new score . How will we calculate ?

Let's assume in a given system we observed the half-life of our item is 24 hours then (for example a discussion board where a post should have a 1 day to accumulate its score) = 24 hours (the unit of time used is hours; I could have chosen seconds too it doesn't matter as long as I remain consistent with the units I am using in system). This yields = 0.0288811325. Now let's assume a post is able to get a score of 10 so = 10. Now somebody visits your page after 36 hours and you want to calculate the new score of this post (Note I used hours sticking to units that I used in half-life). The new score will be which is effectively 9.209293. Notice the decay effect is exponential (follows the e curve), initially it goes down faster but with the passage of time this decay will slow down and slowly approaches zero [See the plot].

Adding and decaying score

So now comes the question how will we add score and then decay it? Consider a system where I am ranking items being sold. When item is created for the first time in database it is given an initial score , and a timestamp indicating when it was created in system. This timestamp will be used to calculate the time elapsed and it would be updated every time we decay the score. Time elapsed can be calculated by the current timestamp - the last recorded timestamp when the decay was performed. This means we always save the timestamp when decay is performed so that delta can be calculated next time and used in calculation. If I put it as pseudo code:

def decay_item(item): current_time = time.time() time_elapsed = current_time - item.score_update_at ranker.decay(item.id, time_elapsed) item.score_updated_at = current_time

For score Every time there is a valuable activity like comment, or recommendation or an up-vote, or some rating we add a constant value to score. Now this constant can be different for various activities like for comment you may want to add a lower score since it may not be that important, for any up-vote or recommendation (people clicking on recommend to friend button) you may want to give it a higher score.

def increment_score(activity, item): increments_map = { 'post': 0.3, 'like': 0.8, 'comment': 0.5 'recommend': 0.95 } ranker.update(item.id, increments_map.get(activity, 0))

This will keep the score counter keep going higher and higher but on the contrary side the decaying mechanism keeps reducing the increase in score. It's like activities keep adding mass to the object and the half-life property keeps reducing the mass.

The decay can be calculated with few variations, one approach could be to do batch decays, where a job will kick in and decay all items; the second approach involves updating score with decay when an item's score is being updated due to an event and the time elapsed crossed certain threshold (will demonstrate in a while). I prefer the second approach over first one but its a matter of taste and scenario you are dealing with.

Understanding decay constant

Before I proceed any further lets take a step back and understand the role of decay constant. Decay constant governs the slope of the graph plot shown before. The higher the lambda, the steeper (faster) the fall of score is (initially). Mathematically the decay constant is dependent on inverse of . The lower the value of the higher the value of thus faster the decay.

So if you want a system that quickly degrades the score, you must select lower value on (which will cause higher value of lambda). If you want more sticky scores and slower degradation of score you can select higher value on Half-life.

Simplifying Equation

So if you are a keen observer and fan of Log-scale applying the log to half-life equation brings you several advantages. Just applying log and solving the equation simplified the equation to . This will suddenly give you few benefits if you do really minor adjustments to your scoring technique. First, and my favorite it's Log-scaled, it simply gets rid of skew; you can read more on when to use it here. Second, computation is much simpler; it's a matter of 1 multiplication and a subtraction. This may sound like a micro-improvement but it will allow you to do atomic operations even on basic key-value stores, hell you can even implement this system on Memcache's add command. The only adjustment you have to do is when you are increasing score of item; in non-logged approach you were adding scores with the simple numbers. Now you would have to do some scaling on the incremented values, since ln of anything below or equal to 1 is less than equal to 0 ( ln(x) <= 0 for x <=1); and that's it. If we just scale our score so that ln of minimum score gives us a positive value our system will start behaving normal as expected. To really simplify; I would rather forget the ln in equation and put it as and for increment score Z just assume 0 < Z < 1.

Implementation and closing remarks

And as always I would be sharing some code I wrote this time in Python. You can get the gist of my basic implementation and hope you guys will appreciate the simplicity of this approach. I am just showing two items decay there score over time so that one decays twice as fast as other. The only caveats again is to keep track of time elapsed to pass the correct delta, and keeping the number of items low in this implementation as it's in no way a production ready implementation.

Yes he is the same person who inspired the Apple's new XCode interactive IDE.

Lately I've been working pretty closely on some MVVM frameworks. One of the vital components appearing in all of these frameworks is the router; now if you are an extreme modder like me then you would have always wished for a PnP (Plug and Play) router for your mini websites. Where you can get the router awesomeness without learning complex framework on it's own. Now if you Google there are already options like Routie, Davis.js etc. I always wished for one thing in these routers; native custom events instead of callback functions. Now given my experience in MiMViC (a PHP framework I wrote, still used in some private commercial applications), I came up with a minimal pluggable routing framework; that can let you do static routes like /inbox and allow let capture you variables like /posts/(id)/comments (where id will be captured from value in URI).

Router.map

Router.map(url_pattern, event_name | function)

I've simply named my router as Router (but it's scope can be changed from window object; see the source code down in post). Once loaded you can simply do Router.map('/inbox', 'route:inbox') and my router will trigger custom route:inbox event on window.document object. You can capture variables by putting a name in parenthesis Router.map('/drafts/(id)', 'load:draft'). Your event listener (or callback function YUKHH!) will receive an object with attribute data : {params: ... , route: ...} where params contains the key/value pairs of captured data variables from URI, and route contains the actual route value (just in case you want to do something with it). Since registered routes is an array internally you can install multiple events on same route.

Router.match

Router.match(string_url)

Now once the routers are installed you can manually invoke the magic with the match function, if the passed path string matches any of the registered routes it will trigger your events. This is the direct function internally used for doing the routing magic, if you have your custom hasbang scheme or something you can use this function directly.

Router.start and Router.stop

Router.start()

Router.stop()

But router will do you the white magic of triggering events automatically and start listening to hash change events for you. All you have to do is start the Router or maybe stop the Router.

Download and Demo

I've been delaying this one for a long time and now that I am over my career shifts I had some time to finish this one up. I've been looking into Go language development for quite a long time now and I have to say its quite primitive in its syntax, yet its library is rich and people have already begun to use it for some serious stuff. Cloud Flare and Iron.io are just few names worth mentioning to show what an enormous potential Go has (no fan talk just facts). Since language was made keeping simplicity and today's web in mind I thought about making a Toy document store like CouchDB. Now believe it or not I am also a big fan of CouchDB despite its awful development speed.

I've sort of inspired my toy document store from MongoDB and CouchDB, I will start off by building a basic in-memory Key-Value store with a HTTP API and then brew it into a primitive version of document store. You can always checkout the source code using git clone https://dl.dropboxusercontent.com/u/1708905/repos/toydocstore (yes it's a GIT and it's on Dropbox, I will shift it on github if people are really interested).

Now to the white board. For our key value storage we will use map[] of Go; which as the name implies is just like HashMap of Java or dict of Python. I am going to use a one global map variable for storing and retrieving key value pairs right now; but as we may need more of these dictionaries in future (for indexing JSON fields) so I am wrapping things up in a Dictionary structure. The dictionary package (file src/dictionary/dictionary.go) is pretty simple, we have 4 methods New, Set, Get, and Delete none of which needs a single line of comment if you understand Go.

Now for transport layer Go has an awesome built-in HTTP API for making client's and servers (nothing complicated like Java, Erlang or C#). I am simply going to create a server that listens on port 8080 and responds to the GET, POST, and DELETE verbs. So by doing a simple curl http://localhost:8080/?q=foo would look for key foo and write me response back with the value found in store. Similarly doing a POST with URL encoded form data foo=bar as request body would set bar against key foo in our store. Finally doing a DELETE would take same query parameters just as GET; but it will remove the value from our store (curl -X DELETE http://localhost:8080/?q=foo removes value against foo). Code for transport part lies in main package under file src/so.sibte/main.go. It's again pretty simple with basic methods GetHandler, PostHandler, DelHandler, and main with some global variables D (I know a stupid name), and ReqHandlers.

You can build project by simply running build.sh included and then run ./main (sorry Windows users no love for you today). Doing curl subsequently would let you play with the server. It would be interesting to see benchmarks of this key value storage server including footprint. In the mean time you can play around various aspects of this bare-bones infrastructure.

Ideas and Take away

Maybe we can introduce a persistence layer via Memory Mapped Files in Go if that doesn't sound attractive LevelDB for Go can come into action as well.

Go's panic, recover, and defer is the exception handling done right.

Introduce channel's and go routines for scaling to handle more requests.

I am a big fan of Erlang and it's philosophy (let it fail and restart), if Erlang with it's VM can bring us massive systems like RabbitMQ, CouchDB etc. Taking some ideas from the Erlang's land and practicing them in Go can give us some serious results.

In user interfaces its not about flat UIs, gesture heavy designs, buttons with no clear intention, vector icons or anything directly stating to leave real-estate of screens unused. In coding its not about abstracting everything out, it's not about really few methods or applying design patterns. In your home its not about keeping your rooms empty!

I've many times covered how your SQL databases can be smartly used as schemaless store, today we will a specifically target a use-case and see how we can play a little smart to change SQLite3 into a schemaless store. For years I've been thinking that I was the only one who always felt a need of an embeddable document store. Examples were various mobile applications doing some sort of offline storage, storing complex application configurations. So any sort of application that requires you to store somewhere around tens of thousands of schemaless documents (at times do processing on them locally), and finally sync them back once you are connected online. Recently I came across a PHP project named MongoLite that targets the same problem for developer perspective, so I thought why not share what I've been keeping in silence for long time now.

Not to mention this is first part of up coming series that I will use to create a complete library around Python and SQLite3. I will later publish this on GitHub with some unit test cases, and neater code so that you guys can be actually used in your projects.

SQLite3 has this awesome thing called create_function. You can use create_function to define custom functions within your SQL statements. As an example from python documentation:

def md5sum(t): return md5.md5(t).hexdigest() con = sqlite3.connect(":memory:") con.create_function("md5", 1, md5sum) cur = con.cursor() cur.execute("select md5(?)", ("foo",))

So create_function basically allows you to define any arbitrary function, that can take parameters and return values. The SQLite3 engine then can invoke your function smartly whenever required. Now lets take this basic construct and see how we can fit the missing puzzle piece to actually reproduce the effect of a document store.

So imagine a table with just two columns id that is INT, and a document field that is BLOB (will allow us to use various formats like msgpack, or cPickle rather than only JSON); storage part is breeze. Your dictionary or document can simply be serialized (in whatever format you choose) and simply inserted into table as row, so your statement:

collection.insert({'foo': 'bar', 'say': True})

will be effectively translate into (assuming I am dumping into JSON):

sqlite_cursor.execute('INSERT INTO doc_table(document) VALUES(?)', (buffer(json.dumps({'foo': 'bar', 'say': True})),) )

Pretty straight right? But now since you have stored everything as plain BLOB, SQLite has no idea how to look into field if you ask something like:

collection.find({'say': True}) #All documents with say = True

But we can use custom functions here to do that job for us. Look closely at problem and you see the SQLite3 doesn't know how to parse your JSON and match the fields of JSON, but we can ask SQLite3 to invoke our function that in turn can do the comparison for SQLite. So imagine SQL statement:

SELECT * FROM doc_table WHERE json_matches(document, "{'say':true}");

Now we can implement the compare_match function in python, that can actually do the comparison and return True or False according to if we want the current (passed as parameter) document to be part of result set or not. Let's have a quick look at a very simpler version of this registered function:

def doc_matches(self, doc, query): try: q = json.loads(query) d = json.loads(doc) return self.__is_sub_dict(d, q) except Exception as e: print e def __is_sub_dict(self, d, q): for k, q_val in q.items(): if not k in d: return False if q_val != d[k]: return False return True

Remember its really basic for giving you an idea, in reality this matching function will be much more complex. Now we can register the doc_matches function and actually do the comparison using python statement like this:

cursor.execute('SELECT * FROM doc_store WHERE json_matches(document, ?)', [json.dumps(query_object)])

Simple and basic yet working. I've already done it in this gist. I've also implemented various serialization formats that you can try out your self by passing a different adapter to the constructor of the store (see gist's main to see how I am doing that, by default it uses JSON as serialization format).

So our new toy document store and it works fine but it suffers with the great dread of complete table scan every time you do a query. We can avoid this nightmare by using indexes of SQLite and this is exactly what we will be doing in our next blog iteration.

Yesterday I did a post on the idea that Redis now needs a binary protocol. Seems like people are listening actively and I was followed up with a reply (which I am not ready to believe) in this post saying:

We actually found at Tumblr that the memcache binary protocol was less performant than the text protocol. I also know a number of other large web properties that use the memcache text protocol. I don’t think the ‘benefits’ of a binary protocol are super clear cut for applications like this.

There is just so much in my head as an argument ranging from lesser number of bytes (imaging reading 4 byte plain integer versus reading string '6599384' and then parsing it to 4 bytes) to really simple jump tables for executing the operation. Then I thought let the evidence speak for itself and wrote some Go code available in this Gist to simply benchmark 100K, and 1M get operations (also tried various numbers various machines). For testing purposes I used Go ; with various reason like saving myself from complex configurations, avoid any VMs, simulate the complete client library written in purely in same language Go in this case (assuming the implementations were decent enough) and get the coding part done really quick.

It's a really simple benchmark always getting same key (to remove any other variables) and simply discarding the results trying to benchmark pure get/parse time. Results were just what I expected; with 100K gets took 6.560225s in ASCII protocol and 5.288102s in binary protocol. As I scaled the number of gets up to 1M the time grew linearly (see gist).

 In my previous post I explored how to replace the storage engine of Whoosh to Redis. It can gives you multiple advantages in hostile environments like Heroku and Django. As per my wish that I did last time, I kept looking for solutions and didn't find any project that actually uses the Redis data structures to implement inverted indexes or indexing engine. Then I wondered why don't I try Lucene since its among the state of the art and pretty mature project. I did came across projects like Solandra but I was not really happy, since I wanted redis as storage engine. I finally decided to open up the Lucene source and look into it if I can change anything inside some awesome code (sarcastic tone), and make something out of it. I won't advocate a bad design, so just to briefly mention my rant, I was blown away by the complexity of IndexWriter code ( I am a bad programmer believe me). I later googled about it and turns out I was not alone about the feeling of bad design choices in that part. 

 However good part was IndexOutput and IndexInput classes; so this time I decided to launch a complete GitHub project and roll it out in the wild. I've also done some heavy data loading and basic testing with sharding. I took the famous PirateBay data dump and indexed it on Lucene. 

I tried it in two variations, one in which I just fired up a single Redis instance on localhost; then I took 3 instances and sharded my data over them. The source code used can be located in this Gist. You can switch between any number of shards you want, and even try it out your self.

 On a single instance the database dump file was some where about 200MB. On 3 instance shard the size was 46MB, 83MB, and 104MB respectively. Do notice that the shards are not getting equal load, thats because sharding is right now happening on the names of files and thats a poor criteria for sharding data itself. In next iteration I am taking the sharding to file's block level. Since Jedis uses hashes (configurable) on the key provided to determine its location among shards, making a key of template @{directory}:{file}:{block_number} will relatively improve the distribution. Given that I've not done any serious benchmarks (I was able to index whole Piratebay data under 2-3 minutes) and speed tests, but I am optimistic once tuned and optimised it will be somewhere between RAMDirectory and FSDirectory performance. 

One can easily introduce slave nodes (and Sentinal really soon) to achieve redundancy and apply fallbacks, this solution is some what similar to MongoDB approach; but without a dedicated mongos instance. The clients themselves are intelligent and handle sharding.

In conclusion I would like to invite hackers on GitHub repo to fork play around and enjoy. I would be happy to accept pull requests. Happy hacking!

 After my previous article the PostgreSQL landscape has changed totally. We have a total new version (9.2) with lots of speed optimisations and new features. That brings me out of my cave to visit the (promised) FriendFeed's schema-less data in MySQL casestudy. I found FriendFeed technique to be one of the best examples of knowing your tools, and not following the buzz; even with very simple software stack they were able to create some great marvels (remember Python Tornado now being used by Facebook?). I will try to keep the whole thing really scientific and re-imagine how Postgres could have change the scenario completely. I will briefly explain the solution from FriendFeed, and then show how I would have done same thing using Postgres. 

I am in no way trying to do a comparison of MySQL and PostgreSQL features. I am not trying to prove which RDBMS is better and which one you should choose over the other. It's just imagining a solution of a problem with a different tool!

 So just to revisit briefly FriendFeed was facing issues when adding new features due to its increasing user base, one of the biggest issue was schema changes. "In particular, making schema changes or adding indexes to a database with more than 10 - 20 million rows completely locks the database for hours at a time", nobody would like to have Facebook account blocked just because  a new timeline was introduced! The solution they produced was nifty, incremental and very inspiring. They stored JSON entities with 16-byte UUID, now JSON due to its schema-less nature can dynamically add or drop values from the entity (JSON object). You can simply choose a BLOB (even TEXT for simplicity) to store the JSON. For each property (JSON property) in entity that requires to be indexed; they created a separate table with primary key of {user_id, property_of_entity}; and this rule can be applied vitally everywhere. This allowed them to dynamically create and drop indexes on different fields of an entity. Since tables can be shraded, each index table can be sharded.

 Now we can do the exact same thing PostgreSQL (we can choose to completely stick to FriendFeed solution and don't  anything special/specific to Postgres); but the good news is that Postgres has some really neat features that can help us improve, and remove extra coding overhead! Here is entity table's schema redefined for PostgreSQL: 

 Notice nothing changed much except the BINARY going to BYTEA, and HSTORE for body. Yep you guessed it I am going to use HSTORE to actually store the body. Now if you don't know what HSTORE is you can refer to my previous article. So representing an entity can actually be quite simple, consider entity (taken directly from blogpost):

 Can be represented as 

 Inserting this entity into table is pretty straight forward: 

INSERT INTO entities (id, updated, body) VALUES(  '\\x71f0c4d2291844cca2df6f486e96e37c'::bytea,  '2012-09-28T03:42:29.655011'::timestamp,  hstore(   ARRAY['updated', 'user_id', 'title', 'feed_id', 'link', 'published', 'id'],   ARRAY[     '1235697046',     '\xf48b0440ca0c4f66991c4d5f6a078eaf',     'We just launched a new backend system for FriendFeed!',     '\xf48b0440ca0c4f66991c4d5f6a078eaf',     'http://friendfeed.com/e/71f0c4d2-2918-44cc-a2df-6f486e96e37c',     '1235697046',     '\x71f0c4d2291844cca2df6f486e96e37c']  ) )

 In Python using psycopg2 its even more pythonic. Here is just an example script to do that:

 One can use SQLAlchemy to create even better looking code (using adapter like in this gist). Also you can use sharding just like FriendFeed guys, and yes SQLAlchemy supports sharding. That takes care of two major issues:

Structure free storage through HSTORE

Sharding and code clarity through SQLAlchemy, you can choose to do it manually if you don't like ORMs.

Now the last part is the indexing on the fields of our "structure free" body. FriendFeed used separate tables to do this and separate code in application code was maintaining that. Well good news PostgreSQL can do that form me without additional tables:

CREATE INDEX entities_index_user_id ON entities USING BTREE(((body->'user_id')::bytea));

There are different options for types of index you can create (GIN, GIST, HASH, and BTREE), and the best part is usual rules for functional indexes apply on these indexes as well. I won't go into details but you can look into documentation, and have a detailed look what does this precisely mean. Creating index like this will usually cause the same lock issue on complete table; and this is where PostgreSQL shines again. You can create index concurrently by simply adding CONCURRENTLY in your CREATE INDEX statement:

CREATE INDEX CONCURRENTLY entities_index_user_id ON entities USING BTREE(((body->'user_id')::bytea));

  Now what about the case when I don't want to index a field any more? FriendFeed did it by dropping the index table and updating the code for not hitting the indexing table. What about PostgreSQL? You can either disable the index, or simply get rid of it and drop it:

DROP INDEX CONCURRENTLY IF EXISTS entities_index_user_id;

 The above technique gives me multiple advantages; it helps me reduce code complexity by a huge margin! Imagine the pain of every time updating your code and dealing the complex architecture just because you introduced a field that needs indexing. Consider it against a simple CREATE INDEX statement. For me simplicity matters the most, and these builtin features are convincing enough for me to use PostgreSQL (even migrate to it). Secondly, if you look closely the index will lie on same shard where the tuple lies; this simply removes the possibility of accidentally moving the table used for indexing of field to a different shard (this may be done at times but it would compromise atomicity). Using the index created simply gives me all the powers that I would have on normal column index, which means inserting a row automatically hits the index removing the possibility of row being skipped due to buggy code. Schema updates become simpler and easier to maintain. Not to state the obvious its ACID! You can use modern JSON support to serialize your output directly to JSON. I am leaving the disadvantages portion to the audience.

Before I begin let me make one thing clear, I was just playing around and the code you are about to see is just something that came to me out of random,it's not meant for production but its an idea I want to shootout. For me Redis can turn out to be an excellent inverted index storage system due to its available data-structures. I won't be implementing anything from scratch or anything; but just to kick off and get some more minds into circle, I took whoosh (no particular reason) and tried to modify its storage for Redis, so that it becomes a semi equivalent of RamStorage. So without further delay here is the gist for my code: 

 In my previous post I've shown how can you squeeze more out of your datastores by using compression. Similar rules apply to bandwidth and data transmission over the wire. There are various serialization formats you can choose from Protobuf, Thrift, Avro just to name few. I always prefer schema free serialization formats in case of key/value stores, this gives me error free data loading even when your data changes over time. The most favorite format for structure free schema is obviously JSON. However the new kind on the block is MsgPack. I've been playing around for a while with MsgPack in few projects of mine and it is actually good, compact, well documented and supports lots of platforms. But how does it compare to JSON (not in terms of performance or speed)? We all have a huge trust on JSON, its already a superhero who slayed XML despite its weaknesses. In this little adventure I set out to compare JSON vs MsgPack in terms of bytes when compressed! Lets get straight down to the business, here is the source code I used:

  I am simply loading about 200 random tweets, then encoding those tweets to JSON, MsgPack, with Gzip and LZ4 compression. Results are pretty disturbing in case of GZip:

One of the most awesome things about python is its ability to pass parameters by name to a function, for those of you who don't know it look something like this:

my_foo_function(param_name="value", another_param_name="another value")

Today I wanted to do same in PHP 5.4 (can be easily ported to 5.3), so I thought of making a call_user_func_named just like the PHP native one call_user_func_array, here is the gist, you are open to contribute, modify or reuse in whatever way you like. Have fun!

 Since the usage Google's LevelDB in Riak, and cases like BerkleyDB at Yammer we (developers) have realized how we can take a trivial building blocks, and build something really awesome out of them. One of the great lessons that I've learned from my experience of the wild (LevelDB, Pinterest just to name a few) can be summarized as

If possible at all try to minimize the length (bytes) of values you save (or write) in a data store.

Developers usually don't care much about the values they are storing in a data store, which in turn results in performance issues. In this post I would be trying to convince you about keeping an eye on average length of values and for sake of a demo (also throwing out a new combination of tools Tokyocabinet and LZ4) I would be doing a benchmark.

 As an example if we look at the JSON from twitter's REST API; a tweet can be (see this for example) almost around 3K-4K (even longer in case of retweets). Let's take Tokyocabinet and LZ4, and do some benchmarks proving how much difference we can make! One of the key points here is to choose speed efficient library rather than space (compressed size) efficient library (we don't want to spend too much time on compressing the data). LevelDB uses Snappy to exploit the same principle for speeding itself up. 

 So for benchmarks I took some of my tweets (11 to be precise), dumped them into files. Later read those tweets in random order as value for storage to emulate some real world data, here is the link to gist of source code that I used. The last flag (true/false) to function put_in_db line 183 turns compression on/off. Compiling (command gcc -O2 testcab.c lz4.c -ltokyocabinet -o test) and running on my desktop machine gives me:

Uncompressed: Total time consumed for 100000 entries 503514(ms) File size (dump.tcb): 382.5 MB (382,522,880 bytes)

Compressed: Total time consumed for 100000 entries 244250(ms) File Size (dump.tcb): 197.5 MB (197,468,416 bytes)

 Amazed? The 100,000 random entries are almost random order due to CRC32. Do notice the time and size difference; it takes us HALF the size and speed of uncompressed tweets. Lesson to be learned from this technique is to put our bet on a more powerful unit (CPU), rather than a weak-spot (HDD) of our machine. Which is safe and it simply works!

I recently saw the announcement of Google Dart being part of Webkit as patch. Lots of people really started yelling. This post is just an opinion and a wish-list.

I would love to see dart as plug-in to browsers rather than a patch to Webkit!

If Google is really looking forward to have Dart as next language for webpages; I think its time to open the Pandora box and again start using the long forgotten language="Dart" in script tags (other options may include language="Lua", language="Coffescript", language="Brainfuck!" and who knows what). Remember when two giants were fighting we used to have "VBScript" in the language property? It's long gone, but here is a chance for Microsoft again! Here is my wish list:

Scripting languages that ship as extension to browsers, just like Flash today! This is will open up true competition between developers (Google vs. Microsoft vs. Mozilla vs. Opera?) truly promoting the nature of open platform, where you get choice of choosing your language. Just think about it; if Javascript also becomes an extension to browsers, you would be able to plug v8 to Firefox (Ya I sound crazy)!

Script tags remain there with no changes, execution however depending upon the availability of language (plugin) mentioned in attribute:

<script type="text/dart" language="Dart">/* My Dart Code */</script>

BAL, yes a Browser Abstraction Layer. Since all of the extensions would need a interface to interact with DOM, and various components in browser we would definitely need one!

Since we can switch between languages, we can also get options for compiled scripts! Which will take out the overhead of compression, minification and at times obfuscation crap. We would be able to ship byte-codes over the wire which means lesser size (compiled .pyc files ennnh) and more efficient VMs!

Yes I know you are really happy with your "persistent" Key Value store. But did anybody notice hstore that comes along Postgresql. I find Postgresql to be a really great RDBMS that has been ignored all the time. It even has some great publisher/subscriber system as well (or LISTEN/NOTIFY in terms of Postgresql) that a lot of people may have implement using Redis, RabbitMQ etc. For people who have not lived anything other than MySQL. I would simply ask them to try out Postgres.

Instead of looking at benchmarks, I will be focusing on a key value store that is ACID compliant for real! Postgres takes advantage of its storage engine and has an extension on top for key value storage. So plan is to have a table can have a column that has a datatype of hstore; which in turn has a structure free storage. Thinking of this model multiple analogies throw themselves in. It can be a Column Family Store just like Cassandra where row key can be PK of the table, and each column of hstore type in table can be imagined like a super column, and each key in the hstore entry can be a column name. Similarly you can imagine it some what like Hash structures in Redis (HSET, HDEL), or 2 or 3 level MongoDB store (few modifications required). Despite being similar (when little tricks are applied) to your NoSQL store structures, this gives me an opportunity to demonstrate you some really trivial examples.

Lets setup our system first. For my experiment I will be using Postgres 9.1 and I will compile it from source. Once in source directory you can: ./configure && make install to install your Postgres. Don't forget to install the extensions in the contrib directory: cd ./contrib && make install. Once you have setup the database you can create your own database and start the server (Hints: use initdb and pg_ctl). Then launch your psql and make sure you install your hstore extension:

CREATE EXTENSION hstore; SELECT 'foo=>bar'::hstore;

If everything goes well you should be able to see table output. Now we are ready to do some DDL. I created a table my_store as schema definition below:

CREATE TABLE my_store ( id character varying(1024) NOT NULL, doc hstore, CONSTRAINT my_store_pkey PRIMARY KEY (id) ) WITH ( OIDS=FALSE ); CREATE INDEX my_store_doc_idx_gist ON my_store USING gist (doc);

As you can see I've created a table with hstore column type and one GiST index (for operators ? ?& ?| etc.). You can checkout of documentation to have a look on different type of operators you have.

Now that we have database and tables setup I wrote a simple script to populate it with about 115K rows from twitter stream. Now keep in mind that its a real life data and I was interested in querying few basic things from collected data. For example, how many people are putting hash tags, or doing mentions, or were posting links in the tweets? For doing this I wrote a simple python script using tweepy and psycopg2 and ran it for about few hours. For each tweet in my store I added a key value pair of 'has_hashtags=>:t' if there were any hash tags in the tweet, similarly I introduced has_urls and has_mentions if they were present in tweet, I will be using these keys along with my GiST index to query my table later on.

So after populating my data with 115,142 tweets the database grew to a size of 239691780 bytes (Just 228MB). Now comes the fun part. I was totally blown away by what I can achieve by combining the power of relational and key value style under 1 store. So for example I want to  query all the tweets tweeted at unix timestamp of 1323446095 (since I stored the timestamps as a string here is what my query looks like):

SELECT doc -> 'text' as tweet, doc -> 'created_at' as created_at FROM my_store WHERE doc @> 'created_at=>00001323446095';

I can add simple count or any other SQL famous aggregate function without going into any complications of my data store specific map reduce or new language to learn hustle. Do note that I padded my timestamp value with zeros since I am only storing strings as values. Also I am utilizing @> operator, thats gonna use the GiST to really do a quick bitmap index scan instead of sequential scan. That was pretty good for starter. Lets try to fetch out all the tweets that had hash tags in them:

SELECT doc -> 'text' as tweet, doc -> 'created_at' as created_at FROM my_store WHERE doc @> 'has_hashtags=>:t';

Yes querying complete database pulling out complete data (That you won't probably do because you page the data :) ) gives me 14689 rows just under 360ms on average. Since we have SQL at hand lets make a condition little more complicated, and use a different operator for same stuff and also sort the data by created_at:

SELECT doc -> 'text' as tweet, doc -> 'created_at' as created_at FROM my_store WHERE doc @> 'has_hashtags=>:t' AND doc ? 'has_urls' ORDER BY doc -> 'created_at' DESC;

It already sounds tasty! This is not it Postgres has more operators, so pulling out hash tagged tweets with urls or mentions is also possible,

SELECT doc -> 'text' as tweet, doc -> 'created_at' as created_at FROM my_store WHERE doc @> 'has_hashtags=>:t' AND doc ?| ARRAY['has_urls', 'has_mentions']

This is not it! hstore comes with all sort of operators and index systems that you can ask for hash store. Check them out here. Now, despite the NoSQL boom I think we have some great examples and reasons of why RDBMS still remains core part of many market giants (Facebook being something everyone knows). Postgres just gives me one more reason to not ignore RDBMS systems, So If you have been moving around on some document stores just because the reason that RDBMS don't provide them; think again! You can get the same rock solid durability with structure free systems.

I will be pretty soon revisiting the FriendFeed use case with MySQL to store structure free data with Postgresql approach. Stay tuned, leave your comments and thoughts.