Sql优化是一项复杂的工作，以下的一些基本原则是本人看书时所记录下来的，很明确且没什么废话：

1．  索引的使用：

（1）.当插入的数据为数据表中的记录数量的10%以上，首先需要删除该表的索引来提高数据的插入效率，当数据插入后，再建立索引。

（2）.避免在索引列上使用函数或计算，在where子句中，如果索引是函数的一部分，优化器将不再使用索引而使用全表扫描。如：

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

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

(3).避免在索引列上使用not和 “!=”，索引只能告诉什么存在于表中，而不能告诉什么不存在于表中，当数据库遇到not 和 “!=”时，就会停止使用索引而去执行全表扫描。

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

 低效：select * from emp where deptno > 3

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

两者的区别在于，前者dbms将直接跳到第一个deptno等于4的记录，而后者将首先定位到deptno等于3的记录并且向前扫描到第一个deptno大于3的。

(5).非要对一个使用函数的列启用索引，基于函数的索引是一个较好的方案。

2. 游标的使用：

   当在海量的数据表中进行数据的删除、更新、插入操作时，用游标处理的效率是最慢的，但是游标又是必不可少的，所以正确使用游标十分重要：

   (1). 在数据抽取的源表中使用时间戳，这样每天的维表数据维护只针对更新日期为最新时间的数据来进行，大大减少需要维护的数据记录数。

   (2). 在insert和update维表时都加上一个条件来过滤维表中已经存在的记录，例如：

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

 ods_customer为数据源表。dim_customer为维表。

   (3). 使用显式的游标，因为隐式的游标将会执行两次操作，第一次检索记录，第二次检查too many rows这个exception,而显式游标不执行第二次操作。

3．  据抽取和上载时的sql优化：

(1). Where 子句中的连接顺序：

oracle采用自下而上的顺序解析where子句，根据这个原理，表之间的连接必须写在其他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). 删除全表时，用truncate 替代 delete,同时注意truncate只能在删除全表时适用，因为truncate是ddl而不是dml。

   (3). 尽量多使用commit

只要有可能就在程序中对每个delete,insert,update操作尽量多使用commit,这样系统性能会因为commit所释放的资源而大大提高。

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

   (5). 用not exists 替代 not in

   (6). 优化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：这样做排序就不必要了，效率会提高3到5倍。

   (8). 分离表和索引

       总是将你的表和索引建立在不同的表空间内，决不要将不属于oracle内部系统的对象存放到system表空间内。同时确保数据表空间和索引表空间置于不同的硬盘控制卡控制的硬盘上。

转自：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表中各部门的部门号，最高工资，最低工资
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 部门号 from emp where job = 'CLERK' group by deptno;

3 对于emp中最低工资小于1000的部门，列出job为'CLERK'的员工的部门号，最低工资，最高工资
select max(sal) as 最高工资,min(sal) as 最低工资,deptno as 部门号 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 根据部门号由高而低，工资有低而高列出每个员工的姓名，部门号，工资
select deptno as 部门号,ename as 姓名,sal as 工资 from emp order by deptno desc,sal asc

5 写出对上题的另一解决方法
（请补充）

6 列出'张三'所在部门中每个员工的姓名与部门号
select ename,deptno from emp where deptno = (select deptno from emp where ename = '张三')

7 列出每个员工的姓名，工作，部门号，部门名
select ename,job,emp.deptno,dept.dname from emp,dept where emp.deptno=dept.deptno

8 列出emp中工作为'CLERK'的员工的姓名，工作，部门号，部门名
select ename,job,dept.deptno,dname from emp,dept where dept.deptno=emp.deptno and job='CLERK'

9 对于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 对于dept表中，列出所有部门名，部门号，同时列出各部门工作为'CLERK'的员工名与工作
select dname as 部门名,dept.deptno as 部门号,ename as 员工名,job as 工作 from dept,emp
where dept.deptno *= emp.deptno and job = 'CLERK'

11 对于工资高于本部门平均水平的员工，列出部门号，姓名，工资，按部门号排序
select a.deptno as 部门号,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 对于emp，列出各个部门中平均工资高于本部门平均水平的员工数和部门号，按部门号排序
select count(a.sal) as 员工数,a.deptno as 部门号 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 对于emp中工资高于本部门平均水平，人数多与1人的，列出部门号，人数，按部门号排序
select count(a.empno) as 员工数,a.deptno as 部门号,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 对于emp中低于自己工资至少5人的员工，列出其部门号，姓名，工资，以及工资少于自己的人数
select a.deptno,a.ename,a.sal,(select count(b.ename) from emp as b where b.sal<a.sal) as 人数 from emp as a
where (select count(b.ename) from emp as b where b.sal<a.sal)>5

