存档

文章标签 ‘NoSQL’

Redis实现之虚拟存储系统(VM)实现(二)–数据交换(Swap)的实现

2011年7月17日 sigma 4 条评论 53,776 views

Redis的虚拟存储系统(VM subsystem)的目的是实现将Redis对象(Redis Objects)方便的在主存(Memory)和硬盘(Disk)之间交换。在Redis虚拟存储系统中,Redis仅仅会将和值(Values)关联的对象交换(swap)到硬盘上。在前一篇日志中,对VM涉及的数据结构进行简要介绍,在这篇日志中,将介绍数据交换的具体过程。

在具体讲Redis数据交换的具体实现之前,有必要讲下swap文件,swap文件是由若干页(page)组成的,每页包含着给定字节数的数据。由于不同的redis实例的最优配置不一样(取决于你实际存储数据的大小),这些参数可以通过redis.conf文件进行修改。下面是默认的大小:

 vm-page-size 32
vm-pages 134217728
 

Redis使用位向量(英文为bitmap,这是一些连续的位,每位的值为0或1)来表示在硬盘中page是否被使用。假如一个给定位是1,则表示该页被使用(有swap文件存在上面),为0,表示该页未被使用。

通过在内存中使用位向量(下面将称为页表位向量),可以在很少的内存消耗情况下取得巨大的性能提升,因为我们仅仅只需要为每页提供一位。对于上面的默认配置,总共有4G的虚存,但是只需要16M的内存给页表位向量。

为了将主存上的数据交换到交换空间,我们需要做如下步骤(假设没有使用虚存线程,仅仅是块实现)。

  1. 找出需要多少页来存储交换文件。这仅仅需要通过调用rdbSavedObjectPages函数即可返回需要的页数。
  2. 知道需要的页数后,我们需要找到交换空间中一些连续的页来存储。这是通过vmFindContiguousPages函数实现的。这个函数有可能因为内存满了而失败,也有可能因为找不到连续的页失败。当这种情况发生时,交换将被取消,数据将继续保存在内存中。
  3. 最终,我们只需要调用vmWriteObjectOnSwap函数即可以将数据交换到对应的位置。数据交换完成后,对应的主存被释放,对应的key也被标记为REDIS_VM_SWAPPED,而对应的页表位向量也被标记为使用中。
    而将交换空间的数据切回到主存中,则很简单,由于知道对象存的位置以及占用页数。只需要调用vmLoadObject即可以完成。

注:本文内容翻译自redis源码包doc目录中的相关文档。

Redis实现之虚拟存储系统(VM)实现(一)–Swap file数据结构

2011年7月3日 sigma 8 条评论 10,842 views

Redis的虚拟存储系统(VM subsystem)的目的是实现将Redis对象(Redis Objects)方便的在主存(Memory)和硬盘(Disk)之间交换。在Redis虚拟存储系统中,Redis仅仅会将和值(Values)关联的对象交换(swap)到硬盘上。

在Redis的顶层的Hash 表中,将一部分的Redis对象(键Key)映射到另一部分Redis对象(值Value)。从而实现可以只将value交换到硬盘,而key对象不交换到硬盘,这保证了Redis非常好的查找性能(一般查找都是通过Key实现)。Redis虚存系统设计目标就是保证有虚存的Redis系统和没有虚存的Redis系统性能相差不大。

当一个对象(包括Key 和 Value)被交换到硬盘,在Hash表中:

  • Key还在内存中,保存着一个代表着Kye的Redis对象。
  • Value被设成了NULL。

到这里,你也许会问,在哪里存储被交换出去的Value信息(这Value和某个Key关联着)。事实上,在Redis中,就在Key对象中。

下面是Redis对象robj的数据结构:

  /* The actual Redis Object */
typedef struct redisObject {
    void *ptr;
    unsigned char type;
    unsigned char encoding;
    unsigned char storage;  /* If this object is a key, where is the value?
                             * REDIS_VM_MEMORY, REDIS_VM_SWAPPED, ... */
    unsigned char vtype; /* If this object is a key, and value is swapped out,
                          * this is the type of the swapped out object. */
    int refcount;
    /* VM fields, this are only allocated if VM is active, otherwise the
     * object allocation function will just allocate
     * sizeof(redisObjct) minus sizeof(redisObjectVM), so using
     * Redis without VM active will not have any overhead. */
    struct redisObjectVM vm;
} robj;
 

正如你所看到的,这个数据结构中有一些域是和虚拟存储相关的。最重要的域是storage,其取值可能有如下几个:

  • REDIS_VM_MEMORY: 对应的Value就在内存中
  • REDIS_VM_SWAPPED: 对应的Value已被交换, 并且hash表中入口刚被设成了NULL.
  • REDIS_VM_LOADING: 对应的Value已被交换, hash表中入口是NULL, 并且对象正从硬盘Load到主存中(这个值仅仅在线程VM/ThreadedVM激活时有效,具体什么事threaded VM,详见我的下一篇博文).
  • REDIS_VM_SWAPPING: 对应的Value在主存中, hash表中入口是一个指向redis对象的指针, 但是系统存在一个把这些Value交换到硬盘的IO任务.

阅读全文…

非关系型数据库(NoSQL)Redis实现之String实现

2011年6月25日 sigma 7 条评论 52,995 views

Redis是一个性能非常优异的非关系型数据库,有测试表明,在Linux 2.6, Xeon X3320 2.5Ghz配置的系统中,Redis性能能够达到SET操作每秒钟 110000 次,GET操作每秒钟 81000 次。

其本质上是一个键值(Key-Value)数据库,类似于memcache,但其支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)和zset(有序集合)。据新浪微博首席架构师透露,新浪微博系统里就采用了Redis数据库。Redis的最新版本是2.2.11,现在开发非常活跃,更新非常快。

Redis有四种数据类型:string,list,set及sorted set。其中,String是最基本的数据类型,也是其他几种数据类型的基础,其中所有的key值就是String类型的。下面介绍string类型的数据结构及操作:

Redis的String实现是在sds.c文件中实现的(sds代表Simple Dynamic Strings)。

String的结构体定义sdshdr在sds.h中定义:

 struct sdshdr {
    long len;
    long free;
    char buf[];
};
 

 

阅读全文…

数据库理论之ACID和BASE的比较

2011年6月17日 sigma 3 条评论 21,965 views

传统关系型数据库系统的事务都有ACID的属性,即原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation,又称独立性)、持久性(Durability)。英文为:

  • Atomic: Everything in a transaction succeeds or the entire transaction is rolled back.
  • Consistent: A transaction cannot leave the database in an inconsistent state.
  • Isolated: Transactions cannot interfere with each other.
  • Durable: Completed transactions persist, even when servers restart etc.
  • 中译为:

  • 原子性: 整个事务中的所有操作,要么全部完成,要么全部不完成,不可能停滞在中间某个环节。事务在执行过程中发生错误,会被回滚(Rollback)到事务开始前的状态,就像这个事务从来没有执行过一样。
  • 一致性: 在事务开始之前和事务结束以后,数据库的完整性约束没有被破坏。
  • 隔离性: 两个事务的执行是互不干扰的,一个事务不可能看到其他事务运行时,中间某一时刻的数据。 两个事务不会发生交互。
  • 持久性: 在事务完成以后,该事务所对数据库所作的更改便持久的保存在数据库之中,并不会被回滚。
  • 在数据库系统中,事务的ACID属性保证了数据库的一致性,比如银行系统中,转账就是一个事务,从原账户扣除金额,以及向目标账户添加金额,这两个数据库操作的总和构成一个完整的逻辑过程,不可拆分,为原子,从而保证了整个系统中的总金额没有变化。

然而,这些ACID特性对于大型的分布式系统来说,适合高性能不兼容的。比如,你在网上书店买书,任何一个人买书这个过程都会锁住数据库直到买书行为彻底完成(否则书本库存数可能不一致),买书完成的那一瞬间,世界上所有的人都可以看到熟的库存减少了一本(这也意味着两个人不能同时买书)。这在小的网上书城也许可以运行的很好,可是对Amazon这种网上书城却并不是很好。

阅读全文…

非关系型数据库NoSQL理论基础之CAP理论

2011年6月13日 sigma 没有评论 19,359 views

CAP理论是设计分布式web系统的一个很关键的定律,其主要内容是(非官方定义):

When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three.

中译为:

在设计分布式Web服务中,通常需要考虑三个应用的属性:一致性、可用性以及分区宽容性。但是在实际的设计中,不可能这三方面同时做的很好。

CAP理论的C就是一致性(Consistency),这里不多解释,想了解的可以看看我之前写过的一致性的一些东西;A就是可用性(availability),可以理解为是否可获取数据,以及获取数据的速度;P就是分区容忍度(partion tolerance),指的是系统中的数据分布性的大小对系统的正确性,性能的影响(一定程度上就是可扩展性)。这个理论的主要意思就是这三个是不可以同时做到很好的,我们在实现一个分布式系统时(包括分布式数据库),是不可能同时完美的实现三个方面。其实这个理论可以用“鱼和熊掌不可兼得”一言以蔽之。

CAP理论最早是在2000年7月19号,由Berkeley的Eric Brewer教授在ACM PODC会议上的一个开题演讲中提出,PPT在。此后,MIT的Seth GilbertNancy Lynch理论上证明了Brewer猜想是正确的,CAP理论在学术上正式作为一个定理出现了。

NoSQL一定程度上就是基于这个理论提出来的,因为传统的SQL数据库(关系型数据库)都是都是具有ACID属性,对一致性要求很高,因此降低了A(availability)和P(partion tolerance),因此,为了提高系统性能和可扩展性,必须牺牲C(consistency),推翻关系型数据库中ACID这一套。

依据CAP理论,从应用的需求不同,我们对数据库(其实就是一种结构化数据存储,和Bolb恰好不同)时,可以从三方面考虑:

  • 考虑CA,这就是传统上的关系型数据库(RMDB).
  • 考虑CP,主要是一些Key-value数据库,典型代表为google的Big Table
  • 考虑AP,主要是一些面向文档的适用于分布式系统的数据库,如SimpleDB。

而对大型网站尤其是SNS网站,对于数据的短期存储,可用性与分区容忍性优先级要高于数据一致性,一般会尽量朝着 A、P 的方向设计,而对于数据的持久存储,可以通过传统的SQL来保证一致性(最终一致性)。

CAP理论出现后,很多大规模的网站,尤其是SNS网站的数据库设计都利用其思想,包括Amazon,Facebook和Twitter这几个新兴的IT巨头,因此,一定程度上来讲,他们都是CAP的信徒。另一方面,他们从实践上证明了CAP理论的正确性。

最后,附上一张图片,可以形象的解释CAP理论(来源)
CAP-NoSQL
更多内容,请看这篇介绍CAP理论的文章,本文有些内容译自这里。

无觅相关文章插件,快速提升流量