Re: BTrees! (was Re: Understanding loading mechanism)
Jim Fulton <[email protected]> Sun, 24 Feb 2019 10:46:57 -0700
| Newsgroups | gmane.comp.web.zope.zodb |
|---|---|
| Message-ID | <CAPDm-FjAjRNQG58YqzTa9TSxohcg-X5YTQVLGG8Y-U1UzXGhWQ@mail.gmail.com> |
--000000000000c4718e0582a7699c Content-Type: text/plain; charset="UTF-8" On Sat, Feb 23, 2019 at 2:20 PM Qiwen Chen <[email protected]> wrote: > Thanks for the explanation. Actually it's pretty obvious to me now that > the loading unit is a bucket in the BTree. > > The domain is Financial Data. My application loads the time series by min > and max key pair. It's read heavy and write light. So it's well suited. > Yup > The prefetch feature is the exact thing i am looking for. Before doing any > calculation, the application would know the exact min and max key pairs for > a list of time series objects. I would like to load them in one go. > Knowing the min and max keys don't help you as much as you might think. To use prefetch you need oids or (ghost) objects, which BTrees don't have an API to give you. To implement such an API, BTrees would have to load a bunch of internal nodes to find the buckets you want, defeating the purpose. Similarly, iterators don't expose enough information to allow you to prefetch data. You couldn't really implement an interface to get all of the buckets in one go, because you have to load a bucket to get it's next pointer. What could, conceivably, be done is to have BTree iterators prefetch next buckets as buckets are loaded. Then, retrieval of the next bucket could be in flight while an application is processing the current bucket. I'd be open to a PR that implemented this under the control of a new prefetch keyword argument to the BTree items, keys, and values methods. Any reference you can point me to? > Prefetch is a new somewhat experimental method. It's not documented anywhere yet. Prefetch sounds very appealing until you try to figure out how to leverage it. :-] There's a prefetch method on connections (_p_jar attributes of persistent objects) that takes one or more oids, persistent objects, or iterables of oids or persistent objects. It doesn't return anything, but just hints to the connection and underlying storage that the objects will likely be wanted soon. For ZEO, this causes requests to be sent for that data. When the data are returned, they're added to the ZEO cache to be available when the application requests it. If the application requests the data before it's returned, the application will block. At the storage level, prefetch has only been implemented for ZEO. It's ignored for other storages, most notably RelStorage. > In my application, I use the iterator in BTrees extensively. One big > limitation is that I cannot iterate in reversed order. I guess that is > because the linked lists of buckets are only linked in one direction. > Yes. When I designed BTrees I sought to avoid circular references, because I was hoping that we'd have storages that supported reference-counting garbage collection, but we never did that. If I ever redesigned BTrees, I'd probably make them doubly-linked lists (and probably add more internal pointers to simplify computation). Something else I noted that you may not have picked up on in my earlier message is that you can also tune BTrees at the C level. In particular: - You can adjust the maximum bucket size to better fit your requirements, perhaps using much bigger buckets for your application. - You can use different C types that might fit your needs better. Jim > Qiwen > > On Saturday, February 23, 2019 at 10:07:51 AM UTC-5, Jim Fulton wrote: >> >> On Fri, Feb 22, 2019 at 9:30 PM Qiwen Chen <[email protected]> wrote: >> >>> If I use IFBTree ( integer-keyed float-valued BTree) to store some time >>> series data. >>> >> >> Interesting. What's the domain? Financial data? Scientific? >> >> How does the loading work? >>> >> >> BTrees store data stored by key in such a way that only part of a tree >> needs to be loaded into memory to fetch data for a subset of keys. >> Similarly, if only a subset of keys (like 1) is modified, then only a >> subset of the BTree is modified and stored. >> >> See: https://en.wikipedia.org/wiki/B-tree >> >> The leaves of the tree, where the data are stored are called buckets. >> Internal tree nodes help find the right bucket for a key or key range. >> >> >>> For example, if l want to load the entire time series into memory, how >>> many trips happen between the client and server? >>> >> >> That depends on the access pattern. Assuming you iterated over the >> tree, you would load roughly N/100 objects, where N is the number of >> values in the tree. (This is governed by a compile-time max bucket-size >> parameter, which for IFBTrees, 120.) >> Each load requires a round-trip. >> >> Recently, we added a prefetch API that mitigates round trips (by >> effectively doing them in parallel) if you know you're going to load >> multiple objects. This could conceivably leveraged when iterating over a >> BTree. >> >> Loading the entire tree into memory defeats one of the design goals, >> which is to have trees that are much larger than application memory. >> Sometimes, when we want to iterate over trees that are larger than memory, >> we periodically explicitly invoke garbage collection (normally invoked >> implicitly at transaction boundaries) to free memory got leaves were done >> with. >> >> In the document, it says it uses lazy loading. Does it mean each key >>> value pair is loaded from the db to memory one at a time? >>> >> >> No, it means the minimum number of nodes (internal or bucket) are loaded >> to retrieve a given key or key range. >> >> The primary use case of BTrees is storing very large mappings where you >> usually only want to access very small subsets of keys. >> >> There's a feature of our implementation though that might be useful for >> time series data, depending on the application. I mentioned that BTrees >> are trees of nodes with data in buckets at the leaves of the trees. But >> BTrees are *also* linked lists of buckets. Each internal node has a >> reference to it's first bucket and each bucket has a reference to the next >> bucket in the tree. This is to allow efficient iteration. >> >> In the example above, to iterate over the entire tree, we only had to >> load the top node and the buckets. We didn't have to load or traverse >> internal nodes. >> >> As always, picking and tuning data structures depends on application >> usage (update and access) patterns, but I can imagine time-series >> applications for which BTrees could work very well, especially with some >> compile-time tuning (much larger bucket sizes and different storage types). >> >> Early in my career I worked a lot with hydrologic time series data that >> was collected over short fixed time intervals (5 or 15 minutes). This data >> was very expensive to store at the time (early eighties, when a 300MB disk >> was the size of a dishwasher and wildly more expensive). Storage of the >> data was wildly important and the nature of this data allowed it to be very >> compressible, typically 90-95%, which was an important factor in it's >> storage. >> >> (I could imagine a variation of BTrees for fixed-time-interval data that >> avoided storing time values in buckets.) >> >> Of course, storage is much cheaper now, but we store a lot more data. >> The same factors that made a custom storage format for time-series data >> attractive in the 80s, makes columnar formats like Parquet and ORC popular >> today. >> >> (Hm, writing that made me wonder if it would be useful to have a BTree >> variant that used Numpy/Arrow/xnd arrays to store bucket data. Perhaps >> memory-mapped...Hm....) >> >> Jim >> >> -- >> Jim Fulton >> http://jimfulton.info >> > -- > You received this message because you are subscribed to the Google Groups > "zodb" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/d/optout. > -- Jim Fulton http://jimfulton.info -- You received this message because you are subscribed to the Google Groups "zodb" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout. --000000000000c4718e0582a7699c Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr"><div dir=3D"ltr"><br></div><br><div class=3D"gmail_quote">= <div dir=3D"ltr" class=3D"gmail_attr">On Sat, Feb 23, 2019 at 2:20 PM Qiwen= Chen <<a href=3D"mailto:[email protected]">[email protected]</a>> wrot= e:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0= .8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"l= tr">Thanks for the explanation. Actually it's pretty obvious to me now = that the loading unit is a bucket in the BTree.=C2=A0<div><br></div><div>Th= e domain is Financial Data. My application loads the time series by min and= max key pair. It's read heavy and write light. So it's well suited= .=C2=A0</div></div></blockquote><div><br></div><div>Yup</div><div>=C2=A0</d= iv><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bord= er-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div>= The prefetch feature is the exact thing i am looking for. Before doing any = calculation, the application would know the exact min and max key pairs for= a list of time series objects. I would like to load them in one go.</div><= /div></blockquote><div><br></div><div>Knowing the min and max keys don'= t help you as much as you might think.=C2=A0 To use prefetch you need oids = or (ghost) objects, which BTrees don't have an API to give you.=C2=A0 T= o implement such an API, BTrees would have to load a bunch of internal node= s to find the buckets you want, defeating the purpose.</div><div><br></div>= <div>Similarly, iterators don't expose enough information to allow you = to prefetch data. You couldn't really implement an interface to get all= of the buckets in one go, because you have to load a bucket to get it'= s next pointer.</div><div><br></div><div>What could, conceivably, be done i= s to have BTree iterators prefetch next buckets as buckets are loaded.=C2= =A0 Then, retrieval of the next bucket could be in flight while an applicat= ion is processing the current bucket.=C2=A0 I'd be open to a PR that im= plemented this under the control of a new=C2=A0 prefetch keyword argument t= o the BTree items, keys, and values methods.</div><div><br></div><blockquot= e class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px s= olid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div>=C2=A0 Any re= ference you can point me to?<br></div></div></blockquote><div><br></div><di= v>Prefetch is a new somewhat experimental method.=C2=A0 It's not docume= nted anywhere yet.=C2=A0 Prefetch sounds very appealing until you try to fi= gure out how to leverage it. :-]</div><div><br class=3D"gmail-Apple-interch= ange-newline"></div><div>There's a prefetch method on connections (_p_j= ar attributes of persistent objects) that takes one or more oids, persisten= t objects, or iterables of oids or persistent objects.=C2=A0 It doesn't= return anything, but just hints to the connection and underlying storage t= hat the objects will likely be wanted soon.=C2=A0 For ZEO, this causes requ= ests to be sent for that data.=C2=A0 When the data are returned, they'r= e added to the ZEO cache to be available when the application requests it.= =C2=A0 If the application requests the data before it's returned, the a= pplication will block.</div><div><br></div><div>At the storage level, prefe= tch has only been implemented for ZEO. It's ignored for other storages,= most notably RelStorage.</div><div>=C2=A0<br></div><blockquote class=3D"gm= ail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,= 204,204);padding-left:1ex"><div dir=3D"ltr"><div></div><div>In my applicati= on, I use the iterator in BTrees extensively. One big limitation is that I = cannot iterate in reversed order. I guess that is because the linked lists = of buckets are only linked in one direction.=C2=A0<br></div><div></div></di= v></blockquote><div><br></div><div>Yes.=C2=A0 When I designed BTrees=C2=A0 = I sought to avoid circular references, because I was hoping that we'd h= ave storages that supported reference-counting garbage collection, but we n= ever did that.</div><div><br></div><div>If I ever redesigned BTrees, I'= d probably make them doubly-linked lists (and probably add more internal po= inters to simplify computation).</div><div><br></div><div>Something else I = noted that you may not have picked up on in my earlier message is that you = can also tune BTrees at the C level.=C2=A0 In particular:</div><div><br></d= iv><div><ul><li>You can adjust the maximum bucket size to better fit your r= equirements, perhaps using much bigger buckets for your application.</li><l= i>You can use different C types that might fit your needs better.=C2=A0</li= ></ul></div><div>Jim</div><div><br></div><div><br></div><div><br></div><div= ><br></div><div><br></div><div>=C2=A0</div><blockquote class=3D"gmail_quote= " style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);= padding-left:1ex"><div dir=3D"ltr"><div>Qiwen<br><br>On Saturday, February = 23, 2019 at 10:07:51 AM UTC-5, Jim Fulton wrote:<blockquote class=3D"gmail_= quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,= 204);padding-left:1ex"><div dir=3D"ltr"><div dir=3D"ltr"><div dir=3D"ltr">O= n Fri, Feb 22, 2019 at 9:30 PM Qiwen Chen <<a rel=3D"nofollow">qwc...@gm= ail.com</a>> wrote:<br></div><div class=3D"gmail_quote"><blockquote clas= s=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid r= gb(204,204,204);padding-left:1ex"><div dir=3D"ltr">If I use IFBTree ( integ= er-keyed float-valued BTree) to store some time series data.</div></blockqu= ote><div><br></div><div>Interesting. What's the domain? Financial data?= Scientific?<br></div><div><br></div><blockquote class=3D"gmail_quote" styl= e=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);paddin= g-left:1ex"><div dir=3D"ltr"> How does the loading work?</div></blockquote>= <div><br></div><div>BTrees store data stored by key in such a way that only= part of a tree needs to be loaded into memory to fetch data for a subset o= f keys.=C2=A0 Similarly, if only a subset of keys (like 1) is modified, the= n only a subset of the BTree is modified and stored.</div><div><br></div><d= iv>See:=C2=A0<a href=3D"https://en.wikipedia.org/wiki/B-tree" rel=3D"nofoll= ow" target=3D"_blank">https://en.wikipedia.org/wiki/B-tree</a></div><div><b= r></div><div>The leaves of the tree, where the data are stored are called b= uckets. Internal tree nodes help find the right bucket for a key or key ran= ge.</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin= :0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"= ><div dir=3D"ltr"> For example, if =C2=A0l want to load the entire time ser= ies into memory, how many trips happen between the client and server?</div>= </blockquote><div><br></div><div>That depends on the access pattern.=C2=A0 = Assuming you iterated over the tree,=C2=A0 you would load roughly N/100 obj= ects, where N is the number of values in the tree.=C2=A0 (This is governed = by a compile-time max bucket-size parameter, which for IFBTrees, 120.)=C2= =A0=C2=A0</div><div>Each load requires a round-trip.=C2=A0=C2=A0</div><div>= <br></div><div>Recently, we added a prefetch API that mitigates round trips= (by effectively doing them in parallel) if you know you're going to lo= ad multiple objects.=C2=A0 This could conceivably leveraged when iterating = over a BTree.</div><div><br></div><div>Loading the entire tree into memory = defeats one of the design goals, which is to have trees that are much large= r than application memory.=C2=A0 Sometimes, when we want to iterate over tr= ees that are larger than memory, we periodically explicitly invoke garbage = collection (normally invoked implicitly at transaction boundaries) to free = memory got leaves were done with.</div><div><br></div><blockquote class=3D"= gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(20= 4,204,204);padding-left:1ex"><div dir=3D"ltr"> In the document, it says it = uses lazy loading.=C2=A0 Does it mean each key value pair is loaded from th= e db to memory one at a time?</div></blockquote><div><br></div><div>No, it = means the minimum number of nodes (internal or bucket) are loaded to retrie= ve a given key or key range.</div><div><br></div><div>The primary use case = of BTrees is storing very large mappings where you usually only want to acc= ess very small subsets of keys.</div><div><br></div><div>There's a feat= ure of our implementation though that might be useful for time series data,= depending on the application.=C2=A0 I mentioned that BTrees are trees of n= odes with data in buckets at the leaves of the trees.=C2=A0 But BTrees are = <i>also</i> linked lists of buckets.=C2=A0 Each internal node has a referen= ce to it's first bucket and each bucket has a reference to the next buc= ket in the tree.=C2=A0 This is to allow efficient iteration.=C2=A0</div><di= v><br></div><div>In the example above, to iterate over the entire tree, we = only had to load the top node and the buckets. We didn't have to load o= r traverse internal nodes.</div><div><br></div><div>As always, picking and = tuning data structures depends on application usage (update and access) pat= terns, but I can imagine time-series applications for which BTrees could wo= rk very well, especially with some compile-time tuning (much larger bucket = sizes and different storage types).</div><div><br></div><div>Early in my ca= reer I worked a lot with hydrologic time series data that was collected ove= r short fixed time intervals (5 or 15 minutes).=C2=A0 This data was very ex= pensive to store at the time (early eighties, when a 300MB disk was the siz= e of a dishwasher and wildly more expensive).=C2=A0 Storage of the data was= wildly important and the nature of this data allowed it to be very compres= sible, typically 90-95%, which was an important factor in it's storage.= </div><div><br></div><div>(I could imagine a variation of BTrees for fixed-= time-interval data that avoided storing time values in buckets.)</div><div>= <br></div><div>Of course, storage is much cheaper now, but we store a lot m= ore data.=C2=A0 The same factors that made a custom storage format for time= -series data attractive in the 80s, makes columnar formats like Parquet and= ORC popular today.</div><div><br></div><div>(Hm, writing that made me wond= er if it would be useful to have a BTree variant that used Numpy/Arrow/xnd = arrays to store bucket data.=C2=A0 Perhaps memory-mapped...Hm....)</div><di= v><br></div><div>Jim=C2=A0</div><div><br></div></div>-- <br><div dir=3D"ltr= ">Jim Fulton<br><a href=3D"http://jimfulton.info" rel=3D"nofollow" target= =3D"_blank">http://jimfulton.info</a><br></div></div></div> </blockquote></div></div> <p></p> -- <br> You received this message because you are subscribed to the Google Groups &= quot;zodb" group.<br> To unsubscribe from this group and stop receiving emails from it, send an e= mail to <a href=3D"mailto:[email protected]" target=3D"_bla= nk">[email protected]</a>.<br> For more options, visit <a href=3D"https://groups.google.com/d/optout" targ= et=3D"_blank">https://groups.google.com/d/optout</a>.<br> </blockquote></div><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"= class=3D"gmail_signature">Jim Fulton<br><a href=3D"http://jimfulton.info" = target=3D"_blank">http://jimfulton.info</a><br></div></div> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups &= quot;zodb" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an e= mail to <a href=3D"mailto:[email protected]">zodb+unsubscri= [email protected]</a>.<br /> For more options, visit <a href=3D"https://groups.google.com/d/optout">http= s://groups.google.com/d/optout</a>.<br /> --000000000000c4718e0582a7699c--