revision-id: 57659c37daab6048c7d7ec4a6434b39182bd8825 (v5.8-1044-g57659c37d) parent(s): cba804d57d693e5cf7763d404f29d2483992f96a author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2019-07-14 23:19:46 +0300 message: MDEV-19986: MyRocks: Range Locking: SeekForUpdate support: backward scans Add support for backward scans. --- utilities/transactions/pessimistic_transaction.cc | 179 +++++++++++++++------- 1 file changed, 123 insertions(+), 56 deletions(-) diff --git a/utilities/transactions/pessimistic_transaction.cc b/utilities/transactions/pessimistic_transaction.cc index cbac16437..1d46436e7 100644 --- a/utilities/transactions/pessimistic_transaction.cc +++ b/utilities/transactions/pessimistic_transaction.cc @@ -97,19 +97,17 @@ class LockingIterator : public Iterator { // Note: MyRocks doesn't ever call these: virtual void SeekToFirst() override; - virtual void SeekToLast() override { assert(0); } + virtual void SeekToLast() override; virtual void Seek(const Slice& target) override; // Position at the last key in the source that at or before target. // The iterator is Valid() after this call iff the source contains // an entry that comes at or before target. - virtual void SeekForPrev(const Slice& target) { assert(0); } + virtual void SeekForPrev(const Slice& target) override; virtual void Next() override; - virtual void Prev() override { - assert(0); // TODO: implement this - } + virtual void Prev() override; virtual Slice key() const override { assert(Valid()); @@ -125,8 +123,74 @@ class LockingIterator : public Iterator { return status_; } -private: - void ScanForward(const Slice& target, bool call_next); + private: + + template <bool forward> void Scan(const Slice& target, bool call_next) { + if (!iter_->Valid()) { + status_ = iter_->status(); + return; + } + + while (1) { + /* + note: the underlying iterator checks iterator bounds, so we don't need + to check them here + */ + auto end_key = iter_->key(); + if (forward) + status_ = txn_->GetRangeLock(cfh_, Endpoint(target), Endpoint(end_key)); + else + status_ = txn_->GetRangeLock(cfh_, Endpoint(end_key), Endpoint(target)); + + if (!status_.ok()) { + // Failed to get a lock (most likely lock wait timeout) + return; + } + + //Ok, now we have a lock which is inhibiting modifications in the range + // Somebody might have done external modifications, though: + // - removed the key we've found + // - added a key before that key. + if (forward) + iter_->Seek(target); + else + iter_->SeekForPrev(target); + + if (call_next && iter_->Valid()) { + if (forward) + iter_->Next(); + else + iter_->Prev(); + } + + if (iter_->Valid()) { + int invert= forward? 1 : -1; + if (cfh_->GetComparator()->Compare(iter_->key(), end_key) * invert <= 0) { + // Ok, the key is within the range. + status_ = Status::OK(); + break; + } else { + // We've got a row but it is outside the range we've locked. + // Re-try the lock-and-read step. + continue; + } + } else { + // There's no row (within the iterator bounds perhaps). Exit now. + // (we might already have locked a range in this function but there's + // nothing we can do about it) + status_ = iter_->status(); + break; + } + } + } + + inline void ScanForward(const Slice& target, bool call_next) { + Scan<true>(target, call_next); + } + + inline void ScanBackward(const Slice& target, bool call_next) { + Scan<false>(target, call_next); + } }; @@ -145,15 +209,30 @@ Iterator* PessimisticTransaction::GetLockingIterator( return nullptr; } +/* + @brief + Seek to the first key K that is equal or greater than target, + locking the range [target; K]. +*/ void LockingIterator::Seek(const Slice& target) { iter_->Seek(target); ScanForward(target, false); } +void LockingIterator::SeekForPrev(const Slice& target) { + iter_->SeekForPrev(target); + ScanBackward(target, false); +} + /* - Lock from the current position up to the next key - (This is basically like Seek(right_after(current_position)) + @brief + Move the iterator to the next key, locking the range between the current + and the next key. + + @detail + Implementation is similar to Seek(next_key). Since we don't know what the + next_key is, we reach it by calling { Seek(current_key); Next(); } */ void LockingIterator::Next() { assert(Valid()); @@ -165,65 +244,53 @@ void LockingIterator::Next() { ScanForward(Slice(current_key), true); } -// Note: MyRocks never uses this as call as it has index_nr as prefix for all -// keys. -void LockingIterator::SeekToFirst() { +/* + @brief + Move the iterator to the previous key, locking the range between the current + and the previous key. +*/ - iter_->SeekToFirst(); - if (!iter_->Valid()) { - status_ = iter_->status(); - return; - } +void LockingIterator::Prev() { + assert(Valid()); std::string current_key = iter_->key().ToString(); - ScanForward(Slice(current_key), true); + iter_->Prev(); + ScanBackward(Slice(current_key), true); } -void LockingIterator::ScanForward(const Slice& target, bool call_next) { +/* + @detail + Ideally, this function should + - find the first key $first_key + - lock the range [-inf; $first_key] + - return, the iterator is positioned on $first_key + + The problem here is that we cannot have "-infinity" bound. + + Note: we don't have a practical use for this function - MyRocks always + searches within one index_name.table_name, which means we are only looking + at the keys with index_number as the prefix. +*/ + +void LockingIterator::SeekToFirst() { + iter_->SeekToFirst(); if (!iter_->Valid()) { status_ = iter_->status(); return; } - while (1) { - /* - TODO: the underlying iterator respects iterator bounds, so we don't need - to check them here - */ - auto end_key = iter_->key(); - status_ = txn_->GetRangeLock(cfh_, Endpoint(target), Endpoint(end_key)); - if (!status_.ok()) { - // Failed to get a lock (most likely lock wait timeout) - return; - } + std::string current_key = iter_->key().ToString(); + ScanForward(Slice(current_key), true); +} - //Ok, now we have a lock which is inhibiting modifications in the range - // Somebody might have done external modifications, though: - // - removed the key we've found - // - added a key before that key. - iter_->Seek(target); - if (call_next && iter_->Valid()) - iter_->Next(); - - if (iter_->Valid()) { - if (cfh_->GetComparator()->Compare(iter_->key(), end_key) <= 0) { - // Ok, the key is within the range. - status_ = Status::OK(); - break; - } else { - // We've got a row but it is outside the range we've locked. - // Re-try the lock-and-read step. - continue; - } - } else { - // There's no row (within the iterator bounds perhaps). Exit now. - // (we might already have locked a range in this function but there's - // nothing we can do about it) - status_ = iter_->status(); - break; - } - } +/* + @detail + See SeekToFirst. +*/ + +void LockingIterator::SeekToLast() { + status_ = Status::NotSupported("Not implemented"); } /////////////////////////////////////////////////////////////////////////////