<p>Hi all</p>
<p>I would like to get some public opinion on this approach. Basically I have a huge metrics dateset in Google cloud bigtable. Currently all my queries go directly to the server as scans or multigets. This is all fine when the other of the result matches that of the rows. But when trying to fetch rows sorted by something other than the primary key like the value of a column value I need to do a large scan and sort it in the application which can be pretty slow and wasteful considering the fact that most of the queries are of the form "get top 10 rows sort by x" where x is a column name. </p>
<p>I looked for some options and basically came back with either making a secondary index in bigtable with the key having the sort key as prefix or caching on the client. </p>
<p>As the query pattern is only stable within a single user ie user 1 wants stuff sorted by x while user 2 wants things sorted by y, creating large number of secondary index keys seems like a road to hell. </p>
<p>I am now exploring the client side caching option but wanted to check if there is some prior art that I can derive on rather than reinvent the wheel.</p>
<p>Basic problem is: given a query look at the range it covers and if that range has been inserted into local storage, use it to answer else populate missing parts of the range and then use it to build the result.</p>
<p>So the things that I need to track is the ranges that are in the database locally and datastructure that can answer the tell me given a start and end key, if it already is covered by the cache. Something like an interval tree I suppose. </p>
<p>Any comments on my approach or am I barking up the wrong tree here. </p>
<hr/>**评论：**<br/><br/>bak2013: <pre><p>Use spanner, it'll build those indexes for you.</p></pre>ankurcha: <pre><p>I considered that but I need much higher write throughput. </p>
<p>EDIT: Let me elaborate</p>
<p>The bigtable cluster is currently the backend of an analytics database that accepts a large volume of write traffic and based on my calculations, it seemed like Spanner would cost a lot more to run. Furthermore the cost of running a Spanner cluster to meet the write load > $100K per month</p></pre>epiris: <pre><blockquote>
<p>As the query pattern is only stable within a single user ie user 1 wants stuff sorted by x while user 2 wants things sorted by y, creating large number of secondary index keys seems like a road to hell.</p>
</blockquote>
<p>Should your dataset have a user column so you can sort by name? Or leave the existing columns as is and add an additional column for sorting and set it to the user if need be?</p></pre>ankurcha: <pre><p>Could you elaborate? AFAIK Hbase/BigTable only sorts by rowkey and having it in a separate column would require a full scan. The rowkey already has the format:</p>
<pre><code><tableid>/<account>/<day>/<asset-id>
</code></pre>
<p>This means for a single <account>/<day> i can fetch all the assets sorted by id but I want to get them sorted by another value (for example visit_count).</p></pre>epiris: <pre><p>I’m sorry, when I read that I some how interpreted it by sorting by user in the sql light cache, not sorting by a arbitrary column a user may prefer in Bigtable. Will your daily data sets fit in memory? If so you got a lot of flexibility and I would break it into two parts.</p>
<p>First the portion that syncs all the missing chunks of data into a local google/btree (this data may be better suited for a prefix tree, but google btree is the only data structure I import because I’ve used and tested it so much.) with a item that has all the fields normalized into a structure the way you want.</p>
<p>I would then use that to make inserts into one or more completely separate btrees that share the same free list (assuming you occasionally flush data out if not doesn’t really help much accept to preallocate) with an Item that implements your key sorting you want. You may be able to get by with a single tree if your sorting permits it, but I always just make a second tree if I end up starting to type assert multiple structures in my range queries items to differentiate sorting schemes, in my experience it’s asking for bugs. Maybe this doesn’t help (again) but might get you thinking some. Good luck.</p></pre>ankurcha: <pre><p>I believe a part of the data can fit in memory but not a full day. Some of the users may have a large number of <assets> and may request multiple <day>s so it would be unreasonable put that all in memory.</p>
<p>I did consider using google/btree at first but given SQLite is basically b*tree and b+tree under the hood, I chose it to make development/debugging easier at the same time using the hosts ssd drive to handle larger than memory cases. </p>
<p>That said, the most usual query would be: </p>
<pre><code>get me the list of all <asset>s for my <account> sorted by <metric> for the last <n> days
</code></pre>
<p>I will ruminate on your suggestion a little more, i am still not clear on how to do the "figure out which chunks are missing" in the local copy. Do you have a particular algorithm/methodology in mind?</p></pre>epiris: <pre><blockquote>
<p>Do you have a particular algorithm/methodology in mind?</p>
</blockquote>
<p>If I’m interpreting your problem correctly, a query of range [start, end] will always yield the same values and your queries will usually be a range of days. So first thing that comes to mind is my local table regardless of how I choose to approach filling data will become fragmented. So I’ll solve that first by adding additional meta data to my local table, a column that can simply represent 3 mutually exclusive states: start, end, none. Each time I fill my local table I’ll mark the start and end rows from the remote query so I may use it when a local query is made to see if my data complete. If for a given local query for account across n days, there is no start or end edges then I have a valid cache and may perform a query. If there is one or more edges I could fetch the entire range or be clever as I want to for populating the missing ranges.</p>
<p>May be way off but this is just what comes to mind, the key to keeping synchronized with the remote source is the remote queries ranges stored in the local tables at each row edge. Everything else should come easy, minimum chunk sizes per remote query will cause less rescans, allowing partial head / tail back fills for local table with a few simple heuristics verses just full range invalidation will probably have a big impact too depending on your usage patterns. Happy coding.</p></pre>
