RocksDB:线程私有化

• 在RocksDB的PointLockManager中有使用到，是系统层面的优化点

一、线程资源

• 这一小节是实现各种系统设计中通过线程私有化实现性能优化的基础
• 是由编译器和标准库提供的线程资源的支持，有线程特定数据（Thread Specific Data）和线程局部存储 (Thread Local Storage)两种

1.1 TLS

static int thread_local var_1 = 0;

• 通过thread_local标识符修饰的全局或静态变量是线程独立的，线程对该变量的操作对其它线程来说是不可见的

线程栈

• 在Linux中，并没有真正的线程，而是通过多个进程共享资源的方式实现的。但每个线程自己的线程栈是私有的，通过分配的方式将进程的某一块内存分配给线程使用
• 拿到分配的栈空间之后，先将最前面的一段空间初始化为pthread对象，然后就是__thread变量区。代码中所有的 __thread变量是与pthread关联存储的，通过相对于pthread变量地址的偏移实现对变量的寻址

1.2 TSD

• 通过pthread_key_create创建键值映射，每个线程通过键访问线程特定的数据

// 首先声明一个全局的Key
static pthread_key_t heap_key_;
// 并且通过接口完成初始化，定义一个序号值（seq）及一个用于释放数据的“析构函数” （destr）
int pthread_key_create (pthread_key_t *key, void (*destructor)(void *));
// 线程内通过接口设置某个key对应的值
int pthread_setspecific (pthread_key_t key, const void *value);
// 线程内通过接口获取某个key对应的值
void *pthread_getspecific (pthread_key_t key);

int pthread_key_delete (pthread_key_t key);

• 通过TSD可以在每个线程内访问自己私有的变量，同时这些变量在不同的线程中是具有相同的变量名的，即我们在全局声明的pthread_key_t变量

二、TCMalloc

• Golang在设计时借鉴了TCMalloc（线程缓存分配）的设计，实现高速的内存分配
• 它的核心理念是使用多级缓存将对象根据大小分类，并按照类别实施不同的分配策略

2.1 隐式链表分配

• 如果要对一整个Page的内存按照相同的单位进行分配，有非常的方法实现，比如可以使用bitmap的方式，如果对4KB的页按照16byte进行分配，只需要4KB / 16 / 8 = 32byte的bitmap
• 但是出于最大化内存利用率的目的，使用的是另一种经典的方式freelist。因为我们要分配的对象就是内存本身，在构成链表时可以将链表指针放到对象中进行存储，从而不需要额外的内存来存储管理信息了

2.2 内存对齐的规则

• 首先说明，TCMalloc的代码似乎存在多种宏定义可以改变内存的对齐规则，所有下面写的数据不一定是完全不变的
• 一共划分了四个档位：(256KB, +∞)按照8KB进行对齐；[128B, 256KB]按照$(1<<LgFloor(size))/8$来对齐，$LgFloor$其实就是取size二进制最高位1的位置；(16B, 128B)按照16B进行对其；(0, 16B)按照8B进行对其。
• 通过这样设定的对齐方式，对于分配内存小于等于256KB的情况，我们可以将所有的内存size划分穷举出来，被设计成数组方便我们可以直接访问到对应的规则下

2.3 整体框架

• TCMalloc的整体分配框架分成了Thread Cache, Central List, Page Heap三级
• 用户直接向每个线程私有的Thread Cache获取内存块，其基本结构是一个包含所有内存分配单位的数组，每个单元包含这个单位大小的空闲数据块链表，从这里分配内存可以避免多线程的竞争
• 如果线程私有的空闲块没有了，需要向全局的Central List申请，每个可能的单位分配大小都有一个Central List实例。每个实例内部是SpanList，存储着用于划分小内存块的span，每个span包含的page数量是不同的，但是同一个Central List下的span size肯定相同
• 如果还是没有足够的空间，需要向 Page Heap申请内存块了，内部是一个128长度的数组，用于表示size为1～128个page的span。用多种定长page来实现变长page的分配，初始时只有 128 page 的 span，如果要分配 1 个 page 的 span，就把这个 span 分裂成两个，1 + 127，把127再记录下来。对于 span 的回收，需要考虑span的合并问题，否则在分配回收多次之后，就只剩下很小的 span 了，也就是带来了外部碎片问题。

2.4 分配策略

• 每次分配时，从用户申请的对象的size开始，一路发生空间不够向上请求新空间，到最后真正向操作系统申请的内存size是由一些提前设定好的参数决定的
• 首先，用户申请的内存size会被进行对齐处理，这里是通过前面说的方法进行对齐的，但是我们还应该得出这是哪一个内存size下的，及得到Index，这是通过ClassIndex(size)实现的
• 然后，通过Index访问class_to_size_得到实际该给用户返回多大的内存
• 接着，通过Index访问num_objects_to_move_查每次给对应thread_cache分配多少个object，这里有预先多给一部分同样大小的内存块给线程的意思
• 最后，通过Index访问class_to_pages_查每次给不同central_freelist分包含多少个页的span
• 超过256KB的大内存的分配会绕过其他结构直接访问Page Heap，并且单独管理

