Ruminating on BSON vs JSON

MongoDB uses BSON  as the default format to store documents in collections. BSON is a binary-encoded serialization of JSON-like documents. But what are the advantages of BSON over the ubiquitous JSON format?

In terms of space (memory footprint), BSON is generally more efficient than JSON, but it need not always be so. For example, integers are stored as 32 (or 64) bit integers, so they don't need to be parsed to and from text. This uses more space than JSON for small integers.

The primary goal of BSON is to enable very fast traversability i.e faster processing. BSON adds extra information to documents, e.g. length prefixes, that make it easy and fast to traverse. Due to this the BSON parser can parse through the documents at blinding speed.

Thus BSON sacrifices space efficiency for processing efficiency (a.k.a traversability). This is a fair trade-off for MongoDB where speed is the primary concern. 

Types of NoSQL data stores

There are essentially 4 types of NoSQL databases that are getting popular. As architects, when we consider polyglot persistence it's important to understand the pros and cons of each NoSQL type and then select the best fit for the given problem context.

1. Key-Value stores: Redis, Riak
2. Column Family stores (Aggregate-oriented): Cassandra, HBase
3. Document oriented databases: MongoDB, CouchDB
4. Graph databases: Neo4J

A good article comparing all these datastores is available here: http://kkovacs.eu/cassandra-vs-mongodb-vs-couchdb-vs-redis.  Another good article that compares these stores against the CAP theory is here: http://blog.nahurst.com/visual-guide-to-nosql-systems

Martin Fowler's infodeck on NoSQL is also worth a perusal. 

Ruminating on Bloom Filters

Of late, I have been trying to understand "Bloom Filters" and the reason why they are used in many popular NoSQL datastores such as Cassandra, HBase, etc.  Even Google Chrome brower uses it to match URLs of malicious sites.

So what exactly is a Bloom filter? A Bloom filter is a data-structure; essentially a byte array (aka byte vector). Using a bloom filter, we can quickly test for the containment of a particular element in a given set. For e.g. Suppose you have a set of 100K URLs that are malicious. How do you check if the entered URL belongs to the list? You can store all the 100K URLs in memory and iterate through them, but that would be expensive in terms of CPU cycles and memory requirements.

A Bloom filter is a very simple and efficient way to test for containment - with a one-sided error probability. What this means is that if the Bloom filter states that an element is NOT present in the list, then it is 100% true. But if it returns true for the containment test, then it means that the element "MAY" be there; i.e. you could have the risk of a 'false positive'. You can design your Bloom filter data structure in such a way, so that you can predict the probability of 'false positives'; for e.g. 3% probability in a set of 100 million entries. Hence a bloom filter can return 'false positives' but cannot return 'false negatives'.

With the above understanding, you can guess why Bloom filters are popular with NoSQL data-stores. It is used to quickly check whether a row exists in the database or not, before going for disk-access.

The following articles would give you a quick understading of how Bloom Filters work:
http://billmill.org/bloomfilter-tutorial/
http://www.michaelnielsen.org/ddi/why-bloom-filters-work-the-way-they-do/

In a nutshell, in simple terms the following steps are taken:

1. Take a byte array (all elements of the array set to 0)
2. For each element in your set, do the following:
• Hash the element k times (with different hash algorithms). Let's say you hashed it 2 times and the values were 7 and 10. Set the bits at these indexes in the byte array to 1. 
• Do this for all the elements in the set. Thus you would end up with the byte array (Bloom filter) having 0s and 1s scattered around. 
3. Now to test whether an element is present in the set of not, we hash the element using the same hash functions. Now check if there is a 1 or 0 in the Bloom filter at those index positions. If there is a 0, that means the element is definitely not in the list. If there is a 1, then the element may be there and you can proceed with the costly disk-access or service call. 

This stackoverflow discussion also has a good explanation of how bloom filters work.
Google's popular Guava library aslo has a Bloom Filter class that be used in Java projects. The trick is to select the right size of the byte array and the hash functions to use for excellent performance.
.NET implementations are available here and here. 

Ruminating on MongoDB concurrency

In my previous post, I had discussed about the transaction support in MongoDB. Since MongoDB implements a ReadersWriter lock at the database level, I was a bit concerned that a writer lock for a long query may block all read operations for the time the query is running.

For e.g. If we fire a mongoDB query that updates 10,000 documents that would take 5 mins. Would all reads be blocked for the 5 mins till all the records are udpated? If yes, then that would be disastrous.

Fortunately this does not happen, due to lock yielding as stated on the MongoDB site.
Snippet from the site:
"Write operations that affect multiple documents (i.e. update() with the multi parameter,) will yield periodically to allow read operations during these long write operations. Similarly, long running read locks will yield periodically to ensure that write operations have the opportunity to complete."

Read locks are shared, but "read locks" block write locks from being acquired. Write locks prevent both other writes and reads. But MongoDB operations yield periodically to keep other threads waiting for locks from starving. An interesting blog post that shows stats on the performance of MongoDB locks is available here.