Ok, going to spit-ball an idea I had while falling asleep last night.  I'm sure there are tons of corner cases and issues I haven't thought of, but maybe it will lead to more discussion so I'll go out on a limb and post it in the hopes that maybe it can get folks creative juices flowing.  The overall idea is that RGW partitions shards into ranges like in typical range-based sharding approaches, but in each range we have a number of shards.  Objects are distributed over those shards in a (hand-wavy) round-robin-like fashion.  This is done to give us some degree of parallelism for writes/deletes within a given range.  The number of shards per pool remains (mostly?) static.  The range-pool dynamically splits based on the total number of entries which results in the associated shards moving half their keys into shards in the new range pool. The goal behind all of this would be to limit the impact of splits (now range-pool splits) to only a section of the overall bucket and cap the number of objects participating in a split.  A second simultaneous goal is to allow for write parallelism within a given range while not significantly hurting bucket listing times (or if we must, at least cap the pain). Example (using decimal naming for easy of explanation): Object Name: "15" Existing range-shard pools: "0-2, 3-6, 7-20" shards per pool: 8 Reading: 1) Each RGW server has a consistent view of the range-shard pools. 2) Determine the range pool associated with the object. 3) Use hand-wavy-round-robin technique and shards-per-pool count to pick the shard. 4) Follow normal RGW procedure to read the object from the shard. Writing: 1) Each RGW server has a consistent view of the range-shard pools. 2) Determine the range pool associated with the object. 3) Use hand-wavy-round-robin technique and shards-per-pool count to pick the shard. 4) Follow normal RGW procedure to write to the shard. Splitting: Say that placing object "15" should result in a range split. 1) Lock the bucket and pool "7-20". 2) Modify pool 7-20 into 14-20 3) Create new pool 7-13 4) spawn redistribution of the pool map to RGW servers 4) lock pool 7-13 5) unlock the bucket 6) create new shards for pool 7-13 7a) if handy-wavy-RR provides psuedo-random placement: <placeholder, maybe fetch less keys than the whole set> 7b) if hand-wavy-RR provides no uniformity: fetch all keys, sort them, and move the last half from 7-13 to 14-20. 8) unlock pools 7-13 and 14-20. Listing: 1) Find the range pool(s) for the requested range 2a) if hand-wavy-RR provides pseudo-random placement: <placeholder, maybe fetch less keys than the whole set> 2b) if hand-wavy-RR provides no uniformity: fetch all keys from each shard, sort them, return first N and throw away the rest (like we do now). Questions: 1) RR based on the name doesn't guarantee uniformity. 2) Halton sequence gets us somewhere between random and uniform placement? 2) Hashing would get us psuedo-random placement. 3) Alternate technique to preserve ordering with deterministic placement (Eric? Matt?) 4) How does versioning work in this scheme? 5) What else have I screwed up? Mark On 9/9/19 12:33 PM, Mark Nelson wrote: > Hi Casey, > > > Sorry for the slow reply, too many things going on at once and the > days slipped by faster than I realized!  So overall I get the idea > behind this, but I keep finding myself worried that it's trading one > problem (blocking writes during reshard) for others (complexity, more > metadata reads/writes, incompatibility with versioned buckets, etc).  > I'm not sure I have much to add at this point.  I wonder if there's > some kind of hybrid of (mostly) static hash-based sharding and > range-based sharding we could do that would let us avoid blocking > writes to all shards and instead only block writes to smaller > selections of the DB for shorter periods of time.  That would be a > much bigger change but maybe would sort of fall in line with some of > the changes Matt has talked about for preserving ordering for faster > bucket listing?  Might be totally infeasible, but that's sort of the > direction my brain headed after reading your proposal. > > > Anyway, that's it for now, but I'll try to keep thinking about it in > the background. > > > Mark > > On 8/29/19 11:59 AM, Casey Bodley wrote: >> sharing a design for feedback. please let me know if you spot any >> other races, issues or optimizations! >> >> current resharding steps: >> 1) copy the 'source' bucket instance into a new 'target' bucket >> instance with a new instance id >> 2) flag all source bucket index shards with RESHARD_IN_PROGRESS >> 3) flag the source bucket instance with RESHARD_IN_PROGRESS >> 4) list all omap entries in the source bucket index shards >> (cls_rgw_bi_list) and write each entry to its target bucket index >> shard (cls_rgw_bi_put) >> 5a) on success: link target bucket instance, delete source bucket >> index shards, delete source bucket instance >> 5b) on failure: reset RESHARD_IN_PROGRESS flag on source bucket index >> shards, delete target bucket index shards, delete target bucket instance >> >> the current blocking strategy is enforced on the source bucket index >> shards. any write operations received by cls_rgw while the >> RESHARD_IN_PROGRESS flag is set are rejected with >> ERR_BUSY_RESHARDING. radosgw handles these errors by waiting/polling >> until the reshard finishes, then it resends the operation to the new >> target bucket index shard. >> >> to avoid blocking write ops during a reshard, we could instead apply >> their bucket index operations to both the source and target bucket >> index shards in parallel. this includes both the 'prepare' op to >> start the transaction, and the asynchronous 'complete' to commit. >> allowing both buckets to mutate during reshard introduces several new >> races: >> >> I) between steps (2) and (3), radosgw doesn't yet see the >> RESHARD_IN_PROGRESS flag in the bucket instance info, so doesn't know >> to send the extra index operations to the target bucket index shard >> >> II) operations applied on the target bucket index shards could be >> overwritten by the omap entries copied from the source bucket index >> shards in step (4) >> >> III) radosgw sends a 'prepare' op to the source bucket index shard >> before step (2), then sends the async 'complete' op to the source >> bucket index shard after (2). before step (5), this complete op would >> fail with ERR_BUSY_RESHARDING. after step (5), it would fail with >> ENOENT. since the complete is async, and we've already replied to the >> client, it's too late for any recovery >> >> IV) radosgw sends an operation to both the source and target bucket >> index shards that races with (5) and fails with ENOENT on either the >> source shard (5a) or the target shard (5b) >> >> >> introducing a new generation number or 'reshard_epoch' to each bucket >> that increments on a reshard attempt can help to resolve these races. >> so in step (2), the call to cls_rgw_set_bucket_resharding() would >> also increment the bucket index shard's reshard_epoch. similarly, >> step (3) would increment the bucket instance's reshard_epoch. >> >> to resolve the race in (I), cls_rgw would reject bucket index >> operations with a reshard_epoch older than the one stored in the >> bucket index shard. this ERR_BUSY_RESHARDING error would direct >> radosgw to re-read its bucket instance, detect the reshard in >> progress, and resend the operation to both the source and target >> bucket index shards with the updated reshard_epoch >> >> to resolve the race in (II), cls_rgw_bi_put() would have to test >> whether the given key exists before overwriting >> >> the race in (III) is benign, because the 'prepared' entry was >> reliably stored in the source shard before reshard, so we're >> guaranteed to see a copy on the target shard. even though the >> 'complete' operation isn't applied, the dir_suggest mechanism will >> detect the incomplete transaction and repair the index the next time >> the target bucket is listed >> >> the race in (IV) can be treated as a success if the operation >> succeeds on the target bucket index shard. if it fails on the target >> shard, radosgw needs to re-read the bucket entrypoint and instance to >> retarget the operation >> >> >> one thing this strategy cannot handle is versioned buckets. some >> index operations for versioning (namely cls_rgw_bucket_link_olh and >> cls_rgw_bucket_unlink_instance) involve writes to two or more related >> omap entries. because step (4) copies over single omap entries, it >> can't preserve the consistency of these relationships once we allow >> mutation. so we'd need to stick with the blocking strategy for >> versioned buckets >> _______________________________________________ >> Dev mailing list -- dev(a)ceph.io >> To unsubscribe send an email to dev-leave(a)ceph.io

On 9/11/19 3:20 AM, Yehuda Sadeh-Weinraub wrote: This idea of reading from the source shard before writing to the target sounds really useful for versioning support! I don't think we even need the overlay to get the correct result here. Consider the write of an object 'foo' in a versioned bucket: - From the source shard, read the current olh entry for name 'foo' (ENOENT is okay), then apply the index operation. - On the target shard, send a transaction that includes a 'bi put' of that olh entry, along with the actual index operation. As long as this 'bi put' rejects the olh entry if the target already has one with a newer olh epoch, I think this enough to maintain consistency between the olh and instance entries. Even if two writes to the same name 'foo' race during reshard (and so both read the same entry with olh_epoch=5, for example), the first transaction applied to the target shard will 'bi put' olh_epoch=5, then the index op will increment it to 6. The second racing transaction will skip the 'bi put', and its op will increment again to 7. The only difference is that the source and target shards may apply these versioned ops in a different order, so end up with a different olh log and current version. I think we can reconcile this with the same 'bi put' strategy during update_olh(), then replaying the olh log of the target shard. Only if the reshard fails or cancels would we see any inconsistency, because the next call to follow_olh() would replay the source shard's olh log and revert to the different current version. > - Listing will be extended to allow iterating on both the source > overlay and the target. > - iterate over the source bi overlay and try to apply the entries on > the target (will need to verify that target has older entry there). > Target object removals at this point will not completely remove keys, > but rather keep a negative entry so that it would still have the > required info to apply the source overlay. > > 4. Finalize > - reset resharding flag on target > - link target > - iterate over target and squash negative entries > - delete source bi > > Notes: > - The original resharding process will be modified a bit, but will > still be used for first phase. > - objclass changes: overlay functionality (writes, listings, bi*), > negative entries > - rgw core changes: listing to support merge with overlay, bucket > index writes in second phase need to apply relevant overlay key(s). > - versioning should work > - reshard cancellation is not complicated, needs to squash overlay, > but can be done without locking > > > Yehuda > >> _______________________________________________ >> Dev mailing list -- dev(a)ceph.io >> To unsubscribe send an email to dev-leave(a)ceph.io