零碎的知识点-1

---

二叉排序树

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于 它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于 它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。

中序遍历可以得到二叉排序树的有序序列

    40
    / \
   30 50

视图与基本表的对比

视图可以定义在多张表上，因此定义功能比表强。
视图中数据更新受到诸多限制，例如不能有聚集函数，不能是定义在多张表上等，因此操作功能弱于表。
视图的数据控制功能和表的数据控制功能相当，都有GRANT、REVOKE。

视图和表的区别和联系：

• 区别：

1. 视图是已经编译好的sql语句。而表不是
2. 视图没有实际的物理记录。而表有。
3. 表是内容，视图是窗口
4. 表只用物理空间而视图不占用物理空间，视图只是逻辑概念的存在，表可以及时对它进行修改，但视图只能有创建的语句来修改
5. 表是内模式，视图是外模式
6. 视图是查看数据表的一种方法，可以查询数据表中某些字段构成的数据，只是一些SQL语句的集合。从安全的角度说，视图可以不给用户接触数据表，从而不知道表结构。
7. 表属于全局模式中的表，是实表；视图属于局部模式的表，是虚表。
8. 视图的建立和删除只影响视图本身，不影响对应的基本表。

• 联系：

视图（view）是在基本表之上建立的表，它的结构（即所定义的列）和内容（即所有数据行）都来自基本表，它依据基本表存在而存在。一个视图可以对应一个基本表，也可以对应多个基本表。视图是基本表的抽象和在逻辑意义上建立的新关系。

Linux bash 特殊变量：

特殊变量列表
| 变量 | 含义 |
| – | – |
| $0 | 当前脚本的文件名 |
| $n | 传递给脚本或函数的参数。n 是一个数字，表示第几个参数。例如，第一个参数是$1，第二个参数是$2。|
| $# | 传递给脚本或函数的参数个数。|
| $ | 传递给脚本或函数的所有参数。|
| $@ | 传递给脚本或函数的所有参数。被双引号(“ “)包含时，与 $ 稍有不同，下面将会讲到。|
| $? | 上个命令的退出状态，或函数的返回值。|
| $$ | 当前Shell进程ID。对于 Shell 脚本，就是这些脚本所在的进程ID。|

bash中变量的定义和赋值

bash中有两个内置的命令declare 和 typeset 可用于创建变量。除了使用内置命令来创建和设置变量外，还可以直接赋值，格式为：变量名=变量值
注意：变量名前面不应加美元“$”符号。（和PHP不同）

     等号“=”前后不可以有空格。

     Shell中不需要显式的语法来声明变量。

     变量名不可以直接和其他字符相连，如果想相连，必须用括号：    echo “this is $(he)llo!”

umask命令

umask
功能说明：指定在建立文件时预设的权限掩码。
语　　法：umask [-S][权限掩码]
补充说明：umask可用来设定[权限掩码]。[权限掩码]是由3个八进制的数字所组成，将现有的存取权限减掉权限掩码后，即可产生建立文件时预设的权限。

在Linux中 umask:目前用户在新建文件或者目录时候的默认权限值
在Linux中r，w，x的值分别是 ： 4 2 1

链接分硬链接和符号链接。

符号链接可以建立对于文件和目录的链接。符号链接可以跨文件系统，即可以跨磁盘分区。符号链接的文件类型位是l，链接文件具有新的i节点。

硬链接不可以跨文件系统。它只能建立对文件的链接，硬链接的文件类型位是－，且硬链接文件的i节点同被链接文件的i节点相同。

软链接产生的是一个新的文件(类似快捷方式)，但这个文件的作用就是专门指向某个文件的，删了这个软连接文件，那就等于不需要这个连接，和原来的存在的实体原文件没有任何关系，但删除原来的文件，则相应的软连接不可用（cat那个软链接文件，则提示“没有该文件或目录“）。

硬链接实际上是为文件建一个别名，链接文件和原文件实际上是同一个文件。可以通过ls -i来查看一下，这两个文件的inode号是同一个，说明它们是同一个文件。

聚集索引

聚集索引是一种索引，该索引中键值的逻辑顺序决定了表中相应行的物理顺序。

聚集索引确定表中数据的物理顺序。聚集索引类似于电话簿，按姓氏排列数据。由于聚集索引规定数据在表中的物理存储顺序，因此一个表只能包含一个聚集索引。但该索引可以包含多个列（组合索引），就像电话簿按姓氏和名字进行组织一样。

聚集索引对于那些经常要搜索范围值的列特别有效。使用聚集索引找到包含第一个值的行后，便可以确保包含后续索引值的行在物理相邻。例如，如果应用程序执行的一个查询经常检索某一日期范围内的记录，则使用聚集索引可以迅速找到包含开始日期的行，然后检索表中所有相邻的行，直到到达结束日期。这样有助于提高此类查询的性能。同样，如果对从表中检索的数据进行排序时经常要用到某一列，则可以将该表在该列上聚集（物理排序），避免每次查询该列时都进行排序，从而节省成本。
当索引值唯一时，使用聚集索引查找特定的行也很有效率。例如，使用唯一雇员 ID 列 emp_id 查找特定雇员的最快速的方法，是在 emp_id 列上创建聚集索引或 PRIMARY KEY 约束。

块级元素与行内元素的区别

1. 块级元素会独占一行，其宽度自动填满其父元素宽度。行内元素不会独占一行，相邻的行内元素会排列在同一行，直至一行排不下才会换行，其宽度随元素的内容而变化。
2. 块级元素可以包含行内元素和块级元素；行内元素不能包含块级元素。
3. 行内元素设置width、height、margin-top、margin-bottom、padding-top、padding-bottom无效。

块级元素与行内元素的转换:

display:inline-block;
display:inline;
display:block;

Cookie/Session机制

会话（Session）跟踪是Web程序中常用的技术，用来跟踪用户的整个会话。常用的会话跟踪技术是Cookie与Session。Cookie通过在客户端记录信息确定用户身份，Session通过在服务器端记录信息确定用户身份。

###Cookie
Cookie实际上是一小段的文本信息。客户端请求服务器，如果服务器需要记录该用户状态，就使用response向客户端浏览器颁发一个Cookie。客户端浏览器会把Cookie保存起来。当浏览器再请求该网站时，浏览器把请求的网址连同该Cookie一同提交给服务器。服务器检查该Cookie，以此来辨认用户状态。服务器还可以根据需要修改Cookie的内容。

Cookie的原理

子域名可以访问根域名的cookie，反之则不可以。cookie，对于不同的浏览器有不同的大小限制。

Session

Session是另一种记录客户状态的机制，不同的是Cookie保存在客户端浏览器中，而Session保存在服务器上。客户端浏览器访问服务器的时候，服务器把客户端信息以某种形式记录在服务器上。这就是Session。

Session对象是在客户端第一次请求服务器的时候创建的。Session也是一种key-value的属性对，通过getAttribute(Stringkey)和setAttribute(String key，Objectvalue)方法读写客户状态信息。

Session保存在服务器端。为了获得更高的存取速度，服务器一般把Session放在内存里。每个用户都会有一个独立的Session。如果Session内容过于复杂，当大量客户访问服务器时可能会导致内存溢出。因此，Session里的信息应该尽量精简。

Session生成后，只要用户继续访问，服务器就会更新Session的最后访问时间，并维护该Session。用户每访问服务器一次，无论是否读写Session，服务器都认为该用户的Session“活跃（active）”了一次。

CPU调度算法

FCFS 先到先服务

一旦选定进程，那么在结束之前就不能再切换到另一个进程。

SJF 最短优先 精确的讲是最短下一个CPU区间的算法 （可能导致饥饿）

前面提到，一个进程是由CPU区间和I/O区间交替组成的。而SJF是看哪个进程的CPU区间最短。

• SRTF抢占式：又称最短剩余优先，当新进来的进程的CPU区间比当前执行的进程所剩的CPU区间短，则抢占。
• 非抢占：称为下一个最短优先，因为在就绪队列中选择最短CPU区间的进程放在队头。

优先级调度算法 pintos的优先级是0-63 0为最低优先级，63为最高优先级

SJF是特殊的优先级调度算法，以CPU区间长度的倒数为优先级。

• 内部优先级：通过内部数据比如内存要求等。
• 外部优先级：用户自己设定。set_priority

分为抢占式和非抢占式，前者为如果进来的进程优先级高于运行的进程，则替换；后者只是在就绪队列中按优先级排队。

缺点：无线阻塞或饥饿。前者为一个优先级高且运行时间长的进程一直阻塞，后者为优先级低的进程永远都得不到执行。

解决饥饿的方法是老化。通过每个时间间隔后将等待的进程优先级降低。

转轮法 RR算法 抢占式

用于分时系统。每个进程都占用一个时间片的时间。就绪队列为FIFO循环队列。如果一个进程的CPU区间长度小于时间片，则继续下面的进程；如果大于时间片，则中断切换到下一个进程执行。通常时间片长度为10ms-100ms，由此需要确定时间片大小使得上下文切换次数适当少。

多级队列调度

根据某种性质将一个就绪队列分成不同的独立队列，如系统进程，交互进程（前台进程），交互编辑进程，批处理进程，学生进程。

每个队列都有不同的调度算法。

每个队列都有优先级，比如前台队列就比后台队列要有绝对的优先级，因此队列间的分配方法：

（1）只有优先级高的队列为空，才能执行低优先级队列。

（2）为队列分配不同权重的CPU时间，优先级高的分配时间多。

多级反馈队列 抢占式

  动态调整进程，进程在不同队列之间移动，虽然在队列间移动需要耗费资源，但是更合理。按照CPU区间的大小分队列。进程之间的划分是按照所花CPU时间划分，比如队列0是就绪队列，且规定一个时间上界，如果一个进程没能规定时间完成，则被放入队列1中。CPU区间越大的进程就被放入低优先中。每个进程一开始都进入就绪队列。

页替换算法与缺页率

缺页中断

  在请求分页系统中，可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存时，会产生一次缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。

缺页本身是一种中断，与一般的中断一样，需要经过4个处理步骤：
　　1. 保护CPU现场
　　2. 分析中断原因
　　3. 转入缺页中断处理程序进行处理
　　4. 恢复CPU现场，继续执行
　　但是缺页中断时由于所要访问的页面不存在于内存时，有硬件所产生的一种特殊的中断，因此，与一般的中断存区别：
　　 1. 在指令执行期间产生和处理缺页中断信号
　　 2. 一条指令在执行期间，可能产生多次缺页中断
　　 3. 缺页中断返回时，执行产生中断的那一条指令，而一般的中断返回时，执行下一条指令

页面置换算法

  进程运行过程中，如果发生缺页中断，而此时内存中有没有空闲的物理块是，为了能够把所缺的页面装入内存，系统必须从内存中选择一页调出到磁盘的对换区。但此时应该把那个页面换出，则需要根据一定的页面置换算法（Page Replacement Algorithm)来确定。

最佳置换（Optimal， OPT)

  置换以后不再被访问，或者在将来最迟才回被访问的页面，缺页中断率最低。但是该算法需要依据以后各业的使用情况，而当一个进程还未运行完成时，很难估计哪一个页面是以后不再使用或在最长时间以后才会用到的页面。所以该算法是不能实现的。但该算法仍然有意义，作为衡量其他算法优劣的一个标准。

先进先出置换算法（First In First Out, FIFO)

　置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。但是该算法会淘汰经常访问的页面，不适应进程实际运行的规律，目前已经很少使用。

最近最久未使用置换算法（Least Recently Used， LRU）

　　置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。
　　LRU算法普偏地适用于各种类型的程序，但是系统要时时刻刻对各页的访问历史情况加以记录和更新，开销太大，因此LRU算法必须要有硬件的支持。

缺页率

缺页中断率： FIFO > LRU > OPT
  所以OPT的算法效果最好，然后时LRU，最后是FIFO

Linux 设备与驱动

1. 独享设备：在一个用户作业未完成或退出之前，此设备不能分配给其他作业用。所有字符设备都是独享设备。如输入机、磁带机、打印机等。——很明显：需要装驱动。
2. 共享设备：多个用户作业或多个进程可以“同时”从这些设备上存取信息。软硬盘、光盘等块设备都是共享设备。——无需驱动。
3. 虚拟设备：通过软件技术将独享设备改造成共享设备。例如：通过SPOOLing技术将一台打印机虚拟成多台打印机。——实质还是独享设备，需要驱动。
4. 系统设备，需要驱动。

linux定时任务cron

　　 　 　 　 　　command
　　分钟(0-59)　小时(0-23)　日期(1-31)　月份(1-12)　星期(0-6,0代表星期天)　 命令
　　
　　第1列表示分钟1～59 每分钟用或者 */1表示
　　第2列表示小时1～23（0表示0点）
　　第3列表示日期1～31
　　第4列表示月份1～12
　　第5列标识号星期0～6（0表示星期天）

在以上任何值中，星号（）可以用来代表所有有效的值。譬如，月份值中的星号意味着在满足其它制约条件后每月都执行该命令。
　　整数间的短线（-）指定一个整数范围。譬如，1-4 意味着整数 1、2、3、4。
　　用逗号（,）隔开的一系列值指定一个列表。譬如，3, 4, 6, 8 标明这四个指定的整数。
　　正斜线（/）可以用来指定间隔频率。在范围后加上 / 意味着在范围内可以跳过 integer。譬如，0-59/2 可以用来在分钟字段定义每两分钟。间隔频率值还可以和星号一起使用。例如，/3 的值可以用在月份字段中表示每三个月运行一次任务。
　　开头为井号（#）的行是注释，不会被处理

游戏开发-基于netty的文字冒险游戏-1

---

需求分析

概要

现在要设计一个多人在线迷宫移动游戏，多个人可以同时在迷宫中冒险、交流、触发剧情。

登陆系统

待开发

角色信息系统

待开发

场景及角色移动系统

玩家可以前后左右移动，移动时遇到迷宫边界或者障碍则进行提示。
遇到其他玩家，这提示相同的双方的身份。
实时刷新迷宫中角色、障碍物、NPC、怪物、建筑的位置。

战斗系统

待开发

---

总体设计

数据库设计

数据库设计

表名	描述

模块设计

场景及角色移动

用枚举数组来模拟游戏地图，每个枚举对象代表游戏地图的一个点的状态，如道路、山岭、河流、旅馆。

编码

客户端代码

测试

大数据开发知识点-1

数据倾斜

定义：

数据倾斜在MapReduce编程模型中十分常见,用最通俗易懂的话来说,数据倾斜无非就是大量的相同key被partition分配到一个分区里,造成了’一个人累死,其他人闲死’的情况,这种情况是我们不能接受的,这也违背了并行计算的初衷,首先一个节点要承受着巨大的压力,而其他节点计算完毕后要一直等待这个忙碌的节点,也拖累了整体的计算时间,可以说效率是十分低下的。

原理以及现象分析：

出现数据倾斜的原因，基本只可能是因为发生了shuffle操作，在shuffle的过程中，出现了数据倾斜的问题。因为某个，或者某些key对应的数据，远远的高于其他的key。你在自己的程序里面找找，哪些地方用了会产生shuffle的算子，groupByKey、countByKey、reduceByKey、join。看log一般会报是在你的哪一行代码，导致了OOM异常；或者呢，看log，看看是执行到了第几个stage！！！

###解决思路：

1. 对包含少数几个数据量过大的key的那个RDD，通过sample算子采样出一份样本来，然后统计一下每个key的数量，计算出来数据量最大的是哪几个key。
2. 然后将这几个key对应的数据从原来的RDD中拆分出来，形成一个单独的RDD，并给每个key都打上n以内的随机数作为前缀，而不会导致倾斜的大部分key形成另外一个RDD。

接着将需要join的另一个RDD，也过滤出来那几个倾斜key对应的数据并形成一个单独的RDD，将每条数据膨胀成n条数据，这n条数据都按顺序附加一个0~n的前缀，不会导致倾斜的大部分key也形成另外一个RDD。
再将附加了随机前缀的独立RDD与另一个膨胀n倍的独立RDD进行join，此时就可以将原先相同的key打散成n份，分散到多个task中去进行join了。
而另外两个普通的RDD就照常join即可。
最后将两次join的结果使用union算子合并起来即可，就是最终的join结果。

---

Hbase实现快速查询的原因

快速查询:

1. 分区储存
   HBase将每个表划分为多个region，每个region用rowkey来划分，数据的查询也是通过rowkey来查询
   查询过程：client向HBase依赖的zookeeper获取metaregion的位置，然后通过metaregion中的记录获取到所要查询的rowkey
   对应的region，这样就确定到一个region范围
2. HFile的索引
   HFile是HBase最底层数据文件的存储格式，一个region下包含着多个HFile，每个HFile的最后有末尾固定的长度来存储索引，这样可以快速确认你所查询的数据是否在这个HFile中
3. BloomFilter
   BloomFilter是针对HFile的，每一条存储的数据，BloomFilter将记录hash进固定的数组中，这样在查询时对应Hash数组，如果对应位置被改变了，那么所要查的记录可能在这个文件里。如果没有被改变，那么肯定不在，这样可以大幅提高查询的效率

实时查询：

实时查询，可以认为是从内存中查询，一般响应时间在1秒内。HBase的机制是数据先写入到内存中，当数据量达到一定的量（如128M）， 再写入磁盘中， 在内存中，是不进行数据的更新或合并操作的，只增加数据，这使得用户的写操作只要进入内存中就可以立即返回，保证了HBase I/O的 高性能。

实时查询，即反应根据当前时间的数据，可以认为这些数据始终是在内存的，保证了数据的实时响应。

像RDBMS这让的关系型数据库，按行存储，通过严格的ACID事务来进行同步，这造成了系统的可用性和伸缩性方面的大大折扣
HBase，Casandra是NOSQL的数据库或者说no relation，按列存储，是最终一致性的系统，他们为了高的可用性牺牲了一部分的一致性，向HBase就不支持事务特性。

不同点：

1. 存储模式：HBase是基于列存储的，每个列族都有几个HFile保存，不同列族的文件是分离的，关系型数据库则是基于表格结构和行模式保存的
2. 数据操作：HBase只有最简单的CRUD操作，表与表之间是相互分离的，没有关系型数据库中的那些连接操作
3. 数据类型：HBase只有简单的字符类型，所有的类型都是交由用户自己处理，他只保存字符串。而关系性数据库则有丰富的类型和存储方式
4. 数据维护：HBase是基于HDFS的，所以真实的更新操作是通过新增新纪录外加时间戳来实现的
5. 可伸缩性：HBase这类分布式数据库就是为了这个目的开发出来的，他可以轻松的增加或减少硬件的数量，对错误的兼容性比较高

---

Zookeeper的实现原理

ZooKeeper 是一个开源的分布式协调服务，分布式应用程序可以基于 ZooKeeper 实现诸如数据发布/订阅、负载均衡、命名服务、分布式协调/通知、集群管理、Master 选举、分布式锁和分布式队列等功能。

集群角色

• Leader 负责进行投票的发起和决议，更新系统状态
• Follower 追随者用于接受客户端请求并向客户端返回结果，在选主过程中参与投票
• Observer 可以接受客户端连接，将写请求转发给leader，但observer不参加投票过程，只同步leader的状态，observer的目的是为了扩展系统，提高读取速度
• client，请求发起

一个ZooKeeper集群同一时刻只会有一个Leader，其他都是Follower或Observer。Zookeeper的核心是原子广播，这个机制保证了各个Server之间的同步。实现这个机制的协议叫做Zab协议。Zab协议有两种模式，它们分别是恢复模式（选主）和广播模式（同步）。当服务启动或者在领导者崩溃后，Zab就进入了恢复模式，当领导者被选举出来，且大多数Server完成了和leader的状态同步以后，恢复模式就结束了。状态同步保证了leader和Server具有相同的系统状态。

为了保证事务的顺序一致性，zookeeper采用了递增的事务id号（zxid）来标识事务。所有的提议（proposal）都在被提出的时候加上了zxid。实现中zxid是一个64位的数字，它高32位是epoch用来标识leader关系是否改变，每次一个leader被选出来，它都会有一个的epoch，标识当前属于那个leader的统治时期。低32位用于递增计数。

每个Server在工作过程中有三种状态：

• LOOKING：当前Server不知道leader是谁，正在搜寻
• LEADING：当前Server即为选举出来的leader
• FOLLOWING：leader已经选举出来，当前Server与之同步

重要概念

会话(Session)

Session 是指客户端会话，在讲解客户端会话之前，我们先来了解下客户端连接。在 ZooKeeper 中，一个客户端连接是指客户端和 ZooKeeper 服务器之间的TCP长连接。

数据节点(ZNode)

谈到分布式的时候，一般『节点』指的是组成集群的每一台机器。而ZooKeeper 中的数据节点是指数据模型中的数据单元，称为 ZNode。ZooKeeper 将所有数据存储在内存中，数据模型是一棵树（ZNode Tree），由斜杠（/）进行分割的路径，就是一个ZNode，如 /hbase/master，其中 hbase 和 master 都是 ZNode。每个 ZNode 上都会保存自己的数据内容，同时会保存一系列属性信息。

在 ZooKeeper 中，ZNode 可以分为持久节点和临时节点两类。

• 持久节点

所谓持久节点是指一旦这个 ZNode 被创建了，除非主动进行 ZNode 的移除操作，否则这个 ZNode 将一直保存在 ZooKeeper 上。

• 临时节点

临时节点的生命周期跟客户端会话绑定，一旦客户端会话失效，那么这个客户端创建的所有临时节点都会被移除。

另外，ZooKeeper 还允许用户为每个节点添加一个特殊的属性：SEQUENTIAL。一旦节点被标记上这个属性，那么在这个节点被创建的时候，ZooKeeper 就会自动在其节点后面追加上一个整型数字，这个整型数字是一个由父节点维护的自增数字。

Zookeeper 的读写机制

• Zookeeper是一个由多个server组成的集群
• 一个leader，多个follower
• 每个server保存一份数据副本
• 全局数据一致
• 分布式读写
• 更新请求转发，由leader实施

Zookeeper 的保证

• 更新请求顺序进行，来自同一个client的更新请求按其发送顺序依次执行
• 数据更新原子性，一次数据更新要么成功，要么失败
• 全局唯一数据视图，client无论连接到哪个server，数据视图都是一致的
• 实时性，在一定事件范围内，client能读到最新数据

---

数据一致性算法 – Paxos

节点角色

Paxos 协议中，有三类节点:

• Proposer:提案者

Proposer 可以有多个，Proposer 提出议案(value)。所谓 value，在工程中可以是任何操作，例如“修改某个变量的值为某个值”、“设置当前 primary 为某个节点”等等。Paxos 协议中统一将这些操作抽象为 value。
不同的 Proposer 可以提出不同的甚至矛盾的 value，例如某个 Proposer 提议“将变量 X 设置为 1”，另一个 Proposer 提议“将变量 X 设置为 2”，但对同一轮 Paxos 过程，最多只有一个 value 被批准。

• Acceptor:批准者

Acceptor 有 N 个，Proposer 提出的 value 必须获得超过半数(N/2+1)的
Acceptor 批准后才能通过。Acceptor 之间完全对等独立。

• Learner:学习者

Learner 学习被批准的 value。所谓学习就是通过读取各个 Proposer 对 value 的选择结果，如果某个 value 被超过半数 Proposer 通过，则 Learner 学习到了这个 value。

这里类似 Quorum 议会机制，某个 value 需要获得 W=N/2 + 1 的 Acceptor 批准，Learner 需要至少读取 N/2+1 个 Accpetor，至多读取 N 个 Acceptor 的结果后，能学习到一个通过的 value。

约束条件

上述三类角色只是逻辑上的划分，实践中一个节点可以同时充当这三类角色。有些文章会添加一个Client角色，作为产生议题者，实际不参与选举过程。

Paxos中 proposer 和 acceptor 是算法的核心角色，paxos 描述的就是在一个由多个 proposer 和多个 acceptor 构成的系统中，如何让多个 acceptor 针对 proposer 提出的多种提案达成一致的过程，而 learner 只是“学习”最终被批准的提案。

Paxos协议流程还需要满足几个约束条件：

• Acceptor必须接受它收到的第一个提案；
• 如果一个提案的v值被大多数Acceptor接受过，那后续的所有被接受的提案中也必须包含v值（v值可以理解为提案的内容，提案由一个或多个v和提案编号组成）；
• 如果某一轮 Paxos 协议批准了某个 value，则以后各轮 Paxos 只能批准这个value；

---

倒序排序

倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。

倒排索引有两种不同的反向索引形式：

• 一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。
• 一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。

后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。

通过上面的定义可以知道，一个倒排索引包含一个单词词典和一个倒排文件。其中单词词典包含了所有粒度的拆分词；倒排文件则保存了该词对应的所有相关信息。

---

Bitmap大数据去重

BitMap 基于位的映射。

bitmap算法思想

32位机器上，一个整形，比如int a; 在内存中占32bit位，可以用对应的32bit位对应十进制的0-31个数，bitmap算法利用这种思想处理大量数据的排序与查询。

优点：

1. 运算效率高，不许进行比较和移位；
2. 占用内存少，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。

缺点：

所有的数据不能重复。即不可对重复的数据进行排序和查找。

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

public static void main(String[] args) {
        int [] array = new int [] {1,2,3,22,0,3};
        BitSet bitSet  = new BitSet(6);
        //将数组内容组bitmap
        for(int i=0;i<array.length;i++)
        {
            bitSet.set(array[i], true);
        }
       System.out.println(bitSet.size());
        System.out.println(bitSet.get(3));
    }

---

布隆过滤器

Bloom Filter是一种空间效率很高的随机数据结构，Bloom Filter可以看做是对bit-map的扩展。

原理如下：

当一个元素被加入集合时，通过K个Hash函数将这个元素映射成一个位阵列(Bit Array)中的K个点，把它们置为1，检索时我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了。

1. 如果这些点有任何一个0，那么被检索元素一定不存在；

2. 如果都是1，那么被检索元素可能存在；

使用场景

主要使用场景:用来检测某个元素是否是巨量数据集合中的成员，但识别结果存在误差；

识别场景：某个元素实际不存在，但是由于前面元素在进行多个Hash时，刚好对应位为1，那么会误认为其存在，但实际不存在。

如果某个成员确实属于集合，那么Bloom Filter一定能够给出正确的判断。