New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Performance/scalability? #89

Open
aral opened this Issue May 9, 2018 · 9 comments

Comments

Projects
None yet
6 participants
@aral
Copy link

aral commented May 9, 2018

Hey there,

First off, thank you for sharing your paper (A Conflict-Free Replicated JSON Datatype) and this library with the world.

I started playing with automerge this afternoon and wanted to run some basic tests to see if I could use it for the federated personal web site system I’m working on, as I want it to work offline and I’d rather not privilege servers over clients (the goal is, ideally, for this to be a stepping stone towards a p2p world, which I believe is what we’re all working for) :)

So to cut to the chase, I wanted to share my very unsophisticated findings and to also inquire about whether, in the words of Steve Jobs, I’m “holding it wrong” :)

Multiple inserts

Code: https://source.ind.ie/snippets/80

I first tried pushing incremental numbers to an array in a document via the change() method. The timings (on my MacBook) ranged from 6ms for 1 push to 43.75 seconds for 10,000. 100 pushes took 175ms and 1,000 took 1.345 seconds.

screen shot 2018-05-09 at 21 58 41

The storage requirements (tested very roughly using util.inspect to flatten the object, including all hidden fields) also seem to follow a similar curve. A single insert took up 3,557 bytes (size of original object: 18 bytes), 10: ~17KB, 100: ~160KB, 1,000: ~1.6MB, and the array with 10,000 numbers took up ~ 16MB (size of original object: ~80 bytes). Again, my testing methodology doesn’t necessarily reflect the actual amount of space these objects would take up either in memory or on the file system but, unless I’ve done something really daft (which is always a possibility), it does look like the system would result in a sluggish interface on operations on an array with ~100 items or so.

screen shot 2018-05-09 at 21 58 47

Single insert

Then I thought maybe I am holding this wrong and it is meant to be used with batch inserts.

Code: https://source.ind.ie/snippets/81

So instead of testing, say, 10,000 pushes to an array, I wanted to test a single change to the object where an array with 10,000 items is added.

The results I got mirror those of the first scenario.

The timings seem to follow a similar curve at first but the results I got for the array with 10,000 items was ~3x slower at ~115 seconds vs ~43 seconds using the first technique.

screen shot 2018-05-09 at 22 08 31

As for the document sizes, they came out to be slightly less than with the first technique from the 100 item mark onwards. It was still ~1.3MB for 1,000 items and ~13MB for 10,000.

screen shot 2018-05-09 at 22 08 40

I’d love to hear your thoughts on this as well as any criticism of the above (including what I was benchmarking and how). My use case is a personal web site allows both posts and messaging between sites. I was using the 10,000 item test as an upper limit for initial use (e.g., 10,000 posts in a category, 10,000 messages in a conversation.) A more realistic amount might be 20-30 to a few hundred. But even at those levels, the latency would require operations to take place outside of the main thread to avoid a sluggish UI.

Also, since Automerge is already being used in two real-world applications, I’d love to hear of your actual experiences with performance, scalability, and storage requirements.

Thanks again for making this and sharing it. It’s a very hard problem domain indeed.


Update

Based on the feedback of @pvh and @j-f1 (thanks, folks!), I just updated my tests to include:

A key setting test (as opposed to array.push()) – the results are generally comparable to the previous ones:

screen shot 2018-05-10 at 21 43 24

screen shot 2018-05-10 at 21 43 37

And to use Automerge.save(doc) to test storage size (the sizes are 3x-5x smaller):

screen shot 2018-05-10 at 21 43 47

screen shot 2018-05-10 at 21 43 55

screen shot 2018-05-10 at 21 44 08

I’ve added the test files to their own repository at https://source.ind.ie/indienet/spikes/crdt/automerge

@pvh

This comment has been minimized.

Copy link
Contributor

pvh commented May 9, 2018

Wow! Thanks so much for this work Aral! I suspect there's some internal O(n^2) data structure update causing grief here. We've used automerge at larger scales with both Pixelpusher and Trellis without seeing quite this bad of a performance collapse, so I wonder if it's "how you're holding it" (though unlike Apple, we can probably fix our problems instead of blaming the user!)

I took a look at your performance script and I wonder if you could benchmark updating different keys that many times, which might look something like

