Hi Alex, Thanks for the really detailed explanation on transaction size calculation. That is really helpful. Adding a limit to number of indexes is a good idea.
Cheers Garren On Fri, Apr 12, 2019 at 3:58 AM Alex Miller <alexmil...@apple.com.invalid> wrote: > There was some discussion on the FDB forums previously about how to do > index backfill, > If you hadn’t seen it before, but it’s already reasonably similar to what > you’ve proposed: > > https://forums.foundationdb.org/t/best-way-to-add-an-index-on-already-existing-data/97/2 > > There's also two related topics that I'd like to provide some context and > flavor on: > 1. The 10MB transaction size limit. > 2. The performance/latency/throughput implications of writing to multiple > disjoint keys versus multiple nearby keys. > > ### Transaction Size Limit > > There was some previous concern surrounding the FDB 10MB transaction limit, > what it means for CouchDB, and how to communicate the effective maximum > document size to users. Index-on-write will impact this as well, as index > writes will be counted against the 10MB limit. > > As I don't believe I've seen a precise definition yet of the maximum size > of a > document allowed in CouchDB-on-FDB, let us assume it's defined as > "whatever FDB > will accept". It would then be possible that a document can be inserted > that > just barely fits within the size limits, and then indexes can be defined > that > apply to the document. One is now left with a document that exists, and is > valid in the database, but couldn't be read and re-inserted into the > database, > because it would exceed the size limit. My largest concern would be that > this > would have bad implications on CouchDB replication. > > Although the transaction limit is 10MB, it's generally advisable to aim to > stay > under 1MB for the cluster to perform well. I've generally seen latency > start > to get strange for all clients when one client starts exceeding ~5MB. If > one > requires the total size of a document to stay less than 1MB, then this > comfortably leaves room for indexes in the commit request, and the above > case > would be relatively unlikely. > > Exactly how unlikely involves dissecting exactly how the transaction size > limit > is calculated. > > The 10MB limit applies to the size of the commit request, and not to the > sum of > the key-value pair sizes, as one might expect. The largest difference > between > the two meanings is that read and write conflict ranges count against the > 10MB > limit. The rough formula for calculating commit size is: > > $$ 2*len(keys read) + 3*len(keys written) + len(values written) $$ > > Each `get()` adds a read conflict range of the read key and the > sequentially > next key. Each `set()` adds a write conflict range the same way, in > addition > to having to send the actual key and value. This is the source of the > `2*` and > `3*` multipliers. > > `getRange()` adds a read conflict range that exactly reflects the requested > range. However, there is no `setRange()` to automatically optimize the > write > conflict ranges added for inserting sequential values. If one is inserting > keys that given the data model represent one collective, sequential unit, > such > as a full document exploded across multiple key-value pairs, it's > advisable to > use `addWriteConflictRange(firstKey, lastKey+1)` to collapse each > individual > write conflict range into one large write conflict range, and thus greatly > reduce the size of the commit request that will be sent. > > So using this optimization, blindly inserting a document using the scheme > proposed by the "exploded KV" approach, one would end up with a formula > looking > more like > > $$ 2*len(keys read) + 2*len(one key) + len(keys written) + len(values > written) $$ > > With index-on-write, we now need to add inserting (prefix/value/key, "") > for each > index entry into the equation: > > $$ 2*len(keys read) + 2*len(one key) + len(keys written) + len(values > written) + > number of indexes * 3 * ( len(prefix) + len(one value) + len(one key) ) > $$ > > And there's no similar write conflict range optimization that can be done, > as > index writes will be non-sequential and spread widely across the keyspace. > > Index types that can cause a large number of entries to be written will > have an > even larger affect on total commit size. I’ve been using the mental > example of > indexing all the elements of an array nested deep within a document. > However, > if I’ve read CouchDB documentation correctly, all of the index types that > can > cause this explosion are grouped as part of Mango Search indexes, and thus > out > of scope for this proposal. Mango JSON indexes seem to have a direct > correlation > that one (index,field) pair will turn into one Key-Value write to FDB. > Convenient! > > Therefore, in order for a user to run into Mango JSON index-induced > transaction > size limits, they would have to manually add an astounding number of > indexes. > I've failed to quickly find an answer as to if there's an existing maximum > number of Mango JSON indexes that can be added in a CouchDB instance, but > if > there is, this might not be a concern anyway. > > The worst case would be that each field of a document is indexed. > Assuming the > "exploded KV" proposal as the representation, each key and value would be > repeated 3 more times, and thus this would turn into > > $$ 2*len(keys read) + 2*len(one key) + 3*len(prefix) + 4*len(keys written) > + 4*len(values written) $$ > > So if an maximum exploded KV size of 1MB is chosen, transaction commit > requests > would be expected to stay roughly under 4MB. > > However, if you're thinking into the future, and considering that whatever > choice is taken for Mango JSON indexes should also be taken for Mango > Search > indexes as well, the above is definitely a concern. > > ### Indexing Write Penalty > > And, as we're now discussing what would happen with thousands of indexes > defined, let's briefly discuss what impact that would have on actually > committing that transaction. > > With most distributed databases, each index added equates to an additional > shard of data involved in the transaction, and thus likely an additional > server > and RPC. This would lead to an increase in latency and concurrency control > costs, as more indexes are added. This adds a strong cost to each > additional > index. One much larger than the actual cost of the disk IO involved in > doing > the actual index write. > > FoundationDB does all commits against a distributed write-ahead-log, and > asynchronously to the commit, applies the data to each shard of data > involved in > the transaction. This means that a commit of 5 adjacent keys and 5 keys > randomly distributed across the keyspace will be processed in the same way > by > the transaction subsystem. One would actually see better throughput at > saturation when writing to randomly distributed keys, as the work of > applying > those mutations gets sharded across multiple storage servers. > > Creating many indexes still means more disk IO, but is comparatively > cheaper on > FDB than other distributed database architectures. > > > On Apr 11, 2019, at 5:42 AM, Garren Smith <gar...@apache.org> wrote: > > > > > > I was chatting to Adam yesterday and I want to explore the index-on-write > > indexing for Mango a bit more. I know there has been a bit of a > discussion > > that we should only use a background process to build mango indexes but I > > think that building indexes as documents are created/updated along > combined > > with background processing for existing documents will be easier to > > implement. Especially in the beginning as we build the new fdb layer. > > > > Below is the process for building a new index: > > > > 1. When a user defines a new index on an existing database, save the > index > > definition and also save the sequence that the index was added at. The > > index should also be marked that it is in a `building` phase so it won’t > > be used yet to service queries. (I’ll come back to this later) > > 2. Any write requests after that must read the new index definition and > > update the index. When updating the new index, the writers should assume > > that previous versions of the document have already been indexed. > > 3. At the same time a background process will start reading sections of > the > > changes feed and building the index, this background process will keep > > processing the changes read until it reaches the sequence number that the > > index was saved at. Once it reaches that point, the index is up to date > and > > will be marked as `active` and can be used to service queries. > > 4. There are some subtle behaviour around step 3 that is worth > mentioning. > > The background process will have the 5 second transaction limit, so it > will > > process smaller parts of the changes feed. Which means that it won’t have > > one consistent view of the changes feed throughout the index building > > process. This will lead to a conflict situation. For example when the > > background process transaction is adding a document to the index while at > > the same time a write request has a transaction that is updating the same > > document. There are two possible outcomes to this, if the background > > process wins, the write request will get a conflict. At that point the > > write request will try to process the document again, read the old values > > for that document, remove them from the index and add the new values to > the > > index. If the write request wins, and the background process gets a > > conflict, then the background process can try again, the document would > > have been removed from its old position in the changes feed and moved to > > the later position, so the background process won’t see the document and > > will then move on to the next one. > > 5. One other feature to add is to an index progress tracker. We can do > this > > by using doc_count for the database, and then have a counter value that > the > > background workers can increment with the number of documents it updated > > for each batch update. We would also have to update this counter on > write > > requests while the index is in building mode. > > 6. Something we can also explore is splitting the building of the index > > across multiple workers, we can use the `get_boundary_keys` [1] API call > on > > the changes feed to get the full list of the changes feed keys grouped by > > partition boundaries and then split that by workers. > > > > Adding a building and active state to the index’s is a bit of a breaking > > change, but I think its the right way to go. Currently with Mango what > can > > happen is a user creates an index and then immediately does a query that > > would use that index. Mango would then have to build the whole index > before > > responding to that request. In this new index-on-write process, Mango > would > > ignore the new index until it is active which I think is the better way > to > > go on this. > > > > Finally, a big acknowledgment to Adam who is the major brains behind this > > design. > > > > What do you think, I would like to hear any thoughts, questions or > > suggestions on this design. > > > > Cheers > > Garren > > > > [1] > > > https://apple.github.io/foundationdb/api-python.html?highlight=boundary_keys#fdb.locality.fdb.locality.get_boundary_keys > > > > On Mon, Apr 8, 2019 at 3:50 PM Garren Smith <gar...@apache.org> wrote: > > > >> > >> > >> On Tue, Apr 2, 2019 at 3:14 AM Adam Kocoloski <kocol...@apache.org> > wrote: > >> > >>> Hi Will, great comments, I have replies to a couple of them. > >>> > >>>> On Apr 1, 2019, at 5:21 AM, Will Holley <willhol...@gmail.com> wrote: > >>>> > >>>> 2. Does the ICU sort key have a bounded length? Mostly I'm wondering > >>>> whether we can guarantee that the generated keys will fit within the > >>>> maximum FDB key length or if there needs to be some thought as to the > >>>> failure mode / workaround. As Adam mentioned, it seems fine to store > an > >>>> encoded key given Mango (currently) always fetches the associated > >>> document > >>>> / fields from the primary index to filter on anyway. It might even be > >>>> beneficial to have an additional layer of indirection and allow > multiple > >>>> docs to be associated with each row so that we can maintain compact > >>> keys. > >>> > >>> Interesting thought on that layer of indirection; it reminds me of an > >>> optimization applied in the Record Layer’s text indexes. Would have to > >>> compare whether the extra reads needed to maintain the index that way > are > >>> an acceptable tradeoff. > >>> > >>> Good point on the sort key sizes, I’ve not seen any way to place a > >>> reliably safe upper bound on the size of one that might be generated. > The > >>> ICU folks have some hand-wavey guidance at > >>> > http://userguide.icu-project.org/collation/architecture#TOC-Sort-key-size, > >>> but it seems like we might be able to dig a little deeper. > >>> > >>> I personally haven’t given much thought to a workaround where a > >>> user-defined index key exceeds 10 KB. We’ll definitely need to handle > that > >>> failure mode safely even without the sort key complication — people try > >>> crazy things :) > >>> > >> > >> For the 10 KB error, I think we should just return an error. As a > >> comparison, MongoDB has a 1024 Byte limit > >> https://docs.mongodb.com/manual/reference/limits/#Index-Key-Limit > >> > >> > >>>> 3. I don't immediately see how you clear previous values from the > index > >>>> when a doc is updated, but I could easily be missing something obvious > >>> :) > >>> > >>> Ah yeah, this part wasn’t explicit, was it? > >>> > >>> I think the idea is that these are simple indexes on specific fields > of a > >>> document, and we have a data model where those fields are already > stored as > >>> their own keys in FDB, so there’s no need (in the case of Mango) to > >>> maintain a separate docid -> {viewid, [keys]} mapping like we do today > in > >>> each view group. Rather, the flow would go something like > >>> > >>> 1) Check which fields are supposed to be indexed > >>> 2) Retrieve values for those fields in the ?DOCUMENTS space for the > >>> parent revision > >>> 3) Compare the parent values with the ones supplied in this > transaction; > >>> if any indexed values change, clear the old ones and insert the new > ones > >>> > >>> with some additional caveats around checking that the supplied edit is > >>> actually going to be winning (and therefore indexed) version after the > >>> commit succeeds. > >>> > >>>> 4. Regarding "Index on write" behaviour, is there something in the > >>> existing > >>>> design (Mango overlaying mrview / lucene) that would prevent this? I > can > >>>> see some benefit for certain workloads (and headaches for others) but > I > >>>> don't see that it's necessarily coupled to the Mango design given > >>>> background indexing of new/changed indexes needs to be supported > anyway. > >>> > >>> I’m not sure I understand your question. In my mind the reason “index > on > >>> write" is more applicable for Mango JSON than for generalized views is > >>> because in the view case batching is currently quite important to > achieve > >>> good throughput to the JS system. You’re of course correct that we > need to > >>> be able to re-generate Mango JSON indexes in the background as well. > >>> > >>> Adam > >>> > >>> > >>> > >
