foedus::storage::masstree::MasstreePartitioner Class Reference

Partitioner for a masstree storage. More...

Detailed Description

Partitioner for a masstree storage.

The partitioner for masstree simply designs n pairs of a low-key and node.

Low-key

Low-key marks the inclusive beginning of the partition with arbitrary length. For example,

• (low-key: zero-length string, node=0)
• (low-key: "e", node=1)
• (low-key: "k", node=2)
• (low-key: "r", node=1)
• (low-key: "w", node=2)

This means there are 5 partitions placed in 3 nodes. "abc" would be in node 0, "z" would be in node 2, etc. We so far don't do KeySlice optimization used in the transactional-processing side. We might do that later, but let's see if log gleaner is fast enough without fancy optimization.

Design policy

Not suprisingly, the partition design logic is more complex than array and sequential. But, we still want to make partitioner/composer as simple as possible. The compromise is as follows.

One slice as partition key

For efficiency and simplicity we always use one KeySlice (8-bytes) as low-key. We initially explored arbitrary length partitiong keys, but it causes too much overhead and complexity. By using one KeySlice, all comparison is just an integer comparison and fixed-sized.

Enumerating partitions

With this simplification, partition design just checks the root page of first layer. If it's a border page, everything to node 0. If it's an intermediate page, we use separators in it as partitions. Stupidly simple. For each pointer, we determine the owner node simply based on the last updater of the pointed page, which is a rough statistics in the page header (no correctness guaranteed).

Expected issues

The scheme above is so simple and easy to implement/maintain. Of course the simplicity has its price. If all keys start with a common 8-bytes, we are screwed. If pointer-distributions are skewed, eg one pointer leads to billion records while other pointers lead to just one record, it will result in one node receiving almost all records. Nevertheless, the branch-page/partition framework above is flexible enough to address the issue later. We just need advanced algorithm to enumerate branch pages and determine owners. Let's keep it simple for now, and work on this later.

Note

This is a private implementation-details of Masstree Storage, thus file name ends with _impl. Do not include this header from a client program. There is no case client program needs to access this internal class.

Definition at line 98 of file masstree_partitioner_impl.hpp.

#include <masstree_partitioner_impl.hpp>

Public Member Functions
	MasstreePartitioner (Partitioner *parent)
	MasstreePartitioner methods. More...
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

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

Constructor & Destructor Documentation

foedus::storage::masstree::MasstreePartitioner::MasstreePartitioner ( Partitioner *  parent )

explicit

MasstreePartitioner methods.

Definition at line 53 of file masstree_partitioner_impl.cpp.

References foedus::storage::PartitionerMetadata::locate_data(), and foedus::storage::PartitionerMetadata::valid_.

  : engine_(parent->get_engine()),
    id_(parent->get_storage_id()),
    metadata_(PartitionerMetadata::get_metadata(engine_, id_)) {
  if (metadata_->valid_) {
    data_ = reinterpret_cast<MasstreePartitionerData*>(metadata_->locate_data(engine_));
  } else {
    data_ = nullptr;
  }
}

Here is the call graph for this function:

Member Function Documentation

ErrorStack foedus::storage::masstree::MasstreePartitioner::design_partition

(

const Partitioner::DesignPartitionArguments &

args

)

Definition at line 64 of file masstree_partitioner_impl.cpp.

