Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

Soupen源码解析之string实现

写在最前

Soupen是一款高性能的nosql数据库,旨在能在某些方面替代Redis。它由不著名码农、秦汉史历史学家、本站站长Yebangyu同学在业余时间独立开发完成。

Github请访问这里 ,Python客户端请点击这里

在Soupen中有两种字符串(或者更准确的说,字节流)实现: SoupenString和SoupenNormalString。代码都在src/ds/soupen_string.hsrc/ds/soupen_string.cpp文件里。两种实现都设计为大小写不敏感。

SoupenNormalString

\0结尾的字符串实现,也就是说SoupenNormalString中的字符串都是以 \0结尾的。因此,对其施加任何类似于strcmp等传统C字符串函数都是安全的。

在实现时,针对短字符串,为了进一步优化效率,使用了柔性数组技术来提高cache命中。

1
2
3
4
5
6
7
8
9
class SoupenNormalString
{
//......
private:
  static const int64_t CHAR_LEN_THRESHOLD = 48;
  int64_t len_;
  char *data_;
  char buffer_data_[0];
};

如果字符串长度小于48(48是怎么得来的?Soupen使用jemalloc来分配内存,以64字节为一个块单位来分配内存。64位系统里,len_data_各占用8个字节,cache line的大小一般为64字节,因此64 - 8 - 8 = 48。再次提醒,这里需要存储\0),则会使用embedded string,也就是说,此时字符串的内容会和len_data_分配在一块连续的内存中。由于局部性原理,在读取时,它们都会读到cache中,减少了cache miss,大大提高了性能。

不管字符串长度如何,不管是否使用柔性数组技术来提高cache 命中,data_都会被设置为指向字符串的首地址。因此,外部总可以通过data_访问到字符串,

SoupenString

在SoupenString中的字符串存储,都不以\0结尾。因此,不能对其施加strlen等传统C字符串函数。

SoupenString中特别考虑了append函数的实现。为了减少内存分配,每次在append时,都会首先判断当前缓冲区是否够用,如果够用直接append;否则,这时候需要重新分配内存。注意,这时候我们会多分配一倍的内存,以防止下次append时不必要的内存分配动作。当然,这可能会造成内存浪费,但是对于优化时间消耗具有重要意义。