使用ANTLR4编写parser

前言 ANTLR 是一款由 Java 编写的开源语法解析工具。 我们知道在编译的过程中,主要有词法分析(Lexical Analysis), 语法分析(Grammar Analysis), 语义分析(Semantic Analysis), 中间代码生成(Intermediate Code Generation)等过程。 但是这是对于高级语言的编译过程,有时候我们需要设计一些 DSL 或者配置文件格式,这时候只需要词法分析和语法分析就可以解决我们的需求。 ANTLR 可以通过 BNF 或者 EBNF 文法的语法定义文件生成默认的 Lexer 和基本的 ast,并且提供了 listener, visitor 两种可选的方式来遍历 ast。对比起 yacc 和 lex 的组合,它的好处在于能生成相对友好的代码方便你进行处理(不用在几千行的 .y 文件里面爬摸滚打了)。 ANTLR 的最新版本是 4,在这篇文章里我将使用 Go 作为生成的 target 语言。 ANTLR4 的安装 自己看 简单的 EBNF 文法 EBNF, 即扩展巴恩斯范式,是一种上下文无关文法。现代编程语言基本都使用 EBNF 来进行语法定义。 我们首先来简单定义一个四则运算表达式的语法规则: grammar Math; math : expr EOF; expr : op=('+'|'-') expr # unaryExpr | left=expr op=('*'|'/') right=expr # infixExpr | left=expr op=('+'|'-') right=expr # infixExpr | value=NUM # numberExpr ; ADD: '+'; SUB: '-'; MUL: '*'; DIV: '/'; NUM : [0-9]+ ('.
Read full post

LevelDB源码剖析

前言 LevelDB是谷歌开源的一款高性能嵌入式 kv 数据库,基于LSM-tree索引,是Bigtable的简化版实现(可以这么理解)。 它的特点是写入速度非常快,达到了O(1)级别的时间复杂度。但是付出的代价就是读取的速度非常慢,尤其是对于数据库中不存在的 key 进行get操作会扫描所有的记录。 对于 LevelDB 的具体设计本文就不再提及,这里主要从代码的层面分析一下 LevelDB 的结构(膜拜一下 Jeff Dean 亲手写的 C++)。 LevelDB 的入口 db.h db.h中定义了LevelDB对外开放的接口——DB类。 DB类的代码如下: class LEVELDB_EXPORT DB { public: static Status Open(const Options& options, const std::string& name, DB** dbptr); DB() = default; DB(const DB&) = delete; DB& operator=(const DB&) = delete; virtual ~DB(); virtual Status Put(const WriteOptions& options, const Slice& key, const Slice& value) = 0; virtual Status Delete(const WriteOptions& options, const Slice& key) = 0; virtual Status Write(const WriteOptions& options, WriteBatch* updates) = 0; virtual Status Get(const ReadOptions& options, const Slice& key, std::string* value) = 0; virtual Iterator* NewIterator(const ReadOptions& options) = 0; virtual const Snapshot* GetSnapshot() = 0; virtual void ReleaseSnapshot(const Snapshot* snapshot) = 0; virtual bool GetProperty(const Slice& property, std::string* value) = 0; virtual void GetApproximateSizes(const Range* range, int n, uint64_t* sizes) = 0; virtual void CompactRange(const Slice* begin, const Slice* end) = 0; }; 在这个类里面定义了Put, Delete, Get, Write这几个CURD的基本操作,以及LevelDB支持的feature,获取快照等。
Read full post

Redis的LRU缓存

Redis作为一个内存键值对存储的产品,以其高性能、多种数据类型、可选持久化且支持网络等特性成为了许多项目中的宠儿。 一般来说,缓存在获得超快的读写速度的同时,作为代替会牺牲其存储空间。Redis使用内存作为存储介质,比起传统的使用硬盘作为载体的数据库,读写速度快了许多,但是可存储的数据量也受到了内存大小的限制。在频繁的读写操作下,必然会发生对于旧数据的驱逐(eviction),可能是删除数据,或者是置换到外存中。 Redis使用LRU作为唯一的驱逐算法(Redis4.0推出了LFU, Least Frequently Used算法,在本文的后面会提到)。本文将主要围绕Redis的最大内存限制和驱逐算法谈谈Redis作为缓存的一些细节。 Redis最大内存限制的配置 进行了Redis的最大内存配置后,Redis将按照配置使用一个确定大小的内存进行存储。 Redis最大内存有两种配置的方式,一种是在Redis运行时使用Redis的指令CONFIG SET maxmemory 100mb,可以将最大内存配置为100mb。另一种方式就是在redis.conf文件中进行配置maxmemory 100mb,也可以将最大内存配置为100mb。 将maxmemory参数置为0的时候,表示没有内存限制。在64位系统下,这是默认的配置,但是在32位系统下,最大内存限制将被设为3GB。 当Redis使用的内存达到最大内存限制的大小时,将会触发Redis的驱逐策略(eviction policies)。此时Redis可能会采取不同的行动,比如给造成内存超出限制的操作返回一个error,或者驱逐旧数据保证内存不超出限制。 Redis的驱逐策略 当Redis的内存使用达到上限时,会触发通过maxmemory-policy配置设置的驱逐策略。 具体的驱逐策略如下: noeviction: 如果发生了会使内存使用超出限制的操作(大部分是写操作),则返回一个error。 allkeys-lru: 尝试将符合LRU条件的key驱逐用来为新数据腾出空间。 volatile-lru: 和allkeys-lru相似,不过只会驱逐设置了expire set(即有持续时间)的key。 allkeys-random: 在所有的key中随机驱逐(比较迷)。 volatile-random: 在设置了expire set的key中随机驱逐。 volatile-ttl: 在设置了expire set的key中挑选**TTL(time to live)**最小的删除以腾出空间。 其中涉及到volatile的几个选项在没有设置expire set的key的情况下会像noeviction一样返回error。 驱逐策略可以在运行时动态配置,并且可以使用INFO实时监控缓存的命中情况。 以下是选择驱逐策略的几个推荐原则: 在有热点数据,或者不确定该选择哪种方式的时候,选择allkeys-lru。大部分情况下它的表现是最好的。 在数据被环形扫描访问,或者缓存中的数据访问几率呈均匀分布的时候,可以使用allkeys-random。 如果能提供一套对于不同TTL的数据的权衡方案,可以选用volatile-ttl。 另外值得一提的是,设置expire也会消耗内存,因此在内存压力较大,且数据并非硬性需要expire的情况下,使用allkeys-lru并且摒弃expire是一种比较好的做法。 Redis驱逐的过程 在这里非常有必要介绍一下Redis驱逐的大致流程: 客户端使用了Redis的指令并且造成了内存使用的增加 Redis检查内存使用是否超出限制,如果是则按照驱逐策略进行操作 客户端执行新的指令,如此循环 整个流程简单来讲就是使用过量后,再通过驱逐key来使内存的用量降至限制之下。但是这样一来某个操作如果一次性增加了大量的内存使用量(比如插入一个超大的数据),Redis的内存用量就有可能明显超出内存限制。 粗略LRU算法(Approximated LRU algorithm) 实际上Redis的LRU算法并非完全实现原版LRU算法,而是做了一些魔改。这就意味着Redis无法总是选出LRU算法的最佳的驱逐对象,即LRU中定义的最近最少访问的数据。作为代替,他会在一些基本符合要求的数据中选取最后一次访问时间最早的那个key进行驱逐。
Read full post