Joe Hellerstein's Databeta

I'm not sure if you're trolling here:

> The CAP theorem has been beaten.

> As you are about to see, a system like this not only beats the CAP theorem, but annihilates it.

The CAP theorem states that you can't have all three of strong consistency, partition tolerance, and availability at once. This is a proven fact (http://www.cs.cornell.edu/courses/cs6464/2009sp/papers/brewer.pdf).

I don't see how your proposed system provides strong consistency. Eventual consistency is not strong consistency. Let's pretend the HDFS deployment in your batch workflow is partitioned from the rest of the system: sorry, but you won't be able to get strongly consistent data from it, and you'll have to either read stale data or simply block until the partition ends. This is pedantic, the CAP theorem is pretty specific.

Now, if you're saying something about the eventual consistency of logically monotonic facts in the system (see the CALM conjecture, now theorem: http://databeta.wordpress.com/2010/10/28/the-calm-conjecture-reasoning-about-consistency/), which I think you are, then I agree that you have a system providing (even provable) eventual consistency. The basic idea is that if code is logically monotonic, meaning the set of facts it operates on continues to grow over time, then it will obey eventual consistency properties. If I'm not mistaken, your notion of "immutable data" is equivalent to restricting programs to operate on logically monotonic data (in your examples, this is…

Right; you need some notion of a total order or commutativity in your update functions. f(A,B) = f(B,A). "Last writer wins" is one example of commutativity, but that isn't often what you want.

What you want is something like a "Commutative Replicated Data Type" [1], where you define a commutative function specific to your application. Libraries like StateBox allow you to build CRDTs [2]. In fact, your example of document editing was one of the areas where these ideas first came up.

There's also a theorem saying that if your program is "logically monotonic"--that is, if your data only "grows" in size, and facts never change from True to False or vice versa--then your program will work under eventual consistency without modification [3].

Finally, bank accounts have to employ eventual consistency. Banks demand availability from their ATMs and give up consistency to handle partition tolerance: your ATM will still work even if you sever its network connection. However, banks, unlike a lot of software, have well-defined compensation protocols for handling inconsistency. For example, they'll charge you for negative balances left in your account via overdraft fees.

[1] http://arxiv.org/pdf/0710.1784.pdf

[2] http://labs.mochimedia.com/archive/2011/05/08/statebox/

[3] http://databeta.wordpress.com/2010/10/28/the-calm-conjecture-reasoning-about-consistency/

The primary author is Joseph Hellerstein, head of the Berkeley RISELab (the new Spark/AMPLap). Their primary project is called Fluent (which until recently was called Anna [4])...it's the all encompassing name changes that get ya! ;-)

Similarly, see Matei Zaharia's (the original Spark lead) and his team at MIT (he's now at Stanford) SIGMOD 2018 paper called MISTIQUE [4]...

[1] Joe Hellerstein https://github.com/jhellerstein

[2] Berkeley RISELab https://rise.cs.berkeley.edu https://github.com/ucbrise

[3] Fluent Compute Platform https://github.com/fluent-project/fluent

[3] Anna: A Crazy Fast, Super-Scalable, Flexibly Consistent KVS https://databeta.wordpress.com/2018/03/09/anna-kvs/ Discussion: https://news.ycombinator.com/item?id=16551072

[4] MISTIQUE: A System to Store and Query Model Intermediates for Model Diagnosis
https://cs.stanford.edu/~matei/papers/2018/sigmod_mistique.pdf

I assume Lineage Driven Fault Injection stuff [1] has some overlap with Eve's ability to tell you "Why is this blank?": The datalog model allows you to find the logical dependencies of results.

Some other bloom related links:

- Anna KVS[2] showed up recently on hacker news[3] and morning paper[4]

- Lasp lang is in the same space[5], Christopher Meiklejohn has a comparison with bloom[6]

[1]: https://disorderlylabs.github.io/#

[2]: https://databeta.wordpress.com/2018/03/09/anna-kvs/

[3]: https://news.ycombinator.com/item?id=16551072

[4]: https://blog.acolyer.org/2018/03/27/anna-a-kvs-for-any-scale/

[5]: https://lasp-lang.readme.io/

[6]: http://christophermeiklejohn.com/lasp/2018/03/02/lasp-vs-bloom.html

Not just aggregating writes, but merging them.

It seems that high load high scale solutions [1] [2] start to converge on this idea of merging updates and eventual consistency.

[1] https://arxiv.org/pdf/1708.06423.pdf

[2] https://databeta.wordpress.com/2018/03/09/anna-kvs/