SzyWilliam commented on PR #958: URL: https://github.com/apache/ratis/pull/958#issuecomment-1797190637
> I wonder if it is more efficient to use synchronized to implement ReadIndexQueue than ConcurrentSkipListMap? Thanks very much for the patch! Indeed we should complete the future actively. Additionally, I conducted an in-depth analysis of 'ConcurrentSkipListMap' and the synchronized 'TreeMap.' Both data structures have search, insert, and remove operations with a time complexity of O(logN). When removing multiple entries in `complete`, 'TreeMap' requires 2O(logN) + k operations (since it only needs to identify the ceiling and flooring entry), while 'ConcurrentSkipListMap' demands kO(logN) operations (as it loops over all the matching indexes in between). In terms of synchronization, synchronized 'TreeMap' uses locks, while 'ConcurrentSkipListMap' heavily relies on CAS operations with spinning. In conclusion, synchronized 'TreeMap' demonstrates better performance under heavy loads and offers higher throughput, which is typical for Ratis read situations. On the other hand, 'ConcurrentSkipListMap' excels in terms of latency performance. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
