Question about persistent_b_tree in pmemkv
50 views
Skip to first unread message
De W
Apr 1, 2021, 4:15:43 AM4/1/21
to pmem
Hi experts, i am noob and new to PMEM. I am studying persistent_b_tree (https://github.com/pmem/pmemkv/blob/master/src/engines-experimental/stree/persistent_b_tree.h) in pmemkv.
Are keys and values stored in the static array "entries" of the class leaf_node_t? If so, why is it persistent without using persistent_ptr?
Igor
Apr 1, 2021, 6:44:10 AM4/1/21
to De W, pmem
Hi,
it should be clear when you look at how leaf_node_t is allocated. This is done here: https://github.com/pmem/pmemkv/blob/master/src/engines-experimental/stree/persistent_b_tree.h#L2167 As you can see, we use make_persistent for the allocation. This means that the whole leaf_note_t object will be placed on persistent memory.
Best regards,
Igor
it should be clear when you look at how leaf_node_t is allocated. This is done here: https://github.com/pmem/pmemkv/blob/master/src/engines-experimental/stree/persistent_b_tree.h#L2167 As you can see, we use make_persistent for the allocation. This means that the whole leaf_note_t object will be placed on persistent memory.
Best regards,
Igor
On Thu, Apr 1, 2021 at 10:15 AM De W <hjhjbet...@gmail.com> wrote:
Hi experts, i am noob and new to PMEM. I am studying persistent_b_tree (https://github.com/pmem/pmemkv/blob/master/src/engines-experimental/stree/persistent_b_tree.h) in pmemkv.Are keys and values stored in the static array "entries" of the class leaf_node_t? If so, why is it persistent without using persistent_ptr?
--
You received this message because you are subscribed to the Google Groups "pmem" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pmem+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/pmem/34a92347-fb31-4bff-ba39-1391ced927adn%40googlegroups.com.
De W
Apr 1, 2021, 7:14:56 AM4/1/21
to pmem
Thanks for your replying. Is it safe to do like this? Aren't we supposed to use persistent_ptr?
Vào lúc 17:44:10 UTC+7 ngày Thứ Năm, 1 tháng 4, 2021, Igor Chorążewicz đã viết:
Igor
Apr 1, 2021, 11:55:54 AM4/1/21
to De W, pmem
Yes, it's safe. This entries[] array is a member of leaf_nod. If leaf_node is stored on pmem so is the array.
Persistent_ptr is only a way to reference data (similar to normal pointer). It can even point to dram data. There's nothing special about persistent_ptr apart from the fact that you can safely store it on pmem (which is not possible with regular pointers since they would be invalid after app restart) and all modifications done to a persistent_ptr within a transaction are logged and can be rolled back on failure.
Best regards,
Igor
Persistent_ptr is only a way to reference data (similar to normal pointer). It can even point to dram data. There's nothing special about persistent_ptr apart from the fact that you can safely store it on pmem (which is not possible with regular pointers since they would be invalid after app restart) and all modifications done to a persistent_ptr within a transaction are logged and can be rolled back on failure.
Best regards,
Igor
To view this discussion on the web visit https://groups.google.com/d/msgid/pmem/cffe6a11-b656-429a-80f7-bb22ce77cb7bn%40googlegroups.com.
De W
Apr 1, 2021, 6:43:42 PM4/1/21
to pmem
"entries" is a regular pointer, why is it not invalid after app restart? And how can it roll back on failure?
This doesn't make sense to me.
Vào lúc 22:55:54 UTC+7 ngày Thứ Năm, 1 tháng 4, 2021, Igor Chorążewicz đã viết:
Igor
Apr 2, 2021, 3:46:41 AM4/2/21
to De W, pmem
Actually 'entries' is not a pointer, it's an array (so, data is stored inline in the leaf).
The B tree implementation might not be the best data structure to look at when you you're trying to understand libpmemobj-cpp. There are some optimizations which can make code harder to understand. I would recommend looking at some simpler data structures first, e.g. : https://github.com/pmem/libpmemobj-cpp/blob/master/examples/queue/queue.cpp You can find pretty good explanation of this example (and how to convert DRAM data structure to a pmem one) in the book: https://pmem.io/book/ in chapter 8 (it also explains why using regular pointers on pmem is not a good idea).
As for the second question: "And how can it roll back on failure?"
In general, to make sure modifications of some variable are power-fail atomic you use:
* pmem::obj::p for trivial types
* pmem::obj::persistent_ptr for pointers
* pmem::obj::array, pmem::obj::vector or some other containers (see here and here and here) for storing multiple values. There are some blog posts about them: https://pmem.io/2018/11/02/cpp-array.html, https://pmem.io/2019/02/20/cpp-vector.html, https://pmem.io/2018/11/20/cpp-persistent-containers.html
In the B tree, we are not using a pmem::obj container for 'entries' but rather we use a regular array and add the modifications to a transaction log manually as an optimization (e.g. here: https://github.com/pmem/pmemkv/blob/master/src/engines-experimental/stree/persistent_b_tree.h#L865). You probably don't to do this unless you find out that using pmem::obj::array or pmem::obj::vector is a bottleneck.
Best regards,
Igor
The B tree implementation might not be the best data structure to look at when you you're trying to understand libpmemobj-cpp. There are some optimizations which can make code harder to understand. I would recommend looking at some simpler data structures first, e.g. : https://github.com/pmem/libpmemobj-cpp/blob/master/examples/queue/queue.cpp You can find pretty good explanation of this example (and how to convert DRAM data structure to a pmem one) in the book: https://pmem.io/book/ in chapter 8 (it also explains why using regular pointers on pmem is not a good idea).
As for the second question: "And how can it roll back on failure?"
In general, to make sure modifications of some variable are power-fail atomic you use:
* pmem::obj::p for trivial types
* pmem::obj::persistent_ptr for pointers
* pmem::obj::array, pmem::obj::vector or some other containers (see here and here and here) for storing multiple values. There are some blog posts about them: https://pmem.io/2018/11/02/cpp-array.html, https://pmem.io/2019/02/20/cpp-vector.html, https://pmem.io/2018/11/20/cpp-persistent-containers.html
In the B tree, we are not using a pmem::obj container for 'entries' but rather we use a regular array and add the modifications to a transaction log manually as an optimization (e.g. here: https://github.com/pmem/pmemkv/blob/master/src/engines-experimental/stree/persistent_b_tree.h#L865). You probably don't to do this unless you find out that using pmem::obj::array or pmem::obj::vector is a bottleneck.
Best regards,
Igor
To view this discussion on the web visit https://groups.google.com/d/msgid/pmem/b653e674-c5fe-4e80-9173-6a3a1bc040a8n%40googlegroups.com.
De W
Apr 2, 2021, 4:23:06 AM4/2/21
to pmem
Thank you so much for your work, it helps me a lot, the second question is clear to me now.
But according to my understanding, an array is basically a constant pointer, point to the first element of the array. So you actually store a constant pointer, not its content. Please correct me if i am wrong.
But according to my understanding, an array is basically a constant pointer, point to the first element of the array. So you actually store a constant pointer, not its content. Please correct me if i am wrong.
Vào lúc 14:46:41 UTC+7 ngày Thứ Sáu, 2 tháng 4, 2021, Igor Chorążewicz đã viết:
Jan K
Apr 2, 2021, 4:53:57 AM4/2/21
to De W, pmem
> But according to my understanding, an array is basically a constant
> pointer, point to the first element of the array.
Your understanding is clearly wrong.
> pointer, point to the first element of the array.
In C array of type X and pointer to type X are wildly different things.
A pointer to X is a region of memory that contains a single memory
address and is of single memory address size.
An array of X is a region of memory that contains given number of Xs
and is of size of all the Xs inside (and is of this size for pointer
arithmetic as well, so beware).
I would recommend you to start from learning in-depth C and C++ in the
first place.
2021-04-02 10:23 GMT+02:00, De W <hjhjbet...@gmail.com>:
> Thank you so much for your work, it helps me a lot, the second question is
> clear to me now.
> But according to my understanding, an array is basically a constant
> pointer, point to the first element of the array. So you actually store a
> constant pointer, not its content. Please correct me if i am wrong.
>
> Vào lúc 14:46:41 UTC+7 ngày Thứ Sáu, 2 tháng 4, 2021, Igor Chorążewicz đã
> viết:
>
>> Actually 'entries' is not a pointer, it's an array (so, data is stored
>> inline in the leaf).
>>
>> The B tree implementation might not be the best data structure to look at
>>
>> when you you're trying to understand libpmemobj-cpp. There are some
>> optimizations which can make code harder to understand. I would recommend
>>
>> looking at some simpler data structures first, e.g. :
>> https://github.com/pmem/libpmemobj-cpp/blob/master/examples/queue/queue.cpp
>>
>> You can find pretty good explanation of this example (and how to convert
>> DRAM data structure to a pmem one) in the book: https://pmem.io/book/ in
>> chapter 8 (it also explains why using regular pointers on pmem is not a
>> good idea).
>>
>> As for the second question: "And how can it roll back on failure?"
>> In general, to make sure modifications of some variable are power-fail
>> atomic you use:
>> * pmem::obj::p
>>
>> for trivial types
>> * pmem::obj::persistent_ptr
>> <https://pmem.io/libpmemobj-cpp/master/doxygen/classpmem_1_1obj_1_1persistent__ptr.html>
>> for trivial types
>> * pmem::obj::persistent_ptr
>>
>> for pointers
>> * pmem::obj::array
>> <https://pmem.io/libpmemobj-cpp/master/doxygen/structpmem_1_1obj_1_1array.html>,
>> for pointers
>> * pmem::obj::array
>>
>> pmem::obj::vector
>> <https://pmem.io/libpmemobj-cpp/master/doxygen/classpmem_1_1obj_1_1vector.html>
>>
>> or some other containers (see here
>> <https://pmem.io/libpmemobj-cpp/master/doxygen/dir_83ecae25392e6e33dc533801e27668b5.html>
>> or some other containers (see here
>> and
>> here
>> <https://pmem.io/libpmemobj-cpp/master/doxygen/classpmem_1_1obj_1_1experimental_1_1concurrent__map.html>
>> and
>> here
>> <https://pmem.io/libpmemobj-cpp/master/doxygen/classpmem_1_1obj_1_1experimental_1_1radix__tree.html>)
>>>>>>> .
>>>>>>>
>>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "pmem" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>>>
>>>>> an email to pmem+uns...@googlegroups.com.
>>>>>
>>>> To view this discussion on the web visit
>>>>> https://groups.google.com/d/msgid/pmem/cffe6a11-b656-429a-80f7-bb22ce77cb7bn%40googlegroups.com
>>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "pmem" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>>>
>>>>> an email to pmem+uns...@googlegroups.com.
>>>>>
>>>> To view this discussion on the web visit
>>>>>
>>>>> <https://groups.google.com/d/msgid/pmem/cffe6a11-b656-429a-80f7-bb22ce77cb7bn%40googlegroups.com?utm_medium=email&utm_source=footer>
>>>>> .
>>>>>
>>>> --
>>> You received this message because you are subscribed to the Google Groups
>>>
>>> "pmem" group.
>>> To unsubscribe from this group and stop receiving emails from it, send an
>>>
>>> email to pmem+uns...@googlegroups.com.
>>>
>> To view this discussion on the web visit
>>> https://groups.google.com/d/msgid/pmem/b653e674-c5fe-4e80-9173-6a3a1bc040a8n%40googlegroups.com
>>>> --
>>> You received this message because you are subscribed to the Google Groups
>>>
>>> "pmem" group.
>>> To unsubscribe from this group and stop receiving emails from it, send an
>>>
>>> email to pmem+uns...@googlegroups.com.
>>>
>> To view this discussion on the web visit
>>>
>>> <https://groups.google.com/d/msgid/pmem/b653e674-c5fe-4e80-9173-6a3a1bc040a8n%40googlegroups.com?utm_medium=email&utm_source=footer>
>>> .
>>>
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "pmem" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to pmem+uns...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/pmem/2ee26667-f6cc-4e7b-b9d1-678855e713c1n%40googlegroups.com.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "pmem" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to pmem+uns...@googlegroups.com.
> To view this discussion on the web visit
>
De W
Apr 2, 2021, 5:15:46 AM4/2/21
to pmem
Thank you so much for your time. I'll learn more in-depth C/C++.
Vào lúc 15:53:57 UTC+7 ngày Thứ Sáu, 2 tháng 4, 2021, Jan K đã viết:
Reply all
Reply to author
Forward
0 new messages