海量，分布式，重量级

1. Bigtable(G)  HBase(Hadoop)  Hypertable(Zvents)

2. Dynamo(Amazon) Cassandra(F)

#1 基于GFS或HDFS，基于表，相关组件依赖多，维护麻烦(Zookeeper, HBASE,Hadoop)，和Hadoop系的一些工具集成简单（lucene，MP）

#2 P2P的KV系统，去中心化，KEY只能是字符串，支持列排序，不支持大文件

其它可持久

Mongodb， Redis, Membase,memcachedb_rget, Mysql,Timesten,Voldemort,Memcachedb ,Scalaris,simpledb, levelDB, Mnesia

其它：

velocity(MS),  memcached

Note:

Redis,  数据大小有局限。虚拟内存方式下工作不佳。
Mongodb， 数据恢复时间过长，异常关机会导致数据库数据出异常。依赖系统时钟，否则有灾难性后果。

levelDB， 

   目前只提供API,还没网络封装。如bdb, SQLite一样，内嵌的，这样可以在很多方案中方便替换后端存储引擎。

    LSM算法（The Log-structured Merge Tree）  its emphasis on efficient disk based random access using log-structured-merge (LSM) trees. 解决思路就是把写操作延迟和批处理化。具体的做法就是写一个条目的时候先写到内存中的数据结构中，然后批量的 merge 到磁盘中的数据结构中。
log-structured-merge (LSM) trees: They are mostly useful to optimize random I/Os at insertion/delete time at the price of a slightly degradation of read access time. They are extremely efficient at indexing data in random order stored on rotational disks (i.e. better than b-trees).

   随机IO他是如何解决的呢？ 它的写都是先记录到日志文件去的，在日志文件满之前只是简单的更新memtable,那么就把随机写转化成了顺序写。在日志满了后，把日志里面的数据排序写成sst表同时和之前的sst进行合并，这个动作也是顺序读和写。大家都知道传统磁盘raid的顺序读写吞吐量是很大的，100M左右是没有问题。在写日志文件的时候，用到是buffer IO，也就是说如果操作系统有足够的内存，这个读写全部由操作系统缓冲，效果非常好。即使是sync写模式，也是以数据累计到4K为一个单位写的，所以效率高。随机读呢？这个它解决不了。但是ssd盘最擅长随机读了。这个硬件很自然的解决了这个问题。所以leveldb的绝配是ssd盘的raid.

由于leveldb默认的sst文件是2M, 在数据集达到100G的时候要占用几万个文件，修改了：version_set.cc：23 static const int kTargetFileSize = 32 * 1048576;
让默认的文件变成32M,减少目录的压力。（LQ: 操作的过程会频繁的merge文件，这样修改会导致合并的成本增加？??）

该测试中请注意snappy压缩没有打开，如果有压缩性能还会高很多，因为IO少了一半。

write_buffer_size=$((256*1024*1024))，log大小设成256M，这样减少切换日志的开销和减少数据合并的频率。

同时应该注意到db_bench是单线程程序，还有一个compact线程，所以最多的时候这个程序只能跑到200%的cpu, IO util也不是很高. 换句话说如果是多线程程序的话性能还要N倍的提高。

介绍levelDB的好文 http://highscalability.com/blog/2011/8/10/leveldb-fast-and-lightweight-keyvalue-database-from-the-auth.html?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+HighScalability+%28High+Scalability%29

Project Voldemort

虽然不是一份详尽的清单,下面是我们考查这两个存储系统最关心的优势与劣势.

• 优势
  • 更简单的API
  • 基于Berkley DB的持久化,一个成熟并广泛使用的键值DB
  • 使用向量时钟而不是简单的时间戳.它不需要节点(客户端)的时钟保持同步.
• 劣势
  • 没有内置的”多数据中心”相关路由支持(意味着至少有一个额外的数据中心有此数据的一份拷贝)

Apache Cassandra

• 优势
  • 更广泛的生产系统部署(Facebook、Twitter、Digg、Rackspace)
  • 更丰富的API,值可以支持动态的列结构(Schema-free).列可以独立演化,意味着你不需要读出整个结构就可以更新其中的一列.
  • 为写操作做过专门优化(设计上).
  • 可配置的一致性级别(在每个请求上指定)
• 劣势
  • 文件格式仍在开发中,内部结构仍然可能会发生变化.鉴于它所支持的灵活性,文件格式更加复杂也更加难以理解,在性能方面尤其如此
  • 需要同步时钟(NTP)(节点与客户端都需要)
  • 与竞争产品相比,读操作更加磁盘密集
  • 不支持客户端的冲突检测,因此最近的数据总是赢家

=======================================================================

真正使用的时候，在海里数据下，下面这些指标更重要：

• 对系统环境的依赖少
• 大数据量下系统启动速度
• 数据的可恢复性
• 状态输出和数据备份
  
• 系统的开销可预测性
  

LevelDB内部实现

Files

LevelDB的实现本质上类似于Bigtable中的tablet(参见Bigtable论文5.3节)。但是，与论文中的具体的文件组织方式稍有不同，解释如下：

每个数据库由一组存储在指定目录下的一个文件集合组成。有如下几种文件类型：

Log files

日志文件(*.log)存储了最近的一系列更新。每个更新操作会被追加到当前的日志文件中。当日志文件达到预定义的大小后，会被转化为一个sorted table，同时一个新的日志文件会被创建出来以接受未来的更新。

同时会在一个内存结构(memtable)中保存一份当前的日志文件的一个copy。该copy会参与到每次读操作中，这样最新的已日志化的更新就能够反映到读操作中。

Sorted tables

sorted table (*.sst) 存储了一系列根据key值排好序的记录。每条记录要么是某key值对应的value，要么是一个针对该key值的删除标记。(删除标记会被用来去掉那些老的sorted tables中已过时的value值)。

sorted tables集合是通过一系列的level来进行组织的。从日志文件生成的sorted table会被放置在一个特殊的young level(也称作level 0)内。当该level下的文件数超过一定阈值(当前是4)时，该level下的所有文件会与level 1下与之有重叠的那些文件merge到一块，从而产生一系列新的level 1下的文件(我们会为每2MB的数据创建一个level 1文件)。

在level 0下的不同文件可能包含重叠的key值。但是其他level下的文件，它们的key range都是不重叠的(是指同一个level内部的文件不会重叠，不同的level之间会存在重叠)。设现有level L(L>=1),当level L下的文件总大小超过(10^L)MB时(比如，对应level 1就是10MB，level 2就是100MB，…),level L下的一个文件就会与level L+1下的所有与它有重叠的key的文件merge成一系列level L+1下的新文件。为最小化昂贵的seek开销，这些merge操作通过批量的读写操作，逐步的将新的更新从young level迁移到最大的level下。

Manifest

MANIFEST文件列出了组成每个level的sorted tables集合，对应的key range，以及其他一些重要的元数据。只要数据库被重新打开，就会产生一个新的MANIFEST文件(文件名会嵌入一个新的数字)。MANIFEST文件会被格式化为一个log，所有导致状态改变(文件增加或删除)的变更都会追加到该log里。

Current

CURRENT 是一个包含了最新的MANIFEST文件名称的文本文件。

Info logs

一些信息会被输出到名为LOG及LOG.old的文件中。

Others

其他用于各种目的的可能会产生的文件 (LOCK, *.dbtmp).

Level 0

当日志文件超过一定大小(默认1MB)时，会进行如下操作：

• 创建一个全新的memtable结构和log文件，同时将未来的更新指向它们
• 同时在后台进行如下操作：
  • 将之前的memtable的内容写入到sstable里
  • 丢弃该memtable
  • 删除老的log文件及memtable
  • 将新的sstable添加到level 0下

Compactions

当level L的大小超过自身的限制时，我们会在一个后台线程中进行compact操作。该操作会选择来自level L的一个文件，以及那些level L+1中所有与该文件重叠的文件。需要注意的是，即使level L下的这个文件只与level L+1下的某文件的一部分有重叠，也需要读取整个level L+1下的那个文件进行compaction，之后这个旧的level L+1下的文件就会被丢弃。另外：因为level 0很特殊(文件相互之间可能是有重叠的)，因此对于从level 0到level 1的compaction需要特殊对待：当level 0的某些文件相互重叠时，它的compaction就需要选择不止一个level 0的下的文件。Compaction会merge它选定的那些文件产生一系列新的level L+1下的文件。当当前输出文件大小达到目标大小(2MB)时，我们就会产生出一个新的level L+1下的文件。另外当当前输出文件的key range已经大的与10个以上的level L+2下的文件有重叠时，我们也会立即产生出一个新文件，而不一定非要等到它达到2MB，这是为了保证后面针对level L+1的Compaction不会从level L+2下获取过多数据。

老的文件会被丢弃，新的文件会被添加到服务状态。针对特定level下的Compaction是在整个key值空间内螺旋式地进行的。详细来说，比如对于Level L，我们会记住它上次compaction的那个最后的key值，在对于Level L的下次compaction时，我们会选择排在该key之后的第一个文件开始(如果没有这样的文件，那我们就再从头开始)。

Compaction会丢弃掉被覆盖的那些value值。同时如果更高level下的文件的key range不包含当前key时，针对它的删除标记也可以被丢弃掉{!更高level下的文件实际上是一些更老的值，如果它们包含该key，那么如果我们丢弃该低level下的删除标记，会导致该删除操作的丢失}

Timing

Level 0的compaction可能会从level 0下读取最多4个1MB文件，以及最坏情况下会读取所有的level 1下的文件(10MB)，这意味着，我们可能需要读14MB，写14MB。

除了比较特殊的Level 0的compaction，其他情况下我们会选取level L下的一个2MB的文件。最坏情况下，level L+1下可能有12个文件与它重叠(10是因为level L+1比level L大10倍，另外的2是因为在level L下的文件边界通常与level L+1下的边界并不是对其的)。因此compaction会读26MB，写26MB。假设磁盘IO带宽是100MB/s，最坏情况下的compaction可能需要大概0.5秒。

如果我们对后台操作进行一些限制，比如限制在全部IO带宽的10%，那么compaction时间可能会达到5秒。如果用户在用户以10MB/s的速度写入，我们就可能会创建出大量的level 0下的文件(可能会达到50，因为compaction需要5秒，而5秒内客户端已经又写入了50MB，而每个1MB，因此是50个)。这可能会显著增加读操作的开销，因为每次读操作都需要merge更多的文件。

• 解决方案 1:为了减少这种问题，我们可以在level-0下的文件数很大的时候，增加log切换的阈值。缺点是，阈值越大，相对应的memtable用掉的内存也就会越多。
• 解决方案2: 当level 0下的文件数上升很快时，我们可以人为地降低写操作速率。
• 解决方案3: 尽量降低merge的开销。由于大多数的level 0下的文件的block都已经缓存在cache里了，因此我们只需要关注merge迭代过程中的O(N)的复杂度。

Number of files

为降低文件数，我们可以为更高level下的文件使用更大的文件大小，取代固定的2MB文件。当然这可能导致更多的compactions过程中的波动。另外我们也可以将文件集合划分到多个目录下。

2011-02-04，我们在ext3文件系统下做了一个关于目录下的文件数与文件打开时间的关系的实验：

Files in directory   Microseconds to open a file
1000   9
10000  10
100000 16

看起来在现代文件系统中，没有必要进行目录切分。

Recovery

• 读取CURRENT文件找到最新提交的MANIFEST文件名
• 读取该 MANIFEST文件
• 清空垃圾文件
• 我们可以打开所有的sstable，但是使用惰性加载的方式会更好些…
• 将日志转化为一个新的level 0下的sstable
• Start directing new writes to a new log file with recovered sequence#
• Garbage collection of files

DeleteObsoleteFiles()会在每次compaction结束及recovery结束后调用。它会找到数据库中所有文件的名称。删掉除当前日志文件的所有日志文件。删掉那些不属于任何level及任何活动的compaction输出的table文件。

Immutable table文件格式

文件格式如下：

===========
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
...
[meta block K]
[metaindex block]
[index block]
[Footer]        (fixed size; starts at file_size - sizeof(Footer))

文件包含一些内部指针。每个这样的指针被称为一个BlockHandle，包含如下信息：

• offset: varint64
• size: varint64

• (1)文件内的key/value对序列有序排列，然后划分到一系列的data blocks里。这些blocks一个接一个的分布在文件的开头。每个data block会根据block_builder.cc里的代码进行格式化，然后进行可选地压缩。
• (2)在数据blocks之后存储的一些meta blocks，目前支持的meta block类型会在下面进行描述。未来也可能添加更多的meta block类型。每个meta block也会根据block_builder.cc里的代码进行格式化，然后进行可选地压缩。
• (3) A “metaindex” block.会为每个meta block保存一条记录，记录的key值就是meta block的名称，value值就是指向该meta block的一个BlockHandle。
• (4) An “index” block. 会为每个data block保存一条记录,key值是>=对应的data block里最后那个key值，同时在后面的那个data block第一个key值之前的那个key值，value值就是指向该meta block的一个BlockHandle。
• (5) 文件的最后是一个定长的footer，包含了metaindex和index这两个blocks的BlockHandle，以及一个magic number。

metaindex_handle:    char[p];    // Block handle for metaindex

index_handle:        char[q];    // Block handle for index

padding:             char[40-p-q]; // 0 bytes to make fixed length

// (40==2*BlockHandle::kMaxEncodedLength)

magic:                 fixed64;    // == 0xdb4775248b80fb57

"stats" Meta Block

------------------

该meta block包含一系列统计信息。Key就是该统计单元的名称，value包含一系列统计信息如下：

data size
index size
key size (uncompressed)
value size (uncompressed)
number of entries
number of data blocks

日志文件格式

日志文件内容由一系列的32KB blocks组成。唯一的异常是文件的末尾可能只包含一个部分块。每个block由一系列记录组成：
block := record* trailer?
{!‘*’可以看做是正则表达式里的*,代表0个或n个record。‘?’也是，代表0个或者1个trailer }
record :=
checksum: uint32       // crc32c of type and data[]
length: uint16
type: uint8            // One of FULL, FIRST, MIDDLE, LAST
data: uint8[length]

一条记录永远都不会从block的最后6个字节开始(因为它肯定放不下，看上面的记录checksum+length+type就占了7个字节了)。在这里组成trailer的最左处那些字节，要么完全是由0字节组成要么必须被读取者跳过。

此外: 如果当前block目前只剩下7个字节，然后现在需要添加一个非0长度的记录，那么写入者需要输出一个FIRST记录(不包含任何的用户数据)来填充该block剩余的7字节的空，然后将用户数据存放到下一个block里。

未来可以添加更多的类型。某些读取者可能会直接skip掉那些它不理解的记录，其他的一些可能会报告某些数据被skip掉了。

FULL == 1
FIRST == 2
MIDDLE == 3
LAST == 4

FULL 类型的记录包含了完整的用户记录

FIRST, MIDDLE, LAST 用于那些被分成多个片段(通常是因为block的边界导致的)的用户记录的。FIRST表明是用户记录的第一个片段，FIRST表明是用户记录的最后一个片段，MID表明用户记录的中间片段类型。

Example: consider a sequence of user records:

A: length 1000
B: length 97270
C: length 8000

A会作为一个FULL类型的记录存放在第一个block里。B 会被划分成三个片段:第一个片段会填充第一个block的剩余部分, 第二个片段会填充整个的第二个block, 第二个片段会填充第三个block的前面一部分. 最后，第三个block就只剩下6个字节，会作为trailer而留空。C将会作为一个FULL类型的记录存放在第四个block里。

===================

Some benefits over the recordio format:

• (1) We do not need any heuristics for resyncing – just go to next block boundary and scan. If there is a corruption, skip to the next block. As a side-benefit, we do not get confused when part of the contents of one log file are embedded as a record inside another log file.
• (2) Splitting at approximate boundaries (e.g., for mapreduce) is simple: find the next block boundary and skip records until we hit a FULL or FIRST record.
• (3) We do not need extra buffering for large records.

Some downsides compared to recordio format:

• (1) No packing of tiny records. This could be fixed by adding a new record type, so it is a shortcoming of the current implementation,not necessarily the format.

• (2) No compression. Again, this could be fixed by adding new record types.