Composer for an masstree storage. More...

Detailed Description

Composer for an masstree storage.

This is the most complex composer out of the four storage types.

Differences from volatile pages

There are a few fundamental differences from volatile world.

Very high fill factor. Almost 100%.
No foster children.
All keys are completely sorted by keys in boundary pages, which speeds up cursor.

Constructing pages that match volatile pages well: One of the differences from the simpler array storage is that page boundaries depend on the data. If the snapshot pages have all different page boundaries from volatile pages, the only snapshot pointer we can install after snapshotting is the root pointer. We can only drop the entire volatile pages in that case. In the current version, this is the case. We drop everything and we don't consider where's the page bounary in the volatile world. This is one of major todos. However, it should be just an implementation issue. "Peeking" the volatile world's page boundary is not a difficult thing especially because we don't care 100% accuracy; if the page boundary doesn't match occasionally, that's fine. We just use it to loosely guide the choice of page boundaries in snapshot pages.

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 69 of file masstree_composer_impl.hpp.

#include <masstree_composer_impl.hpp>

Public Member Functions
	MasstreeComposer (Composer *parent)
	MasstreeComposer methods. More...

std::string	to_string () const

ErrorStack	compose (const Composer::ComposeArguments &args)

ErrorStack	construct_root (const Composer::ConstructRootArguments &args)

Composer::DropResult	drop_volatiles (const Composer::DropVolatilesArguments &args)
	drop_volatiles and related methods More...

void	drop_root_volatile (const Composer::DropVolatilesArguments &args)

Constructor & Destructor Documentation

foedus::storage::masstree::MasstreeComposer::MasstreeComposer ( Composer * parent )

explicit

MasstreeComposer methods.

Definition at line 71 of file masstree_composer_impl.cpp.

References ASSERT_ND, and foedus::storage::Storage< CONTROL_BLOCK >::exists().

   : engine_(parent->get_engine()),
     storage_id_(parent->get_storage_id()),
     storage_(engine_, storage_id_) {
   ASSERT_ND(storage_.exists());
 }

Here is the call graph for this function:

Member Function Documentation

ErrorStack foedus::storage::masstree::MasstreeComposer::compose ( const Composer::ComposeArguments & args )

Definition at line 78 of file masstree_composer_impl.cpp.

References foedus::storage::Composer::ComposeArguments::base_epoch_, CHECK_ERROR, foedus::debugging::StopWatch::elapsed_ms(), foedus::DefaultInitializable::initialize(), foedus::storage::kMasstreeStorage, foedus::storage::masstree::MasstreeComposeContext::kMaxLevels, foedus::kRetOk, foedus::storage::Composer::ComposeArguments::log_streams_, foedus::storage::Composer::ComposeArguments::log_streams_count_, foedus::debugging::StopWatch::stop(), to_string(), foedus::DefaultInitializable::uninitialize(), and foedus::storage::Composer::ComposeArguments::work_memory_.