2.5 线程私有

• 在TCMalloc的三层结构中，Thread Cache这一层为了避免多线程的竞争从而带来的性能影响，选择了使用线程私有的方式实现
• 代码中使用了TSD的方式，为每个线程在需要通过TCMalloc申请内存时，构建一个线程私有的Thread Cache，实现内存分配上的线程私有话，避免了线程之间的竞争
• 但是因为TSD方式对局部变量的访问需要通过pthread_getspecific()，速度比较慢，因此Thread Cache中还有__thread变量存储每个线程对象的副本
• 但是因为需要注册清理函数，所以必须要TSD的方式创建线程局部变量

三、ThreadLocalPtr

• RocksDB对线程私有存储的封装
• 实现线程私有的方法也非常简单，就是使用pthread_key_t，但是这样的实现方式较为原生，对于每一个需要私有化的变量都需要我们声明并创建。并且当我们不能事先知道需要多少私有变量个数时，会更加不方便
• 可以在全局就用一个pthread_key_t，这样所有线程都能知道它并通过它来访问自己的私有存储，然后在这个私有存储上做文章，让它支持维护多个变量就可以了

3.1 使用方法

// 1.首先定义线程退出时的回掉函数，用于释放存储的局部对象
void UnrefHandle(void *ptr) {
  //当线程退出的时候会回调UnrefHandle来释放该线程的私有存储，ptr指向该私有存储地址
  //所以这里需要定义这块私有存储该如何释放，比如最简单的:
  delete static_cast<Object>(ptr);
}

// 2.创建一个私有的存储变量，对应着pthread_key_create
ThreadLocalPtr *local_1 = new ThreadLocalPtr(&UnrefHandle);

// 3.设置本线程对应的该私有存储变量的值，对应pthread_setspecific
Object *ptr_1 = new Object();
void *old_ptr_1 = local_1->Swap(ptr_1);
// 或者使用reset，其实和swap是一样的，差别在是否返回原来位置上的值
local_1->Reset(ptr_1);

// 4.读取本线程对应的私有存储变量的值，对应pthread_getspecific
void *cur_ptr_1 = local_l->Get();

3.2 实现过程

• 首先所有真正被存放在ThreadLocalPtr中的都是指针，而不是数据本身，并且都是被转换成void*类型被包装在Entry对象中的，不用的线程只要能够获取到不同的指针就能访问到私有的内存了

• 然后是ThreadData包含std::vector<Entry>，这里其实存放了用户的多个私有内存的指针，因此只要我们能够实现每个线程都单独具有一个ThreadData对象，然后将每个线程需要私有化的内容放到ThreadData的数组中就可以了

• 接着是最重要的StaticMeta，其在整个程序中只存在一份，是单例模式。其内部包含了static thread_local ThreadData* tls_;和pthread_key_t pthread_key_;两个变量，都是存储的ThreadData指针，其中TLS方式是为了加速访问存储的副本

• 最后ThreadLocalPtr对象只存储了一个ID值，这是用于访问在ThreadData中保存的私有变量时，用于索引std::vector<Entry>的，其实就是通过下标的方式标明是哪一个变量。因为数组的长度不能无限的增长，因此ID其实是会进行回收使用的

• 关于对象的释放操作，目前存在两个维度的对象释放：

  1. 当某个线程结束之后，其下管理的所有私有对象都应该被释放。这是由注册线程私有ThreadData时，通过pthread_key_create传入的回掉函数OnThreadExit完成。线程退出时自动调用回掉函数，会遍历ThreadData中的数组，并对每一个变量调用它的释放函数
  2. 当我们主动删除某一个线程私有变量时（也就是删除某个ThreadLocalPtr对象），我们需要将所有线程下的该私有对象都进行释放处理。这里是通过ThreadData自己构成的双向链表，找出所有线程下的变量进行释放

四、线程私有优化案例

4.1 PointLockManager优化

• 在RocksDB的点锁实现PointLockManager中，不同ColumnFamily拥有不同的LockMap，而所有的LockMap是被集中存储在一个LockMaps下的

• 因此当我们需要对某个ColumnFamily下的Key加锁时，需要先将整个PointLockManager锁起来，然后从LockMaps中取出对应ColumnFamily的LockMap，然后再执行后续的操作

• 这里为了获得ColumnFamily对应的LockMap需要对整个PointLockManager对象进行加锁显然会造成较大的竞争。因此这里采用了线程优化的方式，在每个线程中都准备了一个LockMaps，并且把当前线程需要用到的ColumnFamily的LockMap放入其中

• 在线程私有化LockMaps之后，进行加锁时只需要访问线程本地的LockMaps，并查询ColumnFamily对应的LockMap，不需要加整个PointLockManager对象中的大锁

• 当然也有可能出现当前线程本地的LockMaps中不存在某个ColumnFamily的LockMap的问题，这个时候就需要加大锁从全局的LockMaps中查询结果，并添加到本地的LockMaps中