valgrind跑一个rocksdb应用出现错误，以及背后的write hint

02 Jun 2019 | |

valgrind 3.10 日志是这样的

valgrind: m_syswrap/syswrap-linux.c:5255 (vgSysWrap_linux_sys_fcntl_before): Assertion 'Unimplemented functionality' failed.
valgrind: valgrind

host stacktrace:
==26531==    at 0x3805DC16: ??? (in /usr/lib64/valgrind/memcheck-amd64-linux)
==26531==    by 0x3805DD24: ??? (in /usr/lib64/valgrind/memcheck-amd64-linux)
==26531==    by 0x3805DEA6: ??? (in /usr/lib64/valgrind/memcheck-amd64-linux)
==26531==    by 0x380D53A0: ??? (in /usr/lib64/valgrind/memcheck-amd64-linux)
==26531==    by 0x380B0834: ??? (in /usr/lib64/valgrind/memcheck-amd64-linux)
==26531==    by 0x380AD242: ??? (in /usr/lib64/valgrind/memcheck-amd64-linux)
==26531==    by 0x380AE6F6: ??? (in /usr/lib64/valgrind/memcheck-amd64-linux)
==26531==    by 0x380BDD7C: ??? (in /usr/lib64/valgrind/memcheck-amd64-linux)

sched status:
  running_tid=1

Thread 1: status = VgTs_Runnable
==26531==    at 0x60903A4: fcntl (in /usr/lib64/libpthread-2.17.so)
==26531==    by 0x53571F6: rocksdb::PosixWritableFile::SetWriteLifeTimeHint(rocksdb::Env::WriteLifeTimeHint) (io_posix.cc:897)
...

找到rocksdb代码，接口是这样的

env/io_posix.cc

void PosixWritableFile::SetWriteLifeTimeHint(Env::WriteLifeTimeHint hint) {
#ifdef OS_LINUX
// Suppress Valgrind "Unimplemented functionality" error.
#ifndef ROCKSDB_VALGRIND_RUN
  if (hint == write_hint_) {
    return;
  }
  if (fcntl(fd_, F_SET_RW_HINT, &hint) == 0) {
    write_hint_ = hint;
  }
#else
  (void)hint;
#endif // ROCKSDB_VALGRIND_RUN
#else
  (void)hint;
#endif // OS_LINUX
}

…结果显然了，不支持fcntl F_SET_RW_HINT选项。

注意：

  • 如果需要跑valgrind，编译的rocksdb需要定义ROCKSDB_VALGRIND_RUN
  • 如果有必要，最好也定义PORTABLE，默认是march=native可能会遇到指令集不支持

特意搜了一下，这个参数是这样定义的

env/io_posix.cc

#if defined(OS_LINUX) && !defined(F_SET_RW_HINT)
#define F_LINUX_SPECIFIC_BASE 1024
#define F_SET_RW_HINT (F_LINUX_SPECIFIC_BASE + 12)
#endif

在linux中是这样的

https://github.com/torvalds/linux/blob/dd5001e21a991b731d659857cd07acc7a13e6789/include/uapi/linux/fcntl.h#L53

/*
 * Set/Get write life time hints. {GET,SET}_RW_HINT operate on the
 * underlying inode, while {GET,SET}_FILE_RW_HINT operate only on
 * the specific file.
 */
#define F_GET_RW_HINT		(F_LINUX_SPECIFIC_BASE + 11)
#define F_SET_RW_HINT		(F_LINUX_SPECIFIC_BASE + 12)
#define F_GET_FILE_RW_HINT	(F_LINUX_SPECIFIC_BASE + 13)
#define F_SET_FILE_RW_HINT	(F_LINUX_SPECIFIC_BASE + 14)

另外这里也移植了一个https://github.com/riscv/riscv-gnu-toolchain/blob/master/linux-headers/include/linux/fcntl.h

write life time hints

搜到了这个实现的patch https://patchwork.kernel.org/patch/9794403/

和这个介绍，linux 4.13引入的https://www.phoronix.com/scan.php?page=news_item&px=Linux-4.13-Write-Hints

简单说，这是为NVMe加上的功能，暗示写入数据是ssd的话，调度就会把数据尽可能靠近，这样方便后续回收

patchset讨论里还特意说到了rocksdb。。。https://lwn.net/Articles/726477/

降低写放大十分可观

A new iteration of this patchset, previously known as write streams. As before, this patchset aims at enabling applications split up writes into separate streams, based on the perceived life time of the data written. This is useful for a variety of reasons:

  • For NVMe, this feature is ratified and released with the NVMe 1.3 spec. Devices implementing Directives can expose multiple streams. Separating data written into streams based on life time can drastically reduce the write amplification. This helps device endurance, and increases performance. Testing just performed internally at Facebook with these patches showed up to a 25% reduction in NAND writes in a RocksDB setup.

  • Software caching solutions can make more intelligent decisions on how and where to place data.

这背后又有一个NVMe特性，Stream ID，https://lwn.net/Articles/717755/

一个用法，见pg的patch以及讨论 https://www.postgresql.org/message-id/CA%2Bq6zcX_iz9ekV7MyO6xGH1LHHhiutmHY34n1VHNN3dLf_4C4Q%40mail.gmail.com

这里还没有更深入讨论。只是罗列了资料。下班了，就到这里

ref

contacts

Read More

lsm-tree延迟分析

15 May 2019 | |
  • L0满， 无法接收 write-buffer不能及时Flush，阻塞客户端
    • 高层压缩占用IO
    • L0 L1压缩慢
    • L0 空间少
  • Flush 太慢，客户端阻塞 -> rate limiter限速

rocksdb的解决方案就是rate limiter限速

slik思路

（1）优先flushing和lower levels的compaction，低level的compaction优先于高level的compaction，这样保证flushing能尽快的写入level 0，level 0尽快compaction level 1，（a）尽量避免因为memtable到达上限卡client I/O，（b）尽量避免因为level 0的sstable文件数到达上限卡client I/O。实际实现的时候会有一个线程池专门用于Flushing；另外一个线程池用于其他的Compaction

（2）Preempting Compactions：支持抢占式Compaction，也就是高优先级的compaction可以抢占低优先级的compaction，也就是说另外一个用于L0~LN之间的compaction的线程池，优先级高的low level compaction可以抢占high level的compaction，这样L0->L1在这个线程池，最高优先级的compaction就能够在必要的时候抢占执行，保证尽量不会出现level 0的sstable数量超过阈值

（3）在low load的时候，给Internal Operation（compaction）分配更多的bandwidth，相反，在high load的时候，给Client operation分配更多的带宽，这样可以保证Compaction在适当的时候也能得到更多的处理，减少read放大和空间放大，这个调度策略也是基于通常的client operation load是波动这事实来设计的，如下图，就是一个真实环境的workload变化规律：

ref

  1. https://blog.csdn.net/Z_Stand/article/details/109683804
  2. https://zhuanlan.zhihu.com/p/77543818
  3. 论文地址 https://www.usenix.org/system/files/atc19-balmau.pdf
Read More

MongoRocks优化与实践

11 May 2019 | |

腾讯云mongorocks做的工作，作者kdy是个大神。

mongorocsk编码原理不说了。只说他们做的改进点

分ColumnFamily存储

  • 多ColumnFamily
    • kv业务索引少
    • 每个索引单独CF/数据单独CF
  • 索引/表快速删除
    • dropColumnFamily 物理删除CF数据
    • 便于Oplog按sst文件删除
      • 计算出需要删除的oplog所在的sstfiles
      • RocksDB::DeleteFilesInRange
    • 方便按CF为粒度对Cache大小调参

针对KV业务的缓存优化

  • 开启RowCache，减小BlockCache
    • 对于KV业务,点查询优先于区间查询
  • 对于存数据的CF，开启optimize_filters_for_hits
    • 索引CF中存在，数据CF中一定存在
    • 数据CF无bloomFilter的必要性
    • 该参数减小CF的bloomFilter大小
ref
  1. https://mongoing.com/wp-content/uploads/2017/04/mongoRocks.pdf
Read More

工作环境中的proxy使用

09 May 2019 | |

why

工作环境，由于某种原因，不能直接使用pip vcpkg git npm go get pacman 等直接下载，需要设置代理

如果都是通过cmd调用的话，可以在cmd层设置代理

直接

Set https_proxy=https://username:password@proxy.xxx.com:8080/

具体的账户密码网址，按照公司给的使用就行，go get/vcpkg按照上面的设置也有效

针对npm

npm config set proxy https_proxy=https://username:password@proxy.xxx.com:8080/

针对git 修改.gitconfig文件，在C:\Users\xxxusername 下，也可以自己新增一个

[http]
	sslVerify = false
	proxy =  https://username:password@proxy.xxx.com:8080/
[https]
	proxy = https://username:password@proxy.xxx.com:8080/

如果还不行，对于pip和pacman更有可能是源的问题，可以考虑换成公司内部源，配置文件位置

msys64\etc\pacman.d
C:\Users\username\pip\pip.ini

easy_install和pip类似，linux在home下，.pydistutils.cfg

注意密码转义

空格    -    %20
"          -    %22
#         -    %23
%        -    %25
&         -    %26
(          -    %28
)          -    %29
+         -    %2B
,          -    %2C
/          -    %2F
:          -    %3A
;          -    %3B
<         -    %3C
=         -    %3D
>         -    %3E
?         -    %3F
@       -    %40
\          -    %5C
|          -    %7C 

ref

contact

Read More

使用gsl::not_null封装raw pointer

06 May 2019 | |

why

这篇文章是参考链接的总结，主要是讲替代原生指针，使用not_null封装

如果是原生指针，就会有很多if

if (pMyData)
    pMyData->Process();

or:

auto result = pObj ? pObj->Compute() : InvalidVal;

or

void Foo(Object* pObj)
{
    if (!pObj)
        return;

    // Do stuff...
}

多余的if判断,使代码复杂等等等等

一个使用not_null的例子

// { autofold
// not_null playground
// bfilipek.com


#include <iostream>
#include <string_view>
#include <string>
#include <memory>
// }

#include "gsl/gsl"

// { autofold
class App
{
public:
	App(const std::string& str) : m_name(str) { }

	void Run() { std::cout << "Running " << m_name << "\n"; }
	void Shutdown() { std::cout << "App " << m_name << " is closing...\n"; }
	void Diagnose() { std::cout << "Diagnosing...\n"; }

private:
	std::string m_name;
};
// }


void RunApp(gsl::not_null<App *> pApp)
{
	pApp->Run();
	pApp->Shutdown();
}

void DiagnoseApp(gsl::not_null<App *> pApp)
{
	pApp->Diagnose();
}

int main()
{
    // first case: deleting and marking as null:
	{
		gsl::not_null<App *> myApp = new App("Poker");

		// we can delete it, but cannot assign null
		delete myApp;
		//myApp = nullptr;
	}

    // second case: breaking the contract
	{
		// cannot invoke such function, contract violation
		//RunApp(nullptr);
	}

    // assigning a null on initilization
	{
		//gsl::not_null<App *> myApp = nullptr;
	}
	
	std::cout << "Finished...\n";
}

接口语义保证不会null，更清晰，并且编译期就能确保不是null

另外，参考链接二提到，既然有not_null，就应该有optional_ptr, 保证默认null，这个实际上也是observer_ptr的加强版，observer_ptr是对原生ptr的封装，也是通过一个接口语义来清晰观测或者对应rust 的 borrow

拓展阅读

在not_null的实现里，get指针是这样的

    template <typename U, typename = std::enable_if_t<std::is_convertible<U, T>::value>>
    constexpr not_null(U&& u) : ptr_(std::forward<U>(u))
    {
        Expects(ptr_ != nullptr);
    }

    template <typename = std::enable_if_t<!std::is_same<std::nullptr_t, T>::value>>
    constexpr not_null(T u) : ptr_(std::move(u))
    {
        Expects(ptr_ != nullptr);
    }

    constexpr std::conditional_t<std::is_copy_constructible<T>::value, T, const T&> get() const
    {
        Ensures(ptr_ != nullptr);
        return ptr_;
    }

其中expects和ensures定义是这样的

#if defined(__clang__) || defined(__GNUC__)
#define GSL_LIKELY(x) __builtin_expect(!!(x), 1)
#define GSL_UNLIKELY(x) __builtin_expect(!!(x), 0)

#else

#define GSL_LIKELY(x) (!!(x))
#define GSL_UNLIKELY(x) (!!(x))
#endif // defined(__clang__) || defined(__GNUC__)

#define GSL_CONTRACT_CHECK(type, cond)                                                             \
    (GSL_LIKELY(cond) ? static_cast<void>(0) : gsl::details::terminate())

#define Expects(cond) GSL_CONTRACT_CHECK("Precondition", cond)
#define Ensures(cond) GSL_CONTRACT_CHECK("Postcondition", cond)

为啥get需要Ensures校验？本身都非空了，这样不是多此一举吗？

考虑只能指针的move，比如gsl::not_null<unique_ptr<T> >发生了move行为，那旧的not_null就是是空指针了

这里是为了留这么一手 至于运行时的消耗，就让编译期优化吧，编译器能判定出来分支走到static_cast<void>(0) 整个分支都没有任何作用，应该就会优化掉

ref

contact

Read More

Buffering SQL Writes with Redis

04 May 2019 | |

why

这篇文章Sentry公司的博客，介绍他们怎么用redis的(好像是一个运营监控服务软件公司)

Sentry公司大量使用pg，两个集群，一个集群存储事件元数据，另一个存储Sentry平台数据，都有冷备，只在灾备或者维护期间使用

数据流分成三类，时序数据

  • 事件blob数据，不变的，直接存储到Riak集群里
  • kv对，表示tag，通常是设备名，操作系统之类的
  • 属性 聚合操作用

大多数数据是SQL，事件Blob数据存在Riak来保持扩展性，实际上也是用来做KV存储

突发情况

Sentry的数据信息有特征，比如突然传来一个错误事件，这些事件重复程度高，出现频率也高，所以需要一个去重-聚合动作，又分两种情况

  • 相同错误出现多次
  • 大量不同错误生成新的聚合

可以从下面两个属性来观测到

  • 基数计数器 Cardinality counters，
  • Latest Value 看聚合操作中出现key用个字段记录

第一种设置个counter

UPDATE table SET counter = counter + 1 WHERE key = %s;

第二种就设置个字段记录

UPDATE table SET last_seen = %s WHERE key = %s;

count 引入的锁还有可能影响性能，所以把count拆开，拆成多行，避免行锁竞争

下面这个例子是一百行的

UPDATE table SET counter = counter + 1 WHERE key = %s AND partition = ABS(RANDOM() * 100);

pg提供强一致，浪费很多时间在锁上，所以用buffer来省掉这些竞争

buffer write，先聚合一堆写，定时刷回去，需要考虑最低损失数据，据此来决定回写周期，Sentry实践是10秒一次

这引入两种问题

  • UI不会自动更新，十秒需要触发一次更新
  • 可能丢失数据，比如网络问题

使用Redis

  • 每个entity 一个hash

  • flush 一组hash集合

当数据来

  • 对每个entity hashkey
    • hincrby counter
    • 更新其他字段，hset，比如last seen timestamp
  • zadd 把pending key加入集合中

然后类似cron任务，10秒一次，zrange拿到集合，对于pending hash key 加入到队列，然后zrem移除集合

worker从队列中拿到job，开始写

  • pipeline
    • zrem，保证没副作用
    • hgetall 拿到key
    • rem hashkey
  • 转换成sql，直接执行最后结果
    • set counter = counter +%d
    • set value = %s

限制条数，使用sorted set(zset)

可以水平扩展，加redis节点

这个模型保证一行sql就更新一次，降低锁竞争，达到预期

问题：为什么不用时序数据库？

博客还提到了几个提升的点子

  • 通常优先级高的事情发生的概率比较低，当前是模型是LIFO，也可改成FIFO 用zadd nx
  • 数据冲突踩踏，大量数据任务可能同时触发，虽然可能实际处理后和noop没区别，但还是有这种突发增加延迟的问题，当前是push模型，可以改成pull，控制主动权 限流器也行 实现上的复杂导致没能采用
  • 丢写，加个备份集合

ref

contact

其他联系方式在主页

Read More

unique_ptr实现pimpl惯用法

03 May 2019 | |

why

这篇文章是参考链接的总结

pimpl惯用法，pointer to implementation，就是用指针来拆分实现，这样改动不会导致所有文件都编译一遍，也是一种解耦

以前的实现

#include "Engine.h"
 
