multiversion-concurrency-control VS t-digest

The code is in this repository https://github.com/samsquire/multiversion-concurrency-control in MultiplexingThread.java and MultiplexProgramParser.java

https://github.com/samsquire/multiversion-concurrency-contro...

And I implemented a 3 way text diff with myers algorithm based on https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm...

https://github.com/samsquire/text-diff

I implemented an eventually consistent mesh protocol that uses timestamps to provide last write wins

I think I lean towards per-thread sharding instead of mutex based or lock free data structures except for lockfree ringbuffers.

You can get embarassingly parallel performance if you split your data by thread and aggregate periodically.

If you need a consistent view of your entire set of data, that is slow path with sharding.

In my experiments with multithreaded software I simulate a bank where many bankaccounts are randomly withdrawn from and deposited to. https://github.com/samsquire/multiversion-concurrency-contro...

I get 700 million requests per second due to the sharding of money over accounts.

If you want some sample code to implement MVCC, I implemented MVCC in multithreaded Java as a toy example

https://github.com/samsquire/multiversion-concurrency-contro...

First read TransactionC.java then read MVCC.java

I wrote an unrolled switch statement in Java to simulate eager async/await across treads.

https://github.com/samsquire/multiversion-concurrency-contro...

The goal is that a compiler should generate this for you. This code is equivalent to the following:

   task1:

https://doc.rust-lang.org/book/ch16-00-concurrency.html

I've been working on implementing Java async/await state machine with switch statements and a scheduling loop. If the user doesn't await the async task handle, then the task's returnvalue is never handled. This is similar to the Go problem with the go statement.

https://github.com/samsquire/multiversion-concurrency-contro...

If your async call returns a handle and

yield value2++

https://github.com/samsquire/multiversion-concurrency-contro...

I am still working on allowing multiple coroutines to be in flight in parallel at the same time. At the moment the tasks share the same background thread.

I asked this stackoverflow question regarding C++ coroutines, as I wanted to use coroutines with a thread pool.

https://stackoverflow.com/questions/74520133/how-can-i-pass-...

This is very interesting. Thank you for submitting this and thank you for working on this.

I am highly interested in parallelism and high concurrency. I implemented multiversion concurrency control in Java.

https://github.com/samsquire/multiversion-concurrency-contro...

I am curious how to handle replication with high concurrency. I'm not sure how you detect dangerous reads+writes to the same key (tuples/fields) across different replica machines. In other words, multiple master.

I am aware Google uses truetime and some form of timestamp ordering and detection of interfering timestamps. But I'm not sure how to replicate that.

I began working on an algorithm to synchronize database records, do a sort, then a hash for each row where hash(row) = hash(previous_row.hash + row.data)

Then do a binary search on hashes matching/not matching. This is a synchronization algorithm I'm designing that requires minimal data transfer but multiple round trips.

The binary search would check the end of the data set for hash(replica_a.row[last]) == hash(replica_b.row[last]) then split the hash list in half and check the middle item, this shall tell you which row and which columns are different.

> I get a lot of benefit from this information but somehow it feels shallow.

I take a longer view to this. For example, a few years ago I read about an algorithm to calculate percentiles in real time. [0]

It literally just came up at work today. I haven't used that information but maybe two times since I read it, but it was super relevant today and saved my team potential weeks of development.

So maybe it's not so shallow.

But to your actual question, I have a similar problem. The best I can say is that deadlines help. I usually put down the HN and Youtube when I have a deadline coming up. And not just at work. I make sure my hobbies have deadlines too.

I tell people when I think something will be done, so they start bugging me about it when it doesn't get done, so that I have a "deadline". Also one of my hobbies is pixel light shows for holidays, which come with excellent natural deadlines -- it has to be done by the holiday or it's useless.

So either find an "accountability buddy" who will hold you to your self imposed deadlines, or find a hobby that has natural deadlines, like certain calendar dates, or annual conventions or contests that you need to be done by.

[0] https://github.com/tdunning/t-digest

I am enamored by data structures in the sketch/summary/probabilistic family: t-digest[1], q-digest[2], count-min sketch[3], matrix-sketch[4], graph-sketch[5][6], Misra-Gries sketch[7], top-k/spacesaving sketch[8], &c.

What I like about them is that they give me a set of engineering tradeoffs that I typically don't have access to: accuracy-speed[9] or accuracy-space. There have been too many times that I've had to say, "I wish I could do this, but it would take too much time/space to compute." Most of these problems still work even if the accuracy is not 100%. And furthermore, many (if not all of these) can tune accuracy to by parameter adjustment anyways. They tend to have favorable combinatorial properties ie: they form monoids or semigroups under merge operations. In short, a property of data structures that gave me the ability to solve problems I couldn't before.

I hope they are as useful or intriguing to you as they are to me.

1. https://github.com/tdunning/t-digest

2. https://pdsa.readthedocs.io/en/latest/rank/qdigest.html

3. https://florian.github.io/count-min-sketch/

4. https://www.cs.yale.edu/homes/el327/papers/simpleMatrixSketc...

5. https://www.juanlopes.net/poly18/poly18-juan-lopes.pdf

6. https://courses.engr.illinois.edu/cs498abd/fa2020/slides/20-...

7. https://people.csail.mit.edu/rrw/6.045-2017/encalgs-mg.pdf

8. https://www.sciencedirect.com/science/article/abs/pii/S00200...

9. It may better be described as error-speed and error-space, but I've avoided the term error because the term for programming audiences typically evokes the idea of logic errors and what I mean is statistical error.

Ah, I misunderstood what you meant. If you are reporting static buckets I get how that is better than what folks typically do but how do you know the buckets a priori? Others back their histograms with things like https://github.com/tdunning/t-digest. It is pretty powerful as the buckets are dynamic based on the data and histograms can be added together.

Yes, but if you need to estimate median on the fly (e.g., over a stream of data) or in parallel there are better ways.

There are some newer data structures that take this to the next level such as T-Digest[1], which remains extremely accurate even when determining percentiles at the very tail end (like 99.999%)

[1]: https://arxiv.org/pdf/1902.04023.pdf / https://github.com/tdunning/t-digest

[2] https://github.com/tdunning/t-digest

T-Digest

This is pretty cool. The title would be a bit more descriptive if it were “Fast Rolling Quantile Filters for Python”, since the high-pass/low-pass filter functionality seems to be the focus.

The README mentions it uses binary heaps - if you’re willing to accept some (bounded) approximation, then it should be possible to reduce memory usage and somewhat reduce runtime by using a sketching data structure like Dunning’s t-digest: https://github.com/tdunning/t-digest/blob/main/docs/t-digest....

There is an open source Python implementation, although I haven’t used it and can’t vouch for its quality: https://github.com/CamDavidsonPilon/tdigest