MasstreeComposer's compose() implementation separated from the class itself. More...

Detailed Description

MasstreeComposer's compose() implementation separated from the class itself.

It's a complicated method, so worth being its own class. This defines all the variables maintained during one compose() call.

Algorithm Overview

As described above, the biggest advantage to separate composer from transaction execution is that it simplifies the logic to construct a page. The sorted log stream provides log entries in key order. This class follows the same order when it constructs a pages. For every key, we do:

Make sure this object maintains pages in the path from root to the page that contains the key.
Each maintained page is initialized by previous snapshot page, empty if not exists.
The way we initialize with snapshot page is a bit special. We keep the image of the snapshot page as original page and append them to the maintained page up to the current key. The original page is stored in work memory (because we will not write them out), and PathLevel points to it. More details below (Original page pointer).
Assuming the original page trick, each maintained page always appends a new record to the end or update the record in the end, thus it's trivial to achieve 100% fill factor without any record movement.
Each maintained page might have a next-page pointer in foster_twin[1], which is filled when the page becomes full (note: because keys are ordered, we never have to do the split with records. it just puts a next-page pointer).

Page path and open/close

We maintain one path of pages (route) from the root to a border page that contains the current key. Each level consists of exactly one page with optional next page chain and original page. As far as we keep appending a key in the page of last level, we keep the same path forever upto the end of logs. The following cases trigger a change in the path.

Creation of next layer. We just deepen the path for one level. This is the easiest change.
Nexy key is beyond high-fence of the page of last level. We then close the last level, insert to the parent, repeat until the ancestor that logically contains the key (potentially root of the first layer), then open the path for next key.
Full page buffer. When we can't add any more page in writer's buffer, we flush out the last level page chain upto the tail page (the tail page is kept because it's currently modified). This keeps the current path except that last level's head/low-fence are moved forward.

Original page pointer: The active page in each level has a non-null pointer with kOriginalPage flag in foster_twin[0] so that we can append remaining records/links when next key is same or above the keys. The original page image is created when the page in the path is opened, and kept until it's closed. Thus, there are at most #-of-levels original pages, which should be pretty small.

Definition at line 161 of file masstree_composer_impl.hpp.

#include <masstree_composer_impl.hpp>

Classes
struct	FenceAndPointer

struct	PageBoundaryInfo
	Represents a minimal information to install a new snapshot page pointer. More...

struct	PageBoundarySort
	Points to PageBoundaryInfo with a sorting information. More...

struct	PathLevel
	One level in the path. More...

Public Types
enum	Constants { kMaxLevels = 32, kMaxLayers = 16, kMaxLogGroupSize = 1 << 14, kTmpBoundaryArraySize = kMaxLogGroupSize }

Public Member Functions
	MasstreeComposeContext (Engine engine, snapshot::MergeSort merge_sort, const Composer::ComposeArguments &args)
	MasstreeComposeContext methods. More...

ErrorStack	execute ()
	MasstreeComposeContext::execute() and subroutines for log groups. More...

Member Enumeration Documentation

enum foedus::storage::masstree::MasstreeComposeContext::Constants

Enumerator
kMaxLevels	We assume the path wouldn't be this deep.
kMaxLayers	We assume B-trie depth is at most this (prefix is at most 8*this value)
kMaxLogGroupSize	Maximum number of logs execute_xxx_group methods process in one shot.
kTmpBoundaryArraySize	Size of the tmp_boundary_array_. Most likely we don't need this much, but this memory consumtion is negligible anyways.

Definition at line 163 of file masstree_composer_impl.hpp.

                  {
     kMaxLevels = 32,
     kMaxLayers = 16,
     kMaxLogGroupSize = 1 << 14,
     kTmpBoundaryArraySize = kMaxLogGroupSize,
   };

Constructor & Destructor Documentation

foedus::storage::masstree::MasstreeComposeContext::MasstreeComposeContext	(	Engine *	engine,
		snapshot::MergeSort *	merge_sort,
		const Composer::ComposeArguments &	args
	)

MasstreeComposeContext methods.

Definition at line 291 of file masstree_composer_impl.cpp.

References foedus::snapshot::SnapshotWriter::get_next_page_id().

   : engine_(engine),
     merge_sort_(merge_sort),
     id_(merge_sort->get_storage_id()),
     storage_(engine, id_),
     args_(args),
     snapshot_id_(args.snapshot_writer_->get_snapshot_id()),
     numa_node_(get_writer()->get_numa_node()),
     max_pages_(get_writer()->get_page_size()),
     root_(reinterpret_cast<MasstreeIntermediatePage*>(args.root_info_page_)),
     page_base_(reinterpret_cast<Page*>(get_writer()->get_page_base())),
     original_base_(merge_sort->get_original_pages()) {
   page_id_base_ = get_writer()->get_next_page_id();
   refresh_page_boundary_info_variables();
   root_index_ = 0;
   root_index_mini_ = 0;
   allocated_pages_ = 0;
   cur_path_levels_ = 0;
   page_boundary_info_cur_pos_ = 0;
   page_boundary_elements_ = 0;
   std::memset(cur_path_, 0, sizeof(cur_path_));
   std::memset(cur_prefix_be_, 0, sizeof(cur_prefix_be_));
   std::memset(cur_prefix_slices_, 0, sizeof(cur_prefix_slices_));
   std::memset(tmp_boundary_array_, 0, sizeof(tmp_boundary_array_));
 }

Here is the call graph for this function:

Member Function Documentation

ErrorStack foedus::storage::masstree::MasstreeComposeContext::execute ( )

MasstreeComposeContext::execute() and subroutines for log groups.

Definition at line 371 of file masstree_composer_impl.cpp.

                                            {
   write_dummy_page_zero();
   CHECK_ERROR(init_root());
 
 #ifndef NDEBUG
   char debug_prev[8192];
   uint16_t debug_prev_length = 0;
 #endif  // NDEBUG
 
   uint64_t processed = 0;
   while (true) {
     CHECK_ERROR(merge_sort_->next_batch());
     uint64_t count = merge_sort_->get_current_count();
     if (count == 0 && merge_sort_->is_ended_all()) {
       break;
     }
 
 #ifndef NDEBUG
     // confirm that it's fully sorted
     for (uint64_t i = 0; i < count; ++i) {
       const MasstreeCommonLogType* entry =
         reinterpret_cast<const MasstreeCommonLogType*>(merge_sort_->resolve_sort_position(i));
       const char* key = entry->get_key();
       KeyLength key_length = entry->key_length_;
       ASSERT_ND(key_length > 0);
       if (key_length < debug_prev_length) {
         ASSERT_ND(std::memcmp(debug_prev, key, key_length) <= 0);
       } else {
         ASSERT_ND(std::memcmp(debug_prev, key, debug_prev_length) <= 0);
       }
       std::memcpy(debug_prev, key, key_length);
       debug_prev_length = key_length;
     }
 #endif  // NDEBUG
 
     // within the batch, we further split them into "groups" that share the same key or log types
     // so that we can process a number of logs in a tight loop.
     uint64_t cur = 0;
     uint32_t group_count = 0;
     while (cur < count) {
       snapshot::MergeSort::GroupifyResult group = merge_sort_->groupify(cur, kMaxLogGroupSize);
       ASSERT_ND(group.count_ <= kMaxLogGroupSize);
       if (LIKELY(group.count_ == 1U)) {  // misprediction is amortized by group, so LIKELY is better
         // no grouping. slowest case. has to be reasonably fast even in this case.
         ASSERT_ND(!group.has_common_key_);
         ASSERT_ND(!group.has_common_log_code_);
         CHECK_ERROR(execute_a_log(cur));
       } else if (group.has_common_key_) {
         CHECK_ERROR(execute_same_key_group(cur, cur + group.count_));
       } else {
         ASSERT_ND(group.has_common_log_code_);
         log::LogCode log_type = group.get_log_type();
         if (log_type == log::kLogCodeMasstreeInsert) {
           CHECK_ERROR(execute_insert_group(cur, cur + group.count_));
         } else if (log_type == log::kLogCodeMasstreeDelete) {
           CHECK_ERROR(execute_delete_group(cur, cur + group.count_));
         } else if (log_type == log::kLogCodeMasstreeUpdate) {
           CHECK_ERROR(execute_update_group(cur, cur + group.count_));
         } else {
           ASSERT_ND(log_type == log::kLogCodeMasstreeOverwrite);
           CHECK_ERROR(execute_overwrite_group(cur, cur + group.count_));
         }
       }
       cur += group.count_;
       processed += group.count_;
       ++group_count;
     }
     ASSERT_ND(cur == count);
     VLOG(1) << storage_ << " processed a batch of " << cur << " logs that has " << group_count
       << " groups";
   }
 
   VLOG(0) << storage_ << " processed " << processed << " logs. now pages=" << allocated_pages_;
   CHECK_ERROR(flush_buffer());
 
   // at the end, install pointers to the created snapshot pages except root page.
   uint64_t installed_count = 0;
   CHECK_ERROR(install_snapshot_pointers(&installed_count));
   return kRetOk;
 }

Here is the call 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

Classes

Public Types

Public Member Functions

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation