jaksprats

Two phase commit (in spanner) is similar to a lock, so the short answer is YES you need locks for distributed TRANSACTIONS

But you dont need transactions to do distributed computation. This is where CRDTs come in, they allow you to modify data locally w/ zero wait and the replication of these modifications happens asynchronously (imagine a split second later) and then there are algorithms that run on the receiver of the replication that automatically and intuitively resolve any conflicts that happened because the data was not (globally) locked

I will have a post next week on serverless.com explaining the internals of CRDTs, it should help clear stuff like this up.

This is a very good question but its also a leading question :)

Datanet provides a level of abstraction such that business logic does not need to be framed in commutative operations rather you just do normal data manipulation on JSON objects and under the covers there is a bunch of commutative operation magic.

CRDTs data guarantee is called strong eventual consistency (SEC), so they are not fit for certain use cases (e.g. take $10 out of accountA and atomically put it in accountB), but the vast majority (~70%) of use cases can be accomplished w/ SEC guarantees (google Peter Bailis' work).

If you can explain a specific business case I can show you how to determine if it is OK to do in SEC

Link is back up as of 12:30 PDT

in the redis community we have also discussed having a daemon sitting next to the server and doing localhost redis communication. The downsides to doing this are it introduces an extra piece to break. W/ luajit2, which is almost as fast as post-JITted Java, the speed of the scripts are amazingly fast (Salvatore's current method of calling the scripts is dead on, it requires no interpretation, it maps directly to lua_p* calls).

Disclaimer: I wrote AlchemyDB, embedded lua in redis a while back and have played w/ it constantly (it is robust and mind bogglingly flexible).

As for the speed differences of embedded lua vs a daemon sitting next to the server, Alchemy has its test suite in Lua and some tests I run via an external client, and some tests I run internally via embedded Lua. The speed difference between client/daemon and embedded lua becomes VERY evident (10X faster) on large loops, where I/O and TCP kernel time are saved ... but as redis is single threaded server, scripts block the server during their execution, so it is just dangerous for novice programmers.

All in all, if redis embeds lua correctly, it will really open up the project and it is a very minimal bloat, lua is tiny, and it is just one command :)

that will work (as good as can be hoped for).

the process can be thought of as a map-reduce. first pass would be figure out where all your SETs are located and how big they are. then intersect all co-located SETs. then (in parallel) take smaller SETs and MIGRATE them towards larger SETS, intersect those and repeat (respecting new sizes). A pyramid of SET intersection can be done until the result is the final two SETs being intersected, a process will need to coordinate all of this, but luckily intersections are idempotent, so if one parallel job finishes quicker, it doesn't need to wait.

W/ redis speed, the overhead (for the coordinator) to get the size of the different SETs in all these steps should be minimal as compared to the time taken to MIGRATE the data (meaning for-free). Also w/ redis' speed the MIGRATE will be very fast and the cross-node-join (or cross-node-intersecton) bottlenecks on network I/O, so if a good framework for this redis map-reduce is created, it will be a pretty optimal setup, and it wont bloat the server w/ tasks that can not be done directly in the server (cross-node-intersections are done at something more like a proxy level, they require intermediate results).

this problem is a hard one, data analytic stores optimise to this problem by storing data redundantly w/ a "pre-joined" colocation strategy, which works for star schemas and a limited number of tables, but doesnt make sense w/ 1000s of SETs, so this is a real good solution and classic redis anti-bloat.

I am the author of Redisql and I wrote a blog post today explaining the concepts behind Redisql (a RDBMS on top of the NOSQL datastore redis) http://jaksprats.wordpress.com/2010/09/28/introducing-redisq... The original idea was to have a single roof to house both relational data and redis data and both types of data would exhibit similar lookup/insert latencies under similar concurrency levels. And then I added simple commands to convert redis data into relation tables and vice versa, and I made many memory optimisations, etc... the result hopes to be the complete datastore solution for applications that require the fastest data lookups/inserts possible

what are you using as backend? mysql? postgres? couchdb? redis?