Netty高性能数据结构

Netty高性能数据结构

Netty 用高性能数据结构的主要目的是为了提高网络通信的效率和系统的整体性能。

所谓的高性能数据结构是指，那些在特定场景下优化了性能和效率的数据结构，通常能够提供更快的操作速度、更低的内存消耗或更高的并发处理能力。

数据结构	原因	好处
FastThreadLocal	ThreadLocal 在高并发场景中性能较低且容易造成内存泄漏。	更快的访问速度，优化线程本地存储；避免内存泄漏，提供更安全的内存管理。
HashedWheelTimer	传统定时任务调度效率低，在高负载环境中成为性能瓶颈。	高效调度，时间轮算法优化任务组织；减少资源消耗，通过批量处理任务。
MpscLinkedQueue	传统队列实现性能瓶颈，需要无锁队列支持多个生产者。	提高并发性，支持多个线程同时添加任务；高效任务处理，减少锁竞争。

FastThreadLocal

FastThreadLocal是Netty针对高并发场景优化的线程本地存储解决方案，通过减少内存占用、锁竞争和性能开销，提供了比ThreadLocal更高效的线程本地存储能力。

在Netty中，FastThreadLocal被广泛使用于处理网络事件和任务调度。主要包括：

• EventLoop： Netty的EventLoop组件使用FastThreadLocal来存储和管理线程本地的数据，如Channel处理上下文、任务调度信息等。
• 线程池管理：FastThreadLocal用于优化线程池中的线程本地存储，来提高任务处理的效率。

FastThreadLocal对比ThreadLocal优势主要在快速的定位数据和更高的安全性。FastThreadLocal的设计是为了在高性能需求场景下提供优化的性能表现。

快速定位数据具体体现在，当调用ThreadLocal.set()添加Entry对象时，ThreadLocal是使用线性探测法解决Hash冲突的。线性探测法是一种用于解决哈希表中冲突的开放地址法。它的基本思路是在哈希表中发生冲突时，线性地探测哈希表中的下一个位置来寻找空闲的存储位置。当两个或更多的元素被哈希到相同的槽位时，会发生冲突。当发生冲突时，探测下一个位置。如果下一个位置也被占用，则继续探测下一个位置，直到找到一个空闲的位置。

为了便于理解，我们采用一组简单的数据模拟ThreadLocal.set()的过程是如何解决Hash冲突的。

• threadLocalHashCode = 4，threadLocalHashCode & 15 = 4；此时数据应该放在数组下标为4的位置。下标4的位置正好没有数据，可以存放。
• threadLocalHashCode = 19，threadLocalHashCode & 15 = 4；但是下标4的位置已经有数据了，如果当前需要添加的Entry与下标4位置已存在的Entry两者的key相同，那么该位置Entry的value将被覆盖为新的值。我们假设key都是不相同的，所以此时需要向后移动一位，下标5的位置没有冲突，可以存放。
• threadLocalHashCode = 33，threadLocalHashCode & 15 = 3；下标3的位置已经有数据，向后移一位，下标4位置还是有数据，继续向后查找，发现下标6没有数据，可以存放。

ThreadLocal.get()的过程也是类似的，也是根据threadLocalHashCode的值定位到数组下标，然后判断当前位置Entry对象与待查询Entry对象的key是否相同，如果不同，继续向下查找。由此可见，ThreadLocal.set()/get()方法在数据密集时很容易出现Hash冲突，需要O(n)时间复杂度解决冲突问题，效率较低。

FastThreadLocal在定位数据的时候可以直接根据数组下标index获取，时间复杂度O(1)。此外，FastThreadLocal相比ThreadLocal数据扩容更加简单高效，FastThreadLocal以index为基准向上取整到2的次幂作为扩容后容量，然后把原数据拷贝到新数组。而ThreadLocal由于采用的哈希表，所以在扩容后需要再做一轮rehash。

安全性体现在，ThreadLocal使用不当可能造成内存泄漏，只能等待线程销毁。在使用线程池的场景下，ThreadLocal只能通过主动检测的方式防止内存泄漏，从而造成了一定的开销。然而FastThreadLocal不仅提供了remove()主动清除对象的方法，而且在线程池场景中Netty还封装了FastThreadLocalRunnable，FastThreadLocalRunnable最后会执行FastThreadLocal.removeAll()将Set集合中所有FastThreadLocal对象都清理掉。

FastThreadLocal使用示例：

public class FastThreadLocalExample {private static final FastThreadLocal<String> threadLocal = new FastThreadLocal<String>() {@Overrideprotected String initialValue() {return "Initial Value";}};public static void main(String[] args) {// 创建并启动两个线程FastThreadLocalThread thread1 = new FastThreadLocalThread(() -> {String value = threadLocal.get();System.out.println("Thread1 initial value: " + value);threadLocal.set("Thread1 Value");System.out.println("Thread1 new value: " + threadLocal.get());});FastThreadLocalThread thread2 = new FastThreadLocalThread(() -> {String value = threadLocal.get();System.out.println("Thread2 initial value: " + value);threadLocal.set("Thread2 Value");System.out.println("Thread2 new value: " + threadLocal.get());});thread1.start();thread2.start();try {thread1.join();thread2.join();} catch (InterruptedException e) {e.printStackTrace();}}
}

HashedWheelTimer时间轮

为了实现高性能的定时任务调度，Netty引入了时间轮算法驱动定时任务的执行。它通过将定时任务分配到轮盘上的不同槽位来避免高频率的任务调度开销，这种设计主要用于处理大量的定时任务。

在Netty中，HashedWheelTimer主要用于处理任务的延迟执行，例如定时任务、超时处理等。HashedWheelTimer是一种基于时间轮算法的定时任务调度器，主要用于高效地管理和执行大量定时任务。时间轮算法将时间分割成一个个固定大小的时间片，并将任务安排到相应的时间片上，从而优化了定时任务的管理。

时间轮可以理解为一种环形结构，像钟表一样被分为多个slot槽位。每个slot代表一个时间段，每个slot中可以存放多个任务，使用的是链表结构保存该时间段到期的所有任务。时间轮通过一个时针随着时间一个个slot转动，并执行slot中的所有到期任务。

时间轮有点类似HashMap，如果多个任务如果对应同一个slot，处理冲突的方法采用的是拉链法。在任务数量比较多的场景下，适当增加时间轮的slot数量，可以减少时针转动时遍历的任务个数。时间轮定时器最大的优势就是，任务的新增和取消都是O(1)时间复杂度，而且只需要一个线程就可以驱动时间轮进行工作。

时间轮是以时间作为刻度组成的一个环形队列，所以叫做时间轮。这个环形队列采用数组来实现HashedWheelBucket[]，数组的每个元素称为槽，每个槽可以存放一个定时任务列表，叫HashedWheelBucket，它是一个双向链表，链表的每个节点表示一个定时任务项（HashedWheelTimeout），其中封装了真正的定时任务TimerTask。

public HashedWheelTimer(ThreadFactory threadFactory,long tickDuration, TimeUnit unit, int ticksPerWheel, boolean leakDetection,long maxPendingTimeouts) {// 省略其他代码wheel = createWheel(ticksPerWheel); // 创建时间轮的环形数组结构mask = wheel.length - 1; // 用于快速取模的掩码long duration = unit.toNanos(tickDuration); // 转换成纳秒处理// 省略其他代码workerThread = threadFactory.newThread(worker); // 创建工作线程leak = leakDetection || !workerThread.isDaemon() ? leakDetector.track(this) : null; // 是否开启内存泄漏检测this.maxPendingTimeouts = maxPendingTimeouts; // 最大允许等待任务数，HashedWheelTimer 中任务超出该阈值时会抛出异常// 如果 HashedWheelTimer 的实例数超过 64，会打印错误日志if (INSTANCE_COUNTER.incrementAndGet() > INSTANCE_COUNT_LIMIT &&WARNED_TOO_MANY_INSTANCES.compareAndSet(false, true)) {reportTooManyInstances();}
}

HashedWheelTimer的核心组件：

• HashedWheelTimeout，任务的封装类，包含任务的到期时间、需要经历的圈数remainingRounds等属性。
• HashedWheelBucket，相当于时间轮的每个slot，内部采用双向链表保存了当前需要执行的HashedWheelTimeout列表。
• Worker，HashedWheelTimer的核心工作引擎，负责处理定时任务。

HashedWheelTimer的工作流程：

• 新增任务：通过当前时间和任务的延迟时间计算出任务的到期时间。根据任务的到期时间，计算出任务应放置在时间轮的哪个槽位。这个计算基于当前时间与到期时间的差值，经过一定的模运算。将任务封装成HashedWheelTimeout对象，并插入到对应的HashedWheelBucket中。

  public Timeout newTimeout(TimerTask task, long delay, TimeUnit unit) {// 计算任务的到期时间long deadline = System.nanoTime() + unit.toNanos(delay);// 计算任务应插入的槽位int tick = (int) ((deadline / tickDurationNanos) & mask);// 创建 HashedWheelTimeout 对象HashedWheelTimeout timeout = new HashedWheelTimeout(this, task, deadline, tick);// 将任务添加到相应的 HashedWheelBucket 中wheel[tick].add(timeout);return timeout;
  }
  

• 执行任务：HashedWheelTimer 使用 Worker 线程来周期性地推进时间轮。Worker线程每隔一个刻度时间推进时间轮一个槽位。每次推进时，它检查当前槽位中的所有任务。对于到期的任务，Worker线程将其从槽位中移除并执行。任务执行后，HashedWheelTimeout 对象会被标记为已完成，执行相关的回调方法。

  private final class Worker implements Runnable {@Overridepublic void run() {while (workerState == WORKER_STATE_STARTED) {try {Thread.sleep(tickDuration);advanceClock(); // 推进时间轮processTimeouts(); // 执行到期任务} catch (InterruptedException e) {// 处理异常}}}private void advanceClock() {// 更新当前时间轮的槽位}private void processTimeouts() {// 遍历当前槽位，执行到期任务}
  }
  

• 取消任务：如果需要取消一个任务，可以调用Timeout对象的cancel方法。取消任务会从槽位中移除相应的HashedWheelTimeout对象，确保它不会被执行。

