数据库减少副本算法

1. 分布式存储中，怎样使用paxos算法保证数据的一致性

在分布式系统中，我们经常遇到多数据副本保持一致的问题，在我们所能找到的资料中该问题讲的很笼统，模模糊糊的，把多个问题或分类糅合在一起，难以理解。在思考和翻阅资料后，通俗地把一致性的问题可分解为2个问题：
1、任何一次修改保证数据一致性。
2、多次数据修改的一致性。
在弱一致性的算法，不要求每次修改的内容在修改后多副本的内容是一致的，对问题1的解决比较宽松，更多解决问题2，该类算法追求每次修改的高度并发性，减少多副本之间修改的关联性，以获得更好的并发性能。例如最终一致性，无所谓每次用户修改后的多副本的一致性及格过，只要求在单调的时间方向上，数据最终保持一致，如此获得了修改极大的并发性能。
在强一致性的算法中，强调单次修改后结果的一致，需要保证了对问题1和问题2要求的实现，牺牲了并发性能。本文是讨论对解决问题1实现算法，这些算法往往在强一致性要求的应用中使用。
解决问题1的方法，通常有两阶段提交算法、采用分布式锁服务和采用乐观锁原理实现的同步方式,下面分别介绍这几种算法的实现原理。

两阶段提交算法

在两阶段提交协议中，系统一般包含两类机器（或节点）：一类为协调者（coordinator），通常一个系统中只有一个；另一类为事务参与者（participants，cohorts或workers），一般包含多个，在数据存储系统中可以理解为数据副本的个数。两阶段提交协议由两个阶段组成，在正常的执行下，这两个阶段的执行过程如下所述：
阶段1：请求阶段（commit-request phase，或称表决阶段，voting phase）。
在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。
阶段2：提交阶段（commit phase）。
在该阶段，协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行响应的操作。
举个例子：A组织B、C和D三个人去爬长城：如果所有人都同意去爬长城，那么活动将举行；如果有一人不同意去爬长城，那么活动将取消。用2PC算法解决该问题的过程如下：
首先A将成为该活动的协调者，B、C和D将成为该活动的参与者。
阶段1：A发邮件给B、C和D，提出下周三去爬山，问是否同意。那么此时A需要等待B、C和D的邮件。B、C和D分别查看自己的日程安排表。B、C发现自己在当日没有活动安排，则发邮件告诉A它们同意下周三去爬长城。由于某种原因，D白天没有查看邮件。那么此时A、B和C均需要等待。到晚上的时候，D发现了A的邮件，然后查看日程安排，发现周三当天已经有别的安排，那么D回复A说活动取消吧。
阶段2：此时A收到了所有活动参与者的邮件，并且A发现D下周三不能去爬山。那么A将发邮件通知B、C和D，下周三爬长城活动取消。此时B、C回复A“太可惜了”，D回复A“不好意思”。至此该事务终止。
两阶段提交算法在分布式系统结合，可实现单用户对文件（对象）多个副本的修改，多副本数据的同步。其结合的原理如下：
1、客户端（协调者）向所有的数据副本的存储主机（参与者）发送：修改具体的文件名、偏移量、数据和长度信息，请求修改数据，该消息是1阶段的请求消息。
2、存储主机接收到请求后，备份修改前的数据以备回滚，修改文件数据后，向客户端回应修改成功的消息。 如果存储主机由于某些原因（磁盘损坏、空间不足等）不能修改数据，回应修改失败的消息。
3、客户端接收发送出去的每一个消息回应，如果存储主机全部回应都修改成功，向每存储主机发送确认修改的提交消息；如果存在存储主机回应修改失败，或者超时未回应，客户端向所有存储主机发送取消修改的提交消息。该消息是2阶段的提交消息。
4、存储主机接收到客户端的提交消息，如果是确认修改，则直接回应该提交OK消息；如果是取消修改，则将修改数据还原为修改前，然后回应取消修改OK的消息。
5、 客户端接收全部存储主机的回应，整个操作成功。
在该过程中可能存在通信失败，例如网络中断、主机宕机等诸多的原因，对于未在算法中定义的其它异常，都认为是提交失败，都需要回滚，这是该算法基于确定的通信回复实现的，在参与者的确定回复（无论是回复失败还是回复成功）之上执行逻辑处理，符合确定性的条件当然能够获得确定性的结果哲学原理。

分布式锁服务

分布式锁是对数据被外界修改持保守态度，在整个数据处理过程中将数据处于锁定状态，在用户修改数据的同时，其它用户不允许修改。
采用分布式锁服务实现数据一致性，是在操作目标之前先获取操作许可，然后再执行操作，如果其他用户同时尝试操作该目标将被阻止，直到前一个用户释放许可后，其他用户才能够操作目标。分析这个过程，如果只有一个用户操作目标，没有多个用户并发冲突，也申请了操作许可，造成了由于申请操作许可所带来的资源使用消耗，浪费网络通信和增加了延时。
采用分布式锁实现多副本内容修改的一致性问题， 选择控制内容颗粒度实现申请锁服务。例如我们要保证一个文件的多个副本修改一致， 可以对整个文件修改设置一把锁，修改时申请锁，修改这个文件的多个副本，确保多个副本修改的一致，修改完成后释放锁；也可以对文件分段，或者是文件中的单个字节设置锁， 实现更细颗粒度的锁操作，减少冲突。
常用的锁实现算法有Lamport bakery algorithm （俗称面包店算法）， 还有Paxos算法。下面对其原理做简单概述。

Lamport面包店算法

是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。 由Leslie Lamport（英语：Leslie Lamport）发明。
Lamport把这个并发控制算法可以非常直观地类比为顾客去面包店采购。面包店只能接待一位顾客的采购。已知有n位顾客要进入面包店采购，安排他们按照次序在前台登记一个签到号码。该签到号码逐次加1。根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0. 如果完成购买的顾客要再次进店购买，就必须重新排队。
这个类比中的顾客就相当于线程，而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点，存在两个线程获得相同的签到号码的情况，这是因为两个线程几乎同时申请排队的签到号码，读取已经发出去的签到号码情况，这两个线程读到的数据是完全一样的，然后各自在读到的数据上找到最大值，再加1作为自己的排队签到号码。为此，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。
把该算法原理与分布式系统相结合，即可实现分步锁。

Paxos算法

该算法比较热门，参见WIKI，http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。节点通信存在两种模型：共享内存(Shared memory)和消息传递(Messages passing)。Paxos算法就是一种基于消息传递模型的一致性算法。BigTable使用一个分布式数据锁服务Chubby，而Chubby使用Paxos算法来保证备份的一致性。

采用乐观锁原理实现的同步

我们举个例子说明该算法的实现原理。如一个金融系统，当某个操作员读取用户的数据，并在读出的用户数据的基础上进行修改时（如更改用户帐户余额），如果采用前面的分布式锁服务机制，也就意味着整个操作过程中（从操作员读出数据、开始修改直至提交修改结果的全过程，甚至还包括操作员中途去煮咖啡的时间），数据库记录始终处于加锁状态，可以想见，如果面对几百上千个并发，这样的情况将导致怎样的后果。
乐观锁机制在一定程度上解决了这个问题。乐观锁，大多是基于数据版本（ Version）记录机制实现。何谓数据版本？即为数据增加一个版本标识，在基于数据库表的版本解决方案中，一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时，将此版本号一同读出，之后更新时，对此版本号加一。此时，将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对，如果提交的数据版本号大于数据库表当前版本号，则予以更新，否则认为是过期数据。
对于上面修改用户帐户信息的例子而言，假设数据库中帐户信息表中有一个 version 字段，当前值为 1 ；而当前帐户余额字段（ balance ）为 $100 。
操作员 A 此时将其读出（version=1 ），并从其帐户余额中扣除 $50（$100-$50 ）。
在操作员 A 操作的过程中，操作员B也读入此用户信息（ version=1 ），并从其帐户余额中扣除 $20 （ $100-$20 ）。
操作员 A 完成了修改工作，将数据版本号加一（ version=2 ），连同帐户扣除后余额（ balance=$50 ），提交至数据库更新，此时由于提交数据版本大于数据库记录当前版本，数据被更新，数据库记录 version 更新为 2 。
操作员 B 完成了操作，也将版本号加一（ version=2 ）试图向数据库提交数据（ balance=$80 ），但此时比对数据库记录版本时发现，操作员 B 提交的数据版本号为 2 ，数据库记录当前版本也为 2 ，不满足 “ 提交版本必须大于记录当前版本才能执行更新 “ 的乐观锁策略，因此，操作员 B 的提交被驳回。这样，就避免了操作员 B 用基于 version=1 的旧数据修改的结果覆盖操作员A 的操作结果的可能。
乐观锁机制与分布式系统相结合上， 我整理了伪代码如下：
obj 操作的目标
vlaue 修改的值
atom_update_ver 每个目标上的版本，每次修改该值递增
set( obj, value)
{
//从每个节点上取出修改前的对象版本
get original_ver = obj.atom_update_ver from each node;
//将值赋到每个节点的obj目标
set obj = value from each node;
//条件修改每个节点的obj版本，目标版本加一
//比较和修改操作是原子操作
result = (set obj.atom_update_ver = original_ver + 1
where original_ver + 1 > obj.atom_update_ver
for each node);
if(result == ok)
return set_ok;
else
return set(obj, value);//不成功递归修改

该算法未考虑节点下线、失效等问题，在后续我将分析采用乐观锁原理实现一致性算法，解决问题2、节点失效、通信失败等问题。

2. 分布式数据库容忍副本故障

在常见的分布式存储系统中，实现2F+1个副本冗余，最多能容忍F个副本同时故障。
在分布式存储中，一般通过冗余服务、数据来满足可用性需求。冗余服务提供的存储服务断不断。主备模式涉及到提供服务的节点进行切换，对外服务可能中断。双活与无状态分布不断服务。
无论是云计算、大数据还是互联网公司的各种应用，其后台基础设施的主要目标都是构建低成本、高性能、可扩展、易用的分布式存储系统。

3. 影响数据库性能的主要因素有哪些

以MySQL为例：

影响数据库性能的主要因素总结如下：

1、sql查询速度

2、网卡流量

3、服务器硬件

4、磁盘IO

以上因素并不是时时刻刻都会影响数据库性能，而就像木桶效应一样。如果其中一个因素严重影响性能，那么整个数据库性能就会严重受阻。另外，这些影响因素都是相对的。

例如：当数据量并没有达到百万千万这样的级别，那么sql查询速度也许就不是个重要因素，换句话说，你的sql语句效率适当低下可能并不影响整个效率多少，反之，这种情况，无论如何怎么优化sql语句，可能都没有太明显的效果。

相关内容拓展：

1、SQL查询速度

风险：效率低下的SQL

2、网卡流量

风险：网卡IO被占满（100Mb/8=100MB）

方案：

①减少从服务器的数量。从服务器都要从主服务器上复制日志，所以，从服务器越多，网络流量越大。

②进行分级缓存。前方大量缓存突然失效会对数据库造成严重的冲击。

③避免使用“select * ”进行查询

④分离业务网络和服务器网络

3、磁盘IO

风险：磁盘IO性能突然下降。

方案：使用更好的磁盘设备解决。

4. 数据库技术知识数据结构的算法

数据库技术知识数据结构的算法

对于将要参加计算机等级考试的考生来说，计算机等级考试的知识点辅导是非常重要的复习资料。以下是我收集的数据库技术知识数据结构的算法，希望大家认真阅读!

1、数据：数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位

2、数据结构：数据的逻辑结构、数据的存储结构、数据的运算

3、主要的数据存储方式：顺序存储结构(逻辑和物理相邻，存储密度大)和链式存储结构

顺序存储结构：

顺序存储计算公式 Li=L0+(i-1)×K 顺序结构可以进行随机存取;插人、删除运算会引起相应节点的大量移动

链式存储结构：a、指针域可以有多个，可以指向空，比比顺序存储结构的存储密度小

b、逻辑上相邻的节点物理上不一定相邻。 c、插人、删除等不需要大量移动节点

4、顺序表：一般情况下，若长度为n的顺序表，在任何位置插入或删除的概率相等，元素移动的平均次数为n/2(插入)和(n-1)/2(删除)。

5、链表：线性链表(单链表和双向链表等等)和非线性链表

线性链表也称为单链表，其每个一节点中只包含一个指针域，双链表中，每个节点中设置有两个指针域。(注意结点的插入和删除操作)

6、栈：“后进先出”(LIFO)表。栈的应用：表达式求解、二叉树对称序周游、快速排序算法、递归过程的实现等

7、队列：“先进先出”线性表。应用：树的层次遍历

8、串：由零个或多个字符组成的有限序列。

9、多维数组的顺序存储：

10、稀疏矩阵的存储：下三角矩阵顺序存储

其他常见的存储方法还有三元组法和十字链表法

11、广义表：由零个或多个单元素或子表所组成的有限序列。广义表的元素可以是子表，而子表的元素还可以是子表

12、树型结构：非线性结构。常用的树型结构有树和二叉树。

二叉树与树的区别：二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

13、树(森林)与二叉树之间的转换(要会转换)

14、二叉树和树的周游(遍历)

二叉树的周游主要有以下3种方式：前序法(NLR)、对称序法(LNR)、后序法(LRN)

周游树和树林：深度优先和按广度优先两种方式进行。深度优先方式又可分为按先根次序和按后根次序周游

树与二叉树周游之间的对应关系：按先根次序周游树正好与按前序法周游树对应的二叉树等同，后根次序周游树正好与按对称序法周游对应的`二叉树等同

按广度优先方式就是层次次序周游

15、二叉树的存储和线索

二叉树的存储结构：二叉树的llink一rlink法存储表示

线索二叉树：在有n个节点的二叉树的且llink - rlink法存储表示中，必定有n+1个空指针域

16、哈夫曼树：一类带权路径长度最短的树。树的带权路径长度为树中所有叶子节点的带权路径长度之和WPL。

17、查找：

(1)顺序查找：平均查找长度为(n +1 )/2次，时间复杂度为O(n)

(2)二分法查找：线性表节点必须按关键码值排序，且线性表是以顺序存储方式存储的。查找成功比较次数log2n，查找失败比较次数log2n+1

(3)分块查找：先是块间查找，然后块内查找。

(4)散列表(哈希表Hash)的存储和查找：处理冲突的方法：开地址法(线性探测法)、拉链法等

负载因子(装填因子)=表实际存储的结点个数/表的最大能存储结点个数(即表长)

二叉排序树：每个结点左子树的所有关键码值都小于该结点关键码值，右子树所有结点关键码值都大于该结点关键码值。对称周游二叉排序树，得到一个有序序列，时间复杂度O(log2n)

B树和B+树：M阶树，每个结点至多有M-1个关键码，至少有M/2(取上界)-1个关键码。B树适合随机查找，不适合顺序查找。B+树适合顺序查找。

18、排序

直接插人排序、希尔排序、直接选择排序、堆排序、起泡排序、快速排序等排序算法要了解。

直接选择排序、希尔排序、快速排序和堆排序是不稳定排序，其他排序为稳定排序

5. 我做了个相似性的算法，要与数据库上百万比对，其他一些网站都用了Hadoop分布式，知网也是这样的吗

引言

Hadoop分布式文件系统(HDFS)被设计成适合运行在通用硬件(commodity hardware)上的分布式文件系统。它和现有的分布式文件系统有很多共同点。但同时，它和其他的分布式文件系统的区别也是很明显的。HDFS是一个高度容错性的系统，适合部署在廉价的机器上。HDFS能提供高吞吐量的数据访问，非常适合大规模数据集上的应用。HDFS放宽了一部分POSIX约束，来实现流式读取文件系统数据的目的。HDFS在最开始是作为Apache Nutch搜索引擎项目的基础架构而开发的。HDFS是Apache Hadoop Core项目的一部分。这个项目的地址是http://hadoop.apache.org/core/。

前提和设计目标

硬件错误

硬件错误是常态而不是异常。HDFS可能由成百上千的服务器所构成，每个服务器上存储着文件系统的部分数据。我们面对的现实是构成系统的组件数目是巨大的，而且任一组件都有可能失效，这意味着总是有一部分HDFS的组件是不工作的。因此错误检测和快速、自动的恢复是HDFS最核心的架构目标。

流式数据访问

运行在HDFS上的应用和普通的应用不同，需要流式访问它们的数据集。HDFS的设计中更多的考虑到了数据批处理，而不是用户交互处理。比之数据访问的低延迟问题，更关键的在于数据访问的高吞吐量。POSIX标准设置的很多硬性约束对HDFS应用系统不是必需的。为了提高数据的吞吐量，在一些关键方面对POSIX的语义做了一些修改。

大规模数据集

运行在HDFS上的应用具有很大的数据集。HDFS上的一个典型文件大小一般都在G字节至T字节。因此，HDFS被调节以支持大文件存储。它应该能提供整体上高的数据传输带宽，能在一个集群里扩展到数百个节点。一个单一的HDFS实例应该能支撑数以千万计的文件。

简单的一致性模型

HDFS应用需要一个“一次写入多次读取”的文件访问模型。一个文件经过创建、写入和关闭之后就不需要改变。这一假设简化了数据一致性问题，并且使高吞吐量的数据访问成为可能。Map/Rece应用或者网络爬虫应用都非常适合这个模型。目前还有计划在将来扩充这个模型，使之支持文件的附加写操作。

“移动计算比移动数据更划算”

一个应用请求的计算，离它操作的数据越近就越高效，在数据达到海量级别的时候更是如此。因为这样就能降低网络阻塞的影响，提高系统数据的吞吐量。将计算移动到数据附近，比之将数据移动到应用所在显然更好。HDFS为应用提供了将它们自己移动到数据附近的接口。

异构软硬件平台间的可移植性

HDFS在设计的时候就考虑到平台的可移植性。这种特性方便了HDFS作为大规模数据应用平台的推广。

Namenode 和 Datanode

HDFS采用master/slave架构。一个HDFS集群是由一个Namenode和一定数目的Datanodes组成。Namenode是一个中心服务器，负责管理文件系统的名字空间(namespace)以及客户端对文件的访问。集群中的Datanode一般是一个节点一个，负责管理它所在节点上的存储。HDFS暴露了文件系统的名字空间，用户能够以文件的形式在上面存储数据。从内部看，一个文件其实被分成一个或多个数据块，这些块存储在一组Datanode上。Namenode执行文件系统的名字空间操作，比如打开、关闭、重命名文件或目录。它也负责确定数据块到具体Datanode节点的映射。Datanode负责处理文件系统客户端的读写请求。在Namenode的统一调度下进行数据块的创建、删除和复制。

Namenode和Datanode被设计成可以在普通的商用机器上运行。这些机器一般运行着GNU/Linux操作系统(OS)。HDFS采用Java语言开发，因此任何支持Java的机器都可以部署Namenode或Datanode。由于采用了可移植性极强的Java语言，使得HDFS可以部署到多种类型的机器上。一个典型的部署场景是一台机器上只运行一个Namenode实例，而集群中的其它机器分别运行一个Datanode实例。这种架构并不排斥在一台机器上运行多个Datanode，只不过这样的情况比较少见。

集群中单一Namenode的结构大大简化了系统的架构。Namenode是所有HDFS元数据的仲裁者和管理者，这样，用户数据永远不会流过Namenode。

文件系统的名字空间 (namespace)

HDFS支持传统的层次型文件组织结构。用户或者应用程序可以创建目录，然后将文件保存在这些目录里。文件系统名字空间的层次结构和大多数现有的文件系统类似：用户可以创建、删除、移动或重命名文件。当前，HDFS不支持用户磁盘配额和访问权限控制，也不支持硬链接和软链接。但是HDFS架构并不妨碍实现这些特性。

Namenode负责维护文件系统的名字空间，任何对文件系统名字空间或属性的修改都将被Namenode记录下来。应用程序可以设置HDFS保存的文件的副本数目。文件副本的数目称为文件的副本系数，这个信息也是由Namenode保存的。

数据复制

HDFS被设计成能够在一个大集群中跨机器可靠地存储超大文件。它将每个文件存储成一系列的数据块，除了最后一个，所有的数据块都是同样大小的。为了容错，文件的所有数据块都会有副本。每个文件的数据块大小和副本系数都是可配置的。应用程序可以指定某个文件的副本数目。副本系数可以在文件创建的时候指定，也可以在之后改变。HDFS中的文件都是一次性写入的，并且严格要求在任何时候只能有一个写入者。

Namenode全权管理数据块的复制，它周期性地从集群中的每个Datanode接收心跳信号和块状态报告(Blockreport)。接收到心跳信号意味着该Datanode节点工作正常。块状态报告包含了一个该Datanode上所有数据块的列表。

副本存放: 最最开始的一步

副本的存放是HDFS可靠性和性能的关键。优化的副本存放策略是HDFS区分于其他大部分分布式文件系统的重要特性。这种特性需要做大量的调优，并需要经验的积累。HDFS采用一种称为机架感知(rack-aware)的策略来改进数据的可靠性、可用性和网络带宽的利用率。目前实现的副本存放策略只是在这个方向上的第一步。实现这个策略的短期目标是验证它在生产环境下的有效性，观察它的行为，为实现更先进的策略打下测试和研究的基础。

大型HDFS实例一般运行在跨越多个机架的计算机组成的集群上，不同机架上的两台机器之间的通讯需要经过交换机。在大多数情况下，同一个机架内的两台机器间的带宽会比不同机架的两台机器间的带宽大。

通过一个机架感知的过程，Namenode可以确定每个Datanode所属的机架id。一个简单但没有优化的策略就是将副本存放在不同的机架上。这样可以有效防止当整个机架失效时数据的丢失，并且允许读数据的时候充分利用多个机架的带宽。这种策略设置可以将副本均匀分布在集群中，有利于当组件失效情况下的负载均衡。但是，因为这种策略的一个写操作需要传输数据块到多个机架，这增加了写的代价。

在大多数情况下，副本系数是3，HDFS的存放策略是将一个副本存放在本地机架的节点上，一个副本放在同一机架的另一个节点上，最后一个副本放在不同机架的节点上。这种策略减少了机架间的数据传输，这就提高了写操作的效率。机架的错误远远比节点的错误少，所以这个策略不会影响到数据的可靠性和可用性。于此同时，因为数据块只放在两个（不是三个）不同的机架上，所以此策略减少了读取数据时需要的网络传输总带宽。在这种策略下，副本并不是均匀分布在不同的机架上。三分之一的副本在一个节点上，三分之二的副本在一个机架上，其他副本均匀分布在剩下的机架中，这一策略在不损害数据可靠性和读取性能的情况下改进了写的性能。

当前，这里介绍的默认副本存放策略正在开发的过程中。

副本选择

为了降低整体的带宽消耗和读取延时，HDFS会尽量让读取程序读取离它最近的副本。如果在读取程序的同一个机架上有一个副本，那么就读取该副本。如果一个HDFS集群跨越多个数据中心，那么客户端也将首先读本地数据中心的副本。

安全模式

Namenode启动后会进入一个称为安全模式的特殊状态。处于安全模式的Namenode是不会进行数据块的复制的。Namenode从所有的 Datanode接收心跳信号和块状态报告。块状态报告包括了某个Datanode所有的数据块列表。每个数据块都有一个指定的最小副本数。当Namenode检测确认某个数据块的副本数目达到这个最小值，那么该数据块就会被认为是副本安全(safely replicated)的；在一定百分比（这个参数可配置）的数据块被Namenode检测确认是安全之后（加上一个额外的30秒等待时间），Namenode将退出安全模式状态。接下来它会确定还有哪些数据块的副本没有达到指定数目，并将这些数据块复制到其他Datanode上。

文件系统元数据的持久化

Namenode上保存着HDFS的名字空间。对于任何对文件系统元数据产生修改的操作，Namenode都会使用一种称为EditLog的事务日志记录下来。例如，在HDFS中创建一个文件，Namenode就会在Editlog中插入一条记录来表示；同样地，修改文件的副本系数也将往Editlog插入一条记录。Namenode在本地操作系统的文件系统中存储这个Editlog。整个文件系统的名字空间，包括数据块到文件的映射、文件的属性等，都存储在一个称为FsImage的文件中，这个文件也是放在Namenode所在的本地文件系统上。

Namenode在内存中保存着整个文件系统的名字空间和文件数据块映射(Blockmap)的映像。这个关键的元数据结构设计得很紧凑，因而一个有4G内存的Namenode足够支撑大量的文件和目录。当Namenode启动时，它从硬盘中读取Editlog和FsImage，将所有Editlog中的事务作用在内存中的FsImage上，并将这个新版本的FsImage从内存中保存到本地磁盘上，然后删除旧的Editlog，因为这个旧的Editlog的事务都已经作用在FsImage上了。这个过程称为一个检查点(checkpoint)。在当前实现中，检查点只发生在Namenode启动时，在不久的将来将实现支持周期性的检查点。

Datanode将HDFS数据以文件的形式存储在本地的文件系统中，它并不知道有关HDFS文件的信息。它把每个HDFS数据块存储在本地文件系统的一个单独的文件中。Datanode并不在同一个目录创建所有的文件，实际上，它用试探的方法来确定每个目录的最佳文件数目，并且在适当的时候创建子目录。在同一个目录中创建所有的本地文件并不是最优的选择，这是因为本地文件系统可能无法高效地在单个目录中支持大量的文件。当一个Datanode启动时，它会扫描本地文件系统，产生一个这些本地文件对应的所有HDFS数据块的列表，然后作为报告发送到Namenode，这个报告就是块状态报告。

通讯协议

所有的HDFS通讯协议都是建立在TCP/IP协议之上。客户端通过一个可配置的TCP端口连接到Namenode，通过ClientProtocol协议与Namenode交互。而Datanode使用DatanodeProtocol协议与Namenode交互。一个远程过程调用(RPC)模型被抽象出来封装ClientProtocol和Datanodeprotocol协议。在设计上，Namenode不会主动发起RPC，而是响应来自客户端或 Datanode 的RPC请求。

健壮性

HDFS的主要目标就是即使在出错的情况下也要保证数据存储的可靠性。常见的三种出错情况是：Namenode出错, Datanode出错和网络割裂(network partitions)。

磁盘数据错误，心跳检测和重新复制

每个Datanode节点周期性地向Namenode发送心跳信号。网络割裂可能导致一部分Datanode跟Namenode失去联系。Namenode通过心跳信号的缺失来检测这一情况，并将这些近期不再发送心跳信号Datanode标记为宕机，不会再将新的IO请求发给它们。任何存储在宕机Datanode上的数据将不再有效。Datanode的宕机可能会引起一些数据块的副本系数低于指定值，Namenode不断地检测这些需要复制的数据块，一旦发现就启动复制操作。在下列情况下，可能需要重新复制：某个Datanode节点失效，某个副本遭到损坏，Datanode上的硬盘错误，或者文件的副本系数增大。

集群均衡

HDFS的架构支持数据均衡策略。如果某个Datanode节点上的空闲空间低于特定的临界点，按照均衡策略系统就会自动地将数据从这个Datanode移动到其他空闲的Datanode。当对某个文件的请求突然增加，那么也可能启动一个计划创建该文件新的副本，并且同时重新平衡集群中的其他数据。这些均衡策略目前还没有实现。

数据完整性

从某个Datanode获取的数据块有可能是损坏的，损坏可能是由Datanode的存储设备错误、网络错误或者软件bug造成的。HDFS客户端软件实现了对HDFS文件内容的校验和(checksum)检查。当客户端创建一个新的HDFS文件，会计算这个文件每个数据块的校验和，并将校验和作为一个单独的隐藏文件保存在同一个HDFS名字空间下。当客户端获取文件内容后，它会检验从Datanode获取的数据跟相应的校验和文件中的校验和是否匹配，如果不匹配，客户端可以选择从其他Datanode获取该数据块的副本。

元数据磁盘错误

FsImage和Editlog是HDFS的核心数据结构。如果这些文件损坏了，整个HDFS实例都将失效。因而，Namenode可以配置成支持维护多个FsImage和Editlog的副本。任何对FsImage或者Editlog的修改，都将同步到它们的副本上。这种多副本的同步操作可能会降低Namenode每秒处理的名字空间事务数量。然而这个代价是可以接受的，因为即使HDFS的应用是数据密集的，它们也非元数据密集的。当Namenode重启的时候，它会选取最近的完整的FsImage和Editlog来使用。

Namenode是HDFS集群中的单点故障(single point of failure)所在。如果Namenode机器故障，是需要手工干预的。目前，自动重启或在另一台机器上做Namenode故障转移的功能还没实现。

快照

快照支持某一特定时刻的数据的复制备份。利用快照，可以让HDFS在数据损坏时恢复到过去一个已知正确的时间点。HDFS目前还不支持快照功能，但计划在将来的版本进行支持。

数据组织

数据块

HDFS被设计成支持大文件，适用HDFS的是那些需要处理大规模的数据集的应用。这些应用都是只写入数据一次，但却读取一次或多次，并且读取速度应能满足流式读取的需要。HDFS支持文件的“一次写入多次读取”语义。一个典型的数据块大小是64MB。因而，HDFS中的文件总是按照64M被切分成不同的块，每个块尽可能地存储于不同的Datanode中。

Staging

客户端创建文件的请求其实并没有立即发送给Namenode，事实上，在刚开始阶段HDFS客户端会先将文件数据缓存到本地的一个临时文件。应用程序的写操作被透明地重定向到这个临时文件。当这个临时文件累积的数据量超过一个数据块的大小，客户端才会联系Namenode。Namenode将文件名插入文件系统的层次结构中，并且分配一个数据块给它。然后返回Datanode的标识符和目标数据块给客户端。接着客户端将这块数据从本地临时文件上传到指定的Datanode上。当文件关闭时，在临时文件中剩余的没有上传的数据也会传输到指定的Datanode上。然后客户端告诉Namenode文件已经关闭。此时Namenode才将文件创建操作提交到日志里进行存储。如果Namenode在文件关闭前宕机了，则该文件将丢失。

上述方法是对在HDFS上运行的目标应用进行认真考虑后得到的结果。这些应用需要进行文件的流式写入。如果不采用客户端缓存，由于网络速度和网络堵塞会对吞估量造成比较大的影响。这种方法并不是没有先例的，早期的文件系统，比如AFS，就用客户端缓存来提高性能。为了达到更高的数据上传效率，已经放松了POSIX标准的要求。

流水线复制

6. 如何通过 Nutanix 数据库管理避免不必要的数据库开支

可从Forrester Consulting 采访报告中可以看出，大多数选择Nutanix数据库管理Era的客户一是看中了它在功能、降低成本和低风险方面的好处；二是Nutanix数据库管理基于超融合基础架构，使用可扩展的节点结构来满足组织需求，同时还可以避免高昂的前期基础架构成本，虽然部署于本地，但可以点来类云的使用体验，可以用于管理不同类型的数据库大大的好。
具体是通过这些避免不必要的数据库开支的：
加快数据库置备速度；
将副本和备份存储需求减少 60%；
更简单的数据库管理可将数据库管理员的加班时间减少多达 50%；
降低与管理工具集和许可相关的成本；
自动化的数据库修补和管理，避免了每小时超过 35,000 美元的损失。

7. 数据冗余由什么引起

数据冗余由什么引起?
数据库中数据冗余会产生什么问题？？如果表空间占满，会有插入，更新操作失败的问题发生。
数据冗余是什么意思啊?大概一点....数据冗余:在一个数据集合中重复的数据称为数据冗余.数据冗余技术是使用一组或多组附加驱动器存储数据的副本,这就叫数据冗余技术。比如镜像就是一种数据冗余技术。数据冗余技术。工控软件开发中，冗余技术是一项最为重要的技术，它是系统长期稳定工作的保障。OPC技术的使用可以更加方便的实现软件冗余，而且具有较好的开放性和可互操作性。出现这种情况，是因为光盘刻录时有某些数据记录不正确，也有可能是光盘与你的光驱不兼容，或光驱某处物理损坏读不过去。循环冗余检查(CRC)是一种数据传输检错功能，对数据进行多项式计，并将得到的结果附在帧的后面，接收设备也执行类似算法，以保证数据传输的正确性和完整性。若CRC校验不通过，系统重复向硬盘复制数据，陷入死循环，导致复制过程无法完成。
什么是数据冗余，数据冗余会带来哪些问题？数据冗余就是指一些不必要的，多余的内容。最常见的就是在数据库中，由于数据结构、存储等方面设计不合理，造成信息重复。
数据冗余产生哪些问题数据冗余:在一个数据集合中重复的数据称为数据冗余.
数据冗余的目的：
数据的应用中为了某种目的采取数据冗余方式。
1、重复存储或传输数据以防止数据的丢失。
2、对数据进行冗余性的编码来防止数据的丢失、错误，并提供对错误数据进行反变换得到原始数据的功能。
3、为简化流程所造成额数据冗余。例如向多个目的发送同样的信息、在多个地点存放同样的信息，而不对数据进行分析而减少工作量。
4、为加快处理过程而将同一数据在不同地点存放。例如并行处理同一信息的不同内容，或用不同方法处理同一信息等。
5、为方便处理而是同一信息在不同地点有不同的表现形式。例如一本书的不同语言的版本。
6、大量数据的索引。一般在数据库中经常使用。其目的类似第4点。
7、方法类的信息冗余：比如每个司机都要记住同一城市的基本交通信息；大量个人电脑都安装类似的操作系统或软件。
8、为了完备性而配备的冗余数据。例如字典里的字很多，但我们只查询其中很少的一些字。软件功能很多，但我们只使用其中一部分。
9、规则性的冗余。根据法律、制度、规则等约束进行的。例如合同中大量的模式化的内容。
10、为达到其他目的所进行的冗余。例如重复信息以达到被重视等等。
数据冗余或者信息冗余是生产、生活所必然存在的行为，没有好与不好的总体倾向。
而对于自然界，则是物质存在的一种形式，是客观存在情况。例如每个人都有与其他人基本相同的基因。
数据冗余是指数据之间的重复，也可以说是同一数据存储在不同数据文件中的现象。可以说增加数据的独立性和减少数据冗余是企业范围信息资源管理和大规模信息系统获得成功的前提条件。
以上回答来自网络……
冗余是什么意思在数据库中的数据冗余大概是这么个意思:数据重复鼎浪费空间.例如:
一个数据库中有两个表,一个表中有一字段存放某个人员的照片,如果在第二个表中再次存放照片就是典型的数据冗余.
其实我们在描述一个对象的时候,这个对象又很多的属性.在用数据库保存这些属性时,就应该将这些属性恰当的放到数据库中的某个具体的表中去.设计好的表,数据冗余就小.例如描述一个学生的属性有一些基本星信和成绩信息等,这样就应该将基本信息和成绩信息分成两个表分别存储,否则当你查看基本信息时,成绩信息就是多余的,影响性能,浪费时间.
什么是数据冗余数据冗余概念简单说就是多个地方重复存储相同数据。一般是用在数据库上。
城市数据团-数据不说谎：大数据之下的世界
数据冗余的类型有哪些数据的应用中为了某种目的采取数据冗余方式。
1、重复存储或传输数据以防止数据的丢失。
2、对数据进行冗余性的编码来防止数据的丢失、错误，并提供对错误数据进行反变换得到原始数据的功能。
3、为简化流程所造成额数据冗余。例如向多个目的发送同样的信息、在多个地点存放同样的信息，而不对数据进行分析而减少工作量。
4、为加快处理过程而将同一数据在不同地点存放。例如并行处理同一信息的不同内容，或用不同方法处理同一信息等。
5、为方便处理而使同一信息在不同地点有不同的表现形式。例如一本书的不同语言的版本。
6、大量数据的索引,一般在数据库中经常使用。其目的类似第4点。
7、方法类的信息冗余：比如每个司机都要记住同一城市的基本交通信息；大量个人电脑都安装类似的操作系统或软件。
8、为了完备性而配备的冗余数据。例如字典里的字很多，但我们只查询其中很少的一些字。软件功能很多，但我们只使用其中一部分。
9、规则性的冗余。根据法律、制度、规则等约束进行的。例如合同中大量的模式化的内容。
10、为达到其他目的所进行的冗余。例如重复信息以达到被重视等等。
什么是数据冗余?什么是数据的完整性?如何来实施数据完整性?数据冗余是指在两个或更多文件中重复出现的数据。例如，职工的信息可能同时在人事部文件、销售部文件和财务部文件中存在。它可能产生的后果有：数据异常、数据不一致性和影响数据的完整性
数据完整性分为以下3类。
（1）域完整性：是指一个列的输入有效性，是否允许为空值。强制域完整性的方法有：限制类型（通过设定列的数据类型）、格式（通过CHECK约束和规则）或可能值的范围（通过FOREIGNKEY约束、CHECK约束、DEFAULT定义、NOTNULL定义和规则）。如：学生的考试成绩必须在0～100之间，性别只能是“男”或“女”。
（2）实体完整性：是指保证表中所有的行唯一。实体完整性要求表中的所有行都有一个唯一标识符。这个唯一标识符可能是一列，也可能是几列的组合，称为主键。也就是说，表中的主键在所有行上必须取唯一值。强制实体完整性的方法有：索引、UNIQUE约束、PRIMARYKEY约束或IDENTITY属性。如：student表中sno（学号）的取值必须唯一，它唯一标识了相应记录所代表的学生，学号重复是非法的。学生的姓名不能作为主键，因为完全可能存在两个学生同名同姓的情况。
（3）参照完整性：是指保证主关键字（被引用表）和外部关键字（引用表）之间的参照关系。它涉及两个或两个以上表数据的一致性维护。外键值将引用表中包含此外键的记录和被引用表中主键与外键相匹配的记录关联起来。在输入、更改或删除记录时，参照完整性保持表之间已定义的关系，确保键值在所有表中一致。这样的一致性要求确保不会引用不存在的值，如果键值更改了，那么在整个数据库中，对该键值的所有引用要进行一致的更改。参照完整性是基于外键与主键之间的关系。例如学生学习课程的课程号必须是有效的课程号，score表（成绩表）的外键o（课程号）将参考course表（课程表）中主键o（课程号）以实现数据完整性。
域完整性、实体完整性及参照完整性分别在列、行、表上实施。数据完整性任何时候都可以实施，但对已有数据的表实施数据完整性时，系统要先检查表中的数据是否满足所实施的完整性，只有表中的数据满足了所实施的完整性，数据完整性才能实施成功。
SQLserver为什么会存在数据冗余？这种数据冗余会导致哪两类典型的问题？不是sqlserver会存在数据冗余，所有的数据库都会存在数抚冗余，数据冗余大多是由于建库的时候表之间的关系没有充分考虑完全，这涉及到数据库中范式的概念（目前最高的是NF范式，不过一般的设计符合第三范式就好）。
冗余会导致：1、存储空间的浪费。2、数据交互和数据库访问执行效率降低。
数据冗余错误的介绍数据冗余错误是一种计算机错误。数据冗余:在一个数据集合中重复的数据称为数据冗余.数据冗余技术是使用一组或多组附加驱动器存储数据的副本,这就叫数据冗余技术。比如镜像就是一种数据冗余技术。

8. 分布式数据库的数据分配方式

（1）集中式：所有数据片段都安排在同一个场地上。
（2）分割式：所有数据只有一份，它被分割成若干逻辑片段，每个逻辑片段被指派在一个特定的场地上。
（3）全复制式：数据在每个场地重复存储。也就是每个场地上都有一个完整的数据副本。
（4）混合式：这是一种介乎于分割式和全复制式之间的分配方式。
目前分布式数据库分配的设计，越来越多的采用寻找最优解的算法，比如遗传算法、退火机制等

9. 基于数据库搜索的算法，关键有哪几点

B+、B- Tree(mysql,oracle,mongodb)
主要用在关系数据库的索引中，如oracle，mysql innodb；mongodb中的索引也是B-树实现的；还有HBase中HFile中的DataBlock的索引等等。
动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树(Red-Black Tree )，B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然会提高查找效率。
但是咱们有面对这样一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下，那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。
也就是说，因为磁盘的操作费时费资源，如果过于频繁的多次查找势必效率低下。那么如何提高效率，即如何避免磁盘过于频繁的多次查找呢？根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，那么是不是便能有效减少磁盘查找存取的次数呢？那这种有效的树结构是一种怎样的树呢？
这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发，自然就想到平衡多路查找树结构，也就是B~tree，即B树结构(后面，我们将看到，B树的各种操作能使B树保持较低的高度，从而达到有效避免磁盘过于频繁的查找存取操作，从而有效提高查找效率)。

Hash表+桶(redis)
mysql中的adaptive hash index，redis中的数据存储实现都是采用hash，可以高效的进行数据的查询。
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位
数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。综合两者特性，设计一种寻址容易，插入删除也容易的数据结构，如拉链法实现的哈希表。

Booleam Filter（HBase）
HBase中的rowkey设置建立Booleam Filter映射，用于快速判断rowkey是否在一个HFile中。在分布式数据库中用的比较多。
基于BitMap的存储结构，采用的是哈希函数的方法，将一个元素映射到一个 m 长度的阵列上的一个点，当这个点是 1 时，那么这个元素在集合内，反之则不在集合内。这个方法的缺点就是当检测的元素量很多时候可能有冲突，解决方法就是使用 k 个哈希 函数对应 k 个点，如果所有点都是 1 的话，那么元素在集合内，如果有 0 的话，元素则不再集合内。