Skip to content
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

Weak isolation/failure-atomicity level of the current implementation #2

Closed
baotonglu opened this issue Dec 17, 2020 · 5 comments
Closed

Comments

@baotonglu
Copy link

The current implementation may only provide the weakest isolation level, i.e., read uncommitted.
Specifically, the threads may read the data that is not durable in persistent memory and return.
The reason is that your current implementation releases the lock before flushing the data to PM.
For example, at line 735 of lbtree.cc, the code first releases the lock and then flushes the data to PM at line 738.
If thread 1 hangs after executing line 735 but before line 738 due to some reasons (e.g., context switch), thread 2 could read the non-persistent data that thread 1 wrote, and return to the application.
This case violates durable linearizability.
Do you think this is one of the limitations of your current implementation? If so, how could you solve it?

@schencoding
Copy link
Owner

The write to the lock bit in a hardware transaction will stop any ongoing lookup operations. After that, if the insertion has not changed the lock bit, a lookup will see the lock bit and retry. Therefore, lookups will not see any ongoing modifications.

@schencoding
Copy link
Owner

The lock bit trick is proposed in FP-Tree. This trick allows the use of hardware transaction and clwb/sfence in the same algorithm. Normally, clwb/sfence will immediately abort a hardware transaction. To avoid this, the trick sets the lock bit in the hardware transaction and perform clwb/sfence after the hardware transaction. The trick effectively achieves serializability for the index.

@baotonglu
Copy link
Author

baotonglu commented Dec 17, 2020

Thanks for the reply. I understand how locking and hardware transaction memory are coordinated to guarantee the correct synchronization. The problem I observed is that the current implementation releases the lock at the leaf node too early. You could check the code lines I pointed: one thread first (1) releases the lock and then (2) flushes the data in current implementation so that other threads could read the non-persistent data between the step (1) and (2). The correct procedure is that it should first (1) flush the data and then (2) release the lock to guarantee the correct isolation.

@schencoding
Copy link
Owner

I see what you mean now. There are two ways to solve this problem. First, update the lock bit after clwb/sfence. However, this may incur some overhead. Second, remove the lock bit from the leaf node on NVM and use a lock array in DRAM for the purpose of locking leaf nodes. For example, the lock array consists of K entries. K >> number of cores. (e.g., K =1024). Each entry is 64B. A leaf node is mapped to an entry by (leaf address / 256) % K. The DRAM lock array can be updated after the clwb/sfence with low cost.

@baotonglu
Copy link
Author

baotonglu commented Feb 17, 2021

Thanks for the reply. Using DRAM lock is a bit complex since there is a mapping between tree nodes and DRAM locks. It has the risk of deadlock during leaf node splits (need logic to avoid this). Another solution is to employ non-temporal stores introduced by this project.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants