Terark-CTO-雷鹏-CSDN博客

原创 Mongo on TerarkDB 性能评测

Mongo on TerarkDB 性能评测之前，我们发表过一篇集成 TerichDB 的 MongoDB 性能测试，TerichDB 是 Terark 公司的第一个数据库产品，整个 DB 全部自主研发，因为使用 Terark 自己的引擎，所以功能非常丰富，性能也非常出色，但是与主流数据库不兼容。现在，我们最新的 TerarkDB 完全兼容 RocksDB，我们通过实现 RocksDB 的 SST

2017-03-08 16:54:15 3475 1

原创理想的 huge page

现代计算机的内存越来越大，服务器动辄就有上百GB，甚至 TB 级别的内存，很多应用已经可以把全部数据都放入内存，这样，磁盘空间换取内存空间这个传统中虚拟内存最重要的需求已经相当弱化甚至不复存在。当然我们仍然需要虚拟内存的其它好处（进程隔离、内存保护等），但是，虚拟内存最大的缺点：地址转换开销，在很多应用中越来越突出。于是，大家想起了 huge page ，huge page 大幅减小了

2017-01-25 11:09:49 2057

原创限制 TerichDB 的写速度

TerarkDB 在保持超高压缩率的同时还有非常高的读性能，为此付出的代价是“压缩速度”，如果在短时间内写入大量数据，会导致 TerarkDB 产生过多的 Frozen WritableSegment，进而影响读性能。新版 TerarkDB 增加了对写速度的限制（下称限流），从而解决该问题。默认情况下，没有限流，需要通过 dbmeta.json 设置限流：{ .... "

2016-09-05 18:07:54 2145

原创集成 TerichDB 的 MongoDB 性能测试

1.前言我们将TerichDB集成到了MongoDB社区版中，后续我们将逐步发布性能测试报告，目前，我们分别进行了读、写性能测试。

2016-06-22 13:10:43 2764

原创集成TerichDB的SSDB性能测试

目前很多互联网公司都在使用[SSDB](http://ssdb.io), 它是一款NoSQL的，高性能数据库，目标是替代Redis。我们在 TerichDB 原生 API 的基础上，实现了 LevelDB API，所有使用 LevelDB 的程序，不需要修改任何代码，只需要修改 Makefile，就可以使用 TerichDB，ssdb 就是这样的一个程序。为了方便大家编译、使用基于 TerichDB 的 ssdb

2016-06-22 13:09:39 3447

原创 TerichDB架构简介

TerichDB是一款高性能和高压缩率的存储引擎，既可以单独作为数据库使用，也可以作为已有数据库的存储引擎使用（如MySQL/MongoDB） TerichDB的定位类似于WiredTiger、RocksDB或LevelDB1. 为什么使用 TerichDB高性能的同时具有高压缩率高性能并非来自于时间空间的互换时间和空间同时获得的缩减延迟非常低并且很稳定基于Schema定义，

2016-06-22 13:08:24 3396

原创 TerarkDB 数据库的性能报告与技术解析

TerarkDB是一款功能丰富的数据库，具有优异的读性能和良好的写性能 — 因为使用的是自主研发的索引压缩和数据压缩技术（索引不是传统的B+树或者LSM，数据也不是块压缩）。TerarkDB v0.13 近期刚刚发布，目前这个版本已经具有了比较完善的功能，为了更好地让大家了解我们的产品，我们内部进行了一些比较全面的性能评测。本文包含三种场景: 数据小于内存, 数据略大于内存以及数据远大于内存, 后续我们会发布

2016-05-31 15:01:38 12970 3

转载 Solr or Elasticsearch–That Is the Question

blog source link: http://www.datanami.com/2015/01/22/solr-elasticsearch-question/January 22, 2015Solr or Elasticsearch–That Is the QuestionOtis GospodnetićThat is the common

2015-05-26 18:13:53 2735

原创 nark 数据库简介

不同于普通 Hash 或 Tree 结构的数据库，nark 数据库是基于自动机的，这决定了 nark 的强大与简洁，但是，最重要的是，nark 为大家提供了一整套解决方案。因为自动机只有离线(offline)创建成只读数据库，才能为在线(online)计算提供最节省内存并且高速查找的功能。从而，绝大部分 nark 组件都分为离线(offline)建库和在线(online)搜

2015-02-01 22:42:21 3871

转载正则语言的并交差

正则语言的并交差作者: rockeet 发表日期: 2014年09月08日分类: 自动机评论: 0 条阅读次数: 7 次 [编辑]正则表达式，描述的是正则语言，学过形式语言与自动机理论的人应该都知道，正则语言在并、交、差、补运算下都是封闭的；但是，根据 Wikipedia 的描述，到目前为止，还没有任何一个已知的正则语法(Flavor)将交和差纳入正则语法。理

2014-09-08 17:31:07 5215

原创实现了普通的正则引擎无法实现的两大功能

1. 多正则匹配，要判断输入文本匹配了多个正则中的哪个，不需要逐个判断，扫描一遍就得到结果（google re2.set 是一个半成品的多正则匹配）。2. 正则表达式并交差，这个功能今天刚完成，可以借此实现环视功能的一个超集，很多不严肃的论断认为环视无法用 DFA 实现，在此给大家纠正一下。性能上，10万个正则，待匹配文本平均长度30字节，判断出匹配了哪个（或哪些），平均耗时5

2014-09-07 12:15:24 3173

原创最近做了一个自动纠错演示网页

最近做了一个自动纠错当 Query 中有一些错别字时，搜索引擎会尝试纠错通过相似拼音纠错搜索引擎把这些字还原成拼音，用一个拼音相同的已知 Query 代替。但是，当输错的汉字是多音字，特别是有多个这样的错误输入时，所有的搜索引擎基本上都不管，或者仅使用一个最常用的音去纠错。因为要考虑所有可能的拼音组合，在极端情况下会导致指数爆炸！我的算法解决了这个指数爆炸

2014-08-08 16:52:56 4321 3

原创本博客已经迁移到 http://nark.cc

本博客已经迁移到 http://nfabo.cn , csdn 博客不再同步更新

2014-07-14 21:45:56 3124

原创 cygwin 中 dll 路径

cygwin 中 dll 路径不是用 LD_LIBRARY_PATH 指定，而是 PATH，坑爹！

2014-04-29 00:37:01 3385

转载 rdtsc 备忘

from: http://stackoverflow.com/questions/6814792/why-is-clock-gettime-so-erraticstatic uint64_t rdtsc() {#if defined(__GNUC__)# if defined(__i386__) uint64_t x; __asm__ volatile ("

2014-01-09 17:12:59 3757

原创多正则表达式匹配 (Multiple Regular Expression Matching) 中的动态 DFA 算法

前一段时间，在用多正则表达式匹配工具用于数十万任意的正则表达式时，以前一直担心的问题终于出现了：NFA 转化 DFA 时的指数爆炸，那样的 DFA 根本创建不出来，因为那些正则表达式之间有不可预料的各种交集！这个问题对我打击很大，我甚至顿时觉得多正则表达式匹配工具完全是个废柴，最多，是个玩具！但是，只有挑战，才能激励人的斗志，挖掘人的潜能。我想起了曾经对之不屑一顾的动态 DFA 匹配算

2014-01-05 21:43:43 6048 5

原创多正则表达式匹配工具的用法

2014年3月25日22:55从 http://code.google.com/p/febird/wiki/MultiRegexMatch 更新至最新版Introduction介绍Compileregex_builder 使用方法命令行选项与参数关于 -d 选项输入文件Regex.txt 的格式一个示例的Regex.txt非常重要！注意事项！匹配接口: 二进制模式

2013-12-17 17:34:56 9849 27

原创有多个初始状态的 DFA

最近做了一项工作：允许一个 DFA 有多个起始状态（可以称作根: root）。这样有以下几个好处：对于多正则表达式匹配（Multiple Regular Expression Matching）的 DFA在创建多正则表达式匹配的 DFA 的过程中，有一个 DFA 的 Union 操作，这操作通过 NFA 到 DFA 的转化来完成，在这个过程中，如果状态膨胀失去控制（最坏情况是指数级，一般情

2013-11-28 22:17:55 6958

原创 gcc 4.7.3 的一个 c++11 bug

昨天一个朋友 checkout 了我的 febird 代码，编译时出现了一个诡异的错误。经过仔细勘察，他的 g++ 版本是 4.7.3，而我测试过的 g++4.7.2，g++4.8.2均无问题。后来修改代码，解决了那个问题，但要还原那个bug时，很费了一番力气。以下是还原的那个 bug 的一段简单代码，不过可能不是最简单的。#include struct A { int

2013-11-13 10:30:50 3634 1

原创多正则表达式匹配（Multiple Regular Expression Matching）

目前 febird 中的自动机库已支持正则表达式，并且，支持的是多正则表达式匹配：给定 M 个正则表达式，每个正则表达式有一个 [0, M) 的唯一 ID，该算法为这些正则表达式生成一个 DFA。再给定一个输入文本 Text ，如果只计最长匹配，该 Text 可以匹配 M 个正则表达式中的的 K 个在该DFA上运行我的匹配算法，可以在 O(strlen(Text) + K) 的时间

2013-11-03 22:22:16 7520 15

原创 boost 这帮人也超级不靠谱

刚才开始用 boost::range，就查看了了一下 boost 源码，发现 boost-1.50 一个 bug，觉得应该在新版中已经修改了，下载了最新的 1.54 版，进去一看，bug 仍然在！接着，到 boost bug 追踪系统，准备提交这个 bug ，搜了一下，很快发现，这个bug 在 17 个月前，boost-1.49 就报告出来了： range::unique does not f

2013-09-24 10:58:36 2642 1

原创把自动机用作 Key-Value 存储

以前只有代码，最近简单写了一点文档： google code 上的链接（总是最新）自动机是什么DFA 的最小化将 DFA 用做字典无环DFA (ADFA, Acyclic DFA)编译内存用量/查询性能map 与 set自动机实用程序自动机的 C++接口DFA_InterfaceDAWG_Interface超级功能以拼音输入法为例

2013-08-15 11:51:38 9745

原创原地排序-更简洁的算法

在我以前的这篇文章中：原地排序与链表翻转。解决这个问题是先把链表翻转，然后再循环左移，原理是清楚了，可是稍显繁琐。这里有更简单的解法：

2013-03-24 19:24:19 3583

原创字符串匹配中的图论

问题有一个字符串由多个变量拼接而成： "$x1$x2$x3$x4$x5$x6..." ，这个列表可以一直延伸到 $x10000，而每个变量都至少有一种可能的取值，为了简化问题，每个变量不会再引用别的变量。现在，给定一个字符串T，判断这个字符串是否能由上面这个 "$x1$x2$x3$x4$x5$x6..." 生成。分析我们可以算出，总的可能性（最多）是 n1*n2*n3*n4*n5*

2013-03-24 10:51:15 1975

原创避免临时对象的字符串加法

之前我有一篇文章《 C++ 中让对象的拷贝成为显式的》，使用类似的技巧，可以避免字符串加法中的临时对象，也许是因为惰性，这个想法一直没有诉诸实现，今天有空把它写了出来。先看看这段代码：std::string a = "A";std::string b = a + "B" + "C" + "D" + "E" + "F";在C++11之前的标准 C++1998/2003 中，

2012-12-06 14:04:13 2114 2

原创 gold_hash_idx 完成了

用在 onfly minimal acyclic DFA construction 上，速度提高了大约28%，内存对每个State节约了4个字节。以后有空再努力一下，把 gold_hash_idx 再深入泛化一步，做成可以更方便地用于 multi_index 。

2012-09-25 21:46:11 1329

原创 gold_hash_map abstract++

目前的gold_hash_map 实现中，index和data是耦合在一起的。今天在思考 onfly MinADFA 的进一步优化时，想到了一点：在MinADFA_onfly 中，equivalence_register是一个gold_hash_tab,它以 state_id 为 elem，以StateContent 为key，再深入思考，其实这个state_id 没有存在的必要，equiva

2012-09-23 10:55:34 1466

原创 Trie, Hash, MinADFA

Trie的搜索复杂度是 O(length(strkey))Hash表，计算Hash的复杂度也是O(length(strkey))1. Trie因为每读一个字符，要做一次状态转移，就有一次（随机）访存操作，计算 strkey 的 Hash 不需要每个字符都随机访存，从这一点看，Hash胜出2. Hash 可能会有冲突，而 Trie 没有冲突，这一点，Trie 胜出

2012-09-07 21:25:22 1718

原创 NFA转化DFA

NFA转化DFANFA既然和DFA等价，那么，它们之间就存在对应关系，DFA到NFA的转化是自明的：没有空转移，把返回的单个state编程仅包含一个state的集合，就是一个形式上的NFA。但是，NFA到DFA的转化就不是那么简单了，实际上，在计算理论中，它属于ExpSpace问题，是一类比NP问题更难的问题。往简单了说，因为NFA的转移函数的返回值是个state集合，如果NFA的stat

2012-09-06 22:51:17 6984

原创 DFA的实现

DFA的实现在工业界，DFA的有效实现一直是一个问题，龙书中提到了一种使用四个数组的通用DFA实现，在汉字分词算法中经常用到double array作为Trie的一种实现。四数组的是通用DFA的实现，双数组的仅能用于实现Trie。并且它们的创建速度慢，难以理解，内存占用也比较多，状态id的值域范围稀疏。我的实现我实现了一种很紧凑的DFA，这在某种程度上源于popcount带来的灵感。当

2012-09-05 18:25:51 8513 2

原创 Context 终于进 boost 了

Version 1.51.0New Libraries: ContextBoost.Contextis a foundational library that provides a sort of cooperative multitasking on a single thread. By providing an abstraction of the current exe

2012-09-04 09:55:17 5532 3

原创自动机的一些算法和应用

几个月前实现了一个自动相关的算法，在一个比较乐观的测试中，将一个2.3G的url集合压缩到了27M，同时，key查找的时间复杂度是O(strlen(key))。当然，还有其它一些自动机相关的算法的优化实现，比如Aho-Corasick多模匹配。自动机的实现，这里说的自动机，指确定性的有穷状态自动机(DFA: Deterministic Finite Automata)。关于非确定性的有穷

2012-08-31 19:37:48 7437 4

原创自动机的思维导图

自动机有很多用途，不光是编译器会用到，众所周知的还有正则表达式。其他，简单的如字符串搜索，存储等，复杂点的如模型验证，定理证明……最简单的自动机应该算是DFA了，再往简单了说，一个DFA就是一个 map>, 其中 int 是 state id，char是转移标号；如果有人还嫌不够简单，最最简单的那就是 int [][256] 了，就是一个256列的矩阵。就这么简单的一个东西，却蕴含着非

2012-08-30 20:02:43 2545

转载避免应用程序抢夺焦点窗口

最近老碰到当前窗口被抢焦点，却不知道是哪个程序抢了焦点，找到了这一篇文章：避免应用程序抢夺焦点窗口【7/15/2004 10:19:52】【Serdar Yegulalp】【TechTarget】　　“焦点”（Focus）是用来描述那些当前启用的可以从键盘上输入或选择菜单的应用程

2012-07-13 10:44:49 6643 2

原创实现了一个压缩算法，在数据高度压缩的前提下，还可以快速查找 key

最近写了一个算法，可用于 (key,value) 存储，key 当然是 string 类型。用一个 2.3G 的 url 集合做测试，如果不计 value 占用的空间，key 集合的存储空间可以被压缩70倍！压缩后整个数据结构仅占31M内存！压缩率比 bzip2 还要高。本质性的不同于： gzip, bzip2 等压缩算法仅仅是压缩而已，无法快速地从压缩数据中查找。我实现的这个算法能高

2012-05-06 00:21:10 3741 15

实现了一个压缩算法，在数据高度压缩的前提下，还可以快速查找 key

最近写了一个算法，可用于 (key,value) 存储，key 当然是 string 类型。用一个 2.3G 的 url 集合做测试，如果不计 value 占用的空间，key 集合的存储空间可以被压缩70倍！压缩后整个数据结构仅占31M内存！压缩率比 bzip2 还要高。本质性的不同于： gzip, bzip2 等压缩算法仅仅是压缩而已，无法快速地从压缩数据中查找。我实现的...

2012-05-06 00:21:00 286

原创原地排序与链表翻转

有这样一个问题：有个长度为 n 的 (key,val) 数组 a，其中 key 是 int 类型，并且其值在 [0, n) 之间（前闭后开，包括 0 不包括 n），该数组按 key 是乱序的，但没有重复 key。要求：对 a 原地按 key 排序，可以使用常数个临时变量，不允许使用其它额外空间，时间复杂度必须是O(n)我曾经写过另外一个问题：排列的分解（必须看），与此有点类似：但其实不

2012-04-11 10:57:32 2450

原地排序与链表翻转

有这样一个问题：有个长度为 n 的 (key,val) 数组 a，其中 key 是 int 类型，并且其值在 [0, n) 之间（前闭后开，包括 0 不包括 n），该数组按 key 是乱序的，但没有重复 key。要求：对 a 原地按 key 排序，可以使用常数个临时变量，不允许使用其它额外空间，时间复杂度必须是O(n)我曾经写过另外一个问题：排列的分解（必须看），与此有点类似：但其实不...

2012-04-11 10:57:00 132

原创 C++ 中让对象的拷贝成为显式的

C++中对象的拷贝一般使用拷贝构造函数，从而对象的拷贝大多是隐式的，使用拷贝构造函数的隐式拷贝很方便，但是编译器无法识别不必要的拷贝，虽然我们人类可以识别这些不必要的拷贝，比如在写函数原型时，忘了加&，就会引发一个这样的非必要拷贝。如果这种情况很严重，我们可以禁用拷贝构造函数和赋值函数（声明成private），然后再提供一个显式拷贝函数，如：class HeavyObject {

2012-03-11 21:10:47 2084

C++ 中让对象的拷贝成为显式的

C++中对象的拷贝一般使用拷贝构造函数，从而对象的拷贝大多是隐式的，使用拷贝构造函数的隐式拷贝很方便，但是编译器无法识别不必要的拷贝，虽然我们人类可以识别这些不必要的拷贝，比如在写函数原型时，忘了加&，就会引发一个这样的非必要拷贝。如果这种情况很严重，我们可以禁用拷贝构造函数和赋值函数（声明成private），然后再提供一个显式拷贝函数，如：class HeavyObject ...

2012-03-11 21:10:00 130

C++ Best Practice (高阶教程)

有穷自动机的原理及应用

对称冗余集群架构

Text Clustering

HadoopStreaming

MapReduce应用

Hadoop.MapReduce.分析

febird C++ 库（附带所有源码）

空空如也