Referenced by foedus::storage::Composer::compose().

                                                                          {
   VLOG(0) << to_string() << " composing with " << args.log_streams_count_ << " streams.";
   debugging::StopWatch stop_watch;
 
   snapshot::MergeSort merge_sort(
     storage_id_,
     kMasstreeStorage,
     args.base_epoch_,
     args.log_streams_,
     args.log_streams_count_,
     MasstreeComposeContext::kMaxLevels,
     args.work_memory_);
   CHECK_ERROR(merge_sort.initialize());
 
   MasstreeComposeContext context(engine_, &merge_sort, args);
   CHECK_ERROR(context.execute());
 
   CHECK_ERROR(merge_sort.uninitialize());  // no need for scoped release. its destructor is safe.
 
   stop_watch.stop();
   LOG(INFO) << to_string() << " done in " << stop_watch.elapsed_ms() << "ms.";
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

ErrorStack foedus::storage::masstree::MasstreeComposer::construct_root ( const Composer::ConstructRootArguments & args )

Definition at line 111 of file masstree_composer_impl.cpp.

Referenced by foedus::storage::Composer::construct_root().

                                                                                       {
   ASSERT_ND(args.root_info_pages_count_ > 0);
   VLOG(0) << to_string() << " combining " << args.root_info_pages_count_ << " root page info.";
   debugging::StopWatch stop_watch;
   SnapshotPagePointer new_root_id = args.snapshot_writer_->get_next_page_id();
   Page* new_root = args.snapshot_writer_->get_page_base();
   std::memcpy(new_root, args.root_info_pages_[0], kPageSize);  // use the first one as base
   if (args.root_info_pages_count_ == 1U) {
     VLOG(0) << to_string() << " only 1 root info page, so we just use it as the new root.";
   } else {
     // otherwise, we merge inputs from each reducer. because of how we design partitions,
     // the inputs are always intermediate pages with same partitioning. we just place new
     // pointers to children
     CHECK_ERROR(check_buddies(args));
 
     // because of how we partition, B-tree levels might be unbalanced at the root of first layer.
     // thus, we take the max of btree-level here.
     MasstreeIntermediatePage* base = reinterpret_cast<MasstreeIntermediatePage*>(new_root);
     ASSERT_ND(!base->is_border());
     for (uint16_t buddy = 1; buddy < args.root_info_pages_count_; ++buddy) {
       const MasstreeIntermediatePage* page
         = reinterpret_cast<const MasstreeIntermediatePage*>(args.root_info_pages_[buddy]);
       if (page->get_btree_level() > base->get_btree_level()) {
         LOG(INFO) << "MasstreeStorage-" << storage_id_ << " has an unbalanced depth in sub-tree";
         base->header().masstree_in_layer_level_ = page->get_btree_level();
       }
     }
 
     uint16_t updated_count = 0;
     for (SlotIndex i = 0; i <= base->get_key_count(); ++i) {
       MasstreeIntermediatePage::MiniPage& base_mini = base->get_minipage(i);
       for (SlotIndex j = 0; j <= base_mini.key_count_; ++j) {
         SnapshotPagePointer base_pointer = base_mini.pointers_[j].snapshot_pointer_;
         if (from_this_snapshot(base_pointer, args)) {
           ++updated_count;
           continue;  // base has updated it
         }
 
         for (uint16_t buddy = 1; buddy < args.root_info_pages_count_; ++buddy) {
           const MasstreeIntermediatePage* page
             = reinterpret_cast<const MasstreeIntermediatePage*>(args.root_info_pages_[buddy]);
           const MasstreeIntermediatePage::MiniPage& mini = page->get_minipage(i);
           SnapshotPagePointer pointer = mini.pointers_[j].snapshot_pointer_;
           if (from_this_snapshot(pointer, args)) {
             base_mini.pointers_[j].snapshot_pointer_ = pointer;  // this buddy has updated it
             ++updated_count;
             break;
           }
         }
       }
     }
     VLOG(0) << to_string() << " has " << updated_count << " new pointers from root.";
   }
 
   // In either case, some pointer might be null if that partition had no log record
   // and if this is an initial snapshot. Create a dummy page for them.
   MasstreeIntermediatePage* merged = reinterpret_cast<MasstreeIntermediatePage*>(new_root);
   ASSERT_ND(!merged->is_border());
   uint16_t dummy_count = 0;
   for (MasstreeIntermediatePointerIterator it(merged); it.is_valid(); it.next()) {
     DualPagePointer& pointer = merged->get_minipage(it.index_).pointers_[it.index_mini_];
     if (pointer.snapshot_pointer_ == 0) {
       // this should happen only while an initial snapshot for this storage.
       ASSERT_ND(storage_.get_control_block()->root_page_pointer_.snapshot_pointer_ == 0);
       KeySlice low, high;
       merged->extract_separators_snapshot(it.index_, it.index_mini_, &low, &high);
       uint32_t offset = 1U + dummy_count;  // +1 for new_root
       SnapshotPagePointer page_id = args.snapshot_writer_->get_next_page_id() + offset;
       MasstreeBorderPage* dummy = reinterpret_cast<MasstreeBorderPage*>(
         args.snapshot_writer_->get_page_base() + offset);
       dummy->initialize_snapshot_page(storage_id_, page_id, 0, low, high);
       pointer.snapshot_pointer_ = page_id;
       ++dummy_count;
     }
   }
   VLOG(0) << to_string() << " has added " << dummy_count << " dummy pointers in root.";
 
   ASSERT_ND(new_root->get_header().snapshot_);
   ASSERT_ND(new_root->get_header().storage_id_ == storage_id_);
   ASSERT_ND(new_root->get_header().get_page_type() == kMasstreeIntermediatePageType);
 
   new_root->get_header().page_id_ = new_root_id;
   *args.new_root_page_pointer_ = new_root_id;
   WRAP_ERROR_CODE(args.snapshot_writer_->dump_pages(0, 1 + dummy_count));
 
   // AFTER writing out the root page, install the pointer to new root page
   storage_.get_control_block()->root_page_pointer_.snapshot_pointer_ = new_root_id;
   storage_.get_control_block()->meta_.root_snapshot_page_id_ = new_root_id;
 
   stop_watch.stop();
   VLOG(0) << to_string() << " done in " << stop_watch.elapsed_ms() << "ms.";
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::masstree::MasstreeComposer::drop_root_volatile ( const Composer::DropVolatilesArguments & args )

Definition at line 2622 of file masstree_composer_impl.cpp.

References foedus::storage::VolatilePagePointer::clear(), foedus::storage::masstree::MasstreePage::get_btree_level(), foedus::Attachable< CONTROL_BLOCK >::get_control_block(), foedus::storage::masstree::MasstreeStorage::get_masstree_metadata(), foedus::storage::Storage< CONTROL_BLOCK >::get_name(), foedus::storage::Metadata::keeps_all_volatile_pages(), and foedus::storage::DualPagePointer::volatile_pointer_.

Referenced by foedus::storage::Composer::drop_root_volatile().

                                                                                     {
   if (storage_.get_masstree_metadata()->keeps_all_volatile_pages()) {
     LOG(INFO) << "Oh, but keep-all-volatile is on. Storage-" << storage_.get_name()
       << " is configured to keep all volatile pages.";
     return;
   }
   DualPagePointer* root_pointer = &storage_.get_control_block()->root_page_pointer_;
   MasstreeIntermediatePage* volatile_page = reinterpret_cast<MasstreeIntermediatePage*>(
     resolve_volatile(root_pointer->volatile_pointer_));
   if (volatile_page == nullptr) {
     LOG(INFO) << "Oh, but root volatile page already null";
     return;
   }
 
   if (is_to_keep_volatile(0, volatile_page->get_btree_level())) {
     LOG(INFO) << "Oh, but " << storage_ << " is configured to keep the root page.";
     return;
   }
 
   // yes, we can drop ALL volatile pages!
   LOG(INFO) << "Okay, drop em all!!";
   drop_all_recurse(args, root_pointer);
   root_pointer->volatile_pointer_.clear();
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Composer::DropResult foedus::storage::masstree::MasstreeComposer::drop_volatiles ( const Composer::DropVolatilesArguments & args )

drop_volatiles and related methods

Definition at line 2558 of file masstree_composer_impl.cpp.

Referenced by foedus::storage::Composer::drop_volatiles().

                                               {
   Composer::DropResult result(args);
   if (storage_.get_masstree_metadata()->keeps_all_volatile_pages()) {
     LOG(INFO) << "Keep-all-volatile: Storage-" << storage_.get_name()
       << " is configured to keep all volatile pages.";
     result.dropped_all_ = false;
     return result;
   }
 
   DualPagePointer* root_pointer = &storage_.get_control_block()->root_page_pointer_;
   MasstreeIntermediatePage* volatile_page = reinterpret_cast<MasstreeIntermediatePage*>(
     resolve_volatile(root_pointer->volatile_pointer_));
   if (volatile_page == nullptr) {
     LOG(INFO) << "No volatile root page. Probably while restart";
     return result;
   }
 
   // Unlike array-storage, each thread decides partititions to follow a bit differently
   // because the snapshot pointer might be not installed.
   // We check the partitioning assignment.
   PartitionerMetadata* metadata = PartitionerMetadata::get_metadata(engine_, storage_id_);
   ASSERT_ND(metadata->valid_);
   MasstreePartitionerData* data
     = reinterpret_cast<MasstreePartitionerData*>(metadata->locate_data(engine_));
   ASSERT_ND(data->partition_count_ > 0);
   ASSERT_ND(data->partition_count_ < kMaxIntermediatePointers);
   uint16_t cur = 0;
   for (MasstreeIntermediatePointerIterator it(volatile_page); it.is_valid(); it.next()) {
     DualPagePointer* pointer = &volatile_page->get_minipage(it.index_).pointers_[it.index_mini_];
     if (!args.partitioned_drop_) {
       result.combine(drop_volatiles_recurse(args, pointer));
       continue;
     }
     // the page boundaries as of partitioning might be different from the volatile page's,
     // but at least it's more coarse. Each pointer belongs to just one partition.
     // same trick as install_pointers.
     KeySlice low = it.get_low_key();
     KeySlice high = it.get_high_key();
     while (true) {
       KeySlice partition_high;
       if (cur + 1U == data->partition_count_) {
         partition_high = kSupremumSlice;
       } else {
         partition_high = data->low_keys_[cur + 1U];
       }
       if (high <= partition_high) {
         break;
       }
       ++cur;
     }
     ASSERT_ND(cur < data->partition_count_);
     if (data->partitions_[cur] == args.my_partition_) {
       if (data->low_keys_[cur] != low) {
         VLOG(0) << "Not exactly matching page boundary.";  // but not a big issue.
       }
       result.combine(drop_volatiles_recurse(args, pointer));
     }
   }
 
   // we so far always keep the volatile root of a masstree storage.
   return result;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

std::string foedus::storage::masstree::MasstreeComposer::to_string ( ) const

Definition at line 282 of file masstree_composer_impl.cpp.

Referenced by compose(), and construct_root().

                                             {
   return std::string("MasstreeComposer-") + std::to_string(storage_id_);
 }

Here is the caller graph for this function:

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

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

Detailed Description

Public Member Functions

Constructor & Destructor Documentation

Member Function Documentation