frankmcsherry

> Yeah, I liked how he realized two possibilities for a number that were next to each other, also meant the box around it could be cleared.

This struck me as a bit weird (as he's clearly 100% sharp): this is just the application of the same rule he had been applying everywhere else: if a number can be in one of two squares than anything that can reach those two by king or knight cannot be correct. He doesn't need to use speculation about which of the two cells it is in.

Yes, I know what it will be, but it isn't really acknowledging the lack of data, is it? It turns NULL input data into a 100% false result.

Let's check out SQL's "acknowledged lack of data" in a case statement:

    create table test(a bool);
    insert into test(a) values (NULL);
    select case a when a then true else false end from test;

The answer should be NULL, right?

Haskell.

I don't think it's about giving up, but accepting that churn has costs.

Of the first 15 or so Rust releases, 4 of them caused library code I maintain (timely dataflow) to publicly break. They were all minor "paper cut" breaks that one could fix by changing the syntax, but several were in the public APIs (most were around convenience features, clashing in namespaces). The stated position of the Rust team was that it is ok to break code in this way.

I brought this up with some of the team; I do think they are more aware of it now; many are still more excited to land new things than preserve the experience of the users (I'm ok with that, but it is what it is).

Hi, I work at Materialize!

It's early days, but I can confirm that it's a bit hard to know out of the gates whether Materialize can handle such workloads. In particular, unless I missed it the query workload isn't really discussed in the post, and that is all that matters.

Druid makes a few compromises that Materialize isn't willing to make. For example AFAIK Druid doesn't support deletions or modifications in "realtime", which means they can track "min/max" style queries much more efficiently, but they lose out on some other features (connecting pipelines of these views where you might have to "retract" a prior min or max). This could certainly let it scale more, but also means that you learn a few months down the road that it doesn't do everything you hoped it would.

No joins in Druid is also reportedly a bit of a pain. Instead, you get to pre-denormalize your data. No need with Materialize (and hey, feel free to push down reductions through the joins, rather than denormalize and then reduce).

Short version, Materialize is definitely a "higher sophistication" data processing play. Whether that works out well remains to be seen! I'll slap up a blog post later today with a worked example.

In the event that it helps anyone, the following is how I think of Rust ownership stuff:

1. Ownership-based memory management is statically elided reference counting.

2. Borrowing (shared and mutable) is statically elided reader-writer locks.

The underlying compute framework, differential dataflow, supports multi-temporal timestamps. The Crux folks were at one point looking at it for Juxt, though not sure what they concluded.

DDLs that alter schemas definitely cause things to catch on fire at the moment (Debezium writes them to a side-topic, which isn't obviously synchronized with the data topics). In principle `CREATE` and `DROP` statements are things we could pass through, but some work needs to get done to pull the right information out of Debezium at the right moments (and drop the right prefixes of the existing Kafka topics if you re-create a table with the same name).

Yes, the term we're using is "Sink", dual to a Source.

    https://materialize.io/docs/sql/create-sink/

At the moment you can create Kafka sinks, and we'll write the change log out to that topic. They are still baking though, and need some hardening for failure cases.

It looks like a caching bug somewhere in the web pipeline. It isn't running on Materialize, sadly.

There are a pile of known limitations, and our goal is to be 100% clear about them.

The main distinction that led to a different name is that (unlike most instances of dynamic or incremental algorithms) differential dataflow allows you to move through a partial order of updates, rather than a sequence of updates. This is important for automatically updating iterative computations, if you want to do multi-temporal streaming computation, and a few other reasons.

It appeared at the time analogous to multivariate calculus, though the better analogy appears to be to Moebius inversion (roughly: integration and differentiation on partial orders). Read more here: https://en.wikipedia.org/wiki/Möbius_inversion_formula

"Moebius dataflow" would have been a pretty bad-ass name, I think we can all agree. And it might have done a better job of preparing the reader for what was about to happen to their brain.

Depending on what you are looking for, DDlog (https://github.com/vmware/differential-datalog) is interesting. I'm casually involved, for people weirded out by that, but it supports arbitrary changes to the input facts without recomputation.

I think you've misread the paper, which is about differentially private RAM. Differential privacy (w/o "RAM") is neither weaker nor stronger than ORAM.

I googled "kafka documention", went to https://kafka.apache.org/documentation/, searched for "queue" and found 29 matches.

Absolutely! I read the von Neumann extractor and presumed too much. For fun, you can reduce the numbers asked by getting a batch of k people, and if all numbers are dissimilar you get a draw from k!

The OP is silly though; if you know the distribution there are way better techniques. They don't seem to worry about how they measure it.

Rejection sampling isn't the best way to go.

With b bits you are subdividing the (0,1) interval into 2^b regions, and only need more bits if one of the 9 multiples of 0.1 land in the interval you've picked. As b increases this probability drops exponentially.

It's a fair point that the number of "numbers" depends on how low the entropy of the source is, but in the link the probability of collision wasn't massive.

Nonsense. It requires roughly 1+log(10) bits in expectation and has a geometric tail.

> Nitpick, but you can only sort in linear time if your sort key domain is bounded (e.g. 64-bit integers).

It is more subtle than this. Top-down radix sort (which discrimination generalizes) is linear time in the number of input bytes, rather than the number of input records. One special case is when each element has a constant number of bytes, like you mention, but it isn't the only case.

<3

Moar links!

(caveat: I am involved in many things)

1. You can implement some minor flavor of Doop in differential dataflow (https://github.com/TimelyDataflow/differential-dataflow/tree...). The fragment came from Yannis which he described as a minimal non-trivial analysis (vs other, even smaller fragments), but it still uses some 900 dataflow operators (updates in 10s of ms when inputs change, though). The DD impl isn't meant to be understood, I'm afraid.

2. Many ex-LB folks are now at relational.ai doing .. advanced weird tech like they did with LB. I'd watch them (I do).

3. Polonius (https://github.com/rust-lang/polonius) defines the Rust borrow checker as Datalog rules, and went from differential dataflow to datafrog (https://github.com/rust-lang/datafrog).

4. If you want to check out other incremental Datalog environments, in addition to IncA, there are

https://github.com/comnik/declarative-dataflow

https://github.com/ryzhyk/differential-datalog

https://github.com/TimelyDataflow/differential-dataflow

Good times for Datalog, imo.

No worries!

Niko's talk should probably be the reference material, but you definitely can deploy new queries interactively, against maintained indexed representations of the historical streams. No recompilation required. Streams are maintained in indexed form and don't need to be re-flowed (they may need to be re-indexed if your query calls for an index that doesn't exist).

Deploying a new query takes ~milliseconds if the correct indices exist, and if not it seems to be no slower than purpose-built Datalog systems (e.g. LogicBlox, but performance seems solid compared with Souffle). This is despite then running against live-updated data.

As I suspect you know, we cannot report performance relative to Datomic. ;)

For some context on "what Niko presented at the Conj",

    https://2018.clojure-conj.org/nikolas-gobel/

which is a reactive Datalog implementation built over differential dataflow. The .. um reported anxiety that to add new queries requires a recompile loop, replaying all of history, etc, suggests maybe they aren't entirely on top of how the system works.

Edit: and again tomorrow at clojureD:

    https://clojured.de/schedule/#nikolasGoebel

> What am I missing?

That it is a multi-value map? Could be more too; could also be just one part in a larger system and not everything is a race.

If you want to check out more about high-throughput incremental view maintenance in a Datomic-like system, here's a decent read (caveat: I'm involved):

https://www.nikolasgoebel.com/2018/09/13/incremental-datalog...

Also, a recent video from ClojureConj on the subject:

https://www.youtube.com/watch?v=ZgqFlowyfTA

I just watched this, and it was abundantly clear that the presenter believes there is a scaling issue ("scaling these propulsion methods is not easy" at 6:37). They literally say this, and then present the 10,000N/m^2 vs 3N/m^2 numbers for the jet engine versus this engine. There is then a minute or so explaining why this is a problem.

> Something I'd like to see is benchmarks of batch-query performance: If we can queue a couple of queries, then trees should gain a lot from processing them in-order (then, the last query has already warmed the cache for the next; this probably can pay for approximately sorting the batch).

I'm not sure if this is your point, but when you actually look at the uses of trees like the above (often: query processing) then the point look-up times are less relevant for implementations that do not serialize the look-ups.

Another place this shows up is when folks switch from closed-loop testing to open-loop testing (i.e. testing under a fixed rate of look-ups, rather than one or some few at a time). The latency-throughput trade-off curve makes trees look a lot less bad, but they still have a large minimal latency. A hash map with a sorted key (e.g. RobinHood hashing) still works better except at peak loads.

You can take this just a bit further and you find that replacing trees with a sorted list also works great (or, LSM of sorted lists, say). "Great" here just means "has some tolerable minimum latency, and peak throughput".

Absolutely worth watching. Cannot un-watch.

> 4. Any sort of refactoring that may adjust ownership. E.g. going from T to Rc<T>. GC requires fewer choices so these refactorings are easier.

This pain is real. I've been using Rust for four years now, and it hasn't gotten any easier. And unfortunately, the best strategy I have for refactoring is still "start refactoring; then see what issues come up and if I have to revert".

1. Jon sits two desks away, right? ;)

Re 2., I assumed (incorrectly, it seems) that virtual memory mappings can eventually spill to disk. If you grab 1/32 of RAM For the kernel, then you could only virtually map 16x RAM if the page tables have 512 entries. Admittedly, I took my OS class in the previous millennium, so I might be out of date here...