foedus::Epoch Class Reference

Represents a time epoch. More...

Detailed Description

Represents a time epoch.

Epoch is an corase-grained timestamp used all over the places.

What is Epoch

An Epoch represents a few to 100s milliseconds. XctManager periodically or by-demand advances the value so that the commit protocol, loggers, garbage collector, etc can loosely and efficiently and synchronize with other parts of the engine. Compared to fine-grained sequence number like Oracle/PostgreSQL's timestamp, this is much more scalable. Several commercial and open-source storage engines use such a coarse-grained timestamp nowadays.

Value range

We use 28 bits to represent an epoch (we need to save 4 bits for the sake of foedus::xct::XctId). The first 4 bits must be always zero. This means the value range of [0, 2^28 - 1]. Assuming 20ms per epoch, this is about 1 year.

Wrap-around

This class can handle wrapping-around assuming there is no case where we have two epochs that are 2^27 or more distant. As one epoch represents tens of milliseconds, this assumption should hold. All very-old epochs will disappear from logs and snapshots by the time we wrap around. We use wrap-around-aware comparison algorithms

See also

RFC 1982

http://en.wikipedia.org/wiki/Serial_number_arithmetic

http://github.com/pjkundert/sequence

Translation unit

This class is header-only except the std::ostream redirect.

Definition at line 61 of file epoch.hpp.

#include <epoch.hpp>

Public Types
enum	Constants {   kEpochInvalid = 0, kEpochInitialDurable = 1, kEpochInitialGrace = 2, kEpochInitialCurrent = 3,   kEpochBits = 28, kEpochIntOverflow = (1 << kEpochBits), kEpochIntHalf = (1 << (kEpochBits - 1)) }
	Defines constant values. More...
typedef uint32_t	EpochInteger
	Unsigned integer representation of epoch. More...

Public Member Functions
	Epoch () noexcept
	Construct an invalid epoch. More...
	Epoch (EpochInteger value) noexcept
	Construct an epoch of specified integer representation. More...
void	reset ()
	Clears this epoch variable so that it points to an invalid epoch. More...
bool	is_valid () const
EpochInteger	value () const
	Returns the raw integer representation. More...
Epoch &	operator++ ()
Epoch &	operator-- ()
Epoch	one_less () const
Epoch	one_more () const
uint32_t	subtract (const Epoch &other) const
	Returns the number epochs from the given epoch to this epoch accounting for wrap-around. More...
void	store_min (const Epoch &other)
	Kind of std::min(this, other). More...
void	store_max (const Epoch &other)
	Kind of std::max(this, other). More...
bool	before (const Epoch &other) const
	Returns if this epoch is before the given epoch in the sense of distance defined in RFC 1982. More...
bool	operator== (const Epoch &other) const
bool	operator!= (const Epoch &other) const
bool	operator< (const Epoch &other) const
bool	operator> (const Epoch &other) const
bool	operator<= (const Epoch &other) const
bool	operator>= (const Epoch &other) const

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

Member Typedef Documentation

typedef uint32_t foedus::Epoch::EpochInteger

Unsigned integer representation of epoch.

"Unsigned" is important. see the links.

Definition at line 64 of file epoch.hpp.

Member Enumeration Documentation

enum foedus::Epoch::Constants

Defines constant values.

Enumerator
kEpochInvalid	Zero is always reserved for invalid epoch. A valid epoch always skips this value.
kEpochInitialDurable	As there is no transaction in ep-1, initial durable_epoch is 1.
kEpochInitialGrace	Usually, current epoch -1 is the grace period before being durable. Initial epochs don't need grace period, but let's reserve one for consistency.
kEpochInitialCurrent	The first epoch (before wrap-around) that might have transactions is ep-3.
kEpochBits	Bits to represent an epoch.
kEpochIntOverflow	Epoch values wrap around at this value.
kEpochIntHalf	Used for before().

Definition at line 66 of file epoch.hpp.

                 {
    kEpochInvalid = 0,
    kEpochInitialDurable = 1,
    kEpochInitialGrace = 2,
    kEpochInitialCurrent = 3,
    kEpochBits = 28,
    kEpochIntOverflow = (1 << kEpochBits),
    kEpochIntHalf = (1 << (kEpochBits - 1)),
  };

Constructor & Destructor Documentation

foedus::Epoch::Epoch ( )

inlinenoexcept

Construct an invalid epoch.

Definition at line 87 of file epoch.hpp.

: epoch_(kEpochInvalid) {}

foedus::Epoch::Epoch ( EpochInteger  value )

inlineexplicitnoexcept

Construct an epoch of specified integer representation.

Definition at line 89 of file epoch.hpp.

References ASSERT_ND, kEpochIntOverflow, and value().

                                                    : epoch_(value) {
    ASSERT_ND(value < kEpochIntOverflow);
  }

Here is the call graph for this function:

Member Function Documentation

bool foedus::Epoch::before ( const Epoch &  other ) const

inline

Returns if this epoch is before the given epoch in the sense of distance defined in RFC 1982.

Both this and other must be valid epochs.

Definition at line 176 of file epoch.hpp.

References ASSERT_ND, is_valid(), and kEpochIntHalf.

Referenced by foedus::xct::XctId::before(), foedus::xct::Xct::issue_next_id(), operator<(), and operator>().

                                        {
    ASSERT_ND(is_valid());
    ASSERT_ND(other.is_valid());
    int64_t diff = static_cast<int64_t>(other.epoch_) - static_cast<int64_t>(epoch_);
    return diff <= -kEpochIntHalf || (diff > 0 && diff < kEpochIntHalf);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::Epoch::is_valid ( ) const

inline

Definition at line 96 of file epoch.hpp.

References ASSERT_ND, kEpochIntOverflow, and kEpochInvalid.

Referenced by foedus::log::ThreadLogBufferMeta::assert_consistent(), before(), foedus::xct::XctId::compare_epoch_and_orginal(), foedus::storage::StorageManagerPimpl::create_storage(), foedus::storage::array::ArrayComposer::drop_root_volatile(), foedus::storage::StorageManagerPimpl::drop_storage(), foedus::snapshot::SnapshotManagerPimpl::drop_volatile_pages(), foedus::log::LoggerRef::get_log_range(), foedus::thread::ThreadGroupRef::get_min_in_commit_epoch(), foedus::xct::XctManagerPimpl::handle_epoch_chime_wait_grace_period(), foedus::snapshot::SnapshotManagerPimpl::handle_snapshot(), foedus::snapshot::SnapshotManagerPimpl::handle_snapshot_triggered(), foedus::storage::array::ArrayPage::initialize_snapshot_page(), foedus::storage::array::ArrayPage::initialize_volatile_page(), foedus::storage::sequential::SequentialStoragePimpl::load(), foedus::storage::sequential::max_from_epoch_snapshot_epoch(), foedus::storage::sequential::SequentialRecordIterator::next(), operator++(), operator--(), foedus::operator<<(), foedus::xct::XctManagerPimpl::precommit_xct_apply(), foedus::restart::RestartManagerPimpl::redo_meta_logs(), foedus::log::LogManagerPimpl::refresh_global_durable_epoch(), foedus::storage::sequential::SequentialCursor::SequentialCursor(), foedus::storage::sequential::SequentialRecordIterator::SequentialRecordIterator(), store_max(), store_min(), subtract(), foedus::snapshot::SnapshotManagerPimpl::trigger_snapshot_immediate(), foedus::storage::sequential::SequentialStoragePimpl::truncate(), foedus::snapshot::LogReducerRef::verify_log_chunk(), foedus::storage::masstree::MasstreeStoragePimpl::verify_single_thread_border(), and foedus::storage::hash::HashStoragePimpl::verify_single_thread_data().

                           {
    ASSERT_ND(epoch_ < kEpochIntOverflow);
    return epoch_ != kEpochInvalid;
  }

Here is the caller graph for this function:

Epoch foedus::Epoch::one_less ( ) const

inline

Definition at line 122 of file epoch.hpp.

Referenced by foedus::xct::XctManager::get_current_grace_epoch(), foedus::xct::XctManager::get_current_grace_epoch_weak(), and foedus::xct::XctManagerPimpl::handle_epoch_chime().

                         {
    Epoch tmp(epoch_);
    tmp.operator--();
    return tmp;
  }

Here is the caller graph for this function:

Epoch foedus::Epoch::one_more ( ) const

inline

Definition at line 127 of file epoch.hpp.

Referenced by foedus::xct::XctManagerPimpl::advance_current_global_epoch(), foedus::thread::ThreadPimpl::collect_retired_volatile_page(), foedus::storage::sequential::SequentialComposer::compose(), foedus::snapshot::SnapshotManagerPimpl::drop_volatile_pages_parallel(), foedus::cache::CacheManagerPimpl::handle_cleaner(), foedus::xct::XctManagerPimpl::handle_epoch_chime(), foedus::xct::XctManagerPimpl::handle_epoch_chime_wait_grace_period(), and foedus::xct::XctManagerPimpl::wait_for_commit().

                         {
    Epoch tmp(epoch_);
    tmp.operator++();
    return tmp;
  }

Here is the caller graph for this function:

bool foedus::Epoch::operator!= ( const Epoch &  other ) const

inline

Definition at line 184 of file epoch.hpp.

{ return epoch_ != other.epoch_; }

Epoch& foedus::Epoch::operator++ ( )

inline

Definition at line 104 of file epoch.hpp.

References ASSERT_ND, is_valid(), and kEpochIntOverflow.

                       {
    ASSERT_ND(is_valid());  // we prohibit increment from invalid epoch
    if (epoch_ == kEpochIntOverflow - 1) {
      epoch_ = 1;  // skip 0, which is always an invalid epoch.
    } else {
      ++epoch_;
    }
    return *this;
  }

Here is the call graph for this function:

Epoch& foedus::Epoch::operator-- ( )

inline

Definition at line 113 of file epoch.hpp.

References ASSERT_ND, is_valid(), and kEpochIntOverflow.

                       {
    ASSERT_ND(is_valid());  // we prohibit decrement from invalid epoch
    if (epoch_ == 1) {
      epoch_ = kEpochIntOverflow - 1;  // skip 0, which is always an invalid epoch.
    } else {
      --epoch_;
    }
    return *this;
  }

Here is the call graph for this function:

bool foedus::Epoch::operator< ( const Epoch &  other ) const

inline

Definition at line 185 of file epoch.hpp.

References before().

Referenced by operator>=().

{ return before(other); }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::Epoch::operator<= ( const Epoch &  other ) const

inline

Definition at line 187 of file epoch.hpp.

References operator>().

{ return !operator>(other); }

Here is the call graph for this function:

bool foedus::Epoch::operator== ( const Epoch &  other ) const

inline

Definition at line 183 of file epoch.hpp.

{ return epoch_ == other.epoch_; }

bool foedus::Epoch::operator> ( const Epoch &  other ) const

inline

Definition at line 186 of file epoch.hpp.

References before().

Referenced by operator<=().

{ return other.before(*this); }

Here is the call graph for this function:

Here is the caller graph for this function:

bool foedus::Epoch::operator>= ( const Epoch &  other ) const

inline

Definition at line 188 of file epoch.hpp.

References operator<().

{ return !operator<(other); }

Here is the call graph for this function:

void foedus::Epoch::reset ( )

inline

Clears this epoch variable so that it points to an invalid epoch.

Definition at line 95 of file epoch.hpp.

References kEpochInvalid.

Referenced by foedus::log::ThreadEpockMark::ThreadEpockMark().

{ epoch_ = kEpochInvalid; }

Here is the caller graph for this function:

void foedus::Epoch::store_max ( const Epoch &  other )

inline

Kind of std::max(this, other).

Precondition

other.is_valid() otherwise what's the point?

If this.is_valid(), this is exactly std::max. If not, other is unconditionally taken.

Definition at line 165 of file epoch.hpp.

References ASSERT_ND, and is_valid().

Referenced by foedus::storage::Composer::DropResult::combine(), foedus::storage::sequential::SequentialComposer::compose(), and foedus::xct::XctManagerPimpl::precommit_xct_verify_readonly().

                                        {
    ASSERT_ND(other.is_valid());
    if (!is_valid() || other > *this) {
      epoch_ = other.epoch_;
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::Epoch::store_min ( const Epoch &  other )

inline

Kind of std::min(this, other).

Precondition

other.is_valid() otherwise what's the point?

If this.is_valid(), this is exactly std::min. If not, other is unconditionally taken.

Definition at line 153 of file epoch.hpp.

References ASSERT_ND, and is_valid().

Referenced by foedus::storage::sequential::SequentialComposer::compose(), foedus::thread::ThreadGroupRef::get_min_in_commit_epoch(), and foedus::log::LogManagerPimpl::refresh_global_durable_epoch().

                                        {
    ASSERT_ND(other.is_valid());
    if (!is_valid() || other < *this) {
      epoch_ = other.epoch_;
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

uint32_t foedus::Epoch::subtract ( const Epoch &  other ) const

inline

Returns the number epochs from the given epoch to this epoch accounting for wrap-around.

Precondition

this->is_valid(). other doesn't have to be valid, considered as 0.

Definition at line 137 of file epoch.hpp.

References ASSERT_ND, is_valid(), and kEpochIntOverflow.

Referenced by foedus::snapshot::MergeSort::assert_sorted(), foedus::storage::array::prepare_sort_entries(), foedus::storage::hash::prepare_sort_entries(), and foedus::storage::masstree::prepare_sort_entries().

                                              {
    ASSERT_ND(is_valid());
    if (epoch_ >= other.epoch_) {
      return epoch_ - other.epoch_;
    } else {
      // wrap around
      return epoch_ + kEpochIntOverflow - other.epoch_;
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

EpochInteger foedus::Epoch::value ( ) const

inline

Returns the raw integer representation.

Definition at line 102 of file epoch.hpp.

Referenced by foedus::log::LogManagerPimpl::announce_new_durable_global_epoch(), foedus::storage::sequential::SequentialStoragePimpl::apply_truncate(), foedus::storage::sequential::SequentialStoragePimpl::create(), Epoch(), foedus::memory::PagePoolOffsetAndEpochChunk::get_safe_offset_count(), foedus::xct::XctManagerPimpl::handle_epoch_chime(), foedus::snapshot::SnapshotManagerPimpl::handle_snapshot_triggered(), foedus::log::LogManagerPimpl::initialize_once(), foedus::xct::XctManagerPimpl::initialize_once(), foedus::log::Logger::initialize_once(), foedus::snapshot::SnapshotManagerPimpl::initialize_once(), foedus::storage::sequential::SequentialStoragePimpl::load(), foedus::operator<<(), foedus::memory::PagePoolOffsetAndEpochChunk::push_back(), foedus::restart::RestartManagerPimpl::recover(), foedus::log::LogManagerPimpl::refresh_global_durable_epoch(), foedus::savepoint::SavepointManagerPimpl::savepoint_main(), foedus::xct::XctManagerPimpl::set_requested_global_epoch(), foedus::snapshot::SnapshotManagerPimpl::snapshot_metadata(), foedus::savepoint::SavepointManagerPimpl::take_savepoint(), foedus::savepoint::SavepointManagerPimpl::take_savepoint_after_snapshot(), and foedus::storage::sequential::SequentialStoragePimpl::truncate().

{ return epoch_; }

Here is the caller graph for this function:

Friends And Related Function Documentation

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

friend

Definition at line 23 of file epoch.cpp.

                                                      {
  if (v.is_valid()) {
    o << v.value();
  } else {
    o << "<INVALID>";
  }
  return o;
}

---

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

• /home/shino/foedus_code/foedus-core/include/foedus/epoch.hpp