Re: BTrees! (was Re: Understanding loading mechanism)
Qiwen Chen <[email protected]> Sat, 23 Feb 2019 13:20:53 -0800 (PST)
| Newsgroups | gmane.comp.web.zope.zodb |
|---|---|
| Message-ID | <[email protected]> |
------=_Part_252_423987488.1550956853670 Content-Type: multipart/alternative; boundary="----=_Part_253_1583367570.1550956853670" ------=_Part_253_1583367570.1550956853670 Content-Type: text/plain; charset="UTF-8" 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. 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. Any reference you can point me to? 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. 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] <javascript:>> > 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. ------=_Part_253_1583367570.1550956853670 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">Thanks for the explanation. Actually it's pretty obvio= us to me now that the loading unit is a bucket in the BTree.=C2=A0<div><br>= </div><div>The domain is Financial Data. My application loads the time seri= es by min and max key pair. It's read heavy and write light. So it'= s well suited.=C2=A0</div><div><br></div><div>The prefetch feature is the e= xact 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 object= s. I would like to load them in one go.=C2=A0 Any reference you can point m= e to?</div><div><br></div><div>In my application, I use the iterator in BTr= ees extensively. One big limitation is that I cannot iterate in reversed or= der. I guess that is because the linked lists of buckets are only linked in= one direction.=C2=A0</div><div><br></div><div>Qiwen<br><br>On Saturday, Fe= bruary 23, 2019 at 10:07:51 AM UTC-5, Jim Fulton wrote:<blockquote class=3D= "gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc s= olid;padding-left: 1ex;"><div dir=3D"ltr"><div dir=3D"ltr"><div dir=3D"ltr"= >On Fri, Feb 22, 2019 at 9:30 PM Qiwen Chen <<a href=3D"javascript:" tar= get=3D"_blank" gdf-obfuscated-mailto=3D"4JDBF_ZcAQAJ" rel=3D"nofollow" onmo= usedown=3D"this.href=3D'javascript:';return true;" onclick=3D"this.= href=3D'javascript:';return true;">[email protected]</a>> wrote:<= br></div><div class=3D"gmail_quote"><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">If I use IFBTree ( integer-keyed float-valued B= Tree) to store some time series data.</div></blockquote><div><br></div><div= >Interesting. What's the domain? Financial data? Scientific?<br></div><= div><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= "ltr"> How does the loading work?</div></blockquote><div><br></div><div>BTr= ees store data stored by key in such a way that only part of a tree needs t= o be loaded into memory to fetch data for a subset of keys.=C2=A0 Similarly= , if only a subset of keys (like 1) is modified, then only a subset of the = BTree is modified and stored.</div><div><br></div><div>See:=C2=A0<a href=3D= "https://en.wikipedia.org/wiki/B-tree" target=3D"_blank" rel=3D"nofollow" o= nmousedown=3D"this.href=3D'https://www.google.com/url?q\x3dhttps%3A%2F%= 2Fen.wikipedia.org%2Fwiki%2FB-tree\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCN= FHGyNelepnkLnAFz8nlosf9TTtHA';return true;" onclick=3D"this.href=3D'= ;https://www.google.com/url?q\x3dhttps%3A%2F%2Fen.wikipedia.org%2Fwiki%2FB-= tree\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFHGyNelepnkLnAFz8nlosf9TTtHA&#= 39;;return true;">https://en.wikipedia.org/<wbr>wiki/B-tree</a></div><div><= br></div><div>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 ra= nge.</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margi= n: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 se= ries 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 ob= jects, 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" target=3D"_blank" rel=3D"= nofollow" onmousedown=3D"this.href=3D'http://www.google.com/url?q\x3dht= tp%3A%2F%2Fjimfulton.info\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHmSNcJBOr= f0pC5m6u_EGiOTWHw1g';return true;" onclick=3D"this.href=3D'http://w= ww.google.com/url?q\x3dhttp%3A%2F%2Fjimfulton.info\x26sa\x3dD\x26sntz\x3d1\= x26usg\x3dAFQjCNHmSNcJBOrf0pC5m6u_EGiOTWHw1g';return true;">http://jimf= ulton.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]">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 /> ------=_Part_253_1583367570.1550956853670-- ------=_Part_252_423987488.1550956853670--