couchdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Garren Smith <gar...@apache.org>
Subject Re: [DISCUSS] Implementing Mango Indexes for FoundationDB
Date Mon, 15 Apr 2019 09:58:03 GMT
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 <alexmiller@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 <garren@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 <garren@apache.org> wrote:
> >
> >>
> >>
> >> On Tue, Apr 2, 2019 at 3:14 AM Adam Kocoloski <kocolosk@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 <willholley@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
> >>>
> >>>
> >>>
>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message