Frank McSherry

That post from Frank McSherry is excellent. His earlier post [1] is also worth reading.

I was curious to read more about the Hilbert ordering of edges, and the delta-encoding. There is a related article from Yzelman & Bisseling titled "A cache-oblivious sparse matrix–vector multiplication scheme based on the Hilbert curve"[2] which discusses Hilbert ordering combined with a delta-encoded version of the usual CSR encoding for sparse matrices [3].

> A Hilbert curve thus can be projected on any [2^m * 2^m] matrix, which in turn can embed the sparse matrix A, thus imposing a 1D ordering
on its nonzeroes.

The largest sparse matrix considered for the experimental results from this article was "wikipedia-20070206" with 45,030,389 nonzeros (aka weighted edges). Ignoring the weights, this is about 1/3000th of the size of the 128 billion edge graph that McSherry mentions in his post.

Yzelman & Bisseling also measure the additional preprocessing time required to convert their sparse matrices using the Hilbert-ordered delta-encoded CSR scheme -- this is roughly 30x the time for a single matrix-vector product evaluation [4]. Clearly this approach is only going to pay off if one plans to do a bunch of analysis using the single matrix / graph, without changing the matrix / graph. McSherry mentions a similar issue but points out that he could preprocess the graph using his approach faster than he could download the data, so the preprocessing speed wasn't really an issue.

[1]…

We are actually talking about orthogonal aspects. You are right that being able to run the system on a smaller number of nodes reduces inefficiencies and reduces the "hit" of diminishing returns stemming from Amdahl's law. However, to do that, you need to speed up your code and I argue that unless you speed up the non-parallelizable part together with the parallelizable part, you won't be able to achieve that system speedup that allows you to remove a number of servers from your cluster in the first place.

However, I think you are right that on small number of servers speeding up parallel part can have a more immediate effect. I did a small calculation just to check the numbers. Assume you have a server that can do 100 RPS. You can either speed up the parallel code 2x (let's be realistic here and stop this 100x nonsense) and bring the RPS almost to 200 or you can take that serial code that is just a fraction and reduce it by half, so that f=0.995 and not 0.99 (and adding a marginal RPS increase to 102 RPS).

Here is the plot: https://imgur.com/a/7w1hms9

Edit: read http://www.frankmcsherry.org/assets/COST.pdf as recommended in the upvoted comment above!

A single server is much faster than most people think, too!

In the microservice or serverless arrangements I've seen, data is scattered across the cloud.

It's common for the dominant factor in performance to be data locality, most times this talk about data locality is about avoiding trips to RAM, or worse disk. But in our "modern" distributed cloud things, finding a bit of data frequently involves a trip over the network. In the monolith world what was once invoking a method on an account object, has become making a HTTP POST to the accounts microservice.

What might have been a microseconds operation in the single server world, might become hundreds of milliseconds in the distributed cloud world. While you can't horizontally scale a single server, your 1000x head start in performance might delay scaling issues for a very long time.

A most excellent paper related to this topic that I think should be mandatory reading before allowing anyone an AWS account is http://www.frankmcsherry.org/assets/COST.pdf :)

> Almost by definition, any company that runs a cluster is probably dealing with TBs of data (otherwise they could probably run it on one machine).

This doesn't follow:

1) One reason to run a cluster is to use flaky commodity hardware instead of high-reliability specialized hardware. Note the transition from specialized hardware and computer rooms of the '80s and '90s to cloud computing on preemptible instances.

2) They might just be straight-up wrong / misguided. http://www.frankmcsherry.org/graph/scalability/cost/2015/01/15/COST.html As a professional developer I've seen tons of distributed systems that could be replaced by a well-designed non-distributed system, but ELK and Mongo and etcd and Kafka and more generally cloud servers are easy off-the-shelf tools.

On another note - these kinds of "let's go back and check what we can do with a single node today" approaches are valuable to recalibrate our thinking once in a while. I didn't interpret this post as a case against distributed processing - there are many things going for it - but just to avoid falling into hype.

A couple of great posts by Frank McSherry along the same lines a few years ago, doing page rank for a 128bil edge graph on a single laptop (in the second post below) -

The first post - "scalability! But at what cost"
http://www.frankmcsherry.org/graph/scalability/cost/2015/01/15/COST.html

The second post - "bigger data, same laptop"
http://www.frankmcsherry.org/graph/scalability/cost/2015/02/04/COST2.html

“the performance of the underlying hardware has increased so much in the last decade that the simplicity of SQLite has become a more important tradeoff”

Thanks for articulating this so clearly! It's going to be interesting also to see how much simplicity is realized from new thread-per-core designs leveraging io_uring to get rid of multithreading, locks and memory barriers scattered throughout the control plane. The performance dynamics are all changing and it's easier than ever to be writing simple, fast systems, that hit the 90% sweet spot.

You've probably also seen McSherry et. al's “Scalability! But at what COST?” [1]

[1] http://www.frankmcsherry.org/graph/scalability/cost/2015/01/15/COST.html