search

baotonglu / dash

Scalable Hashing on Persistent Memory
MIT License
187 stars 26 forks source link

Question about bucket::insert #1

Closed shiniaas closed 4 years ago

shiniaas commented 4 years ago

I think the fingerprints should be persisted as your paper says, but I can't find the corresponding code in ex_finger.h(line 369).

baotonglu commented 4 years ago

I think the fingerprints should be persisted as your paper says, but I can't find the corresponding code in ex_finger.h(line 369).

Hi,

Actually we do some optimization for our implementation for insert operation. The implementation is a little different from the algorithm described in the paper because the current clwb in our machine could invalidate the CPU cache. If the fingerprint is flushed before releasing the lock, the lock release operation will incur high latency because it needs to bring the invalidated fingerprint cacheline from PM to CPU cache.

Thus our policy is to persist the fingerprints after releasing the lock of that bucket. However, this could incur the issue of "use-before-flush/persist". So current policy to guarantee the correctness is that: release one of the locks (target bucket's or probe bucket's) and then do the fingerprint persist, at last release the remaining lock. The reader (search operation) could proceed only if both locks (target bucket and probe bucket) are released. In other words, this is trading a bit of concurrency for correctness. You could check the Table::Insert function to see that we enforce the persistence of fingerprints after releasing one of the locks.

Feel free to contact us if you have further questions. Thank you.

Baotong

shiniaas commented 4 years ago

Thanks! Following your reply, I find what you mean in ex_finger.h(line 879), but there only exists the persistence of bitmap(no fingerprint/finger_array). Besides, you say the current clwb could invalidate the CPU cache, confusing me alot(as far as I know, clwb won't invalidate the cacheline).

baotonglu commented 4 years ago

Thanks! Following your reply, I find what you mean in ex_finger.h(line 879), but there only exists the persistence of bitmap(no fingerprint/finger_array). Besides, you say the current clwb could invalidate the CPU cache, confusing me alot(as far as I know, clwb won't invalidate the cacheline).

The bitmap and fingerprints are in the same cacheline. Therefore flushing the bitmap will also flush the fingerprints.

Although Intel Xeon Gold 6252 CPU (used in our experiments) supports clwb, our test shows that current clwb actually invalidates the cacheline. Please refer to this blog.

shiniaas commented 4 years ago

Thanks! I forgot it! I'll close this issue.