Partitioner for an array storage. More...

Detailed Description

Partitioner for an array storage.

There are a few options to implement partitioning for an array with trade-offs between simplicity/efficiency and accuracy/flexibility.

Current policy: So far our choice prefers simplicity/efficiency. We split the whole range of the array into kInteriorFanout buckets and assign the partition based on who currently holds the page under the root page. Designing this policy is extremely simple; we just take a look at the root page of this storage and sees the volatile pointer's NUMA node.

Balancing policy: We so far balance the partition assignments so that no partitition receives more than average buckets where average is buckets/partitions. The excessive bucket is given to needy ones that do not have enough buckets.

Limitations of current policy: Of course this simple policy has some issue. One issue is that if the root page has direct children fewer than the number of partitions, some partition does not receive any bucket even if there are many more indirect children. That doesn't happen so often, though. We outputs warnings if this happens.

Alternative policy: Another choice we considered was a vector of ArrayRange in an arbitrary length over which we do binary search. However, this is more expensive. For a simple data structure like array, it might not pay off.

Note: This is a private implementation-details of Array 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 72 of file array_partitioner_impl.hpp.

#include <array_partitioner_impl.hpp>

Public Member Functions
	ArrayPartitioner (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

ArrayOffset	get_array_size () const

uint8_t	get_array_levels () const

const PartitionId *	get_bucket_owners () const

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

Constructor & Destructor Documentation

foedus::storage::array::ArrayPartitioner::ArrayPartitioner ( Partitioner * parent )

explicit

Definition at line 43 of file array_partitioner_impl.cpp.

References ASSERT_ND, foedus::soc::SharedMutex::is_initialized(), foedus::storage::PartitionerMetadata::locate_data(), foedus::storage::PartitionerMetadata::mutex_, and foedus::storage::PartitionerMetadata::valid_.

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

Here is the call graph for this function:

Member Function Documentation

ErrorStack foedus::storage::array::ArrayPartitioner::design_partition ( const Partitioner::DesignPartitionArguments & args )

Definition at line 73 of file array_partitioner_impl.cpp.

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

                                                 {
   ASSERT_ND(metadata_->mutex_.is_initialized());
   ASSERT_ND(data_ == nullptr);
   ArrayStorage storage(engine_, id_);
   ASSERT_ND(storage.exists());
   ArrayStorageControlBlock* control_block = storage.get_control_block();
 
   soc::SharedMutexScope mutex_scope(&metadata_->mutex_);
   ASSERT_ND(!metadata_->valid_);
   WRAP_ERROR_CODE(metadata_->allocate_data(engine_, &mutex_scope, sizeof(ArrayPartitionerData)));
   data_ = reinterpret_cast<ArrayPartitionerData*>(metadata_->locate_data(engine_));
 
   data_->array_levels_ = storage.get_levels();
   data_->array_size_ = storage.get_array_size();
 
   if (storage.get_levels() == 1U || engine_->get_soc_count() == 1U) {
     // No partitioning needed.
     data_->bucket_owners_[0] = 0;
     data_->partitionable_ = false;
     data_->bucket_size_ = data_->array_size_;
     metadata_->valid_ = true;
     return kRetOk;
   }
 
   data_->partitionable_ = true;
   ASSERT_ND(storage.get_levels() >= 2U);
 
   // bucket size is interval that corresponds to a direct child of root.
   // eg) levels==2 : leaf, levels==3: leaf*kInteriorFanout, ...
   data_->bucket_size_ = control_block->route_finder_.get_records_in_leaf();
   for (uint32_t level = 1; level < storage.get_levels() - 1U; ++level) {
     data_->bucket_size_ *= kInteriorFanout;
   }
 
   const memory::GlobalVolatilePageResolver& resolver
     = engine_->get_memory_manager()->get_global_volatile_page_resolver();
   // root page is guaranteed to have volatile version.
   ArrayPage* root_page = reinterpret_cast<ArrayPage*>(
     resolver.resolve_offset(control_block->root_page_pointer_.volatile_pointer_));
   ASSERT_ND(!root_page->is_leaf());
 
   // how many direct children does this root page have?
   uint16_t direct_children = storage.get_array_size() / data_->bucket_size_ + 1U;
   if (storage.get_array_size() % data_->bucket_size_ != 0) {
     ++direct_children;
   }
 
   // do we have enough direct children? if not, some partition will not receive buckets.
   // Although it's not a critical error, let's log it as an error.
   uint16_t total_partitions = engine_->get_options().thread_.group_count_;
   ASSERT_ND(total_partitions > 1U);  // if not, why we are coming here. it's a waste.
 
   if (direct_children < total_partitions) {
     LOG(ERROR) << "Warning-like error: This array doesn't have enough direct children in root"
       " page to assign partitions. #partitions=" << total_partitions << ", #direct children="
       << direct_children << ". array=" << storage;
   }
 
   // two paths. first path simply sees volatile/snapshot pointer and determines owner.
   // second path addresses excessive assignments, off loading them to needy ones.
   std::vector<uint16_t> counts(total_partitions, 0);
   const uint16_t excessive_count = (direct_children / total_partitions) + 1;
   std::vector<uint16_t> excessive_children;
   for (uint16_t child = 0; child < direct_children; ++child) {
     const DualPagePointer &pointer = root_page->get_interior_record(child);
     PartitionId partition;
     if (!pointer.volatile_pointer_.is_null()) {
       partition = pointer.volatile_pointer_.get_numa_node();
     } else {
       // if no volatile page, see snapshot page owner.
       partition = extract_numa_node_from_snapshot_pointer(pointer.snapshot_pointer_);
       // this ignores the case where neither snapshot/volatile page is there.
       // however, as we create all pages at ArrayStorage::create(), this so far never happens.
     }
     ASSERT_ND(partition < total_partitions);
     if (counts[partition] >= excessive_count) {
       excessive_children.push_back(child);
     } else {
       ++counts[partition];
       data_->bucket_owners_[child] = partition;
     }
   }
 
   // just add it to the one with least assignments.
   // a stupid loop, but this part won't be a bottleneck (only 250 elements).
   for (uint16_t child : excessive_children) {
     PartitionId most_needy = 0;
     for (PartitionId partition = 1; partition < total_partitions; ++partition) {
       if (counts[partition] < counts[most_needy]) {
         most_needy = partition;
       }
     }
 
     ++counts[most_needy];
     data_->bucket_owners_[child] = most_needy;
   }
 
   metadata_->valid_ = true;
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

uint8_t foedus::storage::array::ArrayPartitioner::get_array_levels ( ) const

Definition at line 60 of file array_partitioner_impl.cpp.

References foedus::storage::array::ArrayPartitionerData::array_levels_, and ASSERT_ND.

                                                  {
   ASSERT_ND(data_);
   return data_->array_levels_;
 }

ArrayOffset foedus::storage::array::ArrayPartitioner::get_array_size ( ) const

Definition at line 55 of file array_partitioner_impl.cpp.

References foedus::storage::array::ArrayPartitionerData::array_size_, and ASSERT_ND.

Referenced by partition_batch().

                                                    {
   ASSERT_ND(data_);
   return data_->array_size_;
 }

Here is the caller graph for this function:

const PartitionId * foedus::storage::array::ArrayPartitioner::get_bucket_owners ( ) const

Definition at line 64 of file array_partitioner_impl.cpp.

References ASSERT_ND, and foedus::storage::array::ArrayPartitionerData::bucket_owners_.

Referenced by partition_batch().

                                                              {
   ASSERT_ND(data_);
   return data_->bucket_owners_;
 }

Here is the caller graph for this function:

bool foedus::storage::array::ArrayPartitioner::is_partitionable ( ) const

Definition at line 68 of file array_partitioner_impl.cpp.

References ASSERT_ND, and foedus::storage::array::ArrayPartitionerData::partitionable_.

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

                                               {
   ASSERT_ND(data_);
   return data_->partitionable_;
 }

Here is the caller graph for this function:

void foedus::storage::array::ArrayPartitioner::partition_batch ( const Partitioner::PartitionBatchArguments & args ) const

Definition at line 175 of file array_partitioner_impl.cpp.

References ASSERT_ND, foedus::storage::array::ArrayPartitionerData::bucket_size_, foedus::assorted::ConstDiv::div64(), get_array_size(), get_bucket_owners(), foedus::log::BaseLogType::header_, is_partitionable(), foedus::storage::array::kInteriorFanout, foedus::log::kLogCodeArrayIncrement, foedus::log::kLogCodeArrayOverwrite, foedus::storage::Partitioner::PartitionBatchArguments::log_buffer_, foedus::storage::Partitioner::PartitionBatchArguments::log_positions_, foedus::log::LogHeader::log_type_code_, foedus::storage::Partitioner::PartitionBatchArguments::logs_count_, foedus::storage::array::ArrayCommonUpdateLogType::offset_, foedus::snapshot::LogBuffer::resolve(), foedus::storage::Partitioner::PartitionBatchArguments::results_, and foedus::log::LogHeader::storage_id_.

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

                                                                                            {
   if (!is_partitionable()) {
     std::memset(args.results_, 0, sizeof(PartitionId) * args.logs_count_);
     return;
   }
 
   ASSERT_ND(data_->bucket_size_ > 0);
   assorted::ConstDiv bucket_size_div(data_->bucket_size_);
   for (uint32_t i = 0; i < args.logs_count_; ++i) {
     const ArrayCommonUpdateLogType *log = reinterpret_cast<const ArrayCommonUpdateLogType*>(
       args.log_buffer_.resolve(args.log_positions_[i]));
     ASSERT_ND(log->header_.log_type_code_ == log::kLogCodeArrayOverwrite
         || log->header_.log_type_code_ == log::kLogCodeArrayIncrement);
     ASSERT_ND(log->header_.storage_id_ == id_);
     ASSERT_ND(log->offset_ < get_array_size());
     uint64_t bucket = bucket_size_div.div64(log->offset_);
     ASSERT_ND(bucket < kInteriorFanout);
     args.results_[i] = get_bucket_owners()[bucket];
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::array::ArrayPartitioner::sort_batch ( const Partitioner::SortBatchArguments & args ) const

Definition at line 312 of file array_partitioner_impl.cpp.

References ASSERT_ND, foedus::memory::AlignedMemory::assure_capacity(), foedus::storage::array::compact_logs(), foedus::debugging::StopWatch::elapsed_ms(), foedus::memory::AlignedMemory::get_block(), foedus::storage::Partitioner::SortBatchArguments::logs_count_, foedus::storage::array::prepare_sort_entries(), foedus::debugging::StopWatch::stop(), foedus::storage::Partitioner::SortBatchArguments::work_memory_, and foedus::storage::Partitioner::SortBatchArguments::written_count_.

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

                                                                                  {
   if (args.logs_count_ == 0) {
     *args.written_count_ = 0;
     return;
   }
 
   // we so far sort them in one path.
   // to save memory, we could do multi-path merge-sort.
   // however, in reality each log has many bytes, so log_count is not that big.
   args.work_memory_->assure_capacity(sizeof(SortEntry) * args.logs_count_);
 
   debugging::StopWatch stop_watch_entire;
 
   ASSERT_ND(sizeof(SortEntry) == 16U);
   SortEntry* entries = reinterpret_cast<SortEntry*>(args.work_memory_->get_block());
   prepare_sort_entries(args, entries);
 
   debugging::StopWatch stop_watch;
   // Gave up non-gcc support because of aarch64 support. yes, we can also assume __uint128_t.
   // CPU profile of partition_array_perf: 50% (introsort_loop) + 7% (other inlined).
   std::sort(
     reinterpret_cast<__uint128_t*>(entries),
     reinterpret_cast<__uint128_t*>(entries + args.logs_count_));
   stop_watch.stop();
   VLOG(0) << "Sorted " << args.logs_count_ << " log entries in " << stop_watch.elapsed_ms() << "ms";
 
   uint32_t result_count = compact_logs(args, entries);
 
   stop_watch_entire.stop();
   VLOG(0) << "Array-" << id_ << " sort_batch() done in  " << stop_watch_entire.elapsed_ms()
       << "ms  for " << args.logs_count_ << " log entries, compacted them to"
         << result_count << " log entries";
   *args.written_count_ = result_count;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

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

friend

Definition at line 347 of file array_partitioner_impl.cpp.

                                                                  {
   o << "<ArrayPartitioner>";
   if (v.data_) {
     o << "<array_size_>" << v.data_->array_size_ << "</array_size_>"
       << "<bucket_size_>" << v.data_->bucket_size_ << "</bucket_size_>";
     for (uint16_t i = 0; i < kInteriorFanout; ++i) {
       o << "<range bucket=\"" << i << "\" partition=\"" << v.data_->bucket_owners_[i] << "\" />";
     }
   } else {
     o << "Not yet designed";
   }
   o << "</ArrayPartitioner>";
   return o;
 }

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

/home/shino/foedus_code/foedus-core/include/foedus/storage/array/array_partitioner_impl.hpp
/home/shino/foedus_code/foedus-core/src/foedus/storage/array/array_partitioner_impl.cpp

Detailed Description

Public Member Functions

Friends

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation