siddcoder

Wondering if any performance comparison was done with Apache Pinot?

It is not necessary. I chose to build a protobuf based serialization and communication since it is widely used in distributed system and more performant than JSON based serialization.

Another reason was ease of use especially because Netty already supports message encoders and decoders for conversion between protobuf and bytebuf.

You could also use https://github.com/FasterXML/jackson-databind but that would require a reasonable amount of custom code for the encoder and decoders

The point is that overhead of locking is too much when the contention on the shared structure is fairly less. The cost of locking/unlocking/blocking/waiting or any other work done as part of enforcing synchronization is something that can be optimized away if the contention on the data structure is less.

By contention, I imply -- contention or conflicts on the same portions/pieces of structure.

If the data structure is subject to high concurrent access but in fairly disjoint regions of the data structure, we should try to implement fine grained locking scheme to increase the degree of parallelism and thus the scalability of data structure.

This is where CAS comes into picture. The article doesn't compare CAS to another locking primitive. Instead, CAS is just used as a mechanism to implement fine grained locking scheme where the methods operating on the data structure don't take global or coarse locks.

If the contention on the entire data structure is unreasonably high for some reason, then CAS based approaches or any flavors of it don't buy us much.

I think spinlock is used when the critical section is relatively smaller where the threads are likely to perform small amount of work after acquiring locks. Thus locks are not expected to be held for longer duration. The other threads contending for the lock prefer to just spin and poll (and of course burn CPU) with the hope that lock will soon be relinquished by the owner thread. This way spinning threads avoid the overhead of context switching as well.

Goes without saying, spinlocks are not useful on uniprocessor machines or single core machines.

Thanks!. I have read that this data structure can be used for range updates and queries. Something that can also be done using Segment Trees. I haven't covered range updates in my article. It only talks about prefix sum and point updates. I will talk about range updates and segment trees in another article soon.

Cool Stuff !!

Hey, thanks for this :)

I tried to be as intuitive as possible in my post, but kind of missed to reason about this one.

Hope you liked the article !!