src/kudu/tablet/delta_key.h

// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.
#pragma once

#include <cstddef>
#include <string>

#include "kudu/common/rowid.h"
#include "kudu/common/timestamp.h"
#include "kudu/gutil/port.h"
#include "kudu/gutil/strings/substitute.h"
#include "kudu/util/slice.h"
#include "kudu/util/status.h"

namespace kudu {

class faststring;

namespace tablet {

// The type of the delta.
enum DeltaType {
  // REDO delta files contain the mutations that were applied
  // since the base data was last flushed/compacted. REDO deltas
  // are sorted by increasing op timestamp.
  REDO,
  // UNDO delta files contain the mutations that were applied
  // prior to the time the base data was last flushed/compacted
  // and allow to execute point-in-time snapshot scans. UNDO
  // deltas are sorted by decreasing op timestamp.
  UNDO
};

const char* DeltaType_Name(DeltaType t);

// An alternate representation of the raw DeltaType. By templating on
// DeltaTypeSelector instead of DeltaType, it's far easier to reference the
// DeltaType at runtime. For example:
//
// template <typename T>
// void Foo() {
//   cout << T::kTag == REDO ? "REDO" : "UNDO" << endl;
// }
//
// Foo<DeltaTypeSelector<REDO>>(); // prints 'REDO'
template <DeltaType Type>
struct DeltaTypeSelector {
  static constexpr DeltaType kTag = Type;
};

// Each entry in the delta memrowset or delta files is keyed by the rowid
// which has been updated, as well as the timestamp which performed the update.
class DeltaKey {
 public:
  DeltaKey() :
    row_idx_(-1)
  {}

  DeltaKey(rowid_t id, Timestamp timestamp)
      : row_idx_(id), timestamp_(timestamp) {}

  // Encode this key into the given buffer.
  //
  // The encoded form of a DeltaKey is guaranteed to share the same sort
  // order as the DeltaKey itself when compared using memcmp(), so it may
  // be used as a string key in indexing structures, etc.
  void EncodeTo(faststring *dst) const {
    EncodeRowId(dst, row_idx_);
    timestamp_.EncodeTo(dst);
  }


  // Decode a DeltaKey object from its serialized form.
  //
  // The slice 'key' should contain the encoded key at its beginning, and may
  // contain further data after that.
  // The 'key' slice is mutated so that, upon return, the decoded key has been removed from
  // its beginning.
  //
  // This function is called frequently, so is marked HOT to encourage inlining.
  Status DecodeFrom(Slice *key) ATTRIBUTE_HOT {
    Slice orig(*key);
    if (!PREDICT_TRUE(DecodeRowId(key, &row_idx_))) {
      // Out-of-line the error case to keep this function small and inlinable.
      return DeltaKeyError(orig, "bad rowid");
    }

    if (!PREDICT_TRUE(timestamp_.DecodeFrom(key))) {
      // Out-of-line the error case to keep this function small and inlinable.
      return DeltaKeyError(orig, "bad timestamp");
    }

    return Status::OK();
  }

  std::string ToString() const {
    return strings::Substitute("(row $0@ts$1)", row_idx_, timestamp_.ToString());
  }

  // Compare this key to another key. Delta keys are sorted by ascending rowid,
  // then ascending timestamp, except if this is an undo delta key, in which case the
  // the keys are sorted by ascending rowid and then by _descending_ timestamp so that
  // the op closer to the base data comes first.
  template<DeltaType Type>
  int CompareTo(const DeltaKey &other) const;

  rowid_t row_idx() const { return row_idx_; }

  const Timestamp &timestamp() const { return timestamp_; }

 private:
  // Out-of-line error construction used by DecodeFrom.
  static Status DeltaKeyError(const Slice& orig, const char* err);

  // The row which has been updated.
  rowid_t row_idx_;

  // The timestamp of the op which applied the update.
  Timestamp timestamp_;
};

template<>
inline int DeltaKey::CompareTo<REDO>(const DeltaKey &other) const {
  if (row_idx_ < other.row_idx_) {
    return -1;
  } else if (row_idx_ > other.row_idx_) {
    return 1;
  }

  return timestamp_.CompareTo(other.timestamp_);
}

template<>
inline int DeltaKey::CompareTo<UNDO>(const DeltaKey &other) const {
  if (row_idx_ < other.row_idx_) {
    return -1;
  } else if (row_idx_ > other.row_idx_) {
    return 1;
  }

  return other.timestamp_.CompareTo(timestamp_);
}

template<DeltaType Type>
struct DeltaKeyLessThanFunctor {
  bool operator() (const DeltaKey& a, const DeltaKey& b) const {
    return a.CompareTo<Type>(b) < 0;
  }
};

template<DeltaType Type>
struct DeltaKeyEqualToFunctor {
  bool operator() (const DeltaKey& a, const DeltaKey& b) const {
    return a.CompareTo<Type>(b) == 0;
  }
};

struct DeltaKeyHashFunctor {
  size_t operator() (const DeltaKey& key) const {
    return (key.row_idx() * 31ULL) + key.timestamp().ToUint64();
  }
};

} // namespace tablet
} // namespace kudu