foedus::storage::Partitioner Class Reference

Partitioning and sorting logic for one storage. More...

Detailed Description

Partitioning and sorting logic for one storage.

When the snapshot module takes snapshot, it instantiates this object for each storage that had some log. Mappers obtain the object and use it to determine which partition to send logs to. Reducers also use it to sort individual logs in the storage by key-then-ordinal order. All methods in this object are in a batched style to avoid overheads per small log entry.

Partitioning Algorithm

So far, create_partitioner() receives only the engine object and ID to design partitioning. This means we can use only information available in the status-quo of the storage in the engine, such as which node owns which volatile/snapshot page. This is so far enough and VERY simple/efficient to design partitioning, but later we might want to explore smarter partitioning that utilizes, say, log entries. (but that will be complex/expensive!)

Sorting Algorithm

Sorting algorithm may use metadata specific to the storage (not just storage type). For example, if we somehow know that every key in the storage is 8 byte, we can do something very efficient. Or, in some case the requirement of sorting itself might depend on the storage.

Shared memory, No virtual methods

Unfortunately, virtual methods are hard to use in multi-process and multi-node environment. All dynamic data of Partitioner is stored in shared memory as explained in PartitionerMetadata. Thus, Partitioner has no virtual methods. It just does switch-case on the storage type and invokes methods in individual partitioners (which aren't derived classes of this).

For more details of how individual storage types implement them, see the individual partitioners.

Definition at line 70 of file partitioner.hpp.

#include <partitioner.hpp>

Inheritance diagram for foedus::storage::Partitioner:

Collaboration diagram for foedus::storage::Partitioner:

Classes
struct	DesignPartitionArguments
	Arguments for design_partition() More...
struct	PartitionBatchArguments
	Arguments for partition_batch() More...
struct	SortBatchArguments
	Arguments for sort_batch() More...

Public Member Functions
	Partitioner (Engine *engine, StorageId id)
	Instantiate an instance for the given storage. More...
const PartitionerMetadata &	get_metadata () const
	Returns tiny metadata of the partitioner in shared memory. More...
bool	is_valid () const
	whether this object is ready for partitioning. More...
StorageId	get_storage_id () const
StorageType	get_storage_type () const
bool	is_partitionable ()
	returns if this storage is partitionable. More...
ErrorStack	design_partition (const DesignPartitionArguments &args)
	Determines partitioning scheme for this storage. More...
void	partition_batch (const PartitionBatchArguments &args)
	Identifies the partition of each log record in a batched fashion. More...
void	sort_batch (const SortBatchArguments &args)
	Called from log reducer to sort log entries by keys. More...
Public Member Functions inherited from foedus::Attachable< PartitionerMetadata >
	Attachable ()
	Attachable (Engine *engine)
	Attachable (Engine *engine, PartitionerMetadata *control_block)
	Attachable (PartitionerMetadata *control_block)
	Attachable (const Attachable &other)
virtual	~Attachable ()
Attachable &	operator= (const Attachable &other)
virtual void	attach (PartitionerMetadata *control_block)
	Attaches to the given shared memory. More...
bool	is_attached () const
	Returns whether the object has been already attached to some shared memory. More...
PartitionerMetadata *	get_control_block () const
Engine *	get_engine () const
void	set_engine (Engine *engine)

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

Additional Inherited Members
Protected Attributes inherited from foedus::Attachable< PartitionerMetadata >
Engine *	engine_
	Most attachable object stores an engine pointer (local engine), so we define it here. More...
PartitionerMetadata *	control_block_
	The shared data on shared memory that has been initialized in some SOC or master engine. More...

Constructor & Destructor Documentation

foedus::storage::Partitioner::Partitioner	(	Engine *	engine,
		StorageId	id
	)

Instantiate an instance for the given storage.

Parameters

[in]	engine	Engine
[in]	id	ID of the storage

This method only attaches to a shared memory, so it has no cost. You can instantiate Partitioner anywhere you like.

Definition at line 84 of file partitioner.cpp.

References ASSERT_ND, foedus::storage::StorageManager::get_storage(), foedus::Engine::get_storage_manager(), foedus::storage::kInvalidStorage, foedus::storage::StorageControlBlock::meta_, and foedus::storage::Metadata::type_.

  : Attachable< PartitionerMetadata >(engine, PartitionerMetadata::get_metadata(engine, id)) {
  id_ = id;
  type_ = engine->get_storage_manager()->get_storage(id)->meta_.type_;
  ASSERT_ND(type_ != kInvalidStorage);
}

Here is the call graph for this function:

Member Function Documentation

ErrorStack foedus::storage::Partitioner::design_partition

(

const DesignPartitionArguments &

args

)

Determines partitioning scheme for this storage.

This method puts the resulting data in shared memory. This method should be called only once per snapshot.

Definition at line 106 of file partitioner.cpp.

References foedus::storage::sequential::SequentialPartitioner::design_partition(), foedus::storage::hash::HashPartitioner::design_partition(), foedus::storage::array::ArrayPartitioner::design_partition(), foedus::storage::masstree::MasstreePartitioner::design_partition(), foedus::storage::kArrayStorage, foedus::storage::kHashStorage, foedus::storage::kMasstreeStorage, foedus::kRetOk, and foedus::storage::kSequentialStorage.

                                                                             {
  switch (type_) {
  case kArrayStorage: return array::ArrayPartitioner(this).design_partition(args);
  case kHashStorage: return hash::HashPartitioner(this).design_partition(args);
  case kSequentialStorage: return sequential::SequentialPartitioner(this).design_partition(args);
  case kMasstreeStorage: return masstree::MasstreePartitioner(this).design_partition(args);
  default:
    LOG(FATAL) << "Unsupported storage type:" << type_;
    return kRetOk;
  }
}

Here is the call graph for this function:

const PartitionerMetadata & foedus::storage::Partitioner::get_metadata

(

)

const

Returns tiny metadata of the partitioner in shared memory.

Definition at line 91 of file partitioner.cpp.

References foedus::Attachable< PartitionerMetadata >::control_block_.

{ return *control_block_; }

StorageId foedus::storage::Partitioner::get_storage_id ( ) const

inline

Definition at line 86 of file partitioner.hpp.

{ return id_;}

StorageType foedus::storage::Partitioner::get_storage_type ( ) const

inline

Definition at line 87 of file partitioner.hpp.

{ return type_; }

bool foedus::storage::Partitioner::is_partitionable

(

)

returns if this storage is partitionable.

Some storage, such as a B-tree with only a single page (root=leaf), it is impossible to partition. In that case, this returns false to indicate that the caller can just assume all logs should be blindly sent to partition-0. Similarly, if there is only one NUMA node (partition), the caller also skips partitioning, but in that case the caller even skips instantiating partitioners.

Definition at line 94 of file partitioner.cpp.

References foedus::storage::sequential::SequentialPartitioner::is_partitionable(), foedus::storage::hash::HashPartitioner::is_partitionable(), foedus::storage::array::ArrayPartitioner::is_partitionable(), foedus::storage::masstree::MasstreePartitioner::is_partitionable(), foedus::storage::kArrayStorage, foedus::storage::kHashStorage, foedus::storage::kMasstreeStorage, and foedus::storage::kSequentialStorage.

                                   {
  switch (type_) {
  case kArrayStorage: return array::ArrayPartitioner(this).is_partitionable();
  case kHashStorage: return hash::HashPartitioner(this).is_partitionable();
  case kMasstreeStorage: return masstree::MasstreePartitioner(this).is_partitionable();
  case kSequentialStorage: return sequential::SequentialPartitioner(this).is_partitionable();
  default:
    LOG(FATAL) << "Unsupported storage type:" << type_;
    return false;
  }
}

Here is the call graph for this function:

bool foedus::storage::Partitioner::is_valid

(

)

const

whether this object is ready for partitioning.

if only sorting is needed, it doesn't matter

Definition at line 92 of file partitioner.cpp.

References foedus::Attachable< PartitionerMetadata >::control_block_.

{ return control_block_->valid_; }

void foedus::storage::Partitioner::partition_batch

(

const PartitionBatchArguments &

args

)

Identifies the partition of each log record in a batched fashion.

Precondition

!is_partitionable(): in this case, it's waste of time. check it before calling this.

Each storage type implements this method based on the statistics passed to create_partitioner(). For better performance, logs_count is usually at least thousands. Assume the scale when you optimize the implementation in derived classes.

Definition at line 118 of file partitioner.cpp.

References foedus::storage::kArrayStorage, foedus::storage::kHashStorage, foedus::storage::kMasstreeStorage, foedus::storage::kSequentialStorage, foedus::storage::sequential::SequentialPartitioner::partition_batch(), foedus::storage::hash::HashPartitioner::partition_batch(), foedus::storage::array::ArrayPartitioner::partition_batch(), and foedus::storage::masstree::MasstreePartitioner::partition_batch().

                                                                                {
  switch (type_) {
  case kArrayStorage: return array::ArrayPartitioner(this).partition_batch(args);
  case kHashStorage: return hash::HashPartitioner(this).partition_batch(args);
  case kMasstreeStorage: return masstree::MasstreePartitioner(this).partition_batch(args);
  case kSequentialStorage: return sequential::SequentialPartitioner(this).partition_batch(args);
  default:
    LOG(FATAL) << "Unsupported storage type:" << type_;
  }
}

Here is the call graph for this function:

void foedus::storage::Partitioner::sort_batch

(

const SortBatchArguments &

args

)

Called from log reducer to sort log entries by keys.

All log entries passed to this method are for this storage. Each storage type implements an efficient and batched way of sorting all log entries by key-and-then-ordinal. The implementation can do compaction when it is safe. For example, two ovewrite logs on the same key's same data region can be compacted to one log. In that case, written_count becomes smaller than log_positions_count_.

See also

get_required_sort_buffer_size()

Definition at line 129 of file partitioner.cpp.

References foedus::storage::kArrayStorage, foedus::storage::kHashStorage, foedus::storage::kMasstreeStorage, foedus::storage::kSequentialStorage, foedus::storage::sequential::SequentialPartitioner::sort_batch(), foedus::storage::hash::HashPartitioner::sort_batch(), foedus::storage::array::ArrayPartitioner::sort_batch(), and foedus::storage::masstree::MasstreePartitioner::sort_batch().

                                                                      {
  switch (type_) {
  case kArrayStorage: return array::ArrayPartitioner(this).sort_batch(args);
  case kHashStorage: return hash::HashPartitioner(this).sort_batch(args);
  case kMasstreeStorage: return masstree::MasstreePartitioner(this).sort_batch(args);
  case kSequentialStorage: return sequential::SequentialPartitioner(this).sort_batch(args);
  default:
    LOG(FATAL) << "Unsupported storage type:" << type_;
  }
}

Here is the call graph for this function:

Friends And Related Function Documentation

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

friend

Definition at line 140 of file partitioner.cpp.

                                                            {
  o << "<Partitioner>"
    << "<id>" << v.id_ << "</id>"
    << "<type>" << to_storage_type_name(v.type_) << "</type>"
    << *v.control_block_;
  o << "</Partitioner>";
  return o;
}

---

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

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