Detailed Description

Composer for a hash storage.

Composer for hash is much easier than for B-trees, but somewhat trickier than array. Unlike B-trees, we don't have to worry about page-splits, finding where to insert, etc etc. We re-construct each hash bin always as a whole. Huuuuge simplification. Unlike array, we have a quite granular partitioning, so constructing intermediate pages is trickier. We do 2-path construction to parallelize this part without losing partitioning benefit.

HashRootInfoPage as the results

The format is exactly same as HashIntermediatePage, but typedef-ed for clarity. The only differences are:

Snapshot pointer points to HashComposedBinsPage instead of HashDataPage/HashIntermediatePage.
Volatile pointer (which of course is never used in snapshot page) instead represents the number of contiguously-written HashComposedBinsPage in the pointed sub-tree. This allows the combiner to read the entire linked-list in one-shot.

Linked list of HashComposedBinsPage: In hash storage, what compose() returns are just a list of bins. There essentially is no structure of them. The only reason we have this "root" page is to allow parallel combination by the gleaner. Each child-pointer from the root page is assigned to one thread on its own node, then written out in that node. So, after following the first child pointer, we just need a linked list, which is HashComposedBinsPage.

2-path composition

Each reducer returns a linked-list of HashComposedBinsPage for every direct-child of the root page. Then, the gleaner combines them in a parallel fashion, resulting in snapshot interemediate pages that will be installed to the root page. The second phase consists of reading the HashComposedBinsPage from each composer (reducer), collecting updated bins on each page, and creating a new interemediate page hierarchically. We have several classes decoupled from the composer class itself as listed below:

ComposedBin (individual bin)
HashComposedBinsPage (hundreds of bins)
ComposedBinsBuffer (all bins from a sub-tree emit from one composer)
ComposedBinsMergedStream (all bins from a sub-tree emit from all composers)

1-level hashtable: It works the same way even when the hash table has only one level (root directly points to data pages). Even in this case, HashRootInfoPage still points to HashComposedBinsPage, which contains only one entry per page. Kind of wasteful, but it has negligible overheads compared to the entire mapper/reducer. Unlike array package, we don't do special optimization for this case in order to keep the code simpler, and because the storage could benefit from parallelization even in this case (the root page still contains hundreds of hash bins).

Note: This is a private implementation-details of Hashtable 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 62 of file hash_composer_impl.hpp.

#include <hash_composer_impl.hpp>

Public Member Functions
	HashComposer (Composer *parent)
	HashComposer 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)

Static Public Member Functions
static void	launch_construct_root_multi_level (HashComposer pointer, const Composer::ConstructRootArguments args, uint16_t numa_node, HashIntermediatePage root_page, ErrorStack out_error)
	launched on its own thread. More...

Constructor & Destructor Documentation

foedus::storage::hash::HashComposer::HashComposer ( Composer * parent )

explicit

HashComposer methods.

Definition at line 89 of file hash_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_),
     volatile_resolver_(engine_->get_memory_manager()->get_global_volatile_page_resolver()) {
   ASSERT_ND(storage_.exists());
 }

Here is the call graph for this function:

Member Function Documentation

ErrorStack foedus::storage::hash::HashComposer::compose ( const Composer::ComposeArguments & args )

Definition at line 97 of file hash_composer_impl.cpp.

References foedus::storage::Composer::ComposeArguments::base_epoch_, CHECK_ERROR, foedus::debugging::StopWatch::elapsed_ms(), foedus::DefaultInitializable::initialize(), foedus::storage::hash::kHashMaxLevels, foedus::storage::kHashStorage, foedus::kRetOk, foedus::storage::Composer::ComposeArguments::log_streams_, foedus::storage::Composer::ComposeArguments::log_streams_count_, foedus::storage::Composer::ComposeArguments::previous_snapshot_files_, foedus::storage::Composer::ComposeArguments::root_info_page_, foedus::storage::Composer::ComposeArguments::snapshot_writer_, 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_,
     kHashStorage,
     args.base_epoch_,
     args.log_streams_,
     args.log_streams_count_,
     kHashMaxLevels,
     args.work_memory_);
   CHECK_ERROR(merge_sort.initialize());
 
   HashComposeContext context(
     engine_,
     &merge_sort,
     args.snapshot_writer_,
     args.previous_snapshot_files_,
     args.root_info_page_);
   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::hash::HashComposer::construct_root ( const Composer::ConstructRootArguments & args )

Definition at line 126 of file hash_composer_impl.cpp.

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

                                                                                   {
   // Unlike array package, this method might do lots of I/O.
   // Each reducer creates only data pages. They don't create intermediate pages
   // and instead they emit linked-lists of HashComposedBinsPage as well as HashRootInfoPage
   // pointing to them. We combine these information here, writing out new intermediate pages.
 
   // compose() created root_info_pages that contain pointers to fill in the root page,
   // so we just find non-zero entry and copy it to root page.
   const uint8_t levels = storage_.get_levels();
 
   HashIntermediatePage* root_page = reinterpret_cast<HashIntermediatePage*>(
     args.gleaner_resource_->tmp_root_page_memory_.get_block());
   SnapshotPagePointer old_root_page_id = storage_.get_metadata()->root_snapshot_page_id_;
   if (old_root_page_id != 0) {
     WRAP_ERROR_CODE(args.previous_snapshot_files_->read_page(old_root_page_id, root_page));
     ASSERT_ND(root_page->header().storage_id_ == storage_id_);
     ASSERT_ND(root_page->header().page_id_ == old_root_page_id);
     ASSERT_ND(root_page->get_level() + 1U == storage_.get_levels());
     root_page->header().page_id_ = 0;
   } else {
     root_page->initialize_snapshot_page(
       storage_id_,
       0,  // new page ID not known at this point
       storage_.get_levels() - 1U,
       0);
   }
 
   if (levels == 1U) {
     // single-level hash storage's root info page directly points to data pages, so
     // no need for parallelization. we separate the case below.
     CHECK_ERROR(construct_root_single_level(args, root_page));
   } else {
     // otherwise, we parallelze the heavy lifting part, which involves raeds/writes of pages.
     LOG(INFO) << to_string() << " construct_root() multi-level parallelized path";
     std::vector< std::thread > threads;
 
     const uint16_t nodes = engine_->get_soc_count();
     std::unique_ptr< ErrorStack[] > error_stacks(new ErrorStack[nodes]);
     for (uint16_t numa_node = 0; numa_node < nodes; ++numa_node) {
       threads.emplace_back(
         HashComposer::launch_construct_root_multi_level,
         this,
         &args,
         numa_node,
         root_page,
         error_stacks.get() + numa_node);
     }
 
     LOG(INFO) << to_string() << " construct_root() launched " << nodes << " threads...";
     for (uint16_t numa_node = 0; numa_node < nodes; ++numa_node) {
       threads[numa_node].join();
       if (error_stacks.get()[numa_node].is_error()) {
         LOG(ERROR) << to_string() << " construct_root() observed an error in the launched"
           << " thread-" << numa_node << ". will propagate after joining the worker threads. "
           << "error description: " << error_stacks.get()[numa_node];
       }
       CHECK_ERROR(error_stacks.get()[numa_node]);
     }
     LOG(INFO) << to_string() << " construct_root() joined";
     // propagate errors.
     for (uint16_t numa_node = 0; numa_node < nodes; ++numa_node) {
       CHECK_ERROR(error_stacks.get()[numa_node]);
     }
   }
 
   // write out root_page image
   SnapshotPagePointer new_root_page_id = args.snapshot_writer_->get_next_page_id();
   root_page->header().page_id_ = new_root_page_id;
   std::memcpy(args.snapshot_writer_->get_page_base(), root_page, kPageSize);
   WRAP_ERROR_CODE(args.snapshot_writer_->dump_pages(0, 1));
   ASSERT_ND(args.snapshot_writer_->get_next_page_id() == new_root_page_id + 1ULL);
 
   *args.new_root_page_pointer_ = new_root_page_id;
   // AFTER writing out the root page, install the pointer to new root page
   storage_.get_control_block()->root_page_pointer_.snapshot_pointer_ = new_root_page_id;
   storage_.get_control_block()->meta_.root_snapshot_page_id_ = new_root_page_id;
   return kRetOk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::storage::hash::HashComposer::drop_root_volatile ( const Composer::DropVolatilesArguments & args )

Definition at line 1223 of file hash_composer_impl.cpp.

References foedus::Attachable< CONTROL_BLOCK >::get_control_block(), foedus::storage::hash::HashStorage::get_hash_metadata(), foedus::storage::hash::HashStorage::get_levels(), 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_hash_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;
   }
   if (is_to_keep_volatile(storage_.get_levels() - 1U)) {
     LOG(INFO) << "Oh, but Storage-" << storage_.get_name() << " is configured to keep"
       << " the root page.";
     return;
   }
   DualPagePointer* root_pointer = &storage_.get_control_block()->root_page_pointer_;
   HashIntermediatePage* volatile_page = resolve_intermediate(root_pointer->volatile_pointer_);
   if (volatile_page == nullptr) {
     LOG(INFO) << "Oh, but root volatile page already null";
     return;
   }
 
   LOG(INFO) << "Okay, drop em all!!";
   drop_all_recurse(args, root_pointer);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Composer::DropResult foedus::storage::hash::HashComposer::drop_volatiles ( const Composer::DropVolatilesArguments & args )

drop_volatiles and related methods

Definition at line 1165 of file hash_composer_impl.cpp.

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

                                                                                           {
   Composer::DropResult result(args);
   if (storage_.get_hash_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_;
   HashIntermediatePage* volatile_page = resolve_intermediate(root_pointer->volatile_pointer_);
   if (volatile_page == nullptr) {
     LOG(INFO) << "No volatile root page. Probably while restart";
     return result;
   }
 
   // We iterate through all existing volatile pages to drop volatile pages of
   // level-3 or deeper (if the storage has only 2 levels, keeps all).
   // this "level-3 or deeper" is a configuration per storage.
   // Even if the volatile page is deeper than that, we keep them if it contains newer modification,
   // including descendants (so, probably we will keep higher levels anyways).
   uint16_t count = storage_.get_root_children();
   uint8_t root_level = volatile_page->get_level();
   ASSERT_ND(root_level + 1U == storage_.get_levels());
   for (uint16_t i = 0; i < count; ++i) {
     DualPagePointer& child_pointer = volatile_page->get_pointer(i);
     if (!child_pointer.volatile_pointer_.is_null() && child_pointer.snapshot_pointer_ != 0) {
       uint16_t partition = extract_numa_node_from_snapshot_pointer(child_pointer.snapshot_pointer_);
       if (!args.partitioned_drop_ || partition == args.my_partition_) {
         drop_volatiles_child(args, &child_pointer, root_level, &result);
       }
     }
   }
   // root page is kept at this point in this case. we need to check with other threads
   return result;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void foedus::storage::hash::HashComposer::launch_construct_root_multi_level	(	HashComposer *	pointer,
		const Composer::ConstructRootArguments *	args,
		uint16_t	numa_node,
		HashIntermediatePage *	root_page,
		ErrorStack *	out_error
	)

inlinestatic

launched on its own thread.

Definition at line 76 of file hash_composer_impl.hpp.

Referenced by construct_root().

                            {
     *out_error = pointer->construct_root_multi_level(*args, numa_node, root_page);
   }

Here is the caller graph for this function:

std::string foedus::storage::hash::HashComposer::to_string ( ) const

Definition at line 427 of file hash_composer_impl.cpp.

Referenced by compose(), and construct_root().

                                         {
   return std::string("HashComposer-") + 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/hash/hash_composer_impl.hpp
/home/shino/foedus_code/foedus-core/src/foedus/storage/hash/hash_composer_impl.cpp

Detailed Description

HashRootInfoPage as the results

Public Member Functions

Static Public Member Functions

Constructor & Destructor Documentation

Member Function Documentation