search

orientechnologies / orientdb

OrientDB is the most versatile DBMS supporting Graph, Document, Reactive, Full-Text and Geospatial models in one Multi-Model product. OrientDB can run distributed (Multi-Master), supports SQL, ACID Transactions, Full-Text indexing and Reactive Queries.
https://orientdb.dev
Apache License 2.0
4.73k stars 868 forks source link

Implementation of optimistic lock coupling on page level for tree index #9027

Open andrii0lomakin opened 4 years ago

andrii0lomakin commented 4 years ago

After the implementation of https://github.com/orientechnologies/orientdb/issues/9026 we can remove global lock from indexes and implement B-link tree algorithm which despite of the fact that it is quite old it is still one of the most efficient algorithms of concurrency control for B-Tree. https://www.csd.uoc.gr/~hy460/pdf/p650-lehman.pdf Because it requires to keep lock only on the single page simultaneously during the modification of B-Tree. To improve scalability, even more, it is proposed to use optimistic lock coupling instead of classical locks http://sites.computer.org/debull/A19mar/p73.pdf . This type of locks is supported in Java using https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/StampedLock.html .

andrii0lomakin commented 6 months ago

This relates to issue #10065.