0. 主存储
dpdk高性能
轮询机制
在包处理时，采用轮询机制，而避免中断，有利于减少上下文切换的开销，规避不必要的内存拷贝和系统调用。
亲和性与独占
特定任务可以被指定只在某个核上工作，避免线程在不同核间频繁切换，保证更多的cache命中
设置CPU亲和性，让程序近运行在指定的核上，仅读取指定网卡的指定队列，从而避免数据竞争
无锁循环队列
并行指令，从而加速访问
CPU Cache 加速
- cache行对齐
- 预取数据，CPU提供了指令来供程序员使用，提前把要读区的数据从内存加载到对应的Cache
- 每个核尽量不与其他核共享数据，以减少Cache保持一致性带来的额外成本
引入大页表
矛盾：TLB大小有限 VS 尽可能高的查询命中率
解法：但是一个常规页4k，假设一个程序用了512页，总共2MB，这就需要TLB里至少方下512个页表项才能保证每次都能命中，但TLB大小有限。所以为了减少TLB不命中的情况，可以使用大页，以1G为单位进行分页。
降低访存开销：利用内存大页HUGEPAGE降低TLB miss，利用内存多通道交错访问提高内存访问有效带宽
克服NUMA
为了克服SMP的总线负担大的问题，引入NUMA，但是引入了新的问题：访问远程内存效率低下。
DPDK为了克服NUMA的弊端，采取了如下措施：
①Pre-corememory。每个核都有属于自己的内存，经常访问的数据结构有自己的备份。这样既满足了本地内存的需要，又可以避免cache一致性问题。
②本地设备本地处理。如果一个PCI设备在node0上，那这个设备就由Node0处理。比如：
q = rte_zmalloc_socked\t(“fm10k”,sizeof(*q), RTE_CACHE_LINE_SIZE, socket_id);
充分利用DDIO
Data Direct I/O Technology
没有DDIO的情况下，处理一个报文，CPU和网卡需要多次访问内存，而内存又很慢，造成CPU长时间等待内存。
DDIO让外部网卡和cpu通过LLC Cache交换数据，绕过内存。但是报文要存在LLC Cache中，增加了对LLC Cache的容量需求。（*LLC = Last Level Cache）
性能极致优化（内存篇）
一个程序的性能构成要件大概有三个，即算法复杂度、IO开销和并发能力。
首要的影响因素是大家都熟悉的算法复杂度。一次核心算法优化和调整，可以对应用性能产生的影响甚至是代差级别的。例如LSM Tree对No-SQL吞吐的提升，又例如事件触发对epoll大并发能力的提升。
关于IO，尤其是『内存IO』可能需要特别说明一下。
内存池的能力上限
job arena, job reserve（vector的clear,rebuild)
第一种是基础的job arena方案，也就是每个job有一个独立的内存分配器，job中使用的动态内存注册到job的arena中。因为job生命周期明确，中途释放的动态内存被认为无需立即回收，也不会显著增大内存占用。在无需考虑回收的情况下，内存分配不用再考虑分块对齐，每个线程内可以完全连续。最终job结束后，整块内存直接全部释放掉，大幅减少实际的竞争发生。
4.1 顺序访存优化
当硬件监测到连续地址访问模式出现时，会激活多层预取器开始执行，参考当前负载等因素，将预测将要访问的数据加载到合适的缓存层级当中。这样，当后续访问真实到来的时候，能够从更近的缓存层级中获取到数据，从而加速访问速度。因为L1容量有限，L1的硬件预取步长较短，加速目标主要为了提升L2到L1，而L2和LLC的预取步长相对较长，用于将主存提升到cache。
4.2 并发访问优化
CacheLine
典型的问题一般叫做false share现象，也就是不慎将两个本无竞争的数据，放置在一个缓存行内，导致因为体系结构的原因，引入了『本不存在的竞争』
false share: 添加padding
MESI协议 store buffer， invalid buffer
memory-relaxed 每次去做读内存，而不是访问寄存器
memory-release store时，
memory-acquire load时，
要求：对同一变量M分别进行写（release）A和读（acquire）B，B读到了A写入的值。
承诺：A之前的所有其他写操作，对B之后的读操作可见。
再进一步的内存序，就是最强的一级sequentially-consistent，其实就是恢复到了MESI的承诺等级，即顺序一致
要求：对两个变量M，N的（Sequentially Consistent）写操作Am，An。在任意线程中，通过（Sequentially Consistent）的读操作观测到Am先于An。
承诺：在其他线程通过（Sequentially Consistent）的读操作B也会观测到Am先于An。
先给出一个基本测试的结论，看一下一组对比数据：
多线程竞争写入近邻地址sequentially-consistent：0.71单位时间
多线程竞争写入近邻地址release：0.006单位时间
多线程竞争写入cache line隔离地址sequentially-consistent：0.38单位时间
多线程竞争写入cache line隔离地址release：0.02单位时间
这里可以看出，做cache line隔离，对于sequentially-consistent内存序下，有一定的收益，但是对release内存序，反而有负效果。这是由于release内存序下，因为没有强内存屏障，写缓冲起到了竞争缓解的作用。而在充分缓解了竞争之后，因为cache line隔离引入了相同吞吐下更多cache line的传输交互，反而开销变大。
在这个信息指导下，我们在实现无锁队列时，采用了循环数组 + 分槽位版本号的模式来实现。因为队列
操作只需要acquire-release等级，分槽位版本号间无需采用cache line隔离模式设计，整体达到了比较高的并发性能。
Transistors (thousands) 需求一直在等家
Single-Thread Performance (SpecINT x 103) 已经遇到瓶颈了
Frequency(MHz) 已经到达瓶颈
Typical Power (Watts)
Number of Logical Cores 在主频&单线程性能遭遇性能之后，持续增加
这些算力的增长需求大部分还可以通过处理器更新换代来自然解决，可是随着主频增长停滞，如果无法利用多核心来加速，程序的处理性能就会随主频一同面临增长停滞的问题。
因此近些年来，是否能够充分利用多核心计算，也越来越成为高性能程序的一个标签，也只有具备了充分的多核心利用能力，才能随新型硬件演进，继续表现出指数级的性能提升。而伴随多核心多线程程序设计的普及，如何处理好程序的并发也逐渐成了工程师的一项必要技能。
单线程中的并行执行
充分配合CPU完成一些高性能的计算任何，去feed CPU！
SIMD 单指令多数据
OoOE 另一个重要的单线程内并行能力就是乱序执行OoOE（Out of Order Execution）。经典教科书上的CPU流水线机制一般描述如下（经典5级RISC流水线）。
乱序执行系统中，一般会将通过预测维护一个较长的指令序列，并构建一个指令池，通过解析指令池内的依赖关系，形成一张DAG（有向无环图） 组织的网状结构。通过对DAG关系的计算，其中依赖就绪的指令，就可以进入执行态，被提交到实际的执行部件中处理。执行部件类似多线程模型中的工作线程，根据特性细分为计算和访存两类。计算类一般有相对固定可预期的执行周期，而访存类由于指令周期差异较大，采用了异步回调的模型，通过Load/Store Buffer支持同时发起数十个访存操作。
四、多线程并发中的临界区保护
Mutual Exclusion，造成了阻塞放大的现象。
Lock-Free 无锁技术主要解决了临界区内的阻塞传播问题，但是本质上，多个线程依然是排队顺序经过临界区。形象来说，有些类似交通中的三叉路口汇合， 无论是互斥还是无锁，最终都是把两条车道汇聚成了一条单车道，区别只是指挥是否高明能保证没有断流出现。可是无论如何，临界区内全局吞吐降低成串行这点是共同的缺陷。
Wait-Free
而Wait Free级别和无锁的主要区别也就体现在这个吞吐的问题上，在无全局停顿的基础上，Wait Free进一步保障了任意算法参与线程，都应该在有限的步骤内完成。这就和无锁技术产生了区别，不只是整体算法时时刻刻存在有效计算，每个线程视角依然是需要持续进行有效计算。这就要求了多线程在临界区内不能被细粒度地串行起来，而必须是同时都能进行有效计算。回到上面三叉路口汇聚的例子，就以为着在Wait Free级别下，最终汇聚的道路依旧需要是多车道的，以保证可以同时都能够有进展。
由于Lock Free算法一般对临界区需要设计成两阶段提交，以便支持回滚撤销，因此往往需要比对应的互斥保护算法更复杂，局部性也可能更差（例如某些场景必须引入链表来替换数组）。综合来看，一般如果无法做到Wait Free，那么无需对Lock Free过度执着，充分优化临界区的互斥方法往往也足以提供和Lock Free相当的性能表现了。
首先给出一个典型的锁实现，左侧是锁的fast path，也就是如果在外层的原子变量操作中未发现竞争，那么其实上锁和解锁其实就只经历了一组原子变量操作。当fast path检测到可能出现冲突时，才会进入内核，尝试进行排队等待。fast path的存在大幅优化了低冲突场景下的锁表现，而且现代操作系统内核为了优化锁的内存开销，都提供了『Wait On Address』的功能，也就是为了支持这套排队机制，每个锁常态只需要一个整数的存储开销即可，只有在尝试等待时，才会创建和占用额外的辅助结构。
不过即使竞争很低，锁也还是会由一组原子操作实现，而当我们自己查看原子操作时，实际是由cache锁操作保护的原子指令构成，而且这个指令会在乱序执行中起到内存屏障的效果降低访存重叠的可能性。因此针对非常常用的简单计数器，在百度内部我们进行了进一步去除局部锁的改造，来试图进一步降低统计开销。
在比较新的X86和ARM服务端机型上已经可以做到128bit的原子load/store，因此可以利用相应的高位宽指令和正确对齐来实现锁的去除。
队列优化案例：
队列，头尾一起加锁；
队列，头，尾分别加锁
在头尾分离之后，进一步的优化进入了两个方向。首先是因为单节点的操作具备了Lock Free化的可能，因此产生了对应的Michael & Scott无锁队列算法。业界的典型实现有Java的ConcurrentLinkedQueue，以及boost中的boost::lockfree::queue。
而另一个方向是队列分片，即将队列拆解成多个子队列，通过领取token的方式选择子队列，而子队列内部使用传统队列算法，例如tbb:: concurrent_queue就是分片队列的典型实现。
两种方式进行对比，可以发现，在强竞争下，分片队列的效果其实显著胜过单纯的无锁处理，这也是前文对于无锁技术真实效果分析的一个体现。
除了这类通用队列，还有一个强化竞争发布，串行消费的队列也就是bthread::ExecutionQueue，它在是brpc中主要用于解决多线程竞争fd写入的问题。利用一些有趣的技巧，对多线程生产侧做到了Wait Free级别。
整个队列只持有队尾，而无队头。在生产侧，第一步直接将新节点和当前尾指针进行原子交换，之后再将之前的队尾衔接到新节点之后。因为无论是否存在竞争，入队操作都能通过固定的两步完成，因此入队算法是Wait Free的。不过这给消费侧带来的麻烦，消费同样从一个原子交换开始，将队尾置换成nullptr，之后的消费动作就是遍历取到的单链表。但是因为生产操作分了两部完成，此时可能发现部分节点尚处于『断链』状态，由于消费者无从知晓后续节点信息，只能轮询等待生产者最终完成第二步。所以理论上，生产/消费算法其实甚至不是Lock Free的，因为如果生产者在两阶段中间被换出，那么消费者会被这个阻塞传播影响，整个消费也只能先阻塞住。但是在排队写入fd的场景下，专项优化生产并发是合理，也因此可以获得更好的执行效率。
不过为了能利用原子操作完成算法，bthread::ExecutionQueue引入了链表作为数据组织方式，而链表天然存在访存跳跃的问题。那么是否可以用数组来同样实现Wait Free的生产甚至消费并发呢？
回到babylon::ConcurrentBoundedQueue的设计思路上，其实是将子队列拆分做到极致，将同步量粒度降低到每个数据槽位上。每个入队和出队 请求，首先利用原子自增领取一个递增的序号，之后利用循环数组的存储方式，就可以映射到一个具体的数据槽位上。根据操作是入队还是出队， 在循环数组上发生了多少次折叠，就可以在一个数据槽位上形成一个连续的版本序列。例如1号入队和5号出队都对应了1号数据槽位，而1号入队预期的版本转移是0到1，而5号出队的版本转移是2到3。这样针对同一个槽位的入队和出队也可以形成一个连续的版本变更序列，一个领到序号的具体操作，只需要明确检测版本即可确认自己当前是否可以开始操作，并通过自己的版本变更和后续的操作进行同步。
通过同步量下放到每个元素的方式，入队和出队操作在可以除了最开始的序号领取存在原子操作级别的同步，后续都可以无干扰并行开展。而更连续的数据组织，也解决了链表存储的访存跳跃问题。生产消费双端可并发的特点，也提供了更强的泛用性，实际在MPMC（Multiple Producer Multiple Consumer）和MPSC（Multiple Producer Single Consumer）场景下都有不错的性能表现，在具备一定小批量处理的场景下尤其显著。