References foedus::storage::PartitionerMetadata::allocate_data(), ASSERT_ND, foedus::memory::AlignedMemory::assure_capacity(), CHECK_ERROR, foedus::storage::extract_numa_node_from_snapshot_pointer(), foedus::memory::AlignedMemory::get_block(), foedus::Attachable< CONTROL_BLOCK >::get_control_block(), foedus::memory::EngineMemory::get_global_volatile_page_resolver(), foedus::Engine::get_memory_manager(), foedus::Engine::get_soc_count(), foedus::storage::masstree::MasstreePage::is_border(), foedus::storage::masstree::MasstreeIntermediatePointerIterator::is_valid(), foedus::storage::masstree::kInfimumSlice, foedus::storage::kPageSize, foedus::kRetOk, foedus::storage::PartitionerMetadata::locate_data(), foedus::storage::PartitionerMetadata::mutex_, foedus::cache::SnapshotFileSet::read_page(), foedus::memory::GlobalVolatilePageResolver::resolve_offset(), foedus::storage::masstree::MasstreeStorageControlBlock::root_page_pointer_, foedus::storage::Partitioner::DesignPartitionArguments::snapshot_files_, foedus::storage::DualPagePointer::snapshot_pointer_, foedus::storage::PartitionerMetadata::valid_, foedus::storage::DualPagePointer::volatile_pointer_, foedus::storage::Partitioner::DesignPartitionArguments::work_memory_, and WRAP_ERROR_CODE.

Referenced by foedus::storage::Partitioner::design_partition().

                                                   {
  MasstreeStorage storage(engine_, id_);
  MasstreeStorageControlBlock* control_block = storage.get_control_block();
  const memory::GlobalVolatilePageResolver& resolver
    = engine_->get_memory_manager()->get_global_volatile_page_resolver();

  // Read current volatile version and previous snapshot version of the root page
  WRAP_ERROR_CODE(args.work_memory_->assure_capacity(kPageSize * 2));
  Page* buffers = reinterpret_cast<Page*>(args.work_memory_->get_block());
  MasstreeIntermediatePage* vol = reinterpret_cast<MasstreeIntermediatePage*>(buffers);
  MasstreeIntermediatePage* snp = reinterpret_cast<MasstreeIntermediatePage*>(buffers + 1);
  SnapshotPagePointer snapshot_page_id = control_block->root_page_pointer_.snapshot_pointer_;
  MasstreeIntermediatePage* root_volatile = reinterpret_cast<MasstreeIntermediatePage*>(
    resolver.resolve_offset(control_block->root_page_pointer_.volatile_pointer_));
  CHECK_ERROR(read_page_safe(root_volatile, vol));
  if (snapshot_page_id != 0) {
    WRAP_ERROR_CODE(args.snapshot_files_->read_page(snapshot_page_id, snp));
  }

  soc::SharedMutexScope scope(&metadata_->mutex_);  // protect this metadata
  if (metadata_->valid_) {
    // someone has already initialized this??
    LOG(FATAL) << "Masstree-" << id_ << " partition already designed??:" << *this;
  }
  WRAP_ERROR_CODE(metadata_->allocate_data(engine_, &scope, sizeof(MasstreePartitionerData)));
  data_ = reinterpret_cast<MasstreePartitionerData*>(metadata_->locate_data(engine_));

  ASSERT_ND(!vol->is_border());
  if (engine_->get_soc_count() == 1U) {
    // no partitioning needed
    data_->partition_count_ = 1;
    data_->low_keys_[0] = kInfimumSlice;
    data_->partitions_[0] = 0;
  } else {
    // simply the separators in root page is the partition keys.
    // if we already have a snapshot page, we use the same partition keys, though
    // assigned nodes might be changed
    data_->partition_count_ = 0;
    if (snapshot_page_id == 0) {
      CHECK_ERROR(design_partition_first(vol));
    } else {
      // So far same assignment as previous snapshot.
      // TODO(Hideaki) check current volatile pages to change the assignments.
      for (MasstreeIntermediatePointerIterator it(snp); it.is_valid(); it.next()) {
        data_->low_keys_[data_->partition_count_] = it.get_low_key();
        SnapshotPagePointer pointer = it.get_pointer().snapshot_pointer_;
        uint16_t assignment = extract_numa_node_from_snapshot_pointer(pointer);
        data_->partitions_[data_->partition_count_] = assignment;
        ++data_->partition_count_;
      }
    }
  }

  metadata_->valid_ = true;
  LOG(INFO) << "Masstree-" << id_ << std::endl << " partitions:" << *this;
  return kRetOk;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::storage::masstree::MasstreePartitioner::is_partitionable

(

)

const

Definition at line 280 of file masstree_partitioner_impl.cpp.

References foedus::storage::masstree::MasstreePartitionerData::partition_count_.

Referenced by foedus::storage::Partitioner::is_partitionable(), and partition_batch().

                                                 {
  return data_->partition_count_ > 1U;
}

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreePartitioner::partition_batch

(

const Partitioner::PartitionBatchArguments &

args

)

const

Definition at line 284 of file masstree_partitioner_impl.cpp.

References foedus::debugging::RdtscWatch::elapsed(), foedus::storage::masstree::MasstreePartitionerData::find_partition(), foedus::storage::masstree::MasstreeCommonLogType::get_key(), is_partitionable(), foedus::storage::masstree::MasstreeCommonLogType::key_length_, foedus::storage::Partitioner::PartitionBatchArguments::log_buffer_, foedus::storage::Partitioner::PartitionBatchArguments::log_positions_, foedus::storage::Partitioner::PartitionBatchArguments::logs_count_, foedus::storage::masstree::MasstreePartitionerData::partition_count_, foedus::storage::masstree::resolve_log(), foedus::storage::Partitioner::PartitionBatchArguments::results_, and foedus::debugging::RdtscWatch::stop().

Referenced by foedus::storage::Partitioner::partition_batch().

                                                                                              {
  debugging::RdtscWatch stop_watch;
  if (!is_partitionable()) {
    std::memset(args.results_, 0, sizeof(PartitionId) * args.logs_count_);
    return;
  }

  for (uint32_t i = 0; i < args.logs_count_; ++i) {
    const MasstreeCommonLogType* rec = resolve_log(args.log_buffer_, args.log_positions_[i]);
    uint16_t key_length = rec->key_length_;
    const char* key = rec->get_key();
    args.results_[i] = data_->find_partition(key, key_length);
  }
  stop_watch.stop();
  VLOG(0) << "Masstree-:" << id_ << " took " << stop_watch.elapsed() << "cycles"
    << " to partition " << args.logs_count_ << " entries. #partitions=" << data_->partition_count_;
  // if these binary searches are too costly, let's optimize them.
}

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreePartitioner::sort_batch

(

const Partitioner::SortBatchArguments &

args

)

const

Definition at line 489 of file masstree_partitioner_impl.cpp.

References foedus::storage::Partitioner::SortBatchArguments::logs_count_, foedus::storage::Partitioner::SortBatchArguments::longest_key_length_, foedus::storage::Partitioner::SortBatchArguments::shortest_key_length_, and foedus::storage::Partitioner::SortBatchArguments::written_count_.

Referenced by foedus::storage::Partitioner::sort_batch().

                                                                                    {
  if (args.logs_count_ == 0) {
    *args.written_count_ = 0;
    return;
  }

  if (args.longest_key_length_ == sizeof(KeySlice)
      && args.shortest_key_length_ == sizeof(KeySlice)) {
    sort_batch_8bytes(args);
  } else {
    sort_batch_general(args);
  }
}

Here is the caller graph for this function:

Friends And Related Function Documentation

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

friend

Definition at line 503 of file masstree_partitioner_impl.cpp.

                                                                    {
  o << "<MasstreePartitioner>";
  if (v.data_) {
    o << "<partition_count_>" << v.data_->partition_count_ << "</partition_count_>"
      << "<partitions>";
    for (uint16_t i = 0; i < v.data_->partition_count_; ++i) {
      o << std::endl << "  <partition node=\"" << v.data_->partitions_[i] << "\">"
        << assorted::Hex(v.data_->low_keys_[i], 16)
        << "</partition>";
    }
    o << "</partitions>";
  } else {
    o << "Not yet designed";
  }
  o << "</MasstreePartitioner>";
  return o;
}

---

The documentation for this class was generated from the following files:

• /home/shino/foedus_code/foedus-core/include/foedus/storage/masstree/masstree_partitioner_impl.hpp
• /home/shino/foedus_code/foedus-core/src/foedus/storage/masstree/masstree_partitioner_impl.cpp