HBase数据模型

什么是HBase

HBase是开源的NoSQL分布式数据库，是阿帕奇软件基金会的项目之一。HBase参考谷歌BigTable设计，对稀疏表提供更高的存储空间使用率和读写效率。HBase采用存储计算分离架构，存储层基于HDFS存储数据，提供容错机制和可靠性，计算层提供灵活快速的水平扩展、负载均衡和故障恢复能力。

一个分布式系统最多只能同时满足一致性（Consistency）（all nodes see the same data at the same time）、可用性（Availability）（Reads and writes always succeed）和分区容错性（Partition tolerance）（the system continues to operate despite arbitrary message loss or failure of part of the system）这三项中的两项，HBase提供强一致语义，在CAP理论中属于CP系统。

HBase和关系型数据库的差异如下表所示。

HBase的数据模型

HBase以column family组织数据，以rowkey索引数据。其中列族需要在试用期那预先创建，列名不需要预先生命，因此支持半结构化数据模型。支持保留多个版本的数据，通过（行键+列族+列名+版本号）定位具体的值。

HBase数据模型的优缺点

HBase架构设计

主要组件设计：

1. HMaster：元数据管理，集群调度，保活。
2. RegionServer：提供数据读写服务，每个实例负责若干个互不重叠rowkey区间内的数据。
3. ThriftServer：提供Thrift API读写的代理层。

组件依赖：

1. Zookeeper：分布式一致性共识协作管理，例如HMaster选主，人物分发，元数据变更管理等。
2. HDFS：分布式存储系统。

HMaster职责

1. 管理RegionServer实例生命周期，保证服务可用性。
2. 协调RegionServer数据故障恢复，保证数据正确性。
3. 集中管理集群元数据，执行负载均衡。
4. 定期巡检元数据，调整数据分布，清理废弃数据等
5. 处理用户主动发起的元数据操作。

RegionServer职责

1. 提供部分rowkey区间数据读写服务
2. 如果负责meta表，向科五段SDK提供rowkey位置信息。
3. 认领Hmaster发布的故障恢复任务
4. 处理HMaster下达的元数据操作。

Zookeeper职责

1. HMaster登记信息，对active/backup分工达成共识
2. RegionServer登记信息，失联时HMaster保活处理
3. 登记meta表位置信息，供SDK查询读写位置信息。
4. 供HMaster和RegionServer写作处理分布式任务

Region负载均衡

定期巡检各个RegionServer上的region数量，保持region的数量均匀分布在各个RegionServer上。
简单负载均衡具体步骤：

1. 根据总Region数量和RegionServer数量计算平均region数目，设定弹性上下界避免不必要的操作。
2. 将RegionServer按照region数量降序排序，对region数量超出上限的选取要牵出的region并按创建时间从新到老排序

随机负载均衡

1. 随机尝试不同的region放置策略，根据提供的cost function计算不同策略的分值排名
2. cost计算将下列指标纳入统计：region负载，表负载，数据本地性，Memstore大小，HFile大小
3. 根据配置加权计算最终cost。

FavoredNodeLoadBalancer

1. 用于充分利用本地读写HDFS文件来优化读写性能。
2. 每个region会指定优选的3个RegionServer地址，同时会告知HDFS在这些优选节点放置该region的数据
3. 即使第一节点出现故障，HBase也可以将第二节点提升为第一节点，保证稳定的读时延。

HMaster恢复流程

HMaster自身恢复流程

1. 监听到/hbase/active-master临时节点被删除的时间，触发主逻辑。
2. 选主成功后执行HMaster启动流程，从持久化存储读取未完成的procedures从之前状态继续执行
3. 故障HMaster实例恢复后发现主节点已经存在，继续监听/hbase/active-master

调度RegionServer的故障恢复流程

1. AssignmentManager从procedure列表中找出Region-in- Transition状态的region继续调度过程
2. RegionServerTracker从Zookeeper梳理online状态的RegionServer列表，结合ServerCrashProcedure列表，HDFS中WAL目录里alive/splitting状态RegionServer记录，获取掉线RegionServer的列表。

下载ispace.xjtu.edu.cn中的仅预览文件

起因很简单，学习课程的时候发现老师上传的讲稿文件没有下载按钮。之前使用ispace的时候是可以下载的，有两个按钮，一个是预览，一个是下载。

但是现在的文稿不能下载了，然而考试是开卷考试，下载ppt势在必行。

启用F12查看network

本来以为打开此页面的时候ppt就已经加载好，故启用F12，搜索了一圈download和下载等关键字， 无果。

无意间想到有可能是预览的时候才加载，故network了一下。

第一段net是打开网页，第二段是点击预览的时候发生的数据包。发现preview关键词。

pdf链接明文传输，非常开心，复制链接直接下载就行

看了一下链接，链接的下载有timestamp和token，缺一不可，逻辑还算严谨。但是明文传输实在是对学生太友好了。

学习和了解gurobi求解器日志对于理解算法和数学模型有很大帮助，所以加以记录。本文主要记录了simplex和MIP的求解日志。

Header

1
2
3

Optimize a model with 755 rows, 2756 columns and 8937 nonzeros
Model fingerprint: 0x22935346
Variable types: 0 continuous, 2756 integer (0 binary)

展示了模型的大小以及整数变量数目。

1
2
3
4
5

Coefficient statistics:
  Matrix range     [1e+00, 1e+04]
  Objective range  [1e+00, 1e+04]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+04]

这个信息给出了一个非常粗略的指示，说明您在解决模型时是否可以预期数值问题。

Simplex Logging

单纯形日志有三部分，presolve部分，求解过程和总结部分

Presolve Section

1
2
3

Presolve removed 2349 rows and 3378 columns
Presolve time: 0.04s
Presolved: 3722 rows, 8852 columns, 30908 nonzeros

第一步是使用presolve算法简化模型。
示例输出显示，presolve能够删除2349行和3378列，这需要0.04秒。预解部分的最后一行显示了预解后模型的大小。这是传递给simplex优化器的模型的大小。请注意，为该模型计算的解决方案在simplex完成后会自动转换为原始问题的解决方案(在这个过程中通常称为uncrush)，但这个uncrush步骤是透明的，不会产生日志输出。

Progress Section

在每个输出行五列显示单纯形迭代执行的数量,当前的目标函数值,原始的不可行性的程度(计算违反约束的绝对值之和),对偶不可行性的程度(计算违反对偶约束的绝对值之和),和花费的时间(以挂钟时间计算)。Gurobi求解器中默认的单纯形算法是对偶单纯形，它试图在执行单纯形轴心来改进目标的同时保持对偶可行性。

Summary Section

1
2

Solved in 20370 iterations and 5.75 seconds
Optimal objective  1.126639304e+07

字面意思

MIP Logging

日志也是分为三部分the presolve section, the simplex progress section, and the summary section.

Presolve Section

1
2
3
4

Presolve removed 0 rows and 3 columns
Presolve time: 0.01s
Presolved: 12 rows, 148 columns, 1615 nonzeros
Variable types: 1 continuous, 147 integer (145 binary)

在本例中，presolve能够删除3列。最后两行显示了传递给分支切割算法的模型的大小以及剩余变量的类型。

Progress Section

1

Found heuristic solution: objective 157344.61033

这句话说明gurobi在root relaxation 之前用启发式找到了一个整数可行解

1

Root relaxation: objective 3.889390e+04, 50 iterations, 0.00 seconds

第二个是root relaxation，如果这一步耗费时间比较长，会自动将log展开

Nodes部分(前两列)提供了关于搜索进展的一般定量信息。第一列显示到目前为止已经探索的分支和剪切节点的数量，而第二列显示搜索树中仍未探索的叶子节点的数量。有时，输出行开头会有一个H或字符。这表明通过MIP启发式(H)或分支()找到了一个新的可行解。

Current Node部分提供了在分支和切割树中研究的特定节点的信息。它显示了相关松弛的目标，分支和切割树中节点的深度，以及在相关松弛中具有非整数值的整数变量的数量。（松弛变量的数目）

Objective Bounds部分提供了一个可行解的最重要的目标值的信息(即，当前可行解的目标值)，以及搜索树的叶子节点提供的当前目标边界。最佳目标值总是在这两个值之间。本节的第三栏(差距)显示了两个客观边界之间的相对差距。当此间隙小于MIPGap参数时，优化终止。

日志的Work部分提供了到该点为止已经执行了多少工作的信息。第一列显示了分枝和切割树中每个节点执行的单纯形迭代的平均次数。最后一列显示自解算开始以来所经过的时间。

注意，所研究的节点计数通常在较长一段时间内保持为0。这意味着Gurobi MIP求解器正在处理根节点。Gurobi求解器通常会在根节点上花费大量的精力，生成切割平面并尝试各种启发式方法，以减少后续的分支和切割树的大小。

Summary Section

1
2
3
4
5
6
7
8
9
10

Cutting planes:
  Gomory: 1
  MIR: 17

Explored 313128 nodes (1741251 simplex iterations) in 4.80 seconds
Thread count was 8 (of 8 available processors)
Solution count 7: 40005.1 40697.1 41203.6 ... 157345

Optimal solution found (tolerance 1.00e-04)
Best objective 4.000505414200e+04, best bound 4.000505414200e+04, gap 0.0000%

在这个示例中，Gurobi求解器只需要不到5秒的时间就可以将模型求解到最优，并且它使用了8个线程(线程数可以通过threads参数进行限制)。最佳可行解目标与最佳界之间的差距为0.0%，这产生了一个最优终止状态，因为实现的差距小于默认MIPGap参数值。

实变函数和泛函分析

最近学习实变函数和泛函分析，在翟老师的讲解下学习了之前数学家的工作，翟老师也说，实变函数是上世纪才系统性完善的，是近代的数学，很值得我们学习。而且我们学习的都是这些数学大师一生中最精彩的工作，仔细研读可以学到很多数学思想。

为了理解翟老师课上的一些知识，我便在淘宝下单了周民强的实变函数论，翻开附录发现竟有一章是勒贝格传，读传记是我学习数学的一大乐趣之一。故做一些记录。

勒贝格1875年6月28日生于法国的博伟，1941年7月26日卒于巴黎。勒贝格的父亲是一名印刷厂职工，酷爱读书，颇有教养。在父亲的影响下，勒贝格从小勤奋好学，成绩优秀，特别擅长计算。不幸，父亲去世过早。家境衰落，勒贝格在学校老师的帮助下进入中学，后又转入巴黎，1894年考入高等师范学校。大学毕业后，勒贝格在校图书馆工作了两年。在这期间，出版了E.波雷尔关于点集测度的新方法的《函数论讲义》，特别是研究生R.贝尔发表了关于不连续实变函数理论的第一篇论文，这些成功的研究工作说明在上述崭新的领域中进行开拓挥霍的何等重要的成就，因而激发了勒贝格的热情。从1899年到1902年勒贝格在南锡的一所中学任教，虽然工作繁忙，但仍孜孜不倦的研究实变函数，理论，并于1902年发表了博士论文“积分、长度与面积”。在这篇文章中，勒贝格厂里了后来以他的名字命名的积分理论。伺候，他开始在大学任教，并出版了一系列重要著作：《积分法和原函数分析讲义》；《三角级数讲义》。接着，勒贝格又陆续发表了许多关于函数的微分、积分理论的研究成果，勒贝格于1921年获得法兰西血压u呢教授称号，一年作为C.若尔当的后记人被选为巴黎科学院院士。

勒贝格对数学的主要贡献属于积分论领域，这是实变函数理论的中心课题。19世纪以来，微积分开始进入严密话的阶段。1854年，B.黎曼引入了以他的名字命名的积分，这一理论的应用范围主要是连续函数，随着K.威尔斯特拉斯和G.康托尔工作的温室，在数学中出现了许多奇怪的函数与现象，致使黎曼积分理论暴漏出较大的局限性。几乎与这一理论发展的同时，人就已经广泛的开展了对积分理论的改造工作。当时，关于积分论的工作主要集中于无穷集合的性质的探讨，而无处稠密的集合具有正的外容度性质的发现，使集合的测度概念在积分论的研究中占有重要地位。积分的几何意义是曲线围成的面积，黎曼积分的定义是建立在对区间长度的分割的基础上的。因此，人们自然会考虑如何吧长度、面积等概念扩充到更广泛的点集类上，从而吧积分的概念置于集合测度理论的框架之中。这一思想的重要性在于使人们认识到：几何的测度与可测性的推广将意味着函数的积分与可积性的推广。勒贝格积分正式建立在勒贝格测度理论的基础上，是黎曼积分的扩充。

勒贝格曾对他的积分思想做过一个生动有趣的描述：“我必须偿还一笔钱。如果我从口袋中随意地摸出来各种不同面值的钞票，逐一的还给债主直到全部还清，这就是黎曼积分法，不过我还有另外一种做法，就是把钱全部拿出来并吧相同棉质的钞票放在一起，然后再付给应还的数目，这就是我的积分法。”

早在19世纪初期，由J.傅立叶在关于三角级数的工作中提出：当一个有界函数可以表示为一个三角级数时，该级数是它的傅里叶级数吗？这一问题与一个无穷级数是否可以逐项积分有着密切的关系。傅立叶当时曾认为在其和为有界函数时这一运算是正确的，从而给上述问题肯定的答复。然而到了19世纪末，人们认识到逐项积分并不总是可行的，甚至对于黎曼可积函数的一致有界的技术也是这样，因为由该级数所表示的函数不一定是黎曼可积的。这个问题促使勒贝格在新的积分理论中获得了一个十分重要的结果：控制收敛定理。作为一个特殊情形他指出，勒贝格可积的一致有界技术都可以逐项进行积分，从而支持了傅里叶的结论。逐项积分在本质上就是积分号下取极限的问题，他是积分理论中经常遇到的最重要的运算之一。从而这一定理的创立显示了勒贝格积分理论的极大优越性。

勒贝格的一生都献给了数学事业。在1922年被推举为院士的时候，他的著作和论文已经达到90种之多，内容出了积分理论外，还设计集合与函数的构成、变分学、曲面面积以及纬数理论等重要课题，在人生的最后20年中，勒贝格的研究工作仍然十分活跃并反映出广泛的兴趣，不过作品的内容大都涉及教育、历史和初等几何。

勒贝格的工作是对20世纪科学领域的一个重大贡献，但和科学史上每种新思想的出现一样，并不是没有遇到阻力的。原因就是勒贝格的研究中扮演了重要角色的那些不连续函数和不可微函数被认为是违反了所谓的完美性法则，是数学中的“变态和不健康”部分。因此，他的工作收到了某些数学家的冷淡，甚至有人曾企图阻止他关于一篇讨论不可微曲面的论文的发表。勒贝格曾经感叹：“我被称为是一个没有导数的函数的那种人了。”然而，不论人们的主观愿望如何，这些具有种种奇艺性质的对象都自动地进入了研究者曾企图避开他们都问题之中。勒贝格充满信心地指出：“使得自己在这种研究中变得迟钝了的那些人，是在浪费他们的时间，而不是在从事有用的工作。”

如果有能力写一些关于泛函分析的知识类博客，推一些自己很欣赏的定理公式，那必然是更好的。可惜能力不允许，时间也不允许，只能记录一些大师的传记来表达自己的敬意了。