masstree_partitioner_impl.hpp

Go to the documentation of this file.

/*
 * Copyright (c) 2014-2015, Hewlett-Packard Development Company, LP.
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
 * more details. You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 * HP designates this particular file as subject to the "Classpath" exception
 * as provided by HP in the LICENSE.txt file that accompanied this code.
 */
#ifndef FOEDUS_STORAGE_MASSTREE_MASSTREE_PARTITIONER_IMPL_HPP_
#define FOEDUS_STORAGE_MASSTREE_MASSTREE_PARTITIONER_IMPL_HPP_

#include <stdint.h>

#include <algorithm>
#include <cstring>
#include <iosfwd>
#include <queue>
#include <string>
#include <vector>

#include "foedus/fwd.hpp"
#include "foedus/initializable.hpp"
#include "foedus/cache/snapshot_file_set.hpp"
#include "foedus/memory/fwd.hpp"
#include "foedus/memory/page_pool.hpp"
#include "foedus/storage/partitioner.hpp"
#include "foedus/storage/storage_id.hpp"
#include "foedus/storage/masstree/masstree_id.hpp"
#include "foedus/storage/masstree/masstree_log_types.hpp"
#include "foedus/storage/masstree/masstree_page_impl.hpp"
#include "foedus/storage/masstree/masstree_storage.hpp"

namespace foedus {
namespace storage {
namespace masstree {
class MasstreePartitioner final {
 public:
  explicit MasstreePartitioner(Partitioner* parent);

  ErrorStack  design_partition(const Partitioner::DesignPartitionArguments& args);
  bool is_partitionable() const;
  void partition_batch(const Partitioner::PartitionBatchArguments& args) const;
  void sort_batch(const Partitioner::SortBatchArguments& args) const;

  friend std::ostream& operator<<(std::ostream& o, const MasstreePartitioner& v);

 private:
  Engine* const               engine_;
  const StorageId             id_;
  PartitionerMetadata* const  metadata_;
  MasstreePartitionerData*    data_;

  ErrorStack  design_partition_first(const MasstreeIntermediatePage* root);

  void sort_batch_8bytes(const Partitioner::SortBatchArguments& args) const;
  void sort_batch_general(const Partitioner::SortBatchArguments& args) const;

  ErrorStack read_page_safe(MasstreePage* src, MasstreePage* out);
};

struct MasstreePartitionerData final {
  // only for reinterpret_cast
  MasstreePartitionerData() = delete;
  ~MasstreePartitionerData() = delete;

  uint16_t find_partition(const char* key, uint16_t key_length) const;

  uint16_t    partition_count_;
  KeySlice    low_keys_[kMaxIntermediatePointers];
  uint16_t    partitions_[kMaxIntermediatePointers];
};

struct OwnerSamples {
  OwnerSamples(uint32_t nodes, uint32_t subtrees) : nodes_(nodes), subtrees_(subtrees) {
    occurrences_ = new uint32_t[nodes * subtrees];
    std::memset(occurrences_, 0, sizeof(uint32_t) * nodes * subtrees);
    assignments_ = new uint32_t[subtrees];
    std::memset(assignments_, 0, sizeof(uint32_t) * subtrees);
  }
  ~OwnerSamples() {
    delete[] occurrences_;
    occurrences_ = nullptr;
    delete[] assignments_;
    assignments_ = nullptr;
  }

  const uint32_t  nodes_;
  const uint32_t  subtrees_;
  uint32_t*       occurrences_;
  uint32_t*       assignments_;

  void increment(uint32_t node, uint32_t subtree_id) {
    ASSERT_ND(node < nodes_);
    ASSERT_ND(subtree_id < subtrees_);
    ++occurrences_[subtree_id * nodes_ + node];
  }
  uint32_t at(uint32_t node, uint32_t subtree_id) const {
    ASSERT_ND(node < nodes_);
    ASSERT_ND(subtree_id < subtrees_);
    return occurrences_[subtree_id * nodes_ + node];
  }

  uint32_t get_assignment(uint32_t subtree_id) const { return assignments_[subtree_id]; }

  void assign_owners();

  friend std::ostream& operator<<(std::ostream& o, const OwnerSamples& v);
};


inline int compare_keys(
  const char* left,
  uint16_t left_length,
  const char* right,
  uint16_t right_length) {
  uint16_t cmp_length = std::min(left_length, right_length);
  int result = std::memcmp(left, right, cmp_length);
  if (result != 0) {
    return result;
  } else if (left_length < right_length) {
    return -1;
  } else if (left_length > right_length) {
    return 1;
  } else {
    return 0;
  }
}

inline const MasstreeCommonLogType* resolve_log(
  const snapshot::LogBuffer& log_buffer,
  snapshot::BufferPosition pos) {
  const MasstreeCommonLogType* rec = reinterpret_cast<const MasstreeCommonLogType*>(
    log_buffer.resolve(pos));
  ASSERT_ND(rec->header_.get_type() == log::kLogCodeMasstreeInsert
    || rec->header_.get_type() == log::kLogCodeMasstreeDelete
    || rec->header_.get_type() == log::kLogCodeMasstreeUpdate
    || rec->header_.get_type() == log::kLogCodeMasstreeOverwrite);
  return rec;
}

}  // namespace masstree
}  // namespace storage
}  // namespace foedus
#endif  // FOEDUS_STORAGE_MASSTREE_MASSTREE_PARTITIONER_IMPL_HPP_