class Fridge
{
public:
   void coolDown();
private:
   Engine engine_;
};

这样改动Engine就会重编Fridge

引入指针分离

class Fridge
{
public:
   Fridge();
   ~Fridge();
 
   void coolDown();
private:
   class FridgeImpl;
   FridgeImpl* impl_;
};

FridgeImpl封装一层Engine，不可见

#include "Engine.h"
#include "Fridge.h"
 
class FridgeImpl
{
public:
   void coolDown()
   {
      /* ... */
   }
private:
   Engine engine_;
};
 
Fridge::Fridge() : impl_(new FridgeImpl) {}
 
Fridge::~Fridge(){
   delete impl_;
}
 
void Fridge::coolDown(){
   impl_->coolDown();
}

这样还是需要管理impl_生命周期，如果用unique_ptr就更好了

改进的代码

#include <memory>
 
class Fridge
{
public:
   Fridge();
   void coolDown();
private:
   class FridgeImpl;
   std::unique_ptr<FridgeImpl> impl_;
};

#include "Engine.h"
#include "Fridge.h"

class FridgeImpl
{
public:
   void coolDown()
   {
      /* ... */
   }
private:
   Engine engine_;
};

Fridge::Fridge() : impl_(new FridgeImpl) {}

这样会有新问题，编译不过

use of undefined type ‘FridgeImpl’ can’t delete an incomplete type

因为unique_ptr需要知道托管对象的析构，最起码要保证可见性

析构可见性

c++规则，以下两种情况，delete pointer会有未定义行为

  • void* 类型
  • 指针的类型不完整，比如这种前向声明类指针

由于unique_ptr检查，会在编译期直接拒绝 同理的还有boost::checked_delete

进一步讨论，Fridge 和FridgeImpl的析构函数都是没定义的，编译器会自动定义并内联，在Fridge的编译单元，就已经见到了Fridge的析构了，但是见不到FridgeImpl的析构，解决办法就是加上Fridge的析构声明，并把实现放到实现文件中，让Fridge和FridgeImpl的析构同时可见

#include <memory>
 
class Fridge
{
public:
   Fridge();
   +~Fridge();
...
};

#include "Engine.h"
#include "Fridge.h"
 
class FridgeImpl
....
Fridge::Fridge() : impl_(new FridgeImpl) {}
 
+Fridge::~Fridge() = default;

ref

contact

Read More

jemalloc 原理

01 May 2019 | |

先说下glibc自带的ptmalloc

多线程支持

  • Ptmalloc2有一个主分配区(main arena)， 有多个非主分配区。 非主分配区只能使用mmap向操作系统批发申请HEAP_MAX_SIZE（64位系统为64MB）大小的虚拟内存。 当某个线程调用malloc的时候，会先查看线程私有变量中是否已经存在一个分配区，如果存在则尝试加锁，如果加锁失败则遍历arena链表试图获取一个没加锁的arena， 如果依然获取不到则创建一个新的非主分配区。
  • free()的时候也要获取锁。分配小块内存容易产生碎片，ptmalloc在整理合并的时候也要对arena做加锁操作。在线程多的时候，锁的开销就会增大。

ptmalloc内存管理

  • 用户请求分配的内存在ptmalloc中使用chunk表示， 每个chunk至少需要8个字节额外的开销。 用户free掉的内存不会马上归还操作系统，ptmalloc会统一管理heap和mmap区域的空闲chunk，避免了频繁的系统调用。

  • ptmalloc 将相似大小的 chunk 用双向链表链接起来, 这样的一个链表被称为一个 bin。Ptmalloc 一共 维护了 128 个 bin,并使用一个数组来存储这些 bin(图就像二维数组，或者std::deque底层实现那种感觉，rocksdb arena实现也这样的)

    1558506408332

    • 数组中的第一个为 unsorted bin, 数组中从 2 开始编号的前 64 个 bin 称为 small bins, 同一个small bin中的chunk具有相同的大小。small bins后面的bin被称作large bins。
    • 当free一个chunk并放入bin的时候， ptmalloc 还会检查它前后的 chunk 是否也是空闲的, 如果是的话,ptmalloc会首先把它们合并为一个大的 chunk, 然后将合并后的 chunk 放到 unstored bin 中。 另外ptmalloc 为了提高分配的速度,会把一些小的(不大于64B) chunk先放到一个叫做 fast bins 的容器内。
    • 在fast bins和bins都不能满足需求后，ptmalloc会设法在一个叫做top chunk的空间分配内存。 对于非主分配区会预先通过mmap分配一大块内存作为top chunk， 当bins和fast bins都不能满足分配需要的时候, ptmalloc会设法在top chunk中分出一块内存给用户, 如果top chunk本身不够大, 分配程序会重新mmap分配一块内存chunk, 并将 top chunk 迁移到新的chunk上，并用单链表链接起来。如果free()的chunk恰好 与 top chunk 相邻,那么这两个 chunk 就会合并成新的 top chunk，如果top chunk大小大于某个阈值才还给操作系统。主分配区类似，不过通过sbrk()分配和调整top chunk的大小，只有heap顶部连续内存空闲超过阈值的时候才能回收内存。
    • 需要分配的 chunk 足够大,而且 fast bins 和 bins 都不能满足要求,甚至 top chunk 本身也不能满足分配需求时,ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空间。