document.change((doc) => {
  doc["key" + i] = true;
}

or something along those lines? Basically I suspect that having all the updates go to the same value might be what's causing the problem.

Really appreciate you contributing this analysis and very excited to look more closely at what might cause performance problems and how we can fix them.

@j-f1

This comment has been minimized.

Copy link

j-f1 commented May 9, 2018

For measuring the size of the doc, you should be able to measure the length of Automerge.save(doc), which returns a string containing the document and its history.

@schrepfler

This comment has been minimized.

Copy link

schrepfler commented May 10, 2018

This is not trying to steal automerge's thunder (and thunder it has)
@aral, have you tried benchmarking https://gun.eco/ for your use case?

@aral

This comment has been minimized.

Copy link

aral commented May 10, 2018

@schrepfler I’ve looked into gun but I’m wary of it for a number of reasons (including that it has VC and because I don’t see the particular conflict-free algorithm working for my purposes). That said, great to see different people tackling this problem space in different ways and sharing their work. We can only be stronger for it :)

@ept

This comment has been minimized.

Copy link
Member

ept commented May 11, 2018

Hi @aral, this is great, thank you for your measurements. You're not "holding it wrong" — the access patterns in your tests are things that should be supported efficiently.

The util.inspect size metric is probably not very meaningful, because Automerge internally keeps several references to the same object; those objects appear only once in memory, but would appear multiple times in the util.inspect output. But the result of Automerge.save(), as suggested by @j-f1, is a reasonable metric.

In my last round of profiling, as far as I remember, I got results broadly similar to yours. Looking into the breakdown, I found that over half the CPU time was being spent in garbage collection. Therefore I figured that in order to improve the performance of Automerge, we need to move to data structures that are more memory-efficient and GC-friendly. That would also reduce the memory use.

I have worked out an algorithm for Automerge's internal structures that will be much more memory-efficient, and have started implementing it. It'll probably take a few weeks to finish, since it requires significant refactoring of internals. But it's happening, and I am hopeful that the new approach will give significantly better performance, especially on large arrays.

In summary: I'm aware that performance is currently not great, but we have a plan for improving it, and I'm optimistic that big improvements are possible. I'd love to see more of your experiments with Automerge, and I'd love to hear more about the federated personal web site system you're planning to build.

@aral

This comment has been minimized.

Copy link

aral commented May 12, 2018

Hey @ept, thank you for the additional background – it’s very helpful.

As I understand it, GC is a hard problem in peer-to-peer systems as you cannot be certain when a node may come back online with operations that are casually-linked to garbage-collected history. I was just reading Alexei’s (@archagon) excellent round up of CRDTs and his work with Casual Trees and Operational Replicated Data Types (ORDTs) and the solutions he presents there, including for GC, are very exciting (http://archagon.net/blog/2018/03/24/data-laced-with-history/). Not sure if you’ve chatted but you probably should regardless of anything else :)

One of the features I want to implement on whatever CRDT algorithm/library I choose is to have every operation signed and to also include publickeys of authorised people within those signed messages in an attempt to guarantee the integrity of the document (as does DAT/hypercore, for example) as well as implement a decentralised authentication mechanism that doesn’t rely on privileged central servers. So the DAG approach of Casual Trees sounds perfect to me :)

@ept

This comment has been minimized.

Copy link
Member

ept commented May 13, 2018

A few more thoughts on the performance measurements.

The times you give above are the total time taken for n insertions; however, in many applications, you don't often insert 10,000 items into a list in one go, but rather have the list grow gradually through user activity. So perhaps the average time per insertion would be a more relevant metric? And that is 1.3ms per operation for a 1,000-item list, and 4.3ms per operation for a 10,000-item list. To be clear, that's still not blazing fast, but it's a less scary headline figure than 43 seconds.

Secondly, your script does a comparison to regular JavaScript array.push(). As Automerge uses immutable data structures, it has to clone the list for every change, whereas array.push() mutates the list. To make this an apples-to-apples comparison, the script should also clone the array on every change, like this:

  let x = []
  let start = new Date()
  for (let i = 0; i < numInserts; i++) {
    x = x.slice() // clone the array
    x.push(i)
  }
  let duration = (new Date()) - start
  console.log(`Took: ${duration}ms.`)

On my laptop, that script takes 270ms for 10,000 items, while the equivalent changes in Automerge take 39.7 seconds. Thus, Automerge currently incurs roughly a 150x overhead over plain JavaScript data structures. That is the gap we need to try to close.

@aral

This comment has been minimized.

Copy link

aral commented May 13, 2018

@ept Thanks again – this is very helpful (& agree with all your points).

PS. Forgot to mention it, had just watched your talk at a conference in London when I replied earlier. Great talk :) So exciting to see work in this area progressing with pragmatic work in parallel projects :)

@marbemac

This comment has been minimized.

Copy link

marbemac commented Jul 14, 2018

One thing that we noticed, space wise, is that the auto-merge data structure (result of .save, etc), is VERY gzip friendly.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment