Is It Time For NoSQL 2.0?

New submitter rescrv writes "Key-value stores (like Cassandra, Redis and DynamoDB) have been replacing traditional databases in many demanding web applications (e.g. Twitter, Google, Facebook, LinkedIn, and others). But for the most part, the differences between existing NoSQL systems come down to the choice of well-studied implementation techniques; in particular, they all provide a similar API that achieves high performance and scalability by limiting applications to simple operations like GET and PUT. HyperDex, a new key-value store developed at Cornell, stands out in the NoSQL spectrum with its unique design. HyperDex employs a unique multi-dimensional hash function to enable efficient search operations — that is, objects may be retrieved without using the key (PDF) under which they are stored. Other systems employ indexing techniques to enable search, or enumerate all objects in the system. In contrast, HyperDex's design enables applications to retrieve search results directly from servers in the system. The results are impressive. Preliminary benchmark results on the project website show that HyperDex provides significant performance improvements over Cassandra and MongoDB. With its unique design, and impressive performance, it seems fittng to ask: Is HyperDex the start of NoSQL 2.0?"

Comments

Berkeley DB?

[gstoddart]

This sounds like the old Berkeley DB/Sleepy Cat software.

Key/Value pairs instead of relational stuff. Worked with a product years ago that was built on Berkeley -- offered some pretty useful features that simply didn't map to object-relational stuff.

For some applications, you really do need something that works a little differently than an RDB ... however, there's still loads of things I can't imagine trying to do without one.

Choice is good in technology.

Re:Berkeley DB?

[unholy1]

Indeed - BerkleyDB was NoSQL before NoSQL was cool!

Why not both?

[Sarten-X]

Er...

Um...

Why not learn both, and use whichever's strengths suit the application the best?

Re:Why not both?

[Sarten-X]

NoSQL is a terrible misnomer, in that the difference is far more than just "doesn't use SQL", and there are NoSQL systems that do actually support SQL. It's really just referring to data storage systems that aren't based on relations. That change in paradigm has its advantages (speed (in some cases), scalability, and flexibility) and disadvantages (speed (in some cases), lack of consistency, less restriction on bad programming). Of course, each NoSQL system tries to mitigate the disadvantages, and each RDBMS tries to prove itself better than all of NoSQL's advantages. It's a big fun party involving lots of mud-slinging.

Most NoSQL systems I've worked with are distributed hash tables, in a basic sense. Each value has a key, and that key determines where it's stored on a cluster. Values are not tied to any other values, so things like "foreign-key relations" are silly in a discussion of NoSQL. Rather, the algorithm to retrieve the data does all of the processing to connect data, using massive parallelization across a cluster to handle huge amounts of data at once.

With a traditional RDBMS, the application must fit its data to the schema completely before any data can be stored. This, of course, means that all data in the database can be assumed to be complete. You won't find references that don't exist, which makes queries straightforward.

With NoSQL, the database is treated as a more flexible bucket. Data is dumped in with a key, with little concern for fitting the design of the application's model. This, of course, means a bit more planning at design time, but the data can be arranged to better fit whatever it actually represents. Some details are present, and some aren't, but that's okay. The retrieval algorithm (typically a MapReduce program) should check for the existence of whatever data it needs, and handle errors accordingly. Those MapReduce programs are far more complicated than a simple SQL query, but the database's backend is conceptually simpler as an abstract key/value store. Key/value stores have been around for decades, and studied extensively. They can be made more fault-tolerant and scalable than RDBMS shards, but lack the support for large set-based comparisons.

The comparison to the BASIC-vs-C battles is appropriate. Both BASIC and C serve their purposes well (education and system programming, respectively), but neither should be used where the other is better suited. NoSQL and RDBMSs also both have their places.

Re:Why not both?

[w_dragon]

Thank you for a concise summary of the difference between the 2 systems. I must say though that such informative and level-headed comparisons have no place in a slashdot discussion ;)

Re:Why not both?

[justforgetme]

(speed (in some cases), scalability, and flexibility) and disadvantages (speed (in some cases), lack of consistency, less restriction on bad programming).

You have a background in Lisp right?

Re:Why not both?

[Sarten-X]

(not (know (I) (meaning (you))))

Re:Why not both?

[Anonymous Coward]

So that's good at finding the record if you already know the key, but there's no help in finding a record if you don't know the key

Most NoSQL databases have indexes, and the indexes can be searched to find the key(s) you need. As an example, straight from the MongoDB examples:

db.things.find({colors : {$ne : "red"}})
{"_id": ObjectId("4dc9acea045bbf04348f9691"), "colors": ["blue","black"]}

In other words "find all the objects which do not contain 'red' in the field 'colors'". The ObjectId that is returned happens to be the key.

Re:Why not both?

[jd]

NoSQL 1.0 is usually not much more than a hash-accessed flat-table database. GDBM, QDBM and BerkeleyDB are all hash-accessed flat-table databases. The refinements mentioned as being added to NoSQL databases (such as searchable indexes) are simply sequential indexes that associate some indexed parameters with the hash value.

NoSQL generally works by you pushing an item into the database and getting one or more hash values back. You want the item back, you give the database the hash values and you get the item. Object-oriented and object-based NoSQL both work by allowing objects to point to other objects. This gives you inheritance. (Basically you have a hash value that points to another record, where the structure of that other record is fixed rather than chosen at run-time via a join statement.)

Basically, database theory describes all the various forms of database you can have: flat-file, hierarchical, network, relational, object/relational, relational, semi-structured, associative, entity-attribute-value, transactional and star (aka data warehouse). A description of some of these can be found here.

This describes how the data is actually laid out, but does NOT necessarily describe how the data is accessed.

Database theory also describes the following underlying methods of accessing data: sequential, indexed, hash. Any combination of these is permitted, so you can have an index that points into sections of a database that are then searched sequentially for example. Or you can have indexes that point to other indexes that in turn point to a hash value. And so on.

SQL is just a meta-language that allows you to apply a restricted form of set theory on the underlying access methods. There were arguments at the time SQL appeared that it should allow all of set theory - and those arguments still go on, with some SQL alternatives using actual set theory notation as opposed to SQL notation.

NoSQL, in some cases, is just direct access to hash tables for directly accessing items. In other cases, it's a lightweight abstraction layer.

In the example advertised in the summary, an object is referenced through a set of indexes. If you have a partial set of indexes, you reference multiple objects but they will be related in some way. There is nothing X.0 about it, it's just a NoSQL database that uses a network database topology rather than a flat-file topology. It is nothing new.

I recognize that marketspeak is what sells things, that calling the systems by what they actually are would not be nearly as impressive to managers. Managers do not, as a rule, read Slashdot. Geeks and Nerds read Slashdot. Geeks and Nerds know Database Theory. (Well, if they don't, they damn well should -- either that, or they can use Google to look the terms up.) The two additions to database theory in the past 30 years have been the Object-Relational and Object-Oriented models.

Re:Why not both?

[Frnknstn]

A hierarchy IS a relationship. In a hierarchical databases, child segments and parent segments were the main kind of relationship used.

All relational databases did was allow the relationships to be more freely defined.

Further to that, a key / value pair is also a relationship, in that the key symbolically represents the data. That's why it is correct to call them NoSQL databases: They forgo the complexity of a general query language. In doing so, they also lose the ability to inherently store anything except the most basic relationship: the key / value lookup.

Re:Why not both?

[shentino]

Yeth

Re:Why not both?

[lysdexia]

I concur! Shocking really. Gentlemen! Seize that miscreant's pants!

Re:Why not both?

[Terrasque]

I've just gotten my NoSQL feet wet by playing around a weekend with python + mongodb. I am pretty used to SQL, and generally had the same thinking you (and most other SQL people) had.

But, many people liked it, so I figured out I should at least have a look at it. I made a small webapp for tracking my movies, with query to imdb and with users. I was surprised to see that most of the problems I anticipated wasn't a problem at all, and things mostly just worked naturally. For a quick get-started intro to python + mongodb : Part 1 and Part 2. If you got the spare time and some interest, poking around with it is a great little weekend project.

Anyway, back to your question. MongoDB store data in a format very similar to JSON (technically BSON, a JSON superset), if you're familar with that. Unordered key->value and ordered lists. For the python driver, it translates the data to and from native python dict/list structures. I started with three fields; filename, added and imdb. The imdb field was more or less the raw data from imdb (json format, decoded to python native and encoded to mongodb's BSON format again.)

Later on I added option for users to mark movies as favorites and seen (by adding two new fields to movie list, "seenby" and "favoriteof" - both lists - these were added to a movie entry the first time someone marked one as seen or favorite). To add a new user I just did movie["seenby"].append(user_id) and movies.save(movie)

When I wanted to query the db, I created a data structure of what I wanted, and sent that to the server. The server would then return all documents that matched that example structure. So, to find the entry for file "/bla/test.mp4" I would do movies.find( {'filepath': '/bla/test.mp4} ).

For finding by imdb Title value : {'imdb.Title': '300'}. For finding all favorites by user: {"favoriteof": user_id} (yes, it would handle the list of users as you'd expect, and find all that the list of "favoriteof" had user in it. It would also of course skip all entries without that field).

mongodb also support some special keywords for searching. Let's say I have a list of 3 users, and want to have all movies that any of them have favorited. {"favoriteof" : {"$in": users} } would fix that - for movies that all of them have as favorite, {"favoriteof" : {"$all": users} }. Sorting was done using sort_by( field_n_direction_list )

You have a full list of modifiers here. And all could of course be combined to quickly and easily create powerful queries. And you of course have options for indexes. You might notice that you do lose something from normal SQL's here, if you wanted both movie and user info, you'd have to make two queries (well, from what I've understood) so highly relational data is not fitted for this. Also, you don't have the type constraints any more.

In the app I also wanted to list all movie genres (I did one preprocessing of the imdb data, splitting up comma seperated genres string to a list of genres) and number of times each genre was used. This led me to mapreduce, which was the thing I both anticipated most, and feared most. Well, I kinda chickened out, since the pymongo doc had an excellent example which was exactly what I wanted doing, but I did get a look at it at least :) And it was fast enough to not making a noticeable dent in load time for a few hundred movie entries.

*Cough* well, that was a long post.. I hope it helped you at least a bit in answering your question, and maybe inspire you to take a closer look at it when you get some spare time. I've only used it over a weekend, so I've probably just scratched the surface, and I probably have missed some neat features or horrible gotchas here and

wake me in a few years

[joss]

http://www.youtube.com/watch?v=URJeuxI7kHo

is the best introduction to this subject I've seen. Until someone can explain the pros of hyperdex with a funny video featuring cute animals I'm sticking with technology that's been tested more thoroughly.

Re:wake me in a few years

[Sarten-X]

Decisions based on cute animals and straw-man arguments without any facts... You must be a manager!

Wow! That's some neat Progress!

[VortexCortex]

The hashing system is pretty neat. The idea that you could get at records without their specific key via search criterion is astounding.

In the future more advanced hashing systems will allow NoSQL databases to extract a set of records all containing a similar subset of data without keys at all!

Of course we'd need a name for the sections that are matching. Perhaps "Columns", yeah, then each result returned could be called a "Row", makes sense. I bet you could then create even more complex matching patterns for multiple "Columns" against each record in the data-set. If only there was a language to describe query we're sending to the servers... Oh! Server Query Language!

I can't wait to use SQL with NoSQL 3.0!

Re:Wow! That's some neat Progress!

[Sarten-X]

And we'd still be able to have the cluster support, scalability, lax schema, and MapReduce algorithms NoSQL currently provides, right? Sometimes those aspects are vital to the application design, and key to the system's overall performance.

Re:Wow! That's some neat Progress!

[Sarten-X]

[citation needed], and preferably one that actually covers NoSQL as it's intended for use.

Last time I checked thoroughly (2009), most RDBMSs (MS SQL Server included) could scale across an arbitrarily-large cluster, but for every doubling of the cluster's power, the costs would be around 300% to 400%. When you get to the point of needing billions of rows per table (and yes, there are applications out there that need that, even at relatively small startups), those outpacing costs become prohibitive.

The lax schema isn't about not knowing what you're doing, but about acknowledging that you won't know everything about the data you'll receive. Back when I did server programming, the mantra was "be strict in what you provide, and lax in what you accept". This is that principle applied to databases. Maybe the website you're crawling doesn't have a title, or its address is obviously dynamic. Maybe the medical record's patient has seven different insurance providers. Maybe the passport holder legally doesn't have a surname. When you design a schema for a strict database like an RDBMS, you make certain assumptions about the data you'll get. Those assumptions lead to performance increases if they're accurate, and failure if they're wrong.

MapReduce is the key to performance without assumptions, at lower cost. By moving processing to the data, and replicating the data to multiple nodes, network transfer is reduced greatly. The MapReduce programs are designed to operate on any amount of data they are presented with, so each node in the cluster contributes its available resources, and since the data is spread evenly, most "queries" will be partially processed by every node. Contrast that with RDBMS sharding, where certain servers handle certain shards, and the massive parallelism of the cluster isn't used. Some servers will sit idle while others do all of the work. Note that the parallelism applies generally, to all MapReduce algorithms. This means that you do not need to make as many assumptions about your queries ahead of time, like expecting to only look up a customer by name or phone number (and therefore indexing those).

NoSQL isn't just "not using SQL". It's a different storage paradigm, which comes with its own advantages and disadvantages.

Re:Wow! That's some neat Progress!

[binary paladin]

Another brilliant post on Slashdot!

The quality of responses around here improve every day.

Re:Wow! That's some neat Progress!

[afabbro]

300 - 400%? Lol you're doing it wrong. Billions of rows? So what? Easily handled by SQL.

CERN has a database with trillions of rows in a traditional Oracle RDBMS. I saw a presentation on it at Oracle OpenWorld this year by a guy from CERN..

Yahoo also has trillion-rowed databases, on PostGreSQL.

Great for Perl aficionado...

[Spectre]

Many of the key-value pair DBs supply a Perl library that let you tie a Perl hash (%Variable) to the DB directly, giving you persistent hashes.

Makes database storage virtually a native feature of the language. Anybody who uses Perl is probably already a hash buff, so it is a win-win if you and your app already use Perl.

Disclaimer: I run a 10yo web "app" (Perl/CGI/Apache), so I'm a bit biased. But, the thing is rock-solid, so I'm not going to be too apologetic.

Locally sensitive hashing

[Animats]

This is a type of index, not a type of database. See locally sensitive hashing. It's an efficient way to find keys which are "near" the search key in some sense.

Such a mechanism could be provided in a key/value store or an SQL database. It's even possible to do it on top of an SQL database. It's more powerful in a database that can do joins, because you can ask questions with several approximate keys.

This is an area of active research. Many machine-learning algorithms are scaled up by locally sensitive hashing, so they can work on big data.

Re:Keys and values?

[Korin43]

Isn't that what XML is for? XML files are also compatible across systems.

XML is more useful for transferring data between systems. For storing data is kind of sucks, since there's no indexes (not the kind we need for fast lookups anyway) and it's extremely verbose.

Re:Branding

[donscarletti]

It's great branding.

Previously, I was developing MMO backend software that uses MySQL for a data storage. The fit to the model was completely inappropriate, there was just no applications of the relational model, since we were just checking in and out large blobs of data, not actually performing read/update transactions. Storing records (persistent game entities) as files in a directory would have worked far better than forcing that stuff into a relational DB. But customers know that Databases are what professionals use, so we did it anyway. Clients can buy it, realise they need the flat files and turn them on after benchmarking, we get the sale, they get a good product in the end, win win, but a bit of wasted effort.

Now NoSQL is what professionals use, relational DBs can be used for what they are good at and NoSQL gives us marketing hype for doing certain things in the right way that could have been done using filesystems all along. I couldn't be happier. Furthermore we get this nice application level distributed data store with map-reduce stuff built in if we can be bothered using it.

Here's what most geeks don't get about marketing: it's not just about being smarter than the other guy, you've got to be smarter than him and make him give you his money. Money is good, it buys freedom and power and if branding makes sure that you have more of this freedom and power than the fool who falls for it, then the world will be a better place.

Re:NoSQL 2.0

[Sez Zero]

Yeah, all the hipsters will be calling it "No2SQL", which is way more righteous.

Re:Only 2.0?

[kangsterizer]

Or NoSQL 16 if that was Google. What a great joke.