ptmalloc的缺陷

  • 后分配的内存先释放,因为 ptmalloc 收缩内存是从 top chunk 开始,如果与 top chunk 相邻的 chunk 不能释放, top chunk 以下的 chunk 都无法释放。
  • 多线程锁开销大， 需要避免多线程频繁分配释放。
  • 内存从thread的arena中分配， 内存不能从一个arena移动到另一个arena， 就是说如果多线程使用内存不均衡，容易导致内存的浪费。 比如说线程1使用了300M内存，完成任务后glibc没有释放给操作系统，线程2开始创建了一个新的arena， 但是线程1的300M却不能用了。
  • 每个chunk至少8字节的开销很大
  • 不定期分配长生命周期的内存容易造成内存碎片，不利于回收。 64位系统最好分配32M以上内存，这是使用mmap的阈值。

这里的问题在于arena是全局的 jemalloc和tcmalloc都针对这个做优化

tcmalloc的数据结构看参考链接

主要的优化 size分类，TheadCache

小对象分配

  • tcmalloc为每个线程分配了一个线程本地ThreadCache，小内存从ThreadCache分配，此外还有个中央堆（CentralCache），ThreadCache不够用的时候，会从CentralCache中获取空间放到ThreadCache中。
  • 小对象（<=32K）从ThreadCache分配，大对象从CentralCache分配。大对象分配的空间都是4k页面对齐的，多个pages也能切割成多个小对象划分到ThreadCache中。
  • 小对象有将近170个不同的大小分类(class)，每个class有个该大小内存块的FreeList单链表，分配的时候先找到best fit的class，然后无锁的获取该链表首元素返回。如果链表中无空间了，则到CentralCache中划分几个页面并切割成该class的大小，放入链表中。

CentralCache分配管理

  • 大对象(>32K)先4k对齐后，从CentralCache中分配。 CentralCache维护的PageHeap如下图所示， 数组中第256个元素是所有大于255个页面都挂到该链表中。

  • 当best fit的页面链表中没有空闲空间时，则一直往更大的页面空间则，如果所有256个链表遍历后依然没有成功分配。 则使用sbrk, mmap, /dev/mem从系统中分配。
  • tcmalloc PageHeap管理的连续的页面被称为span. 如果span未分配， 则span是PageHeap中的一个链表元素 如果span已经分配，它可能是返回给应用程序的大对象， 或者已经被切割成多小对象，该小对象的size-class会被记录在span中
  • 在32位系统中，使用一个中央数组(central array)映射了页面和span对应关系， 数组索引号是页面号，数组元素是页面所在的span。 在64位系统中，使用一个3-level radix tree记录了该映射关系。

回收

  • 当一个object free的时候，会根据地址对齐计算所在的页面号，然后通过central array找到对应的span。
  • 如果是小对象，span会告诉我们他的size class，然后把该对象插入当前线程的ThreadCache中。如果此时ThreadCache超过一个预算的值（默认2MB），则会使用垃圾回收机制把未使用的object从ThreadCache移动到CentralCache的central free lists中。
  • 如果是大对象，span会告诉我们对象锁在的页面号范围。 假设这个范围是[p,q]， 先查找页面p-1和q+1所在的span，如果这些临近的span也是free的，则合并到[p,q]所在的span， 然后把这个span回收到PageHeap中。
  • CentralCache的central free lists类似ThreadCache的FreeList，不过它增加了一级结构，先根据size-class关联到spans的集合， 然后是对应span的object链表。如果span的链表中所有object已经free， 则span回收到PageHeap中。

