Sql優(yōu)化是一項(xiàng)復(fù)雜的工作，以下的一些基本原則是本人看書時(shí)所記錄下來的，很明確且沒什么廢話：

1．  索引的使用：

（1）.當(dāng)插入的數(shù)據(jù)為數(shù)據(jù)表中的記錄數(shù)量的10%以上，首先需要?jiǎng)h除該表的索引來提高數(shù)據(jù)的插入效率，當(dāng)數(shù)據(jù)插入后，再建立索引。

（2）.避免在索引列上使用函數(shù)或計(jì)算，在where子句中，如果索引是函數(shù)的一部分，優(yōu)化器將不再使用索引而使用全表掃描。如：

低效：select * from dept where sal*12 >2500;

高效：select * from dept where sal>2500/12;

(3).避免在索引列上使用not和 “!=”，索引只能告訴什么存在于表中，而不能告訴什么不存在于表中，當(dāng)數(shù)據(jù)庫遇到not 和 “!=”時(shí)，就會(huì)停止使用索引而去執(zhí)行全表掃描。

(4).索引列上>=代替>

 低效：select * from emp where deptno > 3

 高效：select * from emp where deptno >=4

兩者的區(qū)別在于，前者dbms將直接跳到第一個(gè)deptno等于4的記錄，而后者將首先定位到deptno等于3的記錄并且向前掃描到第一個(gè)deptno大于3的。

(5).非要對(duì)一個(gè)使用函數(shù)的列啟用索引，基于函數(shù)的索引是一個(gè)較好的方案。

2. 游標(biāo)的使用：

   當(dāng)在海量的數(shù)據(jù)表中進(jìn)行數(shù)據(jù)的刪除、更新、插入操作時(shí)，用游標(biāo)處理的效率是最慢的，但是游標(biāo)又是必不可少的，所以正確使用游標(biāo)十分重要：

   (1). 在數(shù)據(jù)抽取的源表中使用時(shí)間戳，這樣每天的維表數(shù)據(jù)維護(hù)只針對(duì)更新日期為最新時(shí)間的數(shù)據(jù)來進(jìn)行，大大減少需要維護(hù)的數(shù)據(jù)記錄數(shù)。

   (2). 在insert和update維表時(shí)都加上一個(gè)條件來過濾維表中已經(jīng)存在的記錄，例如：

insert into dim_customer select * from ods_customer where ods_customer.code not exists (dim_customer.code)

 ods_customer為數(shù)據(jù)源表。dim_customer為維表。

   (3). 使用顯式的游標(biāo)，因?yàn)殡[式的游標(biāo)將會(huì)執(zhí)行兩次操作，第一次檢索記錄，第二次檢查too many rows這個(gè)exception,而顯式游標(biāo)不執(zhí)行第二次操作。

3．  據(jù)抽取和上載時(shí)的sql優(yōu)化：

(1). Where 子句中的連接順序：

oracle采用自下而上的順序解析where子句，根據(jù)這個(gè)原理，表之間的連接必須寫在其他where條件之前，那些可以過濾掉大量記錄的條件必須寫在where子句的末尾。如：

低效：select * from emp e where sal>5000 and job = ‘manager’ and 25<(select count (*) from emp where mgr=e.empno);

高效：select * from emp e where 25<(select count(*) from emp where mgr=e.empno) and sal>5000 and job=’manager’;

   (2). 刪除全表時(shí)，用truncate 替代 delete,同時(shí)注意truncate只能在刪除全表時(shí)適用，因?yàn)?/SPAN>truncate是ddl而不是dml。

   (3). 盡量多使用commit

只要有可能就在程序中對(duì)每個(gè)delete,insert,update操作盡量多使用commit,這樣系統(tǒng)性能會(huì)因?yàn)?/SPAN>commit所釋放的資源而大大提高。

   (4). 用exists替代in ，可以提高查詢的效率。

   (5). 用not exists 替代 not in

   (6). 優(yōu)化group by

提高group by語句的效率，可以將不需要的記錄在group by之前過濾掉。如：

低效：select job, avg(sal) from emp group by job having job = ‘president’ or job=’manager’;

高效： select job, avg(sal) from emp having  job=’president’ or job=’manager’ group by job;

   (7). 有條件的使用union-all 替代 union：這樣做排序就不必要了，效率會(huì)提高3到5倍。

   (8). 分離表和索引

       總是將你的表和索引建立在不同的表空間內(nèi)，決不要將不屬于oracle內(nèi)部系統(tǒng)的對(duì)象存放到system表空間內(nèi)。同時(shí)確保數(shù)據(jù)表空間和索引表空間置于不同的硬盤控制卡控制的硬盤上。

轉(zhuǎn)自：http://blog.csdn.net/eigo/archive/2006/03/02/614157.aspx

/*
建表：
dept:
 deptno(primary key),dname,loc
emp:
 empno(primary key),ename,job,mgr,sal,deptno
*/

1 列出emp表中各部門的部門號(hào)，最高工資，最低工資
select max(sal) as 最高工資,min(sal) as 最低工資,deptno from emp group by deptno;

2 列出emp表中各部門job為'CLERK'的員工的最低工資，最高工資
select max(sal) as 最高工資,min(sal) as 最低工資,deptno as 部門號(hào) from emp where job = 'CLERK' group by deptno;

3 對(duì)于emp中最低工資小于1000的部門，列出job為'CLERK'的員工的部門號(hào)，最低工資，最高工資
select max(sal) as 最高工資,min(sal) as 最低工資,deptno as 部門號(hào) from emp as b
where job='CLERK' and 1000>(select min(sal) from emp as a where a.deptno=b.deptno) group by b.deptno

4 根據(jù)部門號(hào)由高而低，工資有低而高列出每個(gè)員工的姓名，部門號(hào)，工資
select deptno as 部門號(hào),ename as 姓名,sal as 工資 from emp order by deptno desc,sal asc

5 寫出對(duì)上題的另一解決方法
（請(qǐng)補(bǔ)充）

6 列出'張三'所在部門中每個(gè)員工的姓名與部門號(hào)
select ename,deptno from emp where deptno = (select deptno from emp where ename = '張三')

7 列出每個(gè)員工的姓名，工作，部門號(hào)，部門名
select ename,job,emp.deptno,dept.dname from emp,dept where emp.deptno=dept.deptno

8 列出emp中工作為'CLERK'的員工的姓名，工作，部門號(hào)，部門名
select ename,job,dept.deptno,dname from emp,dept where dept.deptno=emp.deptno and job='CLERK'

9 對(duì)于emp中有管理者的員工，列出姓名，管理者姓名（管理者外鍵為mgr）
select a.ename as 姓名,b.ename as 管理者 from emp as a,emp as b where a.mgr is not null and a.mgr=b.empno

10 對(duì)于dept表中，列出所有部門名，部門號(hào)，同時(shí)列出各部門工作為'CLERK'的員工名與工作
select dname as 部門名,dept.deptno as 部門號(hào),ename as 員工名,job as 工作 from dept,emp
where dept.deptno *= emp.deptno and job = 'CLERK'

11 對(duì)于工資高于本部門平均水平的員工，列出部門號(hào)，姓名，工資，按部門號(hào)排序
select a.deptno as 部門號(hào),a.ename as 姓名,a.sal as 工資 from emp as a
where a.sal>(select avg(sal) from emp as b where a.deptno=b.deptno) order by a.deptno

12 對(duì)于emp，列出各個(gè)部門中平均工資高于本部門平均水平的員工數(shù)和部門號(hào)，按部門號(hào)排序
select count(a.sal) as 員工數(shù),a.deptno as 部門號(hào) from emp as a
where a.sal>(select avg(sal) from emp as b where a.deptno=b.deptno) group by a.deptno order by a.deptno

13 對(duì)于emp中工資高于本部門平均水平，人數(shù)多與1人的，列出部門號(hào)，人數(shù)，按部門號(hào)排序
select count(a.empno) as 員工數(shù),a.deptno as 部門號(hào),avg(sal) as 平均工資 from emp as a
where (select count(c.empno) from emp as c where c.deptno=a.deptno and c.sal>(select avg(sal) from emp as b where c.deptno=b.deptno))>1
group by a.deptno order by a.deptno

14 對(duì)于emp中低于自己工資至少5人的員工，列出其部門號(hào)，姓名，工資，以及工資少于自己的人數(shù)
select a.deptno,a.ename,a.sal,(select count(b.ename) from emp as b where b.sal<a.sal) as 人數(shù) from emp as a
where (select count(b.ename) from emp as b where b.sal<a.sal)>5

轉(zhuǎn)自：http://blog.csdn.net/woolceo/archive/2006/03/02/614094.aspx

在開發(fā)部署PORTAL項(xiàng)目時(shí)，遇到異常：
Exception:weblogic.management.ApplicationException: prepare failed for content_repo.jar Module: content_repo.jar Error: Exception preparing module: EJBModule(content_repo.jar,status=NEW) Unable to deploy EJB: content_repo.jar from content_repo.jar: Class not found: com.bea.content.repo.i18n.RepoExceptionTextFormatter java.lang.NoClassDefFoundError: Class not found: com.bea.content.repo.i18n.RepoExceptionTextFormatter at weblogic.ejb20.compliance.EJBComplianceChecker.check([Ljava.lang.Object;)V(EJBComplianceChecker.java:287)

我在weblogic81 sp3的doc中沒有發(fā)現(xiàn)com.bea.content.repo.i18n這個(gè)package.

重新安裝了weblogic sp4，就不再出現(xiàn)這個(gè)錯(cuò)誤了。

Problem Statement
	When editing a single line of text, there are four keys that can be used to move the cursor: end, home, left-arrow and right-arrow. As you would expect, left-arrow and right-arrow move the cursor one character left or one character right, unless the cursor is at the beginning of the line or the end of the line, respectively, in which case the keystrokes do nothing (the cursor does not wrap to the previous or next line). The home key moves the cursor to the beginning of the line, and the end key moves the cursor to the end of the line. You will be given a int, N, representing the number of character in a line of text. The cursor is always between two adjacent characters, at the beginning of the line, or at the end of the line. It starts before the first character, at position 0. The position after the last character on the line is position N. You should simulate a series of keystrokes and return the final position of the cursor. You will be given a String where characters of the String represent the keystrokes made, in order. 'L' and 'R' represent left and right, while 'H' and 'E' represent home and end.
Definition
	Class: CursorPosition Method: getPosition Parameters: String, int Returns: int Method signature: int getPosition(String keystrokes, int N) (be sure your method is public)
Constraints
-	keystrokes will be contain between 1 and 50 'L', 'R', 'H', and 'E' characters, inclusive.
-	N will be between 1 and 100, inclusive.
Examples
0)
	"ERLLL" 10 Returns: 7 First, we go to the end of the line at position 10. Then, the right-arrow does nothing because we are already at the end of the line. Finally, three left-arrows brings us to position 7.
1)
	"EHHEEHLLLLRRRRRR" 2 Returns: 2 All the right-arrows at the end ensure that we end up at the end of the line.
2)
	"ELLLELLRRRRLRLRLLLRLLLRLLLLRLLRRRL" 10 Returns: 3
3)
	"RRLEERLLLLRLLRLRRRLRLRLRLRLLLLL" 19 Returns: 12

---

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

答案：

Problem Statement
	A square matrix is a grid of NxN numbers. For example, the following is a 3x3 matrix: 4 3 5 2 4 5 0 1 9 One way to represent a matrix of numbers, each of which is between 0 and 9 inclusive, is as a row-major String. To generate the String, simply concatenate all of the elements from the first row followed by the second row and so on, without any spaces. For example, the above matrix would be represented as "435245019". You will be given a square matrix as a row-major String. Your task is to convert it into a String[], where each element represents one row of the original matrix. Element i of the String[] represents row i of the matrix. You should not include any spaces in your return. Hence, for the above String, you would return {"435","245","019"}. If the input does not represent a square matrix because the number of characters is not a perfect square, return an empty String[], {}.
Definition
	Class: MatrixTool Method: convert Parameters: String Returns: String[] Method signature: String[] convert(String s) (be sure your method is public)
Constraints
-	s will contain between 1 and 50 digits, inclusive.
Examples
0)
	"435245019" Returns: {"435", "245", "019" } The example above.
1)
	"9" Returns: {"9" }
2)
	"0123456789" Returns: { } This input has 10 digits, and 10 is not a perfect square.
3)
	"3357002966366183191503444273807479559869883303524" Returns: {"3357002", "9663661", "8319150", "3444273", "8074795", "5986988", "3303524" }

---

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

答案：

     摘要: Problem Statement      A simple line drawing program uses a blank 20 x 20 pixel canvas and a directional cursor that starts at the upper left corner pointing straight down. T...  閱讀全文 經(jīng)典面試題

一、面向?qū)ο蟮娜齻€(gè)基本特征
   2、方法重載和方法重寫的概念和區(qū)別
   3、接口和內(nèi)部類、抽象類的特性
   4、文件讀寫的基本類
   **5、串行化的注意事項(xiàng)以及如何實(shí)現(xiàn)串行化
   6、線程的基本概念、線程的基本狀態(tài)以及狀態(tài)之間的關(guān)系
   7、線程的同步、如何實(shí)現(xiàn)線程的同步
   8、幾種常用的數(shù)據(jù)結(jié)構(gòu)及內(nèi)部實(shí)現(xiàn)原理。
   9、Socket通信(TCP、UDP區(qū)別及Java實(shí)現(xiàn)方式)
  **10、Java的事件委托機(jī)制和垃圾回收機(jī)制
  11、JDBC調(diào)用數(shù)據(jù)庫的基本步驟
  **12、解析XML文件的幾種方式和區(qū)別
  13、Java四種基本權(quán)限的定義
  14、Java的國(guó)際化
二、JSP
   1、至少要能說出7個(gè)隱含對(duì)象以及他們的區(qū)別
  ** 2、forward 和redirect的區(qū)別
   3、JSP的常用指令
三、servlet
   1、什么情況下調(diào)用doGet()和doPost()？
   2、servlet的init()方法和service()方法的區(qū)別
   3、servlet的生命周期
   4、如何現(xiàn)實(shí)servlet的單線程模式
   5、servlet的配置
   6、四種會(huì)話跟蹤技術(shù)
四、EJB
   **1、EJB容器提供的服務(wù)
 主要提供聲明周期管理、代碼產(chǎn)生、持續(xù)性管理、安全、事務(wù)管理、鎖和并發(fā)行管理等服務(wù)。
   2、EJB的角色和三個(gè)對(duì)象
 EJB角色主要包括Bean開發(fā)者 應(yīng)用組裝者 部署者 系統(tǒng)管理員 EJB容器提供者 EJB服務(wù)器提供者
 三個(gè)對(duì)象是Remote（Local）接口、Home（LocalHome）接口，Bean類
   2、EJB的幾種類型
 會(huì)話（Session）Bean ，實(shí)體（Entity）Bean 消息驅(qū)動(dòng)的（Message Driven）Bean
 會(huì)話Bean又可分為有狀態(tài)（Stateful）和無狀態(tài)（Stateless）兩種
 實(shí)體Bean可分為Bean管理的持續(xù)性（BMP）和容器管理的持續(xù)性（CMP）兩種
   3、bean 實(shí)例的生命周期
 對(duì)于Stateless Session Bean、Entity Bean、Message Driven Bean一般存在緩沖池管理，而對(duì)于Entity Bean和Statefull Session Bean存在Cache管理，通常包含創(chuàng)建實(shí)例，設(shè)置上下文、創(chuàng)建EJB Object（create）、業(yè)務(wù)方法調(diào)用、remove等過程，對(duì)于存在緩沖池管理的Bean，在create之后實(shí)例并不從內(nèi)存清除，而是采用緩沖池調(diào)度機(jī)制不斷重用實(shí)例，而對(duì)于存在Cache管理的Bean則通過激活和去激活機(jī)制保持Bean的狀態(tài)并限制內(nèi)存中實(shí)例數(shù)量。
   4、激活機(jī)制
 以Statefull Session Bean 為例：其Cache大小決定了內(nèi)存中可以同時(shí)存在的Bean實(shí)例的數(shù)量，根據(jù)MRU或NRU算法，實(shí)例在激活和去激活狀態(tài)之間遷移，激活機(jī)制是當(dāng)客戶端調(diào)用某個(gè)EJB實(shí)例業(yè)務(wù)方法時(shí)，如果對(duì)應(yīng)EJB Object發(fā)現(xiàn)自己沒有綁定對(duì)應(yīng)的Bean實(shí)例則從其去激活Bean存儲(chǔ)中（通過序列化機(jī)制存儲(chǔ)實(shí)例）回復(fù)（激活）此實(shí)例。狀態(tài)變遷前會(huì)調(diào)用對(duì)應(yīng)的ejbActive和ejbPassivate方法。
   5、remote接口和home接口主要作用
 remote接口定義了業(yè)務(wù)方法，用于EJB客戶端調(diào)用業(yè)務(wù)方法
 home接口是EJB工廠用于創(chuàng)建和移除查找EJB實(shí)例
   6、客服端調(diào)用EJB對(duì)象的幾個(gè)基本步驟
一、 設(shè)置JNDI服務(wù)工廠以及JNDI服務(wù)地址系統(tǒng)屬性
二、 查找Home接口
三、 從Home接口調(diào)用Create方法創(chuàng)建Remote接口
四、 通過Remote接口調(diào)用其業(yè)務(wù)方法
五、數(shù)據(jù)庫
   1、存儲(chǔ)過程的編寫
   2、基本的SQL語句
六、weblogic
1、 如何給weblogic指定大小的內(nèi)存?
在啟動(dòng)Weblogic的腳本中（位于所在Domian對(duì)應(yīng)服務(wù)器目錄下的startServerName），增加set MEM_ARGS=-Xms32m -Xmx200m，可以調(diào)整最小內(nèi)存為32M，最大200M
2、 如何設(shè)定的weblogic的熱啟動(dòng)模式(開發(fā)模式)與產(chǎn)品發(fā)布模式?
可以在管理控制臺(tái)中修改對(duì)應(yīng)服務(wù)器的啟動(dòng)模式為開發(fā)或產(chǎn)品模式之一?；蛘咝薷姆?wù)的啟動(dòng)文件或者commenv文件，增加set PRODUCTION_MODE=true。
3、 如何啟動(dòng)時(shí)不需輸入用戶名與密碼?
修改服務(wù)啟動(dòng)文件，增加 WLS_USER和WLS_PW項(xiàng)。也可以在boot.properties文件中增加加密過的用戶名和密碼.
4、 在weblogic管理制臺(tái)中對(duì)一個(gè)應(yīng)用域(或者說是一個(gè)網(wǎng)站,Domain)進(jìn)行jms及ejb或連接池等相關(guān)信息進(jìn)行配置后,實(shí)際保存在什么文件中?
保存在此Domain的config.xml文件中，它是服務(wù)器的核心配置文件。
5、 說說weblogic中一個(gè)Domain的缺省目錄結(jié)構(gòu)?比如要將一個(gè)簡(jiǎn)單的helloWorld.jsp放入何目錄下,然的在瀏覽器上就可打入http://主機(jī):端口號(hào)//helloword.jsp就可以看到運(yùn)行結(jié)果了? 又比如這其中用到了一個(gè)自己寫的javaBean該如何辦?
Domain目錄\服務(wù)器目錄\applications，將應(yīng)用目錄放在此目錄下將可以作為應(yīng)用訪問，如果是Web應(yīng)用，應(yīng)用目錄需要滿足Web應(yīng)用目錄要求，jsp文件可以直接放在應(yīng)用目錄中，Javabean需要放在應(yīng)用目錄的WEB-INF目錄的classes目錄中，設(shè)置服務(wù)器的缺省應(yīng)用將可以實(shí)現(xiàn)在瀏覽器上無需輸入應(yīng)用名。
6、 如何查看在weblogic中已經(jīng)發(fā)布的EJB?
可以使用管理控制臺(tái)，在它的Deployment中可以查看所有已發(fā)布的EJB
7、 如何在weblogic中進(jìn)行ssl配置與客戶端的認(rèn)證配置或說說j2ee(標(biāo)準(zhǔn))進(jìn)行ssl的配置
缺省安裝中使用DemoIdentity.jks和DemoTrust.jks  KeyStore實(shí)現(xiàn)SSL，需要配置服務(wù)器使用Enable SSL，配置其端口，在產(chǎn)品模式下需要從CA獲取私有密鑰和數(shù)字證書，創(chuàng)建identity和trust keystore，裝載獲得的密鑰和數(shù)字證書?？梢耘渲么薙SL連接是單向還是雙向的。
   8、在weblogic中發(fā)布ejb需涉及到哪些配置文件
不同類型的EJB涉及的配置文件不同，都涉及到的配置文件包括ejb-jar.xml,weblogic-ejb-jar.xmlCMP實(shí)體Bean一般還需要weblogic-cmp-rdbms-jar.xml
   9、EJB需直接實(shí)現(xiàn)它的業(yè)務(wù)接口或Home接口嗎,請(qǐng)簡(jiǎn)述理由.
遠(yuǎn)程接口和Home接口不需要直接實(shí)現(xiàn)，他們的實(shí)現(xiàn)代碼是由服務(wù)器產(chǎn)生的，程序運(yùn)行中對(duì)應(yīng)實(shí)現(xiàn)類會(huì)作為對(duì)應(yīng)接口類型的實(shí)例被使用。
  10、說說在weblogic中開發(fā)消息Bean時(shí)的persistent與non-persisten的差別
persistent方式的MDB可以保證消息傳遞的可靠性,也就是如果EJB容器出現(xiàn)問題而JMS服務(wù)器依然會(huì)將消息在此MDB可用的時(shí)候發(fā)送過來，而non－persistent方式的消息將被丟棄。
  11、說說你所熟悉或聽說過的j2ee中的幾種常用模式?及對(duì)設(shè)計(jì)模式的一些看法
   Session Facade Pattern：使用SessionBean訪問EntityBean
Message Facade Pattern：實(shí)現(xiàn)異步調(diào)用
EJB Command Pattern：使用Command JavaBeans取代SessionBean，實(shí)現(xiàn)輕量級(jí)訪問
Data Transfer Object Factory：通過DTO Factory簡(jiǎn)化EntityBean數(shù)據(jù)提供特性
Generic Attribute Access：通過AttibuteAccess接口簡(jiǎn)化EntityBean數(shù)據(jù)提供特性
Business Interface：通過遠(yuǎn)程（本地）接口和Bean類實(shí)現(xiàn)相同接口規(guī)范業(yè)務(wù)邏輯一致性
ＥＪＢ架構(gòu)的設(shè)計(jì)好壞將直接影響系統(tǒng)的性能、可擴(kuò)展性、可維護(hù)性、組件可重用性及開發(fā)效率。項(xiàng)目越復(fù)雜，項(xiàng)目隊(duì)伍越龐大則越能體現(xiàn)良好設(shè)計(jì)的重要性。
轉(zhuǎn)載自：http://blog.csdn.net/laou2008/archive/2005/11/15/529519.aspx

西門子的一道筆試題

設(shè)計(jì)一個(gè)函數(shù)，形式如: int func(unsigned int)，要求求出不大于輸入?yún)?shù)的最大的素?cái)?shù)，比如輸入12，返回11。

轉(zhuǎn)載自：http://community.csdn.net/Expert/topic/4368/4368551.xml?temp=.4177057

微軟MSN在南大的筆試題

羅馬數(shù)字共有七個(gè)，即
I(1)，V(5)，X(10)，L(50)，C(100)，D(500)，M(1000)。

按照下面三條規(guī)則可以表示任意正整數(shù)。

重復(fù)數(shù)次：一個(gè)羅馬數(shù)字重復(fù)幾次，就表示這個(gè)數(shù)的幾倍。

右加左減：在一個(gè)較大的羅馬數(shù)字的右邊記上一個(gè)較小的羅馬數(shù)字，
表示大數(shù)字加小數(shù)字。在一個(gè)較大的數(shù)字的左邊記上一個(gè)較小的羅
馬數(shù)字，表示大數(shù)字減小數(shù)字。但是，左減不能跨越等級(jí)。
比如，99不可以用IC表示，用XCIX表示

基本數(shù)字Ⅰ、X 、C 中的任何一個(gè),自身連用構(gòu)成數(shù)目,或者放在大數(shù)的右邊連用構(gòu)成數(shù)目,都不能超過三個(gè),比如40不能用XXXX,而用XL表示

設(shè)計(jì)一個(gè)函數(shù),將100(包括100)以內(nèi)的整數(shù)轉(zhuǎn)換成羅馬數(shù)字,超過100不考慮
int itor(int n,char* buf,int bufLength)
其中,n是要轉(zhuǎn)換的整數(shù),buf是要輸出的字符串,bufLength是buf的字符長(zhǎng)度
成功,返回0,否則,返回 -1;

比如:
char buf[256];
result = itor(n,buf,sizeof(buf));

when n = 28; result = 0, 輸出"XXVIII"；
when n = 72; result = 0, 輸出"LXXII";

轉(zhuǎn)載自：http://community.csdn.net/Expert/topic/4386/4386877.xml?temp=.411175

Google文件系統(tǒng)
GFS是一個(gè)可擴(kuò)展的分布式文件系統(tǒng)，用于大型的、分布式的、對(duì)大量數(shù)據(jù)進(jìn)行訪問的應(yīng)用。它運(yùn)行于廉價(jià)的普通硬件上，但可以提供容錯(cuò)功能。它可以給大量的用戶提供總體性能較高的服務(wù)。
1、設(shè)計(jì)概覽
（1）設(shè)計(jì)想定
GFS與過去的分布式文件系統(tǒng)有很多相同的目標(biāo)，但GFS的設(shè)計(jì)受到了當(dāng)前及預(yù)期的應(yīng)用方面的工作量及技術(shù)環(huán)境的驅(qū)動(dòng)，這反映了它與早期的文件系統(tǒng)明顯不同的設(shè)想。這就需要對(duì)傳統(tǒng)的選擇進(jìn)行重新檢驗(yàn)并進(jìn)行完全不同的設(shè)計(jì)觀點(diǎn)的探索。
GFS與以往的文件系統(tǒng)的不同的觀點(diǎn)如下：
1、部件錯(cuò)誤不再被當(dāng)作異常，而是將其作為常見的情況加以處理。因?yàn)槲募到y(tǒng)由成百上千個(gè)用于存儲(chǔ)的機(jī)器構(gòu)成，而這些機(jī)器是由廉價(jià)的普通部件組成并被大量的客戶機(jī)訪問。部件的數(shù)量和質(zhì)量使得一些機(jī)器隨時(shí)都有可能無法工作并且有一部分還可能無法恢復(fù)。所以實(shí)時(shí)地監(jiān)控、錯(cuò)誤檢測(cè)、容錯(cuò)、自動(dòng)恢復(fù)對(duì)系統(tǒng)來說必不可少。
2、按照傳統(tǒng)的標(biāo)準(zhǔn)，文件都非常大。長(zhǎng)度達(dá)幾個(gè)GB的文件是很平常的。每個(gè)文件通常包含很多應(yīng)用對(duì)象。當(dāng)經(jīng)常要處理快速增長(zhǎng)的、包含數(shù)以萬計(jì)的對(duì)象、長(zhǎng)度達(dá)TB的數(shù)據(jù)集時(shí)，我們很難管理成千上萬的KB規(guī)模的文件塊，即使底層文件系統(tǒng)提供支持。因此，設(shè)計(jì)中操作的參數(shù)、塊的大小必須要重新考慮。對(duì)大型的文件的管理一定要能做到高效，對(duì)小型的文件也必須支持，但不必優(yōu)化。
3、大部分文件的更新是通過添加新數(shù)據(jù)完成的，而不是改變已存在的數(shù)據(jù)。在一個(gè)文件中隨機(jī)的操作在實(shí)踐中幾乎不存在。一旦寫完，文件就只可讀，很多數(shù)據(jù)都有這些特性。一些數(shù)據(jù)可能組成一個(gè)大倉庫以供數(shù)據(jù)分析程序掃描。有些是運(yùn)行中的程序連續(xù)產(chǎn)生的數(shù)據(jù)流。有些是檔案性質(zhì)的數(shù)據(jù)，有些是在某個(gè)機(jī)器上產(chǎn)生、在另外一個(gè)機(jī)器上處理的中間數(shù)據(jù)。由于這些對(duì)大型文件的訪問方式，添加操作成為性能優(yōu)化和原子性保證的焦點(diǎn)。而在客戶機(jī)中緩存數(shù)據(jù)塊則失去了吸引力。
4、工作量主要由兩種讀操作構(gòu)成：對(duì)大量數(shù)據(jù)的流方式的讀操作和對(duì)少量數(shù)據(jù)的隨機(jī)方式的讀操作。在前一種讀操作中，可能要讀幾百KB，通常達(dá) 1MB和更多。來自同一個(gè)客戶的連續(xù)操作通常會(huì)讀文件的一個(gè)連續(xù)的區(qū)域。隨機(jī)的讀操作通常在一個(gè)隨機(jī)的偏移處讀幾個(gè)KB。性能敏感的應(yīng)用程序通常將對(duì)少量數(shù)據(jù)的讀操作進(jìn)行分類并進(jìn)行批處理以使得讀操作穩(wěn)定地向前推進(jìn)，而不要讓它來來回回的讀。
5、工作量還包含許多對(duì)大量數(shù)據(jù)進(jìn)行的、連續(xù)的、向文件添加數(shù)據(jù)的寫操作。所寫的數(shù)據(jù)的規(guī)模和讀相似。一旦寫完，文件很少改動(dòng)。在隨機(jī)位置對(duì)少量數(shù)據(jù)的寫操作也支持，但不必非常高效。
6、系統(tǒng)必須高效地實(shí)現(xiàn)定義完好的大量客戶同時(shí)向同一個(gè)文件的添加操作的語義。
（2）系統(tǒng)接口
GFS提供了一個(gè)相似地文件系統(tǒng)界面，雖然它沒有向POSIX那樣實(shí)現(xiàn)標(biāo)準(zhǔn)的API。文件在目錄中按層次組織起來并由路徑名標(biāo)識(shí)。
（3）體系結(jié)構(gòu)：
一個(gè)GFS集群由一個(gè)master和大量的chunkserver構(gòu)成，并被許多客戶（Client）訪問。如圖1所示。Master和 chunkserver通常是運(yùn)行用戶層服務(wù)進(jìn)程的Linux機(jī)器。只要資源和可靠性允許，chunkserver和client可以運(yùn)行在同一個(gè)機(jī)器上。
文件被分成固定大小的塊。每個(gè)塊由一個(gè)不變的、全局唯一的64位的chunk－h(huán)andle標(biāo)識(shí)，chunk－h(huán)andle是在塊創(chuàng)建時(shí)由 master分配的。ChunkServer將塊當(dāng)作Linux文件存儲(chǔ)在本地磁盤并可以讀和寫由chunk－h(huán)andle和位區(qū)間指定的數(shù)據(jù)。出于可靠性考慮，每一個(gè)塊被復(fù)制到多個(gè)chunkserver上。默認(rèn)情況下，保存3個(gè)副本，但這可以由用戶指定。
Master維護(hù)文件系統(tǒng)所以的元數(shù)據(jù)（metadata），包括名字空間、訪問控制信息、從文件到塊的映射以及塊的當(dāng)前位置。它也控制系統(tǒng)范圍的活動(dòng)，如塊租約（lease）管理，孤兒塊的垃圾收集，chunkserver間的塊遷移。Master定期通過HeartBeat消息與每一個(gè) chunkserver通信，給chunkserver傳遞指令并收集它的狀態(tài)。
與每個(gè)應(yīng)用相聯(lián)的GFS客戶代碼實(shí)現(xiàn)了文件系統(tǒng)的API并與master和chunkserver通信以代表應(yīng)用程序讀和寫數(shù)據(jù)。客戶與master的交換只限于對(duì)元數(shù)據(jù)（metadata）的操作，所有數(shù)據(jù)方面的通信都直接和chunkserver聯(lián)系。
客戶和chunkserver都不緩存文件數(shù)據(jù)。因?yàn)橛脩艟彺娴囊嫣幬⒑跗湮?，這是由于數(shù)據(jù)太多或工作集太大而無法緩存。不緩存數(shù)據(jù)簡(jiǎn)化了客戶程序和整個(gè)系統(tǒng)，因?yàn)椴槐乜紤]緩存的一致性問題。但用戶緩存元數(shù)據(jù)（metadata）。Chunkserver也不必緩存文件，因?yàn)閴K時(shí)作為本地文件存儲(chǔ)的。
（4）單master。
只有一個(gè)master也極大的簡(jiǎn)化了設(shè)計(jì)并使得master可以根據(jù)全局情況作出先進(jìn)的塊放置和復(fù)制決定。但是我們必須要將master對(duì)讀和寫的參與減至最少，這樣它才不會(huì)成為系統(tǒng)的瓶頸。Client從來不會(huì)從master讀和寫文件數(shù)據(jù)。Client只是詢問master它應(yīng)該和哪個(gè) chunkserver聯(lián)系。Client在一段限定的時(shí)間內(nèi)將這些信息緩存，在后續(xù)的操作中Client直接和chunkserver交互。
以圖1解釋一下一個(gè)簡(jiǎn)單的讀操作的交互。
1、client使用固定的塊大小將應(yīng)用程序指定的文件名和字節(jié)偏移轉(zhuǎn)換成文件的一個(gè)塊索引（chunk index）。
2、給master發(fā)送一個(gè)包含文件名和塊索引的請(qǐng)求。
3、master回應(yīng)對(duì)應(yīng)的chunk handle和副本的位置（多個(gè)副本）。
4、client以文件名和塊索引為鍵緩存這些信息。（handle和副本的位置）。
5、Client 向其中一個(gè)副本發(fā)送一個(gè)請(qǐng)求，很可能是最近的一個(gè)副本。請(qǐng)求指定了chunk handle（chunkserver以chunk handle標(biāo)識(shí)chunk）和塊內(nèi)的一個(gè)字節(jié)區(qū)間。
6、除非緩存的信息不再有效（cache for a limited time）或文件被重新打開，否則以后對(duì)同一個(gè)塊的讀操作不再需要client和master間的交互。
通常Client可以在一個(gè)請(qǐng)求中詢問多個(gè)chunk的地址，而master也可以很快回應(yīng)這些請(qǐng)求。
（5）塊規(guī)模：
塊規(guī)模是設(shè)計(jì)中的一個(gè)關(guān)鍵參數(shù)。我們選擇的是64MB，這比一般的文件系統(tǒng)的塊規(guī)模要大的多。每個(gè)塊的副本作為一個(gè)普通的Linux文件存儲(chǔ)，在需要的時(shí)候可以擴(kuò)展。
塊規(guī)模較大的好處有：
1、減少client和master之間的交互。因?yàn)樽x寫同一個(gè)塊只是要在開始時(shí)向master請(qǐng)求塊位置信息。對(duì)于讀寫大型文件這種減少尤為重要。即使對(duì)于訪問少量數(shù)據(jù)的隨機(jī)讀操作也可以很方便的為一個(gè)規(guī)模達(dá)幾個(gè)TB的工作集緩緩存塊位置信息。
2、Client在一個(gè)給定的塊上很可能執(zhí)行多個(gè)操作，和一個(gè)chunkserver保持較長(zhǎng)時(shí)間的TCP連接可以減少網(wǎng)絡(luò)負(fù)載。
3、這減少了master上保存的元數(shù)據(jù)（metadata）的規(guī)模，從而使得可以將metadata放在內(nèi)存中。這又會(huì)帶來一些別的好處。
不利的一面：
一個(gè)小文件可能只包含一個(gè)塊，如果很多Client訪問改文件的話，存儲(chǔ)這些塊的chunkserver將成為訪問的熱點(diǎn)。但在實(shí)際應(yīng)用中，應(yīng)用程序通常順序地讀包含多個(gè)塊的文件，所以這不是一個(gè)主要問題。
（6）元數(shù)據(jù)（metadata）：
master存儲(chǔ)了三中類型的metadata：文件的名字空間和塊的名字空間，從文件到塊的映射，塊的副本的位置。所有的metadata都放在內(nèi)存中。前兩種類型的metadata通過向操作日志登記修改而保持不變，操作日志存儲(chǔ)在master的本地磁盤并在幾個(gè)遠(yuǎn)程機(jī)器上留有副本。使用日志使得我們可以很簡(jiǎn)單地、可靠地更新master的狀態(tài)，即使在master崩潰的情況下也不會(huì)有不一致的問題。相反，mater在每次啟動(dòng)以及當(dāng)有 chuankserver加入的時(shí)候詢問每個(gè)chunkserver的所擁有的塊的情況。
A、內(nèi)存數(shù)據(jù)結(jié)構(gòu)：
因?yàn)閙etadata存儲(chǔ)在內(nèi)存中，所以master的操作很快。進(jìn)一步，master可以輕易而且高效地定期在后臺(tái)掃描它的整個(gè)狀態(tài)。這種定期地掃描被用于實(shí)現(xiàn)塊垃圾收集、chunkserver出現(xiàn)故障時(shí)的副本復(fù)制、為平衡負(fù)載和磁盤空間而進(jìn)行的塊遷移。
這種方法的一個(gè)潛在的問題就是塊的數(shù)量也即整個(gè)系統(tǒng)的容量是否受限與master的內(nèi)存。實(shí)際上，這并不是一個(gè)嚴(yán)重的問題。Master為每個(gè) 64MB的塊維護(hù)的metadata不足64個(gè)字節(jié)。除了最后一塊，文件所有的塊都是滿的。類似的，每個(gè)文件的名字空間數(shù)據(jù)也不足64個(gè)字節(jié)，因?yàn)槲募且砸环N事先確定的壓縮方式存儲(chǔ)的.如果要支持更大的文件系統(tǒng)，那么增加一些內(nèi)存的方法對(duì)于我們將元數(shù)據(jù)（metadata）保存在內(nèi)存種所獲得的簡(jiǎn)單性、可靠性、高性能和靈活性來說，這只是一個(gè)很小的代價(jià)。
B、塊位置：
master并不為chunkserver所擁有的塊的副本的保存一個(gè)不變的記錄。它在啟動(dòng)時(shí)通過簡(jiǎn)單的查詢來獲得這些信息。Master可以保持這些信息的更新，因?yàn)樗刂扑袎K的放置并通過HeartBeat消息來監(jiān)控chunkserver的狀態(tài)。
這樣做的好處：因?yàn)閏hunkserver可能加入或離開集群、改變路徑名、崩潰、重啟等，一個(gè)集群重有成百個(gè)server，這些事件經(jīng)常發(fā)生，這種方法就排除了master與chunkserver之間的同步問題。
另一個(gè)原因是：只有chunkserver才能確定它自己到底有哪些塊，由于錯(cuò)誤，chunkserver中的一些塊可能會(huì)很自然的消失，這樣在master中就沒有必要為此保存一個(gè)不變的記錄。
C、操作日志：
操作日志包含了對(duì)metadata所作的修改的歷史記錄。它作為邏輯時(shí)間線定義了并發(fā)操作的執(zhí)行順序。文件、塊以及它們的版本號(hào)都由它們被創(chuàng)建時(shí)的邏輯時(shí)間而唯一地、永久地被標(biāo)識(shí)。
操作日志是如此的重要，我們必須要將它可靠地保存起來，并且只有在metadata的改變固定下來之后才將變化呈現(xiàn)給用戶。所以我們將操作日志復(fù)制到數(shù)個(gè)遠(yuǎn)程的機(jī)器上，并且只有在將相應(yīng)的日志記錄寫到本地和遠(yuǎn)程的磁盤上之后才回答用戶的請(qǐng)求。
Master可以用操作日志來恢復(fù)它的文件系統(tǒng)的狀態(tài)。為了將啟動(dòng)時(shí)間減至最小，日志就必須要比較小。每當(dāng)日志的長(zhǎng)度增長(zhǎng)到超過一定的規(guī)模后，master就要檢查它的狀態(tài)，它可以從本地磁盤裝入最近的檢查點(diǎn)來恢復(fù)狀態(tài)。
創(chuàng)建一個(gè)檢查點(diǎn)比較費(fèi)時(shí)，master的內(nèi)部狀態(tài)是以一種在創(chuàng)建一個(gè)檢查點(diǎn)時(shí)并不耽誤即將到來的修改操作的方式來組織的。Master切換到一個(gè)新的日子文件并在一個(gè)單獨(dú)的線程中創(chuàng)建檢查點(diǎn)。這個(gè)新的檢查點(diǎn)記錄了切換前所有的修改。在一個(gè)有數(shù)十萬文件的集群中用一分鐘左右就能完成。創(chuàng)建完后，將它寫入本地和遠(yuǎn)程的磁盤。
（7）數(shù)據(jù)完整性
名字空間的修改必須是原子性的，它們只能有master處理：名字空間鎖保證了操作的原子性和正確性，而master的操作日志在全局范圍內(nèi)定義了這些操作的順序。
文件區(qū)間的狀態(tài)在修改之后依賴于修改的類型，不論操作成功還是失敗，也不論是不是并發(fā)操作。如果不論從哪個(gè)副本上讀，所有的客戶都看到同樣的數(shù)據(jù)，那么文件的這個(gè)區(qū)域就是一致的。如果文件的區(qū)域是一致的并且用戶可以看到修改操作所寫的數(shù)據(jù)，那么它就是已定義的。如果修改是在沒有并發(fā)寫操作的影響下完成的，那么受影響的區(qū)域是已定義的，所有的client都能看到寫的內(nèi)容。成功的并發(fā)寫操作是未定義但卻是一致的。失敗的修改將使區(qū)間處于不一致的狀態(tài)。
Write操作在應(yīng)用程序指定的偏移處寫入數(shù)據(jù)，而record append操作使得數(shù)據(jù)（記錄）即使在有并發(fā)修改操作的情況下也至少原子性的被加到GFS指定的偏移處，偏移地址被返回給用戶。
在一系列成功的修改操作后，最后的修改操作保證文件區(qū)域是已定義的。GFS通過對(duì)所有的副本執(zhí)行同樣順序的修改操作并且使用塊版本號(hào)檢測(cè)過時(shí)的副本（由于chunkserver退出而導(dǎo)致丟失修改）來做到這一點(diǎn)。
因?yàn)橛脩艟彺媪藭?huì)位置信息，所以在更新緩存之前有可能從一個(gè)過時(shí)的副本中讀取數(shù)據(jù)。但這有緩存的截止時(shí)間和文件的重新打開而受到限制。
在修改操作成功后，部件故障仍可以是數(shù)據(jù)受到破壞。GFS通過master和chunkserver間定期的handshake，借助校驗(yàn)和來檢測(cè)對(duì)數(shù)據(jù)的破壞。一旦檢測(cè)到，就從一個(gè)有效的副本盡快重新存儲(chǔ)。只有在GFS檢測(cè)前，所有的副本都失效，這個(gè)塊才會(huì)丟失。
2、系統(tǒng)交互
（1）租約（lease）和修改順序：
（2）數(shù)據(jù)流
我們的目標(biāo)是充分利用每個(gè)機(jī)器的網(wǎng)絡(luò)帶寬，避免網(wǎng)絡(luò)瓶頸和延遲
為了有效的利用網(wǎng)絡(luò)，我們將數(shù)據(jù)流和控制流分離。數(shù)據(jù)是以流水線的方式在選定的chunkerserver鏈上線性的傳遞的。每個(gè)機(jī)器的整個(gè)對(duì)外帶寬都被用作傳遞數(shù)據(jù)。為避免瓶頸，每個(gè)機(jī)器在收到數(shù)據(jù)后，將它收到數(shù)據(jù)盡快傳遞給離它最近的機(jī)器。
（3）原子性的record Append：
GFS提供了一個(gè)原子性的添加操作：record append。在傳統(tǒng)的寫操作中，client指定被寫數(shù)據(jù)的偏移位置，向同一個(gè)區(qū)間的并發(fā)的寫操作是不連續(xù)的：區(qū)間有可能包含來自多個(gè)client的數(shù)據(jù)碎片。在record append中， client只是指定數(shù)據(jù)。GFS在其選定的偏移出將數(shù)據(jù)至少原子性的加入文件一次，并將偏移返回給client。
在分布式的應(yīng)用中，不同機(jī)器上的許多client可能會(huì)同時(shí)向一個(gè)文件執(zhí)行添加操作，添加操作被頻繁使用。如果用傳統(tǒng)的write操作，可能需要額外的、復(fù)雜的、開銷較大的同步，例如通過分布式鎖管理。在我們的工作量中，這些文件通常以多個(gè)生產(chǎn)者單個(gè)消費(fèi)者隊(duì)列的方式或包含從多個(gè)不同 client的綜合結(jié)果。
Record append和前面講的write操作的控制流差不多，只是在primary上多了一些邏輯判斷。首先，client將數(shù)據(jù)發(fā)送到文件最后一塊的所有副本上。然后向primary發(fā)送請(qǐng)求。Primary檢查添加操作是否會(huì)導(dǎo)致該塊超過最大的規(guī)模（64M）。如果這樣，它將該塊擴(kuò)充到最大規(guī)模，并告訴其它副本做同樣的事，同時(shí)通知client該操作需要在下一個(gè)塊上重新嘗試。如果記錄滿足最大規(guī)模的要求，primary就會(huì)將數(shù)據(jù)添加到它的副本上，并告訴其它的副本在在同樣的偏移處寫數(shù)據(jù)，最后primary向client報(bào)告寫操作成功。如果在任何一個(gè)副本上record append操作失敗，client將重新嘗試該操作。這時(shí)候，同一個(gè)塊的副本可能包含不同的數(shù)據(jù)，因?yàn)橛械目赡軓?fù)制了全部的數(shù)據(jù)，有的可能只復(fù)制了部分。GFS不能保證所有的副本每個(gè)字節(jié)都是一樣的。它只保證每個(gè)數(shù)據(jù)作為一個(gè)原子單元被寫過至少一次。這個(gè)是這樣得出的：操作要是成功，數(shù)據(jù)必須在所有的副本上的同樣的偏移處被寫過。進(jìn)一步，從這以后，所有的副本至少和記錄一樣長(zhǎng)，所以后續(xù)的記錄將被指定到更高的偏移處或者一個(gè)不同的塊上，即使另一個(gè)副本成了primary。根據(jù)一致性保證，成功的record append操作的區(qū)間是已定義的。而受到干擾的區(qū)間是不一致的。
（4）快照（snapshot）
快照操作幾乎在瞬間構(gòu)造一個(gè)文件和目錄樹的副本，同時(shí)將正在進(jìn)行的其他修改操作對(duì)它的影響減至最小。
我們使用copy-on-write技術(shù)來實(shí)現(xiàn)snapshot。當(dāng)master受到一個(gè)snapshot請(qǐng)求時(shí)，它首先將要snapshot的文件上塊上的lease。這使得任何一個(gè)向這些塊寫數(shù)據(jù)的操作都必須和master交互以找到擁有l(wèi)ease的副本。這就給master一個(gè)創(chuàng)建這個(gè)塊的副本的機(jī)會(huì)。
副本被撤銷或終止后，master在磁盤上登記執(zhí)行的操作，然后復(fù)制源文件或目錄樹的metadata以對(duì)它的內(nèi)存狀態(tài)實(shí)施登記的操作。這個(gè)新創(chuàng)建的snapshot文件和源文件（其metadata）指向相同的塊（chunk）。
Snapshot之后，客戶第一次向chunk c寫的時(shí)候，它發(fā)一個(gè)請(qǐng)求給master以找到擁有l(wèi)ease的副本。Master注意到chunk c的引用記數(shù)比1大，它延遲對(duì)用戶的響應(yīng)，選擇一個(gè)chunk handle C’,然后要求每一有chunk c的副本的chunkserver創(chuàng)建一個(gè)塊C’。每個(gè)chunkserver在本地創(chuàng)建chunk C’避免了網(wǎng)絡(luò)開銷。從這以后和對(duì)別的塊的操作沒有什么區(qū)別。
3、MASTER操作
MASTER執(zhí)行所有名字空間的操作，除此之外，他還在系統(tǒng)范圍管理數(shù)據(jù)塊的復(fù)制：決定數(shù)據(jù)塊的放置方案，產(chǎn)生新數(shù)據(jù)塊并將其備份，和其他系統(tǒng)范圍的操作協(xié)同來確保數(shù)據(jù)備份的完整性，在所有的數(shù)據(jù)塊服務(wù)器之間平衡負(fù)載并收回沒有使用的存儲(chǔ)空間。
3.1 名字空間管理和加鎖
與傳統(tǒng)文件系統(tǒng)不同的是，GFS沒有與每個(gè)目錄相關(guān)的能列出其所有文件的數(shù)據(jù)結(jié)構(gòu)，它也不支持別名（unix中的硬連接或符號(hào)連接），不管是對(duì)文件或是目錄。GFS的名字空間邏輯上是從文件元數(shù)據(jù)到路徑名映射的一個(gè)查用表。
MASTER在執(zhí)行某個(gè)操作前都要獲得一系列鎖，例如，它要對(duì)/d1/d2…/dn/leaf執(zhí)行操作，則它必須獲得/d1，/d1/d2，…， /d1/d2/…/dn的讀鎖，/d1/d2…/dn/leaf的讀鎖或?qū)戞i（其中l(wèi)eaf可以使文件也可以是目錄）。MASTER操作的并行性和數(shù)據(jù)的一致性就是通過這些鎖來實(shí)現(xiàn)的。
3.2 備份存儲(chǔ)放置策略
一個(gè)GFS集群文件系統(tǒng)可能是多層分布的。一般情況下是成千上萬個(gè)文件塊服務(wù)器分布于不同的機(jī)架上，而這些文件塊服務(wù)器又被分布于不同機(jī)架上的客戶來訪問。因此，不同機(jī)架上的兩臺(tái)機(jī)器之間的通信可能通過一個(gè)或多個(gè)交換機(jī)。數(shù)據(jù)塊冗余配置策略要達(dá)到連個(gè)目的：最大的數(shù)據(jù)可靠性和可用性，最大的網(wǎng)絡(luò)帶寬利用率。因此，如果僅僅把數(shù)據(jù)的拷貝置于不同的機(jī)器上很難滿足這兩個(gè)要求，必須在不同的機(jī)架上進(jìn)行數(shù)據(jù)備份。這樣即使整個(gè)機(jī)架被毀或是掉線，也能確保數(shù)據(jù)的正常使用。這也使數(shù)據(jù)傳輸，尤其是讀數(shù)據(jù)，可以充分利用帶寬，訪問到多個(gè)機(jī)架，而寫操作，則不得不涉及到更多的機(jī)架。
3.3 產(chǎn)生、重復(fù)制、重平衡數(shù)據(jù)塊
當(dāng)MASTER產(chǎn)生新的數(shù)據(jù)塊時(shí)，如何放置新數(shù)據(jù)塊，要考慮如下幾個(gè)因素：（1）盡量放置在磁盤利用率低的數(shù)據(jù)塊服務(wù)器上，這樣，慢慢地各服務(wù)器的磁盤利用率就會(huì)達(dá)到平衡。（2）盡量控制在一個(gè)服務(wù)器上的“新創(chuàng)建”的次數(shù)。（3）由于上一小節(jié)討論的原因，我們需要把數(shù)據(jù)塊放置于不同的機(jī)架上。
MASTER在可用的數(shù)據(jù)塊備份低于用戶設(shè)定的數(shù)目時(shí)需要進(jìn)行重復(fù)制。這種情況源于多種原因：服務(wù)器不可用，數(shù)據(jù)被破壞，磁盤被破壞，或者備份數(shù)目被修改。每個(gè)被需要重復(fù)制的數(shù)據(jù)塊的優(yōu)先級(jí)根據(jù)以下幾項(xiàng)確定：第一是現(xiàn)在的數(shù)目距目標(biāo)的距離，對(duì)于能阻塞用戶程序的數(shù)據(jù)塊，我們也提高它的優(yōu)先級(jí)。最后， MASTER按照產(chǎn)生數(shù)據(jù)塊的原則復(fù)制數(shù)據(jù)塊，并把它們放到不同的機(jī)架內(nèi)的服務(wù)器上。
MASTER周期性的平衡各服務(wù)器上的負(fù)載：它檢查chunk分布和負(fù)載平衡，通過這種方式來填充一個(gè)新的服務(wù)器而不是把其他的內(nèi)容統(tǒng)統(tǒng)放置到它上面帶來大量的寫數(shù)據(jù)。數(shù)據(jù)塊放置的原則與上面討論的相同，此外，MASTER還決定那些數(shù)據(jù)塊要被移除，原則上他會(huì)清除那些空閑空間低于平均值的那些服務(wù)器。
3.4 垃圾收集
在一個(gè)文件被刪除之后，GFS并不立即收回磁盤空間，而是等到垃圾收集程序在文件和數(shù)據(jù)塊級(jí)的的檢查中收回。
當(dāng)一個(gè)文件被應(yīng)用程序刪除之后，MASTER會(huì)立即記錄下這些變化，但文件所占用的資源卻不會(huì)被立即收回，而是重新給文件命了一個(gè)隱藏的名字，并附上了刪除的時(shí)間戳。在MASTER定期檢查名字空間時(shí)，它刪除超過三天（可以設(shè)定）的隱藏的文件。在此之前，可以以一個(gè)新的名字來讀文件，還可以以前的名字恢復(fù)。當(dāng)隱藏的文件在名字空間中被刪除以后，它在內(nèi)存中的元數(shù)據(jù)即被擦除，這就有效地切斷了他和所有數(shù)據(jù)塊的聯(lián)系。
在一個(gè)相似的定期的名字空間檢查中，MASTER確認(rèn)孤兒數(shù)據(jù)塊（不屬于任何文件）并擦除他的元數(shù)據(jù)，在和MASTER的心跳信息交換中，每個(gè)服務(wù)器報(bào)告他所擁有的數(shù)據(jù)塊，MASTER返回元數(shù)據(jù)不在內(nèi)存的數(shù)據(jù)塊，服務(wù)器即可以刪除這些數(shù)據(jù)塊。
3.5 過時(shí)數(shù)據(jù)的探測(cè)
在數(shù)據(jù)更新時(shí)如果服務(wù)器停機(jī)了，那么他所保存的數(shù)據(jù)備份就會(huì)過時(shí)。對(duì)每個(gè)數(shù)據(jù)塊，MASTER設(shè)置了一個(gè)版本號(hào)來區(qū)別更新過的數(shù)據(jù)塊和過時(shí)的數(shù)據(jù)塊。
當(dāng)MASTER授權(quán)一個(gè)新的lease時(shí)，他會(huì)增加數(shù)據(jù)塊的版本號(hào)并會(huì)通知更新數(shù)據(jù)備份。MASTER和備份都會(huì)記錄下當(dāng)前的版本號(hào)，如果一個(gè)備份當(dāng)時(shí)不可用，那么他的版本號(hào)不可能提高，當(dāng)ChunkServer重新啟動(dòng)并向MASTER報(bào)告他的數(shù)據(jù)塊集時(shí)，MASTER就會(huì)發(fā)現(xiàn)過時(shí)的數(shù)據(jù)。
MASTER在定期的垃圾收集程序中清除過時(shí)的備份，在此以前，處于效率考慮，在各客戶及英大使，他會(huì)認(rèn)為根本不存在過時(shí)的數(shù)據(jù)。作為另一個(gè)安全措施， MASTER在給客戶及關(guān)于數(shù)據(jù)塊的應(yīng)答或是另外一個(gè)讀取數(shù)據(jù)的服務(wù)器數(shù)據(jù)是都會(huì)帶上版本信息，在操作前客戶機(jī)和服務(wù)器會(huì)驗(yàn)證版本信息以確保得到的是最新的數(shù)據(jù)。
4、容錯(cuò)和診斷
4.1 高可靠性
4.1.1 快速恢復(fù)
不管如何終止服務(wù)，MASTER和數(shù)據(jù)塊服務(wù)器都會(huì)在幾秒鐘內(nèi)恢復(fù)狀態(tài)和運(yùn)行。實(shí)際上，我們不對(duì)正常終止和不正常終止進(jìn)行區(qū)分，服務(wù)器進(jìn)程都會(huì)被切斷而終止。客戶機(jī)和其他的服務(wù)器會(huì)經(jīng)歷一個(gè)小小的中斷，然后它們的特定請(qǐng)求超時(shí)，重新連接重啟的服務(wù)器，重新請(qǐng)求。
4.1.2 數(shù)據(jù)塊備份
如上文所討論的，每個(gè)數(shù)據(jù)塊都會(huì)被備份到放到不同機(jī)架上的不同服務(wù)器上。對(duì)不同的名字空間，用戶可以設(shè)置不同的備份級(jí)別。在數(shù)據(jù)塊服務(wù)器掉線或是數(shù)據(jù)被破壞時(shí)，MASTER會(huì)按照需要來復(fù)制數(shù)據(jù)塊。
4.1.3 MASTER備份
為確?？煽啃?，MASTER的狀態(tài)、操作記錄和檢查點(diǎn)都在多臺(tái)機(jī)器上進(jìn)行了備份。一個(gè)操作只有在數(shù)據(jù)塊服務(wù)器硬盤上刷新并被記錄在MASTER和其備份的上之后才算是成功的。如果MASTER或是硬盤失敗，系統(tǒng)監(jiān)視器會(huì)發(fā)現(xiàn)并通過改變域名啟動(dòng)它的一個(gè)備份機(jī)，而客戶機(jī)則僅僅是使用規(guī)范的名稱來訪問，并不會(huì)發(fā)現(xiàn)MASTER的改變。
4.2 數(shù)據(jù)完整性
每個(gè)數(shù)據(jù)塊服務(wù)器都利用校驗(yàn)和來檢驗(yàn)存儲(chǔ)數(shù)據(jù)的完整性。原因：每個(gè)服務(wù)器隨時(shí)都有發(fā)生崩潰的可能性，并且在兩個(gè)服務(wù)器間比較數(shù)據(jù)塊也是不現(xiàn)實(shí)的，同時(shí)，在兩臺(tái)服務(wù)器間拷貝數(shù)據(jù)并不能保證數(shù)據(jù)的一致性。
每個(gè)Chunk按64kB的大小分成塊，每個(gè)塊有32位的校驗(yàn)和，校驗(yàn)和和日志存儲(chǔ)在一起，和用戶數(shù)據(jù)分開。
在讀數(shù)據(jù)時(shí)，服務(wù)器首先檢查與被讀內(nèi)容相關(guān)部分的校驗(yàn)和，因此，服務(wù)器不會(huì)傳播錯(cuò)誤的數(shù)據(jù)。如果所檢查的內(nèi)容和校驗(yàn)和不符，服務(wù)器就會(huì)給數(shù)據(jù)請(qǐng)求者返回一個(gè)錯(cuò)誤的信息，并把這個(gè)情況報(bào)告給MASTER。客戶機(jī)就會(huì)讀其他的服務(wù)器來獲取數(shù)據(jù)，而MASTER則會(huì)從其他的拷貝來復(fù)制數(shù)據(jù)，等到一個(gè)新的拷貝完成時(shí)，MASTER就會(huì)通知報(bào)告錯(cuò)誤的服務(wù)器刪除出錯(cuò)的數(shù)據(jù)塊。
附加寫數(shù)據(jù)時(shí)的校驗(yàn)和計(jì)算優(yōu)化了，因?yàn)檫@是主要的寫操作。我們只是更新增加部分的校驗(yàn)和，即使末尾部分的校驗(yàn)和數(shù)據(jù)已被損壞而我們沒有檢查出來，新的校驗(yàn)和與數(shù)據(jù)會(huì)不相符，這種沖突在下次使用時(shí)將會(huì)被檢查出來。
相反，如果是覆蓋現(xiàn)有數(shù)據(jù)的寫，在寫以前，我們必須檢查第一和最后一個(gè)數(shù)據(jù)塊，然后才能執(zhí)行寫操作，最后計(jì)算和記錄校驗(yàn)和。如果我們?cè)诟采w以前不先檢查首位數(shù)據(jù)塊，計(jì)算出的校驗(yàn)和則會(huì)因?yàn)闆]被覆蓋的數(shù)據(jù)而產(chǎn)生錯(cuò)誤。
在空閑時(shí)間，服務(wù)器會(huì)檢查不活躍的數(shù)據(jù)塊的校驗(yàn)和，這樣可以檢查出不經(jīng)常讀的數(shù)據(jù)的錯(cuò)誤。一旦錯(cuò)誤被檢查出來，服務(wù)器會(huì)拷貝一個(gè)正確的數(shù)據(jù)塊來代替錯(cuò)誤的。
4.3 診斷工具
廣泛而細(xì)致的診斷日志以微小的代價(jià)換取了在問題隔離、診斷、性能分析方面起到了重大的作用。GFS服務(wù)器用日志來記錄顯著的事件（例如服務(wù)器停機(jī)和啟動(dòng)）和遠(yuǎn)程的應(yīng)答。遠(yuǎn)程日志記錄機(jī)器之間的請(qǐng)求和應(yīng)答，通過收集不同機(jī)器上的日志記錄，并對(duì)它們進(jìn)行分析恢復(fù)，我們可以完整地重現(xiàn)活動(dòng)的場(chǎng)景，并用此來進(jìn)行錯(cuò)誤分析。
6 測(cè)量
6.1 測(cè)試環(huán)境
一臺(tái)主控機(jī)，兩臺(tái)主控機(jī)備份，16臺(tái)數(shù)據(jù)塊服務(wù)器，16臺(tái)客戶機(jī)。
每臺(tái)機(jī)器：2塊PIII1.4G處理器，2G內(nèi)存，2塊80G5400rpm的硬盤，1塊100Mbps全雙工網(wǎng)卡
19臺(tái)服務(wù)器連接到一個(gè)HP2524交換機(jī)上，16臺(tái)客戶機(jī)倆接到領(lǐng)外一臺(tái)交換機(jī)上，兩臺(tái)交換機(jī)通過1G的鏈路相連。


Google 2003年關(guān)于Google File System的論文

原文出處：http://www.irunnet.com/viewtopic.php?p=913&sid=4f05f5b8a26e7d0b0e2586190c175d0b#913 Confluence 是個(gè)Wiki服務(wù)器，很不錯(cuò)，安裝也很簡(jiǎn)單。
下載：http://www.atlassian.com/software/confluence/

破解和jira一樣。參考我的另外一篇隨筆：《破解JIRA》。