Posted on 2012-12-01 16:57
C小加 閱讀(2149)
評論(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。
- int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)
- { //lpszSring--要查詢的字符串；lpTable 哈希表；nTableSize是哈希表的Size
- int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;
-
- if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString)) //時間復雜度是O(1)
- return nHashPos;
- else
- return -1; //Error value
- }
(3). 上面的處理方法是假設一個字符串通過一個哈希算法只得到唯一一個hashcode(32為int整數)；但是如果存在兩個整數在同一個哈希算法得到同一個hashcode，那這個查詢就不正確的，雖然這個可能性比較小，但確實存在這個風險。
采用的解決辦法是用多個不同的哈希算法來校驗，兩個str 在三個不同的哈希算法得到的hashcode都相同的概率是：1/18889465931478580854784；可以認為是OK的。
- int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
- {
- const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
- int nHash = HashString(lpszString, HASH_OFFSET);
- int nHashA = HashString(lpszString, HASH_A);
- int nHashB = HashString(lpszString, HASH_B);
- int nHashStart = nHash % nTableSize, nHashPos = nHashStart;
- while (lpTable[nHashPos].bExists)
- {
- if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
- return nHashPos;
- else
- nHashPos = (nHashPos + 1) % nTableSize;
- if (nHashPos == nHashStart)
- break;
- }
- return -1; //Error value
- }
這樣就可以保證萬無一失了！
(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 來界定一個完整的事務
- <begin transaction>
- ****
- ****
- ****
- </end transaction>
一個完整的事務由
begin transaction----end transaction 里面的所有操作組成；在關系型數據庫中一個事務可以是一條SQL語句或一組SQL語句或者是一個程序；事務是并發和回滾的基本單位。(2). 事務的ACID屬性：
- Atomicity(原子性)：一個事務是一個不可分割的完整單元，一個transaction里面的所有操作要么都做完，要么都不做；當中間一個操作失敗把所有已經做的操作都回滾！
- Consistency(一致性)：數據庫在一個事務開始前是一致性的，在這個事務執行完畢后仍然是一致性的；只是從一個一致性狀態到另一個一致性狀態；但都是一致性的
- Isolation(隔離性)：一個事務的執行不能被其他事務所打擾，即一個事務內部操作及使用的數據對并發的事務是隔離的，并發執行的事務之間互相不干擾(不理解)!!
- Durablity(持久性)：也就永久性(Permanence)，即一個事務一旦執行完畢，則它對數據庫的更新是持久性的，即不受其他操作的影響；也就是事務修改了數據庫了
這個ACID的屬性是關系型數據庫(DBMS)非常重要的屬性，在執行數據庫操作時必須滿足ACID屬性，其中AI是我們編程中要注意的地方。