jemalloc

  • 与tcmalloc类似，每个线程同样在<32KB的时候无锁使用线程本地cache。

  • Jemalloc在64bits系统上使用下面的size-class分类：

    categories Spacing Size
    Small 8 [8]
      16 [16, 32, 48, …, 128]
      32 [160, 192, 224, 256]
      64 [320, 384, 448, 512]
      128 [640, 768, 896, 1024]
      256 [1280, 1536, 1792, 2048]
      512 [2560, 3072, 3584]
    Large 4 KiB [4 KiB, 8 KiB, 12 KiB, …, 4072 KiB]
    Huge 4 KiB [4 MiB, 8 MiB, 12 MiB, …]

  • small/large对象查找metadata需要常量时间， huge对象通过全局红黑树在对数时间内查找。

  • 虚拟内存被逻辑上分割成chunks（默认是4MB，1024个4k页），应用线程通过round-robin算法在第一次malloc的时候分配arena， 每个arena都是相互独立的，维护自己的chunks， chunk切割pages到small/large对象。free()的内存总是返回到所属的arena中，而不管是哪个线程调用free()。

结构图

jemalloc 的内存分配，可分成四类：

  • small( size < min(arena中得bin) ):如果请求size不大于arena的最小的bin，那么就通过线程对应的tcache来进行分配。首先确定size的大小属于哪一个tbin，比如2字节的size就属于最小的8字节的tbin，然后查找tbin中有没有缓存的空间，如果有就进行分配，没有则为这个tbin对应的arena的bin分配一个run，然后把这个run里面的部分块的地址依次赋给tcache的对应的bin的avail数组，相当于缓存了一部分的8字节的块，最后从这个availl数组中选取一个地址进行分配
  • large( max(tcache中的块) > size > min(arean中的bin) ): 如果请求size大于arena的最小的bin，同时不大于tcache能缓存的最大块，也会通过线程对应的tcache来进行分配，但方式不同。首先看tcache对应的tbin里有没有缓存块，如果有就分配，没有就从chunk里直接找一块相应的page整数倍大小的空间进行分配（当这块空间后续释放时，这会进入相应的tcache对应的tbin里）
  • large( chunk > size > tcache ): 如果请求size大于tcache能缓存的最大块，同时不大于chunk大小（默认是4M），具体分配和第2类请求相同，区别只是没有使用tcache
  • huge(size> chunk ):如果请求大于chunk大小，直接通过mmap进行分配。

简而言之，就是：

小内存（small class）： 线程缓存bin -> 分配区bin(bin加锁) -> 问系统要 中型内存（large class）：分配区bin(bin加锁) -> 问系统要 大内存（huge class）： 直接mmap组织成N个chunk+全局huge红黑树维护(带缓存)

回收流程大体和分配流程类似，有tcache机制的会将回收的块进行缓存，没有tcache机制的直接回收（不大于chunk的将对应的page状态进行修改，回收对应的run；大于chunk的直接munmap）。需要关注的是jemalloc何时会将内存还给操作系统，因为ptmalloc中存在因为使用top_chunk机制（详见华庭的文章）而使得内存无法还给操作系统的问题。目前看来，除了大内存直接munmap，jemalloc还有两种机制可以释放内存：

  1. 当释放时发现某个chunk的所有内存都已经为脏（即分配后又回收）就把整个chunk释放
  2. 当arena中的page分配情况满足一个阈值时对dirty page进行purge（通过调用madvise来进行）。这个阈值的具体含义是该arena中的dirty page大小已经达到一个chunk的大小且占到了active page的1/opt_lg_dirty_mult（默认为1/32）。active page的意思是已经正在使用中的run的page，而dirty page就是其中已经分配后又回收的page。

Ref

这里把搜集的一些资料列举一下，后续做整理

contact

Read More
wanghenshui
王很水
majar buzz kill
^