Re: BTrees! (was Re: Understanding loading mechanism)
Qiwen Chen <[email protected]> Mon, 25 Feb 2019 09:20:44 -0800 (PST)
| Newsgroups | gmane.comp.web.zope.zodb |
|---|---|
| Message-ID | <[email protected]> |
------=_Part_833_1651132715.1551115244894 Content-Type: multipart/alternative; boundary="----=_Part_834_529423266.1551115244895" ------=_Part_834_529423266.1551115244895 Content-Type: text/plain; charset="UTF-8" In this case, i won't be able to leverage the prefetch feature. My application consumes a lot of data but produces very limited amount for persisting. And data for consumption won't be modified in the application. Before i give up on ZODB for this project, maybe I can try the following. First, i can download all the data needed (user defined scope) from a non-ZODB server and create a ZODB file storage on the local disk. That might take a few mins at most. Then i can leverage the lazy loading feature while controlling the memory usage for the calculation process. And all the calculation can still deal with native python objects. Am I right in thinking that way? Essentially I am using ZODB as a on-disk caching for data consumption. Any application data can still write to a ZODB server and it's not a lot of data. Any thoughts? On Sunday, February 24, 2019 at 12:47:11 PM UTC-5, Jim Fulton wrote: > > > > On Sat, Feb 23, 2019 at 2:20 PM Qiwen Chen <[email protected] <javascript:>> > 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] <javascript:>. >> 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. ------=_Part_834_529423266.1551115244895 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">In this case, i won't be able to leverage the prefetch= feature.<div><br></div><div>My application consumes a lot of data but prod= uces very limited amount for persisting. And data for consumption won't= be modified in the application. Before i give up on ZODB for this project,= maybe I can try the following. First, i can download all the data needed (= user defined scope) from a non-ZODB server and create a ZODB file storage o= n the local disk. That might take a few mins at most.=C2=A0 Then i can leve= rage the lazy loading feature while controlling the memory usage for the ca= lculation process. And all the calculation can still deal with native pytho= n objects.=C2=A0 Am I right in thinking that way?=C2=A0 Essentially I am us= ing ZODB as a on-disk caching for data consumption. Any application data ca= n still write to a ZODB server and it's not a lot of data. Any thoughts= ?</div><div><br>On Sunday, February 24, 2019 at 12:47:11 PM UTC-5, Jim Fult= on wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: = 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div= dir=3D"ltr"><br></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On S= at, Feb 23, 2019 at 2:20 PM Qiwen Chen <<a href=3D"javascript:" target= =3D"_blank" gdf-obfuscated-mailto=3D"dsbthDy0AQAJ" rel=3D"nofollow" onmouse= down=3D"this.href=3D'javascript:';return true;" onclick=3D"this.hre= f=3D'javascript:';return true;">[email protected]</a>> wrote:<br>= </div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;b= order-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr">Th= anks for the explanation. Actually it's pretty obvious to me now that t= he loading unit is a bucket in the BTree.=C2=A0<div><br></div><div>The doma= in is Financial Data. My application loads the time series by min and max k= ey 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</div><= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft: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 calc= ulation, the application would know the exact min and max key pairs for a l= ist 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 he= lp 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 To im= plement such an API, BTrees would have to load a bunch of internal nodes 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 p= refetch 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 ne= xt pointer.</div><div><br></div><div>What could, conceivably, be done is to= have BTree iterators prefetch next buckets as buckets are loaded.=C2=A0 Th= en, retrieval of the next bucket could be in flight while an application is= processing the current bucket.=C2=A0 I'd be open to a PR that implemen= ted this under the control of a new=C2=A0 prefetch keyword argument to the = BTree items, keys, and values methods.</div><div><br></div><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"><div>=C2=A0 Any referenc= e you can point me to?<br></div></div></blockquote><div><br></div><div>Pref= etch is a new somewhat experimental method.=C2=A0 It's not documented a= nywhere yet.=C2=A0 Prefetch sounds very appealing until you try to figure o= ut how to leverage it. :-]</div><div><br></div><div>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 ob= jects.=C2=A0 It doesn't return anything, but just hints to the connecti= on and underlying storage that the objects will likely be wanted soon.=C2= =A0 For ZEO, this causes requests to be sent for that data.=C2=A0 When the = data are returned, they're added to the ZEO cache to be available when = the application requests it.=C2=A0 If the application requests the data bef= ore it's returned, the application will block.</div><div><br></div><div= >At the storage level, prefetch has only been implemented for ZEO. It's= ignored for other storages, most notably RelStorage.</div><div>=C2=A0<br><= /div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bo= rder-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><di= v></div><div>In my application, I use the iterator in BTrees extensively. O= ne 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></div></blockquote><div><br></div><div>Yes.=C2=A0 W= hen I designed BTrees=C2=A0 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.</div><div><br></div><div>If I ev= er redesigned BTrees, I'd probably make them doubly-linked lists (and p= robably add more internal pointers 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 p= articular:</div><div><br></div><div><ul><li>You can adjust the maximum buck= et size to better fit your requirements, perhaps using much bigger buckets = for your application.</li><li>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><blo= ckquote 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<b= r><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 di= r=3D"ltr"><div dir=3D"ltr">On Fri, Feb 22, 2019 at 9:30 PM Qiwen Chen <<= a rel=3D"nofollow">[email protected]</a>> wrote:<br></div><div class=3D"g= mail_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"l= tr">If I use IFBTree ( integer-keyed float-valued BTree) 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><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"> How does the load= ing 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 of keys.=C2=A0 Similarly, if only a subset of ke= ys (like 1) is modified, then only a subset of the BTree is modified and st= ored.</div><div><br></div><div>See:=C2=A0<a href=3D"https://en.wikipedia.or= g/wiki/B-tree" rel=3D"nofollow" target=3D"_blank" onmousedown=3D"this.href= =3D'https://www.google.com/url?q\x3dhttps%3A%2F%2Fen.wikipedia.org%2Fwi= ki%2FB-tree\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFHGyNelepnkLnAFz8nlosf9= TTtHA';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';return true;">https= ://en.wikipedia.org/<wbr>wiki/B-tree</a></div><div><br></div><div>The leave= s 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.</div><div>=C2=A0</= div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bor= der-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 series into memory, how m= any 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 objects, where N is the n= umber 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 t= hem in parallel) if you know you're going to load 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 desi= gn goals, which is to have trees that are much larger than application memo= ry.=C2=A0 Sometimes, when we want to iterate over trees that are larger tha= n memory, we periodically explicitly invoke garbage collection (normally in= voked implicitly at transaction boundaries) to free memory got leaves were = done with.</div><div><br></div><blockquote class=3D"gmail_quote" style=3D"m= argin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,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 the db to memory one at= a time?</div></blockquote><div><br></div><div>No, it means the minimum num= ber of nodes (internal or bucket) are loaded to retrieve 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 access very small subset= s of keys.</div><div><br></div><div>There's a feature of our implementa= tion though that might be useful for time series data, depending on the app= lication.=C2=A0 I mentioned that BTrees are trees of nodes with data in buc= kets at the leaves of the trees.=C2=A0 But BTrees are <i>also</i> linked li= sts of buckets.=C2=A0 Each internal node has a reference to it's first = bucket and each bucket has a reference to the next bucket in the tree.=C2= =A0 This is to allow efficient iteration.=C2=A0</div><div><br></div><div>In= the example above, to iterate over the entire tree, we only had to load th= e top node and the buckets. We didn't have to load or traverse internal= nodes.</div><div><br></div><div>As always, picking and tuning data structu= res depends on application usage (update and access) patterns, but I can im= agine time-series applications for which BTrees could work very well, espec= ially with some compile-time tuning (much larger bucket sizes and different= storage types).</div><div><br></div><div>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).=C2=A0 This data was very expensive to store at= the time (early eighties, when a 300MB disk was the size of a dishwasher a= nd wildly more expensive).=C2=A0 Storage of the data was wildly important a= nd the nature of this data allowed it to be very compressible, typically 90= -95%, which was an important factor in it's storage.</div><div><br></di= v><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 c= ourse, storage is much cheaper now, but we store a lot more data.=C2=A0 The= same factors that made a custom storage format for time-series data attrac= tive in the 80s, makes columnar formats like Parquet and ORC popular today.= </div><div><br></div><div>(Hm, writing that made me wonder if it would be u= seful to have a BTree variant that used Numpy/Arrow/xnd arrays to store buc= ket data.=C2=A0 Perhaps memory-mapped...Hm....)</div><div><br></div><div>Ji= m=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" onmousedo= wn=3D"this.href=3D'http://www.google.com/url?q\x3dhttp%3A%2F%2Fjimfulto= n.info\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHmSNcJBOrf0pC5m6u_EGiOTWHw1g= ';return true;" onclick=3D"this.href=3D'http://www.google.com/url?q= \x3dhttp%3A%2F%2Fjimfulton.info\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHmS= NcJBOrf0pC5m6u_EGiOTWHw1g';return true;">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"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"= dsbthDy0AQAJ" rel=3D"nofollow" onmousedown=3D"this.href=3D'javascript:&= #39;;return true;" onclick=3D"this.href=3D'javascript:';return true= ;">zodb+uns...@googlegroups.<wbr>com</a>.<br> For more options, visit <a href=3D"https://groups.google.com/d/optout" targ= et=3D"_blank" rel=3D"nofollow" onmousedown=3D"this.href=3D'https://grou= ps.google.com/d/optout';return true;" onclick=3D"this.href=3D'https= ://groups.google.com/d/optout';return true;">https://groups.google.com/= d/<wbr>optout</a>.<br> </blockquote></div><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"= >Jim Fulton<br><a href=3D"http://jimfulton.info" target=3D"_blank" rel=3D"n= ofollow" onmousedown=3D"this.href=3D'http://www.google.com/url?q\x3dhtt= p%3A%2F%2Fjimfulton.info\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHmSNcJBOrf= 0pC5m6u_EGiOTWHw1g';return true;" onclick=3D"this.href=3D'http://ww= w.google.com/url?q\x3dhttp%3A%2F%2Fjimfulton.info\x26sa\x3dD\x26sntz\x3d1\x= 26usg\x3dAFQjCNHmSNcJBOrf0pC5m6u_EGiOTWHw1g';return true;">http://jimfu= lton.info</a><br></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_834_529423266.1551115244895-- ------=_Part_833_1651132715.1551115244894--