False Sharing
为了弥合CPU 与Memory之间的速度差距，两者之间存在着至少两级缓存(L1 Cache、L2 Cache)。越靠近 CPU 的缓存越快也越小。L1 Cache很小但很快，并且与 CPU 很近。L2 Cache 稍微大一些，也慢一些，并且仍然只能被一个单独的 CPU 使用。Memory 保存着程序运行的所有数据，它更大，更慢，由所有 CPU 共享。
缓存中是以缓存行（Cache Line）为单位存储的。Cache Line是2的整数幂个连续字节，一般为32-256个字节。最常见的Cache Line大小是64个字节。
当多线程修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，这就是伪共享。
缓存行上的写竞争是运行在SMP系统中并行线程实现可伸缩性最重要的限制因素。为了让可伸缩性与线程数呈线性关系，就必须确保不会有两个线程往同一个变量或缓存行中写。
Lock Free
无锁数据结构的实现主要基于两个方面：原子性操作和内存访问控制方法。
原子操作是一个不可分的操作；要么发生，要么不发生，不存在部分结果（partial effects）。
原子性操作可以简单地分为读写（read and write）、原子性交换操作（read-modify-write，RMW）两部分。
构建无锁数据结构时需要用到RMW操作，其包括：compare-and-swap (CAS)、fetch-and-add (FAA)、test-and-set (TAS) 等。
C++ 11中CAS为std::atomic::compare_exchange_weak和std::atomic::compare_exchange_strong。
其如同用std::memcmp 原子地比较 this 的对象表示和 expected 的对象表示，而若它们逐位相等，则以 desired 替换前者。否则，将 this 中的实际值加载进 expected。如同用 std::memcpy 进行复制。
ABA问题
在进行CAS操作的时候，因为在更改V之前，CAS主要询问“V的值是否仍然为A”，所以在第一次读取V之后以及对V执行CAS操作之前，如果将值从A改为B，然后再改回A，会使基于CAS的算法混乱。在这种情况下，CAS操作会成功。这类问题称为ABA问题。
CAS：对于内存中的某一个值V，提供一个旧值A和一个新值B。如果提供的旧值A和V相等就把B写入V。这个过程是原子性的。CAS执行结果要么成功要么失败，对于失败的情形下一班采用不断重试。或者放弃。
ABA：如果另一个线程修改V值假设原来是A，先修改成B，再修改回成A。当前线程的CAS操作无法分辨当前V值是否发生过变化。
关于ABA问题我想了一个例子：在你非常渴的情况下你发现一个盛满水的杯子，你一饮而尽。之后再给杯子里重新倒满水。然后你离开，当杯子的真正主人回来时看到杯子还是盛满水，他当然不知道是否被人喝完重新倒满。
解决这个问题的方案的一个策略是每一次倒水假设有一个自动记录仪记录下，这样主人回来就可以分辨在她离开后是否发生过重新倒满的情况。这也是解决ABA问题目前采用的策略。
Hazard pointer
The Hazard Pointers are one approach to solving the problems posed by dynamic memory management of the nodes in a lock-free data structure.
Each reader thread owns a single-writer/multi-reader shared pointer called “hazard pointer.” When a reader thread assigns the address of a map to its hazard pointer, it is basically announcing to other threads (writers), “I am reading this map. You can replace it if you want, but don’t change its contents and certainly keep your deleteing hands off it.”
Hazard Pointer使用的数据存储结构：
- pointers:用来存储这个线程当前正在访问的内存对象，正在访问的内存对象不能被任何线程释放。
- retire list:被这个线程删除的内存对象，但还没有释放。
红黑树
红黑树本质上是一颗二叉查找树，它是在二叉查找树的基础上给节点增加红黑颜色属性以及五条约束的性质。
红黑树与二叉查找树的查找操作是一模一样的，所以掌握了二叉查找树之后，学习红黑树就只剩下增加及删除节点了。
红黑树（Red-Black-Tree）是在 1972 年由鲁道夫·贝尔发明，被称为对称二叉 B树，是一种由红黑节点组成并能自平衡的二叉查找树。红黑树保证了最坏情形下在 O(logn) 时间复杂度内完成查找、插入及删除操作；
红黑树另外一个熟知的应用场景就是面试了，红黑树作为数据结构当中最典型的一种树，常被拿来当面试题考查树的相关知识。
性质
- 每个节点或者是黑色或者是红色。
- 根节点是黑色。
- 每个叶子节点（null）是黑色。
- 如果一个节点是红色，则它的子节点必须是黑色，即两个红色节点不能直接相连。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点。
二叉查找树遍历
前序遍历：先访问根节点然后遍历左子树，最后遍历右子树。
中序遍历：先遍历左子树然后访问根节点，最后遍历右子树。
后序遍历：先遍历左子树然后遍历右子树，最后访问根节点。
二叉查找树并非平衡树，它只限制了左右子树与根点之间的大小关系，只有在平衡二叉查找树时，其时间复杂度才能达到 O(logn)，并且在极端情况下它甚至会退化成链表；
Reference: