/**
* Hashed Hierarchical Wheel Timer
*
- * Comparison:
- * AsyncTimeout - a single timeout.
- * HHWheelTimer - a set of efficient timeouts with different interval,
- * but timeouts are not exact.
- *
- * All of the above are O(1) in insertion, tick update and cancel
-
- * This implementation ticks once every 10ms.
* We model timers as the number of ticks until the next
* due event. We allow 32-bits of space to track this
* due interval, and break that into 4 regions of 8 bits.
* into a different bucket.
*
* This technique results in a very cheap mechanism for
- * maintaining time and timers, provided that we can maintain
- * a consistent rate of ticks.
+ * maintaining time and timers.
+ *
+ * Unlike the original timer wheel paper, this implementation does
+ * *not* tick constantly, and instead calculates the exact next wakeup
+ * time.
*/
class HHWheelTimer : private folly::AsyncTimeout,
public folly::DelayedDestruction {
/**
* A callback to be notified when a timeout has expired.
*/
- class Callback {
+ class Callback
+ : public boost::intrusive::list_base_hook<
+ boost::intrusive::link_mode<boost::intrusive::auto_unlink>> {
public:
Callback()
: wheel_(nullptr)
HHWheelTimer* wheel_;
std::chrono::milliseconds expiration_;
-
- typedef boost::intrusive::list_member_hook<
- boost::intrusive::link_mode<boost::intrusive::auto_unlink> > ListHook;
-
- ListHook hook_;
+ int bucket_{-1};
typedef boost::intrusive::list<
Callback,
- boost::intrusive::member_hook<Callback, ListHook, &Callback::hook_>,
boost::intrusive::constant_time_size<false> > List;
std::shared_ptr<RequestContext> context_;
return count_;
}
- /**
- * This turns on more exact timing. By default the wheel timer
- * increments its cached time only once everyN (default) ticks.
- *
- * With catchupEveryN at 1, timeouts will only be delayed until the
- * next tick, at which point all overdue timeouts are called. The
- * wheel timer is approximately 2x slower with this set to 1.
- *
- * Load testing in opt mode showed skew was about 1% with no catchup.
- */
- void setCatchupEveryN(uint32_t everyN) {
- catchupEveryN_ = everyN;
- }
-
bool isDetachable() const {
return !folly::AsyncTimeout::isScheduled();
}
typedef Callback::List CallbackList;
CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE];
+ std::vector<uint64_t> bitmap_;
int64_t timeToWheelTicks(std::chrono::milliseconds t) {
return t.count() / interval_.count();
}
bool cascadeTimers(int bucket, int tick);
- int64_t nextTick_;
+ int64_t lastTick_;
+ int64_t expireTick_;
uint64_t count_;
- std::chrono::milliseconds now_;
+ std::chrono::milliseconds startTime_;
+
+ int64_t calcNextTick();
- static constexpr uint32_t DEFAULT_CATCHUP_EVERY_N = 10;
+ void scheduleNextTimeout();
- uint32_t catchupEveryN_;
- uint32_t expirationsSinceCatchup_;
bool* processingCallbacksGuard_;
+ CallbackList timeouts; // Timeouts queued to run
+
+ std::chrono::milliseconds getCurTime() {
+ return std::chrono::duration_cast<std::chrono::milliseconds>(
+ std::chrono::steady_clock::now().time_since_epoch());
+ }
};
} // folly