这个周末真忙

2011年7月9日 sigma 5 条评论 12,580 views

这周比较忙,尤其是周末,看来两天都得去实验室加班。之前就觉得那东西是无底洞,看来我的想法是对的,但愿这周末能够彻底把这无底洞了解。

还有一件郁闷的是,明天705版散伙饭,但是本科班主任过来了,所以0611明天也聚会,时间有点冲突,有点郁闷。

下周也不轻松,暑期学期的课都要结了,N多报告和小论文,够折腾好几天了,加上其他一堆事,真要焦头烂额了。

嗯,这周比较忙,就写这些了,权充数而。

最后,附上一张比较搞的图,放松一下。

分类: life 标签:

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

2011年7月3日 sigma 8 条评论 12,050 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 条评论 53,724 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 条评论 25,940 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 没有评论 21,623 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理论的文章,本文有些内容译自这里。

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