SSTable基本原理

发表于2018-01-31由daniel

LSM Tree/MemTable/SSTable基本原理

时光飞逝，截至今天，2018的进度条已经毫不留情的燃烧掉了8.5%。

2017接触了很多新事物，也实践和落地了一些有意思的技术、产品和框架。要想走得快，一个人走，要想走得远，得学会多回头看，多总结。这也是接下来一系列文章的初衷。当然，前提是自己能够坚持写下去，?

是为记。

背景

2017年，做调用链服务的时候，为了存储整个系统的调用事件数据，遇到了一个存储上的问题：数据每天的写入量大概在10亿级别，也就是1.1w rps(record per second), 加上高峰期流量波动和系统冗余，我们把及格线定为3w rps。这是一个典型的写多读少的场景，自然直接放弃了关系型数据库；同时考虑到写入的时序特性，选型基本锁定到基于LSM Tree为存储引擎的数据库上。挑战依然在，但是基于LSM Tree的数据库一大把（HBase, Cassandra, RockDB, LevelDB, SQLite…），解决问题无非是时间问题。

我们先尝试了ssdb，号称可以替代redis, 一些指标上快过redis. 结果被坑得体无完肤：

key不支持过期（2017.04）；
写入性能压测只有2w qps，如果数据记录增大，性能迅速下降；
翻了下代码实现，虽然很失望，但是感觉因此避开了一个定时炸弹而庆幸?

在同事推荐下，我们尝试了Cassandra. 虽然国内用得不多，但是在《微服务架构》中，看到了奈飞（Netflix）的大规模使用案例，信心还是有的。实际压测结果：单节点写入性能在8w qps，超出预期。此外，系统上线后，同事花了大量时间调优参数，目前线上的单节点性能应该远超8w qps.

基本概念

LSM Tree (Log-structured merge-tree) ：这个名称挺容易让人困惑的，因为你看任何一个介绍LSM Tree的文章很难直接将之与树对应起来。事实上，它只是一种分层的组织数据的结构，具体到实际实现上，就是一些按照逻辑分层的有序文件。

MemTable: LSM Tree的树节点可以分为两种，保存在内存中的称之为MemTable, 保存在磁盘上的称之为SSTable. 严格讲，MemTable与SSTable还有很多细节区别，这里不展开讨论。

基本原理

写操作直接作用于MemTable, 因此写入性能接近写内存。
每层SSTable文件到达一定条件后，进行合并操作，然后放置到更高层。合并操作在实现上一般是策略驱动、可插件化的。比如Cassandra的合并策略可以选择SizeTieredCompactionStrategy或LeveledCompactionStrategy.

Level 0可以认为是MemTable的文件映射内存, 因此每个Level 0的SSTable之间的key range可能会有重叠。其他Level的SSTable key range不存在重叠。
Level 0的写入是简单的创建-->顺序写流程，因此理论上，写磁盘的速度可以接近磁盘的理论速度。

SSTable合并类似于简单的归并排序：根据key值确定要merge的文件，然后进行合并。因此，合并一个文件到更高层，可能会需要写多个文件。存在一定程度的写放大。是非常昂贵的I/O操作行为。Cassandra除了提供策略进行合并文件的选择，还提供了合并时I/O的限制，以期减少合并操作对上层业务的影响。

读操作优先判断key是否在MemTable, 如果不在的话，则把覆盖该key range的所有SSTable都查找一遍。简单，但是低效。因此，在工程实现上，一般会为SSTable加入索引。可以是一个key-offset索引（类似于kafka的index文件），也可以是布隆过滤器（Bloom Filter）。布隆过滤器有一个特性：如果bloom说一个key不存在，就一定不存在，而当bloom说一个key存在于这个文件，可能是不存在的。实现层面上，布隆过滤器就是key--比特位的映射。理想情况下，当然是一个key对应一个比特实现全映射，但是太消耗内存。因此，一般通过控制假阳性概率来节约内存，代价是牺牲了一定的读性能。对于我们的应用场景，我们将该概率从0.99降低到0.8，布隆过滤器的内存消耗从2GB+下降到了300MB，数据读取速度有所降低，但在感知层面可忽略。

Q&A

基于LSM Tree存储引擎的数据适用于哪些场景？
(key or key-range), 且key/key-range整体大致有序。
LSM Tree自从Google BigTable问世后，如此牛x, 为什么没有替代B Tree呀？

LSM Tree本质上也是一种二分查找的思想，只是这种二分局限在key的大致有序这个假设上，并充分利用了磁盘顺序写的性能，但是普适性一般。B Tree对于写多读少的场景，大部分代价开销在Tree的维护上，但是具有更强的普适性。
看起来，你们已经将Cassandra玩得很溜了，你们线上用了多大集群支持当前业务？

其实……还可以吧，主要是队友给力。还有就是国外有独角兽奈飞领头，遇到问题其实还是容易解决的。我们目前线上用了3*(4 core, 16G), 系统冗余还很大。最近奈飞出了一篇关于Cassandra优化的深度博文，如果有对Cassandra有兴趣，可以阅读Scaling Time Series Data Storage.

扩展阅读

Yet Another GeoIP Alfred Workflow

发表于2017-03-24由daniel

Yet Another GeoIP Alfred Workflow

在浏览网站以及在选线路的时候，经常会习惯性的查看一下对方的IP及地理位置信息. 师兄的 ip.cn 以及 ipip.net 都是不错的选择。但无奈自己是小帽子 Alfred 控，本着少做体力活的原则，写了一个 Workflow.

ip me 查看本地的外网ip及位置信息

ip domain 查看域名ip及位置信息

ip url 查看url中域名ip及位置信息

如果觉得你也有这样需求，可以在这里下载，enjoy!

References

http://www.deanishe.net/alfred-workflow

使用Golang reflect 对 gin handler 进行简单封装

发表于2017-03-23由daniel

使用Golang reflect 对 gin handler 进行简单封装

项目中大量使用 gin 作为service API的 http framework. 大部分时候我们的代码结构类似这样：

func main() {

    engine := gin.New()
    engine.GET("/hi", hiHandler)
    engine.Run(":8083")
}

func hiHandler(c *gin.Context) { 
    rsp, err := businessLogicProcess()
    if err != nil {
        c.AbortWithStatus(http.StatusBadRequest)
    } else {
        c.JSON(http.StatusOK, rsp)
    }
 }

func businessLogicProcess() {
    ...
}

func main() {

engine := gin.New()

engine.GET("/hi", hiHandler)

engine.Run(":8083")

}

func hiHandler(c *gin.Context) {

rsp, err := businessLogicProcess()

if err != nil {

c.AbortWithStatus(http.StatusBadRequest)

} else {

c.JSON(http.StatusOK, rsp)

}

func businessLogicProcess() {

...

}

数据流：hiHandler -> businessLogicProcess -> hiHandler. 这本身没有什么严重的问题，但是当你注册的API越来越多的时候，你的项目中会出现大量重复且类似hiHandler 结构的胶水层handler: hiHandler只做了一个 http request 数据与 businessLogicProcess 的粘合，再将返回数据塞回 http response.

从数据流来看，这个胶水层是无法避免的。大量重复的 hiHandler 并不符合 write reusable code 原则。因此，我们可以尝试对该层统一抽象进行封装：

func main() {

    engine := gin.New()
    engine.GET("/time", WrapHandler(GetTime))
    engine.Run(":8083")
}


type GetTimeReq struct {
    Nation string `form:"nation" binding:"required" json:"nation"`
}

func GetTime(req *GetTimeReq) (*OKRsp, *ErrRsp) {
    ...
}


// WrapHandler wrap gin handler, the handler signature should be
// func(req *ReqStruct) (*OKRspStruct, *ErrorRspStruct) or
// func(c *gin.Context, req *ReqStruct) (*OKRspStruct, *ErrorRspStruct)
func WrapHandler(f interface{}) gin.HandlerFunc {
    t := reflect.TypeOf(f)
    if t.Kind() != reflect.Func {
        panic("handdler should be function type")
    }

    fnumIn := t.NumIn()
    if fnumIn == 0 || fnumIn &gt; 2 {
        panic("handler function require 1 or 2 input parameters")
    }

    if fnumIn == 2 {
        tc := reflect.TypeOf(&amp;gin.Context{})
        if t.In(0) != tc {
            panic("handler function first paramter should by type of *gin.Context if you have 2 input parameters")
        }
    }

    if t.NumOut() != 2 {
        panic("handler function return values should contain response data &amp; error")
    }

    // errorInterface := reflect.TypeOf((*error)(nil)).Elem()
    // if !t.Out(1).Implements(errorInterface) {
    //  panic("handler function second return value should by type of error")

    // }

    return func(c *gin.Context) {
        var req interface{}
        if fnumIn == 1 {
            req = newReqInstance(t.In(0))
        } else {
            req = newReqInstance(t.In(1))
        }

        if !c.Bind(req) {
            err := c.LastError()
            log.Warning("bind parameter error:%v", err)
            GinErrRsp(c, ErrCodeParamInvalid, err.Error())
            return
        }

        var inValues []reflect.Value
        if fnumIn == 1 {
            inValues = []reflect.Value{reflect.ValueOf(req)}
        } else {
            inValues = []reflect.Value{reflect.ValueOf(c), reflect.ValueOf(req)}
        }

        ret := reflect.ValueOf(f).Call(inValues)
        if ret[1].IsNil() {
            GinRsp(c, http.StatusOK, ret[0].Interface())
        } else {
            GinRsp(c, http.StatusOK, ret[1].Interface())
        }
    }
}

func newReqInstance(t reflect.Type) interface{} {
    switch t.Kind() {
    case reflect.Ptr, reflect.Interface:
        return newReqInstance(t.Elem())
    default:
        return reflect.New(t).Interface()
    }
}

func main() {

engine := gin.New()

engine.GET("/time", WrapHandler(GetTime))

engine.Run(":8083")

}

type GetTimeReq struct {

Nation string `form:"nation" binding:"required" json:"nation"`

}

func GetTime(req *GetTimeReq) (*OKRsp, *ErrRsp) {

...

}

// WrapHandler wrap gin handler, the handler signature should be

// func(req *ReqStruct) (*OKRspStruct, *ErrorRspStruct) or

// func(c *gin.Context, req *ReqStruct) (*OKRspStruct, *ErrorRspStruct)

func WrapHandler(f interface{}) gin.HandlerFunc {

t := reflect.TypeOf(f)

if t.Kind() != reflect.Func {

panic("handdler should be function type")

}

fnumIn := t.NumIn()

if fnumIn == 0 || fnumIn > 2 {

panic("handler function require 1 or 2 input parameters")

}

if fnumIn == 2 {

tc := reflect.TypeOf(&gin.Context{})

if t.In(0) != tc {

panic("handler function first paramter should by type of *gin.Context if you have 2 input parameters")

}

if t.NumOut() != 2 {

panic("handler function return values should contain response data & error")

}

// errorInterface := reflect.TypeOf((*error)(nil)).Elem()

// if !t.Out(1).Implements(errorInterface) {

// panic("handler function second return value should by type of error")

// }

return func(c *gin.Context) {

var req interface{}

if fnumIn == 1 {

req = newReqInstance(t.In(0))

} else {

req = newReqInstance(t.In(1))

}

if !c.Bind(req) {

err := c.LastError()

log.Warning("bind parameter error:%v", err)

GinErrRsp(c, ErrCodeParamInvalid, err.Error())

return

}

var inValues []reflect.Value

if fnumIn == 1 {

inValues = []reflect.Value{reflect.ValueOf(req)}

} else {

inValues = []reflect.Value{reflect.ValueOf(c), reflect.ValueOf(req)}

}

ret := reflect.ValueOf(f).Call(inValues)

if ret[1].IsNil() {

GinRsp(c, http.StatusOK, ret[0].Interface())

} else {

GinRsp(c, http.StatusOK, ret[1].Interface())

}

func newReqInstance(t reflect.Type) interface{} {

switch t.Kind() {

case reflect.Ptr, reflect.Interface:

return newReqInstance(t.Elem())

default:

return reflect.New(t).Interface()

}

这样做还有一个额外的好处：实现了业务处理函数 (GetTime) 与gin的解耦，使得业务处理函数复用性更强。

行思錄 | Travel Coder

Arch, Coding, Life

LSM Tree/MemTable/SSTable基本原理

LSM Tree/MemTable/SSTable基本原理

背景

基本概念

基本原理

Q&A

扩展阅读

Yet Another GeoIP Alfred Workflow

Yet Another GeoIP Alfred Workflow

ip me 查看本地的外网ip及位置信息

ip domain 查看域名ip及位置信息

ip url 查看url中域名ip及位置信息

References

使用Golang reflect 对 gin handler 进行简单封装

使用Golang reflect 对 gin handler 进行简单封装