111qqz的小窝

老年咸鱼冲锋!

levelDB 学习笔记

大三的时候看过一点levelDB的源码,不过没有怎么用过。

最近有个需求是存人脸的feature到硬盘,似乎使用levelDB比较合适,因此来学习一下使用。

先放参考资料。

关于levelDB的语法,看这里就好了。

以及由于caffe中使用了levelDB,因此也可以参考下caffe源码。不过caffe中对levelDB的使用是又封装了一层。

具体可以参考:

 

 

 

几个文件。。。感觉比看文档更有实际意义orz

levelDB简介

Leveldb是google开源的一个高效率的K/V数据库.有如下特点:

  1. 首先,LevelDb是一个持久化存储的KV系统,和Redis这种内存型的KV系统不同,LevelDb不会像Redis一样狂吃内存,而是将大部分数据存储到磁盘上。
  2. 其次,LevleDb在存储数据时,是根据记录的key值有序存储的,就是说相邻的key值在存储文件中是依次顺序存储的,而应用可以自定义key大小比较函数,LevleDb会按照用户定义的比较函数依序存储这些记录。
  3. 再次,像大多数KV系统一样,LevelDb的操作接口很简单,基本操作包括写记录,读记录以及删除记录。也支持针对多条操作的原子批量操作。
  4. 另外,LevelDb支持数据快照(snapshot)功能,使得读取操作不受写操作影响,可以在读操作过程中始终看到一致的数据。
  5. 除此外,LevelDb还支持数据压缩等操作,这对于减小存储空间以及增快IO效率都有直接的帮助。
  6. LevelDb性能非常突出,官方网站报道其随机写性能达到40万条记录每秒,而随机读性能达到6万条记录每秒。总体来说,LevelDb的写操作要大大快于读操作,而顺序读写操作则大大快于随机读写操作。

LevelDB的安装

以ubuntu14.04为例,但实际上除了路径可能不同,其他部分是系统无关的。

leveldb_github地址

然后记得切换到指定tag

可以使用git tag命令得到,然后用git checkout命令切换,我这里使用的是1.20版本

之后直接执行make

之后将头文件拷贝到系统路径下:

编译之后分别会得到out-shared和out-static两个文件夹,分别是动态库和静态库

我们进入out-shared文件夹,讲libleveldb.so*的三个文件(有两个是链接)拷贝到/usr/lib下

然后用sudo ldconfig 命令将动态库加到缓存中。

我们用如下代码测试一下:

编译选项为:

g++ mytest.cc -o mytest -lpthread -lleveldb

如果运行得到jason,表示安装成功。

 

LevelDB的使用

一些基本操作可以参考github文档

不过发现levelDB的接口似乎只支持key和value都是string类型。。

然而对于人脸提取feature,实际上需要的是string映射到float**

,偶然发现caffe中使用了levelDB,

发现它的做法是使用protobuf将数据序列化,然后再存储。

protobuf学习笔记

 

注意事项

记录一些踩坑的经历..

如果有100条数据,想要每10条存一个数据库,那么每10条执行一次DB::Open就行了…不然会报错在put那里,导致core dumped

 

 

 

内存屏障(Memory Barriers)

起因是最近在看levelDB源码,其中port里的atomic_pointer.h文件用到了内存屏障。。

于是来学习一下。。

粗略得说下我自己的理解。

代码的顺序并不和执行的顺序完全对应,出于对效率的追求,cpu和编译器会对一些顺序指令重排,以期得到最大的执行效率。

比如下面这段代码:

v的值是没有改变的,那么编译器可能会认为 _store = v; v = _store; 是多余的,就直接把这一段给“优化”掉了。这段代码在单线程中确实是多余的,但是在多线程环境下,可能在 somefunc()被调用的时候,另一个线程把v的值给改变了,而这种情况是编译器无法发现的。因此,为了避免这种情况。。。内存屏障登场!

摘自维基百科:

内存屏障,也称内存栅栏内存栅障屏障指令等,是一类同步屏障指令,是CPU或编译器在对内存随机访问的操作中的一个同步点,使得此点之前的所有读写操作都执行后才可以开始执行此点之后的操作。

大多数现代计算机为了提高性能而采取乱序执行,这使得内存屏障成为必须。

语义上,内存屏障之前的所有写操作都要写入内存;内存屏障之后的读操作都可以获得同步屏障之前的写操作的结果。因此,对于敏感的程序块,写操作之后、读操作之前可以插入内存屏障。

在多线程环境里需要使用某种技术来使程序结果尽快可见。。请先假定一个事实:一旦内存数据被推送到缓存,就会有消息协议来确保所有的缓存会对所有的共享数据同步并保持一致。这个使内存数据对CPU核可见的技术被称为内存屏障或内存栅栏

 

再看一个例子

这段代码,是想知道for循环空转100000次的耗时,这里就需要加入一个MemoryBarrier,如果不加,那么编译器可能就会直接把这个无意义的for循环直接优化掉了。

除了编译器,cpu由于指令流水线或者超流水线等计数,也可能导致出现乱序执行的情况。

内存屏障提供了两个功能。首先,它们通过确保从另一个CPU来看屏障的两边的所有指令都是正确的程序顺序,而保持程序顺序的外部可见性;其次它们可以实现内存数据可见性,确保内存数据会同步到CPU缓存子系统。

不过内存平展由于阻碍了cpu和编译器的部分优化。。。因此对性能的影响是不忽略的。

为了达到最佳性能,最好是把要解决的问题模块化,这样处理器可以按单元执行任务,然后在任务单元的边界放上所有需要的内存屏障。采用这个方法可以让处理器不受限的执行一个任务单元。合理的内存屏障组合还有一个好处是:缓冲区在第一次被刷后开销会减少,因为再填充改缓冲区不需要额外工作了。

内存屏障的实现不同平台差别很大。。。因为我们可以看到atomic_pointer.h文件中 一堆和平台相关的条件编译…

 

参考资料:

内存屏障_维基百科

内存屏障_并发编程网

LINUX内核之内存屏障

Lock-free vs wait-free concurrency

参考资料

看leveldb源码中遇到的,关于lock-free 和 wait-free..感觉这个讲得不错,我试着翻译一下?

There are two types of non-blocking thread synchronization algorithms – lock-free, and wait-free. Their meaning is often confused. In lock-free systems, while any particular computation may be blocked for some period of time, all CPUs are able to continue performing other computations. To put it differently, while a given thread might be blocked by other threads in a lock-free system, all CPUs can continue doing other useful work without stalls. Lock-free algorithms increase the overall throughput of a system by occassionally increasing the latency of a particular transaction. Most high- end database systems are based on lock-free algorithms, to varying degrees.

有两种 无阻塞线程同步算法,一种是lock-free,一种是wait-free,它们的含义经常被搞混。在一个lock-free系统中,尽管某个特定的计算会被阻碍一段时间,所有的cpu还是能够继续其他计算。换一种说法,尽管在一个lock-free的系统里,一个线程可能被其他线程阻碍,所有的cpu仍然可以继续做其他工作而不做停顿。lock-free算法通过偶然增加一个特定事物的延迟,增加了系统总体的吞吐率。大多数高端数据库系统都在某种程度上基于lock-free 算法。

 

By contrast, wait-free algorithms ensure that in addition to all CPUs continuing to do useful work, no computation can ever be blocked by another computation. Wait-free algorithms have stronger guarantees than lock-free algorithms, and ensure a high thorughput without sacrificing latency of a particular transaction. They’re also much harder to implement, test, and debug. The lockless page cachepatches to the Linux kernel are an example of a wait-free system.

与此相反,wait-free算法除了保证所有cpu继续做其他工作以外,还保证不会有任何计算被另一个计算阻止。wait-free算法比lock-free算法有更强的保证,确保了在不牺牲某一事物的延迟的基础上,拥有更高的吞吐率.wait-free算法因此也更加难以实现,测试,调试。linux内核的无锁页面缓存(?)就是一个wait-free系统的例子。

 

In a situation where a system handles dozens of concurrent transactions and has soft latency requirements, lock-free systems are a good compromise between development complexity and high concurrency requirements. A database server for a website is a good candidate for a lock-free design. While any given transaction might block, there are always more transactions to process in the meantime, so the CPUs will never stay idle. The challenge is to build a transaction scheduler that maintains a good mean latency, and a well bounded standard deviation.

在一个系统处理几十个并发事务并且对延迟要求不高的情况下,lock-free系统是开发复杂性和高并发性要求之间的良好折衷。一个网站的数据库服务器是lock-free系统的很好的体现。尽管某个特定的事物可能被阻塞,但同时也有更多的事务要处理,所以CPU永远不会空闲。面临的挑战是建立一个好的事物调度表,以此来获得尽可能低的平均延迟和一个有界的标准偏差。

In a scenario where a system has roughly as many concurrent transactions as CPU cores, or has hard real-time requirements, the developers need to spend the extra time to build wait-free systems. In these cases blocking a single transaction isn’t acceptable – either because there are no other transactions for the CPUs to handle, minimizing the throughput, or a given transaction needs to complete with a well defined non-probabilistic time period. Nuclear reactor control software is a good candidate for wait-free systems.

在一个场景中,系统与CPU内核大致相同数量的并发事务,或者有硬实时要求,开发人员需要花费额外的时间来构建wait-free系统。在这种情况下,阻塞单个事务是不可接受的,要么是因为CPU没有其他事务要处理从而减少了吞吐量,要么是给定的事务需要用一个定义良好的非概率时间段来完成(相对比较确定的时间的意思?)。核反应堆控制软件是wait-free系统的一个很好的体现。