WheelTimer哈希轮计时器介绍

sofia 4年前 (2021-03-18) 相关技术 | 抢沙发 852

文章评分 0 次，平均分 0.0 ：

[收起] 文章目录

结论

Hashed wheel timers介绍

哈希轮计时器是一种非常有趣的数据结构，在网络服务器中得到了广泛的应用。它们的低内存开销和合理的效率保证非常适合处理数百万个连接的服务器，每个连接都有一个计时器。我们不会花太多时间描述它们是如何工作的，相反，我们将研究一些实现，并尝试评估它们的相对权衡。

让我们快速回顾一下哈希轮计时器的基本数据结构：

WheelTimer哈希轮计时器介绍

基本的数据结构看起来像一个hashmap，带有单独的链表链接。每个桶代表固定数量的滴答声。当一个计时器加到轮子上时，我们计算它应该落在哪个桶里。尽管任何哈希方案都可以，但我们通常只是从当前时间指针一次向前移动一个bucket，直到消耗了足够的时间来触发超时。然后我们将计时器插入到该桶的列表中。考虑到我们有有限数量的桶，在插入计时器之前，我们可能需要绕着计时器转圈几圈。我们需要用定时器存储这些信息。这通常存储为remainingRounds变量。

虚构计时器接口的初稿是：

struct TimerWheel {
public:
  // Fields ....

  // A Timer is uniquely identified by an id.
  // We don't care how this id is generated.
  Timer* add_timer(uint64_t delay, uint64_t id);  // Assume that the delay is in nanos for now.
  void cancel_timer(Timer* timer);
  // Write the list of expired ids into the input array, assuming it is long enough.
  // Returning a list of expired timers instead of calling the expiry processing inline
  // helps in ensuring the integrity of internal timer data structures
  // since all we need to do is ensure that the timer structures are
  // consistent before and after a function call, but not during.
  void expire_timers(uint64_t* ids, uint64_t size);
}

通常，计时器是通过更通用的接口实现的，每个计时器都有一个可运行的任务，该任务在计时器过期时执行。我们已经做了更具体的事情，要求每个计时器都有一个唯一的id。我们还将每个过期计时器对应的代码的执行留给库的用户。我们可以使用其他标识符而不是id。例如，如果计时器用于关闭过时的连接，则可以使用指向每个连接结构的指针。

因此，我们需要的计时器中的绝对最小数据是：

struct Timer {
  uint64_t id;  // Or some other unique identifier. 8 bytes should be enough.
  uint64_t deadline;
  uint64_t remaining_rounds;
  // Other stuff...
};

给出了这个基本方案，让我们看一下实现前面展示的接口的一些方法

1. 每个存储桶的计时器的链接列表

WheelTimer哈希轮计时器介绍

每个bucket只是指向一个具有侵入性的双链接计时器列表。我们的数据结构如下所示：

enum PreviousType {Timer, TimerWheel};

struct Timer {
  uint64_t id;
  uint64_t deadline;
  uint64_t remaining_rounds;
  Timer* next;
  // A tagged union since the previous could be either a
  // pointer to a timer or a pointer to the bucket.
  union {
    Timer* previous;
    TimerBucket* wheel;
  }
  enum PreviousType previousType;
};

struct TimerBucket {
  Timer* timer_list;
};

struct TimerWheel {
  TimerBucket buckets[NUM_BUCKETS];
  // Other stuff.

  // Methods...
};

我们的算法看起来像

Timer* TimerWheel::add_timer(uint64_t delay, uint64_t id) {
  Timer* timer = create_timer(delay, id);
  TimerBucket* bucket = findBucket(timer);
  // Just prepend the timer to the linked list at the bucket;
  insert_into_bucket(bucket_id, timer);
  return timer;
}

void TimerWheel::cancel_timer(Timer* timer) {
  // Since the timer is part of a doubly linked list,
  // just delete it from the linked list and free the memory.
}

// Write the list of expired ids into the input array, assuming it is long enough.
void TimerWheel::expire_timers(uint64_t* ids, uint64_t size) {
  // If it wasn't already clear this is pseudo code.
  deadline = calculate_deadline();
  int num_ids_added = 0;
  for (bucket : every bucket that could contain expired timers) {
    for (timer : bucket) {
      if (0 >= timer->remainingRounds && timer->deadline <= deadline) {
        append_to_ids(ids, size, &num_ids_added, timer->id);
        cancel_timer(timer);
      } else {
        --timer->remainingRounds;
      }
    }
  }
}

因此，我们的算法特点是：

要添加计时器，只需将其前置到适当的链表中–O（1）
要取消计时器–将其从双链接列表中删除–O（1）
清除所有过期计时器–旅行计时器列表并删除过期计时器–O（过期计时器）。实际时间取决于散列到一个桶上的计时器数。我们可以用一般的散列表数学对这个数字下一些界。

对执行情况的评论

这是我们的底线。我们对计时器上的上一个/下一个指针有很强的记忆。很可怕的是，我们必须在每个add_timer（）和cancel_timer（）调用上使用malloc（）和free（）。当然，O（1）调用还隐藏了一个事实，即我们在计时器到期期间遍历一个链表，这是非常可怕的。

2. 每个bucket的计时器指针向量

WheelTimer哈希轮计时器介绍

我们可以存储指向计时器的指针向量，而不是一个侵入式的链表。我们可以根据需要增加这个向量。如果内存不是一个问题，我们可以分配一个足够大的数组，这样就不需要增加内存（尽管仍然需要增加内存）。我们的计时器结构现在看起来像：

struct Timer {
  uint64_t id;
  uint64_t deadline;
  uint64_t remaining_rounds;
};

struct TimerBucket {
  int size;
  int capacity;
  // Array of pointers to timers.
  Timer* timers[];
};

struct TimerWheel {
  TimerBucket buckets[NUM_BUCKETS];
  // Other stuff.

  // Methods...
};

我们的算法看起来像

Timer* TimerWheel::add_timer(uint64_t delay, uint64_t id) {
  Timer* timer = create_timer(delay, id);
  TimerBucket* bucket = findBucket(timer);
  // Just append the timer to the vector for the bucket.
  append_to_bucket(bucket, timer);
  return timer;
}

void TimerWheel::cancel_timer(Timer* timer) {
  // Since the timer is part of a vector, we can't just adjust a couple pointers.
  // Since ordering within the vector is not important, we copy the last
  // timer pointer (if the deleted timer wasn't the last one in the vector)
  // to the deleted position.
  // Decrement the vector size by 1.
  // Moving the pointer to a timer within the vector doesn't invalidate the
  // pointer, so it's perfectly safe.
  // We then free the memory used by the timer.
}

// The expiry logic remains similar. We just traverse an array of pointers now
// instead of a doubly linked list.
void TimerWheel::expire_timers(uint64_t* ids, uint64_t size) {
  // If it wasn't already clear this is pseudo code.
  deadline = calculate_deadline();
  int num_ids_added = 0;
  for (bucket : every bucket that could contain expired timers) {
    for (timer : bucket) {
      if (0 >= timer->remainingRounds && timer->deadline <= deadline) {
        append_to_ids(ids, size, &num_ids_added, timer->id);
        cancel_timer(timer);
      } else {
        --timer->remainingRounds;
      }
    }
  }
}

因此，我们的算法特点是：

要添加计时器，只需将其附加到适当的向量-O（1）。
若要取消计时器，请将其从向量的中间删除，然后移动指针以占用孔–O（1）。
要清除所有过期计时器–遍历计时器向量并删除过期计时器–O（过期计时器）。同样，实际时间取决于散列到一个桶上的计时器的数量。

对执行情况的评论

这比我们的底线稍有改进。通过使用指向计时器的指针向量，我们消除了对下一个指针的需要—空间利用率略有提高。在每次add_timer（）和cancel_timer（）调用中，我们仍然需要使用malloc（）和free（）。在计时器过期期间，我们现在遍历指向计时器的指针向量，而不是链表。这只比第一个实现稍微好一点，因为计时器本身是随机分配的。

3. 内联计时器向量

WheelTimer哈希轮计时器介绍

让我们看看是否可以通过使我们的接口更加专业化来提高效率。到目前为止，我们已经在add_Timer（）调用中返回了一个Timer*。我们打算用这个指针来取消计时器。因此，我们最终会把这个指针藏在某个地方。可能是在每个连接的结构上，或者是在散列映射上。如果我们可以在计时器中存储指向这个计时器保持器结构（指向我们的计时器）的指针呢？然后我们可以安全地将指针移到计时器上/使其无效，从而更新该计时器实际引用的唯一位置。这里我们假设指向计时器的指针只藏在一个地方。这有点像我们自己的小垃圾收集器更新对四处移动的计时器对象的引用。让我们看看我们的新数据结构：

// Holder of a pseudo-pointer to a timer.
// This can be used to cancel the timer.
struct TimerHolder {
  uint32_t bucket_number;
  uint32_t index_within_bucket;
};

struct Timer {
  uint64_t id;
  uint64_t deadline;
  uint64_t remaining_rounds;
  // Pointer to the sole container of this timer.
  TimerHolder* holder;
};

struct TimerBucket {
  int size;
  int capacity;
  // Array of Timers.
  Timer* timers;
};

struct TimerWheel {
  TimerBucket buckets[NUM_BUCKETS];
  // Other stuff.

  // Methods...
};

我们现在修改的接口是：

// Put the pointer to the timer in the holder.
void add_timer(uint64_t delay, uint64_t id, TimerHolder* holder);

// The TimerHolder is always kept up to date. Since this is a single threaded timer
// this is not impossible to ensure.
void cancel_timer(TimerHolder* timer);

// Write the list of expired ids into the input array, assuming it is long enough.
void expire_timers(uint64_t* ids, uint64_t size);

我们的算法看起来像

void TimerWheel::add_timer(uint64_t delay, uint64_t id, TimerHolder* holder) {
  TimerBucket* bucket = findBucket(timer);
  // Just append timer to end of the bucket, no malloc needed.
  // Update the holder to contain the bucket_number and index_within_bucket.
  initalize_timer(bucket, delay, id, holder);
}

void TimerWheel::cancel_timer(TimerHolder* holder) {
  // Do some sanity checking first.
  TimerBucket* bucket = find_bucket(holder->bucket_number);
  uint32_t cancelled_timer_index = holder->index_within_bucket;
  Timer* timer = find_timer(bucket, cancelled_timer_index);
  // We need to cancel this timer.
  // Just memcpy the last timer in this bucket to occupy the deleted place.
  // A timer is just 32 bytes, copying it VS copying a pointer is not a big deal.
  // If the cancelled timer is the last timer in this bucket no copy is needed.
  // Decrement the vector size by 1.
  Timer* moved_timer = move_last_timer_if_needed(bucket, cancelled_timer_index);
  if (moved_timer != nullptr) {
    // If a timer that was moved, change it's holder's offsets, 
    // so it points to the new location of the timer.
    adjust_holder_pointer(moved_timer->holder, cancelled_timer_index);
  }
  // The holder for the deleted timer should point to something illegal like {-1, -1}.
  // The caller will decide what to do with the holder after this function returns.
  invalidate_holder_timer(holder);
}

// The expiry logic remains similar. We just traverse an array of inlined timers now.

void TimerWheel::expire_timers(uint64_t* ids, uint64_t size) {
  // If it wasn't already clear this is pseudo code.
  deadline = calculate_deadline();
  int num_ids_added = 0;
  for (bucket : every bucket that could contain expired timers) {
    for (timer : bucket) {
      if (0 >= timer->remainingRounds && timer->deadline <= deadline) {
        append_to_ids(ids, size, &num_ids_added, timer->id);
        cancel_timer(timer->holder);
      } else {
        --timer->remainingRounds;
      }
    }
  }
}

因此，我们的算法特点是：

要添加一个计时器，只需在适当的向量-O（1）的末尾涂鸦一些数据。
要取消计时器，请将bucket中的最后一个计时器复制到已删除计时器的位置，并调整对已移动计时器的引用–O（1）。
要清除所有过期的计时器–遍历计时器向量，并使用cancel_timer（）调用–O（过期计时器）删除过期的计时器。同样，实际时间取决于散列到一个桶上的计时器的数量。

对执行情况的评论

我们不再在每次计时器调用时调用malloc（）和free（）。相反，我们管理大的bucket并复制少量的数据来管理删除。我们最终存储了一个指向计时器对象持有者的指针，但总体来说，我们存储的数据没有其他实现存储的数据多。当我们摆脱malloc（）和free（）调用时，我们也摆脱了由它们引起的任何碎片。此外，在到期处理期间，我们遍历一块连续内存，而不是指针跟踪。