  public boolean cancel() {boolean removed = bucket.remove(this); // 从槽位中移除if (removed) {// 执行取消回调等操作}return removed;
  }
  

• 停止定时器：当需要停止HashedWheelTimer时，stop方法会被调用。使用CAS操作将Worker线程的状态更新为SHUTDOWN，确保不会再有新的任务被添加。中断Worker线程并等待其停止。处理线程中断异常，确保线程被完全停止。关闭内存泄漏检测器并减少实例计数，返回所有未处理的任务。

public Set<Timeout> stop() {// 如果当前线程是 workerThread，则抛出异常if (Thread.currentThread() == workerThread) {throw new IllegalStateException(HashedWheelTimer.class.getSimpleName() +".stop() cannot be called from " +TimerTask.class.getSimpleName());}// 尝试通过 CAS 操作将工作线程的状态更新为 SHUTDOWNif (!WORKER_STATE_UPDATER.compareAndSet(this, WORKER_STATE_STARTED, WORKER_STATE_SHUTDOWN)) {if (WORKER_STATE_UPDATER.getAndSet(this, WORKER_STATE_SHUTDOWN) != WORKER_STATE_SHUTDOWN) {INSTANCE_COUNTER.decrementAndGet();if (leak != null) {boolean closed = leak.close(this);assert closed;}return Collections.emptySet();}}try {boolean interrupted = false;// 中断 workerThread 并等待其停止while (workerThread.isAlive()) {workerThread.interrupt(); // 中断工作线程try {workerThread.join(100); // 等待工作线程停止} catch (InterruptedException ignored) {interrupted = true;}}if (interrupted) {Thread.currentThread().interrupt();}} finally {INSTANCE_COUNTER.decrementAndGet(); // 减少实例计数if (leak != null) {boolean closed = leak.close(this);assert closed;}}return worker.unprocessedTimeouts(); // 返回未处理的任务
}

以下是HashedWheelTimer使用示例，展示了如何创建定时器、添加定时任务、执行任务以及停止定时器：

public class HashedWheelTimerExample {public static void main(String[] args) {// 创建 HashedWheelTimer 实例，刻度为1秒，时间轮槽的数量为512HashedWheelTimer timer = new HashedWheelTimer(1, TimeUnit.SECONDS, 512);// 定义一个定时任务TimerTask task = new TimerTask() {@Overridepublic void run(Timeout timeout) {System.out.println("定时任务执行时间: " + System.currentTimeMillis());}};// 添加定时任务到时间轮，设置任务延迟5秒执行timer.newTimeout(task, 5, TimeUnit.SECONDS);// 等待10秒，让定时任务有机会执行try {Thread.sleep(10000);} catch (InterruptedException e) {e.printStackTrace();}// 停止时间轮定时器，并返回未处理的定时任务数量Set<Timeout> unprocessedTimeouts = timer.stop();System.out.println("未处理的定时任务数量: " + unprocessedTimeouts.size());}
}

Mpsc无锁队列

Mpsc的全称是Multi Producer Single Consumer，多生产者单消费者。Mpsc Queue可以保证多个生产者同时访问队列是线程安全的，而且同一时刻只允许一个消费者从队列中读取数据。Netty Reactor线程中任务队列必须满足多个生产者可以同时提交任务，所以Mpsc Queue非常适合Netty Reactor线程模型。

在Netty中，EventLoopGroup负责管理和调度处理网络事件的线程。EventLoopGroup的实现使用了无锁队列来维护待处理的任务和事件。具体来说是SingleThreadEventLoop和NioEventLoop这两个类使用无锁队列来存储任务和事件。这些队列是Mpsc类型的无锁队列，允许多个线程同时提交任务，而由单个事件循环线程处理这些任务。无锁队列的使用有效地提高了并发性能，减少了锁竞争的开销，使得事件处理更加高效。

在传统的锁机制下，当多个线程尝试同时访问共享数据结构时，会产生竞争，从而导致性能下降。使用无锁队列可以避免使用锁，减少线程间的竞争和上下文切换，提高并发性能。它的核心在于利用原子操作来保证线程安全。原子操作是指在执行过程中不会被其他线程打断的操作，保证数据的一致性。通常实现是使用链表结构，其中每个节点包含数据和指向下一个节点的引用。队列的头节点和尾节点通过原子操作来维护，插入和删除操作通过调整节点的链接来完成。

public class MpscQueue<E> {private final Node<E> head;private final AtomicReference<Node<E>> tail;public MpscQueue() {head = new Node<>(null);tail = new AtomicReference<>(head);}public void offer(E item) {Node<E> newTail = new Node<>(item);Node<E> oldTail = tail.getAndSet(newTail);oldTail.next = newTail;}public E poll() {Node<E> headNode = head.next;if (headNode == null) {return null; // 队列为空}head.next = headNode.next;return headNode.item;}private static class Node<E> {private final E item;private Node<E> next;Node(E item) {this.item = item;}}
}