转自：http://blog.csdn.net/woolceo/archive/2006/03/02/614094.aspx

在开发部署PORTAL项目时，遇到异常：
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中没有发现com.bea.content.repo.i18n这个package.

重新安装了weblogic sp4，就不再出现这个错误了。

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...  阅读全文 经典面试题

一、面向对象的三个基本特征
   2、方法重载和方法重写的概念和区别
   3、接口和内部类、抽象类的特性
   4、文件读写的基本类
   **5、串行化的注意事项以及如何实现串行化
   6、线程的基本概念、线程的基本状态以及状态之间的关系
   7、线程的同步、如何实现线程的同步
   8、几种常用的数据结构及内部实现原理。
   9、Socket通信(TCP、UDP区别及Java实现方式)
  **10、Java的事件委托机制和垃圾回收机制
  11、JDBC调用数据库的基本步骤
  **12、解析XML文件的几种方式和区别
  13、Java四种基本权限的定义
  14、Java的国际化
二、JSP
   1、至少要能说出7个隐含对象以及他们的区别
  ** 2、forward 和redirect的区别
   3、JSP的常用指令
三、servlet
   1、什么情况下调用doGet()和doPost()？
   2、servlet的init()方法和service()方法的区别
   3、servlet的生命周期
   4、如何现实servlet的单线程模式
   5、servlet的配置
   6、四种会话跟踪技术
四、EJB
   **1、EJB容器提供的服务
 主要提供声明周期管理、代码产生、持续性管理、安全、事务管理、锁和并发行管理等服务。
   2、EJB的角色和三个对象
 EJB角色主要包括Bean开发者 应用组装者 部署者 系统管理员 EJB容器提供者 EJB服务器提供者
 三个对象是Remote（Local）接口、Home（LocalHome）接口，Bean类
   2、EJB的几种类型
 会话（Session）Bean ，实体（Entity）Bean 消息驱动的（Message Driven）Bean
 会话Bean又可分为有状态（Stateful）和无状态（Stateless）两种
 实体Bean可分为Bean管理的持续性（BMP）和容器管理的持续性（CMP）两种
   3、bean 实例的生命周期
 对于Stateless Session Bean、Entity Bean、Message Driven Bean一般存在缓冲池管理，而对于Entity Bean和Statefull Session Bean存在Cache管理，通常包含创建实例，设置上下文、创建EJB Object（create）、业务方法调用、remove等过程，对于存在缓冲池管理的Bean，在create之后实例并不从内存清除，而是采用缓冲池调度机制不断重用实例，而对于存在Cache管理的Bean则通过激活和去激活机制保持Bean的状态并限制内存中实例数量。
   4、激活机制
 以Statefull Session Bean 为例：其Cache大小决定了内存中可以同时存在的Bean实例的数量，根据MRU或NRU算法，实例在激活和去激活状态之间迁移，激活机制是当客户端调用某个EJB实例业务方法时，如果对应EJB Object发现自己没有绑定对应的Bean实例则从其去激活Bean存储中（通过序列化机制存储实例）回复（激活）此实例。状态变迁前会调用对应的ejbActive和ejbPassivate方法。
   5、remote接口和home接口主要作用
 remote接口定义了业务方法，用于EJB客户端调用业务方法
 home接口是EJB工厂用于创建和移除查找EJB实例
   6、客服端调用EJB对象的几个基本步骤
一、 设置JNDI服务工厂以及JNDI服务地址系统属性
二、 查找Home接口
三、 从Home接口调用Create方法创建Remote接口
四、 通过Remote接口调用其业务方法
五、数据库
   1、存储过程的编写
   2、基本的SQL语句
六、weblogic
1、 如何给weblogic指定大小的内存?
在启动Weblogic的脚本中（位于所在Domian对应服务器目录下的startServerName），增加set MEM_ARGS=-Xms32m -Xmx200m，可以调整最小内存为32M，最大200M
2、 如何设定的weblogic的热启动模式(开发模式)与产品发布模式?
可以在管理控制台中修改对应服务器的启动模式为开发或产品模式之一。或者修改服务的启动文件或者commenv文件，增加set PRODUCTION_MODE=true。
3、 如何启动时不需输入用户名与密码?
修改服务启动文件，增加 WLS_USER和WLS_PW项。也可以在boot.properties文件中增加加密过的用户名和密码.
4、 在weblogic管理制台中对一个应用域(或者说是一个网站,Domain)进行jms及ejb或连接池等相关信息进行配置后,实际保存在什么文件中?
保存在此Domain的config.xml文件中，它是服务器的核心配置文件。
5、 说说weblogic中一个Domain的缺省目录结构?比如要将一个简单的helloWorld.jsp放入何目录下,然的在浏览器上就可打入http://主机:端口号//helloword.jsp就可以看到运行结果了? 又比如这其中用到了一个自己写的javaBean该如何办?
Domain目录\服务器目录\applications，将应用目录放在此目录下将可以作为应用访问，如果是Web应用，应用目录需要满足Web应用目录要求，jsp文件可以直接放在应用目录中，Javabean需要放在应用目录的WEB-INF目录的classes目录中，设置服务器的缺省应用将可以实现在浏览器上无需输入应用名。
6、 如何查看在weblogic中已经发布的EJB?
可以使用管理控制台，在它的Deployment中可以查看所有已发布的EJB
7、 如何在weblogic中进行ssl配置与客户端的认证配置或说说j2ee(标准)进行ssl的配置
缺省安装中使用DemoIdentity.jks和DemoTrust.jks  KeyStore实现SSL，需要配置服务器使用Enable SSL，配置其端口，在产品模式下需要从CA获取私有密钥和数字证书，创建identity和trust keystore，装载获得的密钥和数字证书。可以配置此SSL连接是单向还是双向的。
   8、在weblogic中发布ejb需涉及到哪些配置文件
不同类型的EJB涉及的配置文件不同，都涉及到的配置文件包括ejb-jar.xml,weblogic-ejb-jar.xmlCMP实体Bean一般还需要weblogic-cmp-rdbms-jar.xml
   9、EJB需直接实现它的业务接口或Home接口吗,请简述理由.
远程接口和Home接口不需要直接实现，他们的实现代码是由服务器产生的，程序运行中对应实现类会作为对应接口类型的实例被使用。
  10、说说在weblogic中开发消息Bean时的persistent与non-persisten的差别
persistent方式的MDB可以保证消息传递的可靠性,也就是如果EJB容器出现问题而JMS服务器依然会将消息在此MDB可用的时候发送过来，而non－persistent方式的消息将被丢弃。
  11、说说你所熟悉或听说过的j2ee中的几种常用模式?及对设计模式的一些看法
   Session Facade Pattern：使用SessionBean访问EntityBean
Message Facade Pattern：实现异步调用
EJB Command Pattern：使用Command JavaBeans取代SessionBean，实现轻量级访问
Data Transfer Object Factory：通过DTO Factory简化EntityBean数据提供特性
Generic Attribute Access：通过AttibuteAccess接口简化EntityBean数据提供特性
Business Interface：通过远程（本地）接口和Bean类实现相同接口规范业务逻辑一致性
ＥＪＢ架构的设计好坏将直接影响系统的性能、可扩展性、可维护性、组件可重用性及开发效率。项目越复杂，项目队伍越庞大则越能体现良好设计的重要性。
转载自：http://blog.csdn.net/laou2008/archive/2005/11/15/529519.aspx

西门子的一道笔试题

设计一个函数，形式如: int func(unsigned int)，要求求出不大于输入参数的最大的素数，比如输入12，返回11。

转载自：http://community.csdn.net/Expert/topic/4368/4368551.xml?temp=.4177057

微软MSN在南大的笔试题

罗马数字共有七个，即
I(1)，V(5)，X(10)，L(50)，C(100)，D(500)，M(1000)。

按照下面三条规则可以表示任意正整数。

重复数次：一个罗马数字重复几次，就表示这个数的几倍。

右加左减：在一个较大的罗马数字的右边记上一个较小的罗马数字，
表示大数字加小数字。在一个较大的数字的左边记上一个较小的罗
马数字，表示大数字减小数字。但是，左减不能跨越等级。
比如，99不可以用IC表示，用XCIX表示

基本数字Ⅰ、X 、C 中的任何一个,自身连用构成数目,或者放在大数的右边连用构成数目,都不能超过三个,比如40不能用XXXX,而用XL表示

设计一个函数,将100(包括100)以内的整数转换成罗马数字,超过100不考虑
int itor(int n,char* buf,int bufLength)
其中,n是要转换的整数,buf是要输出的字符串,bufLength是buf的字符长度
成功,返回0,否则,返回 -1;

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

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

转载自：http://community.csdn.net/Expert/topic/4386/4386877.xml?temp=.411175

Google文件系统
GFS是一个可扩展的分布式文件系统，用于大型的、分布式的、对大量数据进行访问的应用。它运行于廉价的普通硬件上，但可以提供容错功能。它可以给大量的用户提供总体性能较高的服务。
1、设计概览
（1）设计想定
GFS与过去的分布式文件系统有很多相同的目标，但GFS的设计受到了当前及预期的应用方面的工作量及技术环境的驱动，这反映了它与早期的文件系统明显不同的设想。这就需要对传统的选择进行重新检验并进行完全不同的设计观点的探索。
GFS与以往的文件系统的不同的观点如下：
1、部件错误不再被当作异常，而是将其作为常见的情况加以处理。因为文件系统由成百上千个用于存储的机器构成，而这些机器是由廉价的普通部件组成并被大量的客户机访问。部件的数量和质量使得一些机器随时都有可能无法工作并且有一部分还可能无法恢复。所以实时地监控、错误检测、容错、自动恢复对系统来说必不可少。
2、按照传统的标准，文件都非常大。长度达几个GB的文件是很平常的。每个文件通常包含很多应用对象。当经常要处理快速增长的、包含数以万计的对象、长度达TB的数据集时，我们很难管理成千上万的KB规模的文件块，即使底层文件系统提供支持。因此，设计中操作的参数、块的大小必须要重新考虑。对大型的文件的管理一定要能做到高效，对小型的文件也必须支持，但不必优化。
3、大部分文件的更新是通过添加新数据完成的，而不是改变已存在的数据。在一个文件中随机的操作在实践中几乎不存在。一旦写完，文件就只可读，很多数据都有这些特性。一些数据可能组成一个大仓库以供数据分析程序扫描。有些是运行中的程序连续产生的数据流。有些是档案性质的数据，有些是在某个机器上产生、在另外一个机器上处理的中间数据。由于这些对大型文件的访问方式，添加操作成为性能优化和原子性保证的焦点。而在客户机中缓存数据块则失去了吸引力。
4、工作量主要由两种读操作构成：对大量数据的流方式的读操作和对少量数据的随机方式的读操作。在前一种读操作中，可能要读几百KB，通常达 1MB和更多。来自同一个客户的连续操作通常会读文件的一个连续的区域。随机的读操作通常在一个随机的偏移处读几个KB。性能敏感的应用程序通常将对少量数据的读操作进行分类并进行批处理以使得读操作稳定地向前推进，而不要让它来来回回的读。
5、工作量还包含许多对大量数据进行的、连续的、向文件添加数据的写操作。所写的数据的规模和读相似。一旦写完，文件很少改动。在随机位置对少量数据的写操作也支持，但不必非常高效。
6、系统必须高效地实现定义完好的大量客户同时向同一个文件的添加操作的语义。
（2）系统接口
GFS提供了一个相似地文件系统界面，虽然它没有向POSIX那样实现标准的API。文件在目录中按层次组织起来并由路径名标识。
（3）体系结构：
一个GFS集群由一个master和大量的chunkserver构成，并被许多客户（Client）访问。如图1所示。Master和 chunkserver通常是运行用户层服务进程的Linux机器。只要资源和可靠性允许，chunkserver和client可以运行在同一个机器上。
文件被分成固定大小的块。每个块由一个不变的、全局唯一的64位的chunk－handle标识，chunk－handle是在块创建时由 master分配的。ChunkServer将块当作Linux文件存储在本地磁盘并可以读和写由chunk－handle和位区间指定的数据。出于可靠性考虑，每一个块被复制到多个chunkserver上。默认情况下，保存3个副本，但这可以由用户指定。
Master维护文件系统所以的元数据（metadata），包括名字空间、访问控制信息、从文件到块的映射以及块的当前位置。它也控制系统范围的活动，如块租约（lease）管理，孤儿块的垃圾收集，chunkserver间的块迁移。Master定期通过HeartBeat消息与每一个 chunkserver通信，给chunkserver传递指令并收集它的状态。
与每个应用相联的GFS客户代码实现了文件系统的API并与master和chunkserver通信以代表应用程序读和写数据。客户与master的交换只限于对元数据（metadata）的操作，所有数据方面的通信都直接和chunkserver联系。
客户和chunkserver都不缓存文件数据。因为用户缓存的益处微乎其微，这是由于数据太多或工作集太大而无法缓存。不缓存数据简化了客户程序和整个系统，因为不必考虑缓存的一致性问题。但用户缓存元数据（metadata）。Chunkserver也不必缓存文件，因为块时作为本地文件存储的。
（4）单master。
只有一个master也极大的简化了设计并使得master可以根据全局情况作出先进的块放置和复制决定。但是我们必须要将master对读和写的参与减至最少，这样它才不会成为系统的瓶颈。Client从来不会从master读和写文件数据。Client只是询问master它应该和哪个 chunkserver联系。Client在一段限定的时间内将这些信息缓存，在后续的操作中Client直接和chunkserver交互。
以图1解释一下一个简单的读操作的交互。
1、client使用固定的块大小将应用程序指定的文件名和字节偏移转换成文件的一个块索引（chunk index）。
2、给master发送一个包含文件名和块索引的请求。
3、master回应对应的chunk handle和副本的位置（多个副本）。
4、client以文件名和块索引为键缓存这些信息。（handle和副本的位置）。
5、Client 向其中一个副本发送一个请求，很可能是最近的一个副本。请求指定了chunk handle（chunkserver以chunk handle标识chunk）和块内的一个字节区间。
6、除非缓存的信息不再有效（cache for a limited time）或文件被重新打开，否则以后对同一个块的读操作不再需要client和master间的交互。
通常Client可以在一个请求中询问多个chunk的地址，而master也可以很快回应这些请求。
（5）块规模：
块规模是设计中的一个关键参数。我们选择的是64MB，这比一般的文件系统的块规模要大的多。每个块的副本作为一个普通的Linux文件存储，在需要的时候可以扩展。
块规模较大的好处有：
1、减少client和master之间的交互。因为读写同一个块只是要在开始时向master请求块位置信息。对于读写大型文件这种减少尤为重要。即使对于访问少量数据的随机读操作也可以很方便的为一个规模达几个TB的工作集缓缓存块位置信息。
2、Client在一个给定的块上很可能执行多个操作，和一个chunkserver保持较长时间的TCP连接可以减少网络负载。
3、这减少了master上保存的元数据（metadata）的规模，从而使得可以将metadata放在内存中。这又会带来一些别的好处。
不利的一面：
一个小文件可能只包含一个块，如果很多Client访问改文件的话，存储这些块的chunkserver将成为访问的热点。但在实际应用中，应用程序通常顺序地读包含多个块的文件，所以这不是一个主要问题。
（6）元数据（metadata）：
master存储了三中类型的metadata：文件的名字空间和块的名字空间，从文件到块的映射，块的副本的位置。所有的metadata都放在内存中。前两种类型的metadata通过向操作日志登记修改而保持不变，操作日志存储在master的本地磁盘并在几个远程机器上留有副本。使用日志使得我们可以很简单地、可靠地更新master的状态，即使在master崩溃的情况下也不会有不一致的问题。相反，mater在每次启动以及当有 chuankserver加入的时候询问每个chunkserver的所拥有的块的情况。
A、内存数据结构：
因为metadata存储在内存中，所以master的操作很快。进一步，master可以轻易而且高效地定期在后台扫描它的整个状态。这种定期地扫描被用于实现块垃圾收集、chunkserver出现故障时的副本复制、为平衡负载和磁盘空间而进行的块迁移。
这种方法的一个潜在的问题就是块的数量也即整个系统的容量是否受限与master的内存。实际上，这并不是一个严重的问题。Master为每个 64MB的块维护的metadata不足64个字节。除了最后一块，文件所有的块都是满的。类似的，每个文件的名字空间数据也不足64个字节，因为文件名是以一种事先确定的压缩方式存储的.如果要支持更大的文件系统，那么增加一些内存的方法对于我们将元数据（metadata）保存在内存种所获得的简单性、可靠性、高性能和灵活性来说，这只是一个很小的代价。
B、块位置：
master并不为chunkserver所拥有的块的副本的保存一个不变的记录。它在启动时通过简单的查询来获得这些信息。Master可以保持这些信息的更新，因为它控制所有块的放置并通过HeartBeat消息来监控chunkserver的状态。
这样做的好处：因为chunkserver可能加入或离开集群、改变路径名、崩溃、重启等，一个集群重有成百个server，这些事件经常发生，这种方法就排除了master与chunkserver之间的同步问题。
另一个原因是：只有chunkserver才能确定它自己到底有哪些块，由于错误，chunkserver中的一些块可能会很自然的消失，这样在master中就没有必要为此保存一个不变的记录。
C、操作日志：
操作日志包含了对metadata所作的修改的历史记录。它作为逻辑时间线定义了并发操作的执行顺序。文件、块以及它们的版本号都由它们被创建时的逻辑时间而唯一地、永久地被标识。
操作日志是如此的重要，我们必须要将它可靠地保存起来，并且只有在metadata的改变固定下来之后才将变化呈现给用户。所以我们将操作日志复制到数个远程的机器上，并且只有在将相应的日志记录写到本地和远程的磁盘上之后才回答用户的请求。
Master可以用操作日志来恢复它的文件系统的状态。为了将启动时间减至最小，日志就必须要比较小。每当日志的长度增长到超过一定的规模后，master就要检查它的状态，它可以从本地磁盘装入最近的检查点来恢复状态。
创建一个检查点比较费时，master的内部状态是以一种在创建一个检查点时并不耽误即将到来的修改操作的方式来组织的。Master切换到一个新的日子文件并在一个单独的线程中创建检查点。这个新的检查点记录了切换前所有的修改。在一个有数十万文件的集群中用一分钟左右就能完成。创建完后，将它写入本地和远程的磁盘。
（7）数据完整性
名字空间的修改必须是原子性的，它们只能有master处理：名字空间锁保证了操作的原子性和正确性，而master的操作日志在全局范围内定义了这些操作的顺序。
文件区间的状态在修改之后依赖于修改的类型，不论操作成功还是失败，也不论是不是并发操作。如果不论从哪个副本上读，所有的客户都看到同样的数据，那么文件的这个区域就是一致的。如果文件的区域是一致的并且用户可以看到修改操作所写的数据，那么它就是已定义的。如果修改是在没有并发写操作的影响下完成的，那么受影响的区域是已定义的，所有的client都能看到写的内容。成功的并发写操作是未定义但却是一致的。失败的修改将使区间处于不一致的状态。
Write操作在应用程序指定的偏移处写入数据，而record append操作使得数据（记录）即使在有并发修改操作的情况下也至少原子性的被加到GFS指定的偏移处，偏移地址被返回给用户。
在一系列成功的修改操作后，最后的修改操作保证文件区域是已定义的。GFS通过对所有的副本执行同样顺序的修改操作并且使用块版本号检测过时的副本（由于chunkserver退出而导致丢失修改）来做到这一点。
因为用户缓存了会位置信息，所以在更新缓存之前有可能从一个过时的副本中读取数据。但这有缓存的截止时间和文件的重新打开而受到限制。
在修改操作成功后，部件故障仍可以是数据受到破坏。GFS通过master和chunkserver间定期的handshake，借助校验和来检测对数据的破坏。一旦检测到，就从一个有效的副本尽快重新存储。只有在GFS检测前，所有的副本都失效，这个块才会丢失。
2、系统交互
（1）租约（lease）和修改顺序：
（2）数据流
我们的目标是充分利用每个机器的网络带宽，避免网络瓶颈和延迟
为了有效的利用网络，我们将数据流和控制流分离。数据是以流水线的方式在选定的chunkerserver链上线性的传递的。每个机器的整个对外带宽都被用作传递数据。为避免瓶颈，每个机器在收到数据后，将它收到数据尽快传递给离它最近的机器。
（3）原子性的record Append：
GFS提供了一个原子性的添加操作：record append。在传统的写操作中，client指定被写数据的偏移位置，向同一个区间的并发的写操作是不连续的：区间有可能包含来自多个client的数据碎片。在record append中， client只是指定数据。GFS在其选定的偏移出将数据至少原子性的加入文件一次，并将偏移返回给client。
在分布式的应用中，不同机器上的许多client可能会同时向一个文件执行添加操作，添加操作被频繁使用。如果用传统的write操作，可能需要额外的、复杂的、开销较大的同步，例如通过分布式锁管理。在我们的工作量中，这些文件通常以多个生产者单个消费者队列的方式或包含从多个不同 client的综合结果。
Record append和前面讲的write操作的控制流差不多，只是在primary上多了一些逻辑判断。首先，client将数据发送到文件最后一块的所有副本上。然后向primary发送请求。Primary检查添加操作是否会导致该块超过最大的规模（64M）。如果这样，它将该块扩充到最大规模，并告诉其它副本做同样的事，同时通知client该操作需要在下一个块上重新尝试。如果记录满足最大规模的要求，primary就会将数据添加到它的副本上，并告诉其它的副本在在同样的偏移处写数据，最后primary向client报告写操作成功。如果在任何一个副本上record append操作失败，client将重新尝试该操作。这时候，同一个块的副本可能包含不同的数据，因为有的可能复制了全部的数据，有的可能只复制了部分。GFS不能保证所有的副本每个字节都是一样的。它只保证每个数据作为一个原子单元被写过至少一次。这个是这样得出的：操作要是成功，数据必须在所有的副本上的同样的偏移处被写过。进一步，从这以后，所有的副本至少和记录一样长，所以后续的记录将被指定到更高的偏移处或者一个不同的块上，即使另一个副本成了primary。根据一致性保证，成功的record append操作的区间是已定义的。而受到干扰的区间是不一致的。
（4）快照（snapshot）
快照操作几乎在瞬间构造一个文件和目录树的副本，同时将正在进行的其他修改操作对它的影响减至最小。
我们使用copy-on-write技术来实现snapshot。当master受到一个snapshot请求时，它首先将要snapshot的文件上块上的lease。这使得任何一个向这些块写数据的操作都必须和master交互以找到拥有lease的副本。这就给master一个创建这个块的副本的机会。
副本被撤销或终止后，master在磁盘上登记执行的操作，然后复制源文件或目录树的metadata以对它的内存状态实施登记的操作。这个新创建的snapshot文件和源文件（其metadata）指向相同的块（chunk）。
Snapshot之后，客户第一次向chunk c写的时候，它发一个请求给master以找到拥有lease的副本。Master注意到chunk c的引用记数比1大，它延迟对用户的响应，选择一个chunk handle C’,然后要求每一有chunk c的副本的chunkserver创建一个块C’。每个chunkserver在本地创建chunk C’避免了网络开销。从这以后和对别的块的操作没有什么区别。
3、MASTER操作
MASTER执行所有名字空间的操作，除此之外，他还在系统范围管理数据块的复制：决定数据块的放置方案，产生新数据块并将其备份，和其他系统范围的操作协同来确保数据备份的完整性，在所有的数据块服务器之间平衡负载并收回没有使用的存储空间。
3.1 名字空间管理和加锁
与传统文件系统不同的是，GFS没有与每个目录相关的能列出其所有文件的数据结构，它也不支持别名（unix中的硬连接或符号连接），不管是对文件或是目录。GFS的名字空间逻辑上是从文件元数据到路径名映射的一个查用表。
MASTER在执行某个操作前都要获得一系列锁，例如，它要对/d1/d2…/dn/leaf执行操作，则它必须获得/d1，/d1/d2，…， /d1/d2/…/dn的读锁，/d1/d2…/dn/leaf的读锁或写锁（其中leaf可以使文件也可以是目录）。MASTER操作的并行性和数据的一致性就是通过这些锁来实现的。
3.2 备份存储放置策略
一个GFS集群文件系统可能是多层分布的。一般情况下是成千上万个文件块服务器分布于不同的机架上，而这些文件块服务器又被分布于不同机架上的客户来访问。因此，不同机架上的两台机器之间的通信可能通过一个或多个交换机。数据块冗余配置策略要达到连个目的：最大的数据可靠性和可用性，最大的网络带宽利用率。因此，如果仅仅把数据的拷贝置于不同的机器上很难满足这两个要求，必须在不同的机架上进行数据备份。这样即使整个机架被毁或是掉线，也能确保数据的正常使用。这也使数据传输，尤其是读数据，可以充分利用带宽，访问到多个机架，而写操作，则不得不涉及到更多的机架。
3.3 产生、重复制、重平衡数据块
当MASTER产生新的数据块时，如何放置新数据块，要考虑如下几个因素：（1）尽量放置在磁盘利用率低的数据块服务器上，这样，慢慢地各服务器的磁盘利用率就会达到平衡。（2）尽量控制在一个服务器上的“新创建”的次数。（3）由于上一小节讨论的原因，我们需要把数据块放置于不同的机架上。
MASTER在可用的数据块备份低于用户设定的数目时需要进行重复制。这种情况源于多种原因：服务器不可用，数据被破坏，磁盘被破坏，或者备份数目被修改。每个被需要重复制的数据块的优先级根据以下几项确定：第一是现在的数目距目标的距离，对于能阻塞用户程序的数据块，我们也提高它的优先级。最后， MASTER按照产生数据块的原则复制数据块，并把它们放到不同的机架内的服务器上。
MASTER周期性的平衡各服务器上的负载：它检查chunk分布和负载平衡，通过这种方式来填充一个新的服务器而不是把其他的内容统统放置到它上面带来大量的写数据。数据块放置的原则与上面讨论的相同，此外，MASTER还决定那些数据块要被移除，原则上他会清除那些空闲空间低于平均值的那些服务器。
3.4 垃圾收集
在一个文件被删除之后，GFS并不立即收回磁盘空间，而是等到垃圾收集程序在文件和数据块级的的检查中收回。
当一个文件被应用程序删除之后，MASTER会立即记录下这些变化，但文件所占用的资源却不会被立即收回，而是重新给文件命了一个隐藏的名字，并附上了删除的时间戳。在MASTER定期检查名字空间时，它删除超过三天（可以设定）的隐藏的文件。在此之前，可以以一个新的名字来读文件，还可以以前的名字恢复。当隐藏的文件在名字空间中被删除以后，它在内存中的元数据即被擦除，这就有效地切断了他和所有数据块的联系。
在一个相似的定期的名字空间检查中，MASTER确认孤儿数据块（不属于任何文件）并擦除他的元数据，在和MASTER的心跳信息交换中，每个服务器报告他所拥有的数据块，MASTER返回元数据不在内存的数据块，服务器即可以删除这些数据块。
3.5 过时数据的探测
在数据更新时如果服务器停机了，那么他所保存的数据备份就会过时。对每个数据块，MASTER设置了一个版本号来区别更新过的数据块和过时的数据块。
当MASTER授权一个新的lease时，他会增加数据块的版本号并会通知更新数据备份。MASTER和备份都会记录下当前的版本号，如果一个备份当时不可用，那么他的版本号不可能提高，当ChunkServer重新启动并向MASTER报告他的数据块集时，MASTER就会发现过时的数据。
MASTER在定期的垃圾收集程序中清除过时的备份，在此以前，处于效率考虑，在各客户及英大使，他会认为根本不存在过时的数据。作为另一个安全措施， MASTER在给客户及关于数据块的应答或是另外一个读取数据的服务器数据是都会带上版本信息，在操作前客户机和服务器会验证版本信息以确保得到的是最新的数据。
4、容错和诊断
4.1 高可靠性
4.1.1 快速恢复
不管如何终止服务，MASTER和数据块服务器都会在几秒钟内恢复状态和运行。实际上，我们不对正常终止和不正常终止进行区分，服务器进程都会被切断而终止。客户机和其他的服务器会经历一个小小的中断，然后它们的特定请求超时，重新连接重启的服务器，重新请求。
4.1.2 数据块备份
如上文所讨论的，每个数据块都会被备份到放到不同机架上的不同服务器上。对不同的名字空间，用户可以设置不同的备份级别。在数据块服务器掉线或是数据被破坏时，MASTER会按照需要来复制数据块。
4.1.3 MASTER备份
为确保可靠性，MASTER的状态、操作记录和检查点都在多台机器上进行了备份。一个操作只有在数据块服务器硬盘上刷新并被记录在MASTER和其备份的上之后才算是成功的。如果MASTER或是硬盘失败，系统监视器会发现并通过改变域名启动它的一个备份机，而客户机则仅仅是使用规范的名称来访问，并不会发现MASTER的改变。
4.2 数据完整性
每个数据块服务器都利用校验和来检验存储数据的完整性。原因：每个服务器随时都有发生崩溃的可能性，并且在两个服务器间比较数据块也是不现实的，同时，在两台服务器间拷贝数据并不能保证数据的一致性。
每个Chunk按64kB的大小分成块，每个块有32位的校验和，校验和和日志存储在一起，和用户数据分开。
在读数据时，服务器首先检查与被读内容相关部分的校验和，因此，服务器不会传播错误的数据。如果所检查的内容和校验和不符，服务器就会给数据请求者返回一个错误的信息，并把这个情况报告给MASTER。客户机就会读其他的服务器来获取数据，而MASTER则会从其他的拷贝来复制数据，等到一个新的拷贝完成时，MASTER就会通知报告错误的服务器删除出错的数据块。
附加写数据时的校验和计算优化了，因为这是主要的写操作。我们只是更新增加部分的校验和，即使末尾部分的校验和数据已被损坏而我们没有检查出来，新的校验和与数据会不相符，这种冲突在下次使用时将会被检查出来。
相反，如果是覆盖现有数据的写，在写以前，我们必须检查第一和最后一个数据块，然后才能执行写操作，最后计算和记录校验和。如果我们在覆盖以前不先检查首位数据块，计算出的校验和则会因为没被覆盖的数据而产生错误。
在空闲时间，服务器会检查不活跃的数据块的校验和，这样可以检查出不经常读的数据的错误。一旦错误被检查出来，服务器会拷贝一个正确的数据块来代替错误的。
4.3 诊断工具
广泛而细致的诊断日志以微小的代价换取了在问题隔离、诊断、性能分析方面起到了重大的作用。GFS服务器用日志来记录显著的事件（例如服务器停机和启动）和远程的应答。远程日志记录机器之间的请求和应答，通过收集不同机器上的日志记录，并对它们进行分析恢复，我们可以完整地重现活动的场景，并用此来进行错误分析。
6 测量
6.1 测试环境
一台主控机，两台主控机备份，16台数据块服务器，16台客户机。
每台机器：2块PIII1.4G处理器，2G内存，2块80G5400rpm的硬盘，1块100Mbps全双工网卡
19台服务器连接到一个HP2524交换机上，16台客户机俩接到领外一台交换机上，两台交换机通过1G的链路相连。


Google 2003年关于Google File System的论文

原文出处：http://www.irunnet.com/viewtopic.php?p=913&sid=4f05f5b8a26e7d0b0e2586190c175d0b#913