C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Nosql入门知识（转）

Posted on 2012-12-01 16:57 C小加 阅读(2118) 评论(0)  编辑 收藏 引用 所属分类: NoSQL

1. NoSQL其实是关系型数据库相对应的，是no relational 即非关系型数据库；web2.0特别是一些用户访问量比较大的网站如：www.taobao.com weibo.com baidu.com 

每秒的访问量可能是上万次(10K);传统的关系型数据库 mysql oracle 每秒进行10K次数据查询还可以勉强应付，但是如果是每秒10K次读写数据库，因为数据库的数据都是卸载磁盘中，所以磁盘IO也是支撑不住每秒10K的读写。

在web的架构中，数据库是最难进行横向扩展的(通过简单的添加机器和硬件，也就是添加一些服务节点来提高负载均衡能力)；对于7*24小时在线的网站来说，对关系型数据库进行升级和扩展(分布式扩展--分库分表)是非常痛苦的事情，往往要进行停机维护；但这种对www.taobao.com 来说是非常丑陋的事情。[--可不可以添加几台服务器然后把复制，然后进行负载均衡--]。

NoSQL 是采用key/value的结构来存储数据，而且大多数的NoSQL采用内存来存储数据，一段时间后把数据同步到磁盘中；由于使用内存保存数据很好地解决了高并发读写的问题；其次NoSQL提供了根据key值进行横向分表(比如：用户id，每2000w数据放到一台数据库服务器中的一张用户表中)；同时实现了主从数据库互备，这样可以让数据库的动态迁移变得简单，让数据库服务器的横向扩展变得容易了。


2. 分布式数据库的CAP理论

 CAP理论是说Consistency（一致性）， Availability（可用性）， partition tolerance（分布）三部分系统；而且任何系统只会满足两个，不会有任何的系统会同时满足这三个条件；在传统的关系型数据库中是强调C 一致性，但是在满足高可用性(高并发时效率不高)，高扩展性(分布式数据库进行横向扩展)存在一定的缺陷。但是NoSQL在进行设计的时候就是针对并发海量数据存储的情况下进行设计的，在这种高并发海量数据下数据一致性并不像银行那样保持数据的强一致性，所以NoSQL·放弃强一致性的追求，从而达到更高的可用性和扩展性，通过“鸽巢原理”达到最终的一致性。

现在的数据库系统肯定是同一个时刻有多个进程对数据库进行读写操作，假设现在有3个进程(A、B、C)对数据库的某表进行操作，

  • 强一致性：A写入的数据x，B、C可以读到数据x
  • 弱一致性：A写入的数据x，B、C一段时间内读不到，最后会读到
  • 最终一致性：是一种特殊的一致性，保证在一段时间内没有数据的更新，但所有的返回都是把最新的数据返回；---缓存的概念，一段时间后把数据更新到数据库，达到最终一致性。
3. 哈希算法
(1). 哈希算法的基本原理：
     哈希算法的提出和应用背景，对于一个庞大的字符串数组array，给你一个字符串让你判断它是否在这个字符串数组中并找到它，最好的办法就是把这个庞大的字符串数组构建成一个哈希表，然后在进行查询是否有这个字符串。
 (2).构建hash table的过程：一般是采用一个32的整数来代表一个字符串，首先这个array的字符串已经存在内存或者磁盘中，我们要做的只是按照一定的算法把每个字符串映射到一个32位的整数，每个int占4个字节，在字符串中每个字符都占一个字节；这样就建立了字符串与32位整数的映射，然后根据程序大小设定一个hash table的Size(这个Size确保所有的int % Size的值是唯一的--取最大值即可)，这个把刚才得到的所有字符串对应的32位整数对这个Size进行取模，这个模值就是此整数在hash table的位置；这个位置与每一个字符串又建立了一个映射关系；这样让你查询这个str是否在array中？
  • 首先，是把这个str，用相同的哈希算法进行编码---->映射到一个32位的int型数据 num
  • 然后，把这个num % Size 获取此字符串在hash table里面的位置；
  • 然后，判断hash table 此位置是否已经有数据占用，如果已经占用说明在array里面有一个字符串对应的32位整数与str的32位整数相同，在一个字符串对应唯一一个32位整数的前提条件下，就说明array里面存在字符串str。
  1. int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)  
  2. { //lpszSring--要查询的字符串；lpTable 哈希表；nTableSize是哈希表的Size  
  3. int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;  
  4.   
  5. if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))  //时间复杂度是O(1)  
  6.   return nHashPos;  
  7. else  
  8.   return -1; //Error value  
  9. }  
(3).  上面的处理方法是假设一个字符串通过一个哈希算法只得到唯一一个hashcode(32为int整数)；但是如果存在两个整数在同一个哈希算法得到同一个hashcode，那这个查询就不正确的，虽然这个可能性比较小，但确实存在这个风险。
采用的解决办法是用多个不同的哈希算法来校验，两个str 在三个不同的哈希算法得到的hashcode都相同的概率是：1/18889465931478580854784；可以认为是OK的。
  1. int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)  
  2. {  
  3. const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;  
  4. int nHash = HashString(lpszString, HASH_OFFSET);  
  5. int nHashA = HashString(lpszString, HASH_A);  
  6. int nHashB = HashString(lpszString, HASH_B);  
  7. int nHashStart = nHash % nTableSize, nHashPos = nHashStart;  
  8. while (lpTable[nHashPos].bExists)  
  9. {  
  10.   if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)  
  11.    return nHashPos;  
  12.   else  
  13.    nHashPos = (nHashPos + 1) % nTableSize;  
  14.   if (nHashPos == nHashStart)  
  15.    break;  
  16. }  
  17. return -1; //Error value  
  18. }  

这样就可以保证万无一失了！
(4). 常见的哈希算法：MD5 SHA  SHA-1等都是常用的哈希算法，而且他们都属于混合哈希算法，除了混合哈希算法还有加法、乘法、除法的哈希算法；
所以，在比较一个文件是否发生变化的方法出了可以用最后修改时间来判断，也可以用其哈希code来比较，比如用MD5来比较，如果其MD5都变化了则文件一定被修改了。

4. Tair 缓存也是一种 基于key/value的NoSQL结构开发的一种缓存机制，其实质也是NoSQL数据库，不过是key/value结构而且是用内存来存储数据，所以用把Tair叫做缓存。

5. 关系型数据库的事务(ACID)
(1). 事务(Transaction)：Transaction是访问并可能更新数据库中各种数据项的一个程序执行单元(unit)，事务一般由高级数据语言(C++ Java SQL)等写的用户程序引起的，并用begin transaction----end transaction 来界定一个完整的事务
  1. <begin transaction>  
  2. ****  
  3. ****  
  4. ****  
  5. </end transaction>  
一个完整的事务由begin transaction----end transaction  里面的所有操作组成；在关系型数据库中一个事务可以是一条SQL语句或一组SQL语句或者是一个程序；事务是并发和回滚的基本单位。
(2). 事务的ACID属性：
  • Atomicity(原子性)：一个事务是一个不可分割的完整单元，一个transaction里面的所有操作要么都做完，要么都不做；当中间一个操作失败把所有已经做的操作都回滚！
  • Consistency(一致性)：数据库在一个事务开始前是一致性的，在这个事务执行完毕后仍然是一致性的；只是从一个一致性状态到另一个一致性状态；但都是一致性的
  • Isolation(隔离性)：一个事务的执行不能被其他事务所打扰，即一个事务内部操作及使用的数据对并发的事务是隔离的，并发执行的事务之间互相不干扰(不理解)!!
  • Durablity(持久性)：也就永久性(Permanence)，即一个事务一旦执行完毕，则它对数据库的更新是持久性的，即不受其他操作的影响；也就是事务修改了数据库了
这个ACID的属性是关系型数据库(DBMS)非常重要的属性，在执行数据库操作时必须满足ACID属性，其中AI是我们编程中要注意的地方。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理