## 2. 线性模型的概率解释

### 推导过程

$$y^{(i)}=\theta^Tx^{(i)} + ε^{(i)}$$

Andrew Ng 讲到在大多数情况下，线性回归的误差值如果综合来看，就是符合高斯分布的。并且根据中心极限定律，正态分布确实是对误差项分布的合理猜想。

$$P(y^{(i)}|x^{(i)}; θ) = \frac{1}{\sqrt{2\pi}\sigma}exp(- \frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2})$$

$P(y^{(i)}|x^{(i)}; θ)$ 表示：在 θ 为给定的参数的情况下，概率 $y^{(i)}$ 以 $x^{(i)}$ 为随机变量的概率分布，注意 θ 不是随机变量。

$$L(θ)=L(θ;X,Y)=p(Y|X;θ) = \prod_{i=1}^{m}\frac{1}{\sqrt{2\pi}\sigma}exp(- \frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2})$$

$$l(\theta)=logL(\theta) = log\prod_{i=1}^{m}\frac{1}{\sqrt{2\pi}\sigma}exp(- \frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2})$$
$$= m\sum_{i=1}^{m}log\frac{1}{\sqrt{2\pi}\sigma} - \frac1{2\sigma^2}\sum_{i=1}^{m}(y^{(i)}-\theta^Tx^{(i)})^2$$

# Reference

## 1. 多变量的线性回归

n: 特征(features) 数量
m: 训练集数量
$x^{(i)}$:

• 表示一条训练数据的向量
• i is an index into the training set
• So
• x is an n-dimensional feature vector
• $x^{(3)}$ is, for example, the 3rd training data

$x^{(j)}_i$: The value of feature j in the ith training example

$$h_θ(x) = θ_0 + θ_1x_1 + θ_2x_2 + θ_3x_3 + θ_4x_4$$

For convenience of notation, $x_0$ = 1, 所以最后的特征向量的维度是 n+1，从 0 开始，记为”X”，

$$h_θ(x)=θ^TX$$
$θ^T$: [1 * (n+1)] matrix

### Cost Function

$$J(θ_0, θ_1, …,θ_n) = \frac1{2m}\sum_{i=1}^{m}{(h_θ(x^{(i)}) - y^{(i)})^2}$$

Repeat {
$$θ_j = θ_j - α\frac\partial{\partial J(θ_0, θ_1, …,θ_n)}$$
}

every iterator

• θj = θj - learning rate (α) times the partial derivative of J(θ) with respect to θJ(…)
• We do this through a simultaneous update of every θj value

$$\frac\partial{\partial J(θ_0, θ_1, …,θ_n)}$$
$$= \frac1m * \sum_{i=1}^{m}{(h_θ(x^{(i)}) - y^{(i)})}*x_j^{(i)}$$

## 2. Gradient Decent in practice

### Learning Rate α

• working correctly: If gradient descent is working then J(θ) should decrease after every iteration
• convergence: 收敛是指每经过一次迭代，J(θ)的值都变化甚小。
• choose α
1. When to use a smaller α
• If J(θ) is increasing, see below picture
• If J(θ) looks like a series of waves, decreasing and increasing again
• But if α is too small then rate is too slow
2. Try a range of α values
• Plot J(θ) vs number of iterations for each version of alpha
• Go for roughly threefold increases: 0.001, 0.003, 0.01, 0.03. 0.1, 0.3

## 3. Normal equation 求解多变量线性回归

### 3.1 Normal equation

$$J(θ_0, θ_1, …,θ_n) = \frac1{2m}\sum_{i=1}^{m}{(h_θ(x^{(i)}) - y^{(i)})^2}$$

$$\frac\partial{\partial θ_j}J(θ_0, θ_1, …,θ_n) = … = 0$$，其中 j = 0,1,2,…,n

$$θ = (X^TX)^{-1}X^Ty$$

## 4. Gradient descent Vs Normal equation

• Need to chose learning rate
• Needs many iterations - could make it slower
• Works well even when n is massive (millions)
• Better suited to big data
• What is a big n though: 100 or even a 1000 is still (relativity) small, If n is 10000 then look at using gradient descent
• 适用于线性回归会逻辑回归

### Normal equation

• No need to chose a learning rate
• No need to iterate, check for convergence etc.
• Normal equation needs to compute $(X^TX)^{-1}$
• This is the inverse of an n x n matrix
• With most implementations computing a matrix inverse grows by O(n3), So not great
• Slow of n is large, Can be much slower
• 仅适用于线性回归

## 5. 局部加权线性回归

$$J(\theta) = \sum_{i=1}^{m} w^{(i)}( y^{(i)}-\theta^Tx^{(i)} )^2$$

$$w^{(i)} = exp (-\frac{(x^{(i)}-x)^2}{\tau^2})$$

$w^{(i)}$的形式跟正态分布很相似，但二者没有任何关系，仅仅只是便于计算。可以发现，$x^{(j)}$ 离 $x^{(i)}$ 非常近时，${w^{(i)}_j}$ 的值接近于1，此时 j 点的贡献很大，当 $x^{(j)}$ 离 $x^{(i)}$ 非常远时，${w^{(i)}_j}$ 的值接近于 0，此时 j 点的贡献很小。

$\tau^2$ 是波长函数(bandwidth)， 控制权重随距离下降的速度，τ 越小则 x 离 $x^{(i)}$ 越远时 $w^{(i)}$ 的值下降的越快。

• 每次对一个点的预测都需要整个数据集的参与，样本量大且需要多点预测时效率低。提高效率的方法参考 Andrew More’s KD Tree
• 不可外推，对样本所包含的区域外的点进行预测时效果不好，事实上这也是一般线性回归的弱点

## Reference

http://www.holehouse.org/mlclass/04_Linear_Regression_with_multiple_variables.html

## 2. 单变量线性回归

$h_{\theta}$(x) = $\theta_{0}$ + $\theta_{1}$

## 3. Cost Function

$$\frac1{2m}\sum_{i=1}^{m}{(h_{\theta}(x^{(i)}) - y^{(i)})^2}$$ 最小的 $\theta$ 值。

$$J(\theta_0, \theta_1) = \frac1{2m}\sum_{i=1}^{m}{(h_{\theta}(x^{(i)}) - y^{(i)})^2}$$

#### Cost Function 的作用

$$J(\theta_1)= \frac1{2m}\sum_{i=1}^{m}{(\theta_1x^{(i)} - y^{(i)})^2}$$

## 4. 梯度下降法

• Start at 0,0 (or any other value)
• Keeping changing $\theta_0$ and $\theta_1$ a little bit to try and reduce J($\theta_0$, $\theta_1$)
• Each time you change the parameters, you select the gradient which reduces J($\theta_0$, $\theta_1$) the most possible
• Repeat
• Do so until you converge to a local minimum
Has an interesting property
• Where you start can determine which minimum you end up
• Here we can see one initialization point led to one local minimum
• The other led to a different one

### 4.1 具体的计算过程

$$\theta_j := \theta_j - \alpha \frac\partial{\partial\theta_j}J(\theta_0, \theta_1)$$
(for j = 0 and j = 1)

### 4.2 Notation

$\alpha$

• Is a number called the learning rate
• Controls how big a step you take
• If α is big have an aggressive gradient descent
• If α is small take tiny steps
• Too small
• Take baby steps
• Takes too long
• Too large
• Can overshoot the minimum and fail to converge

### 4.3 Computer

$$temp0:= \theta_0 - \alpha \frac\partial{\partial\theta_0}J(\theta_0, \theta_1)$$
$$temp1:= \theta_1 - \alpha \frac\partial{\partial\theta_1}J(\theta_0, \theta_1)$$
$$\theta_0 := temp0$$
$$\theta_1 := temp1$$

#### 4.4 利用梯度下降法求解线性回归问题

$$\frac\partial{\partial\theta_j}J(\theta_0, \theta_1)$$

$$=\frac\partial{\partial\theta_j} * \frac1{2m}\sum_{i=1}^{m}{(h_{\theta}(x^{(i)}) - y^{(i)})^2}$$

$$=\frac\partial{\partial\theta_j} * \frac1{2m}\sum_{i=1}^{m}{(\theta_0 +\theta_1x^{(i)} - y^{(i)})^2}$$

j = 0:
$$\frac\partial{\partial\theta_0}J(\theta_0, \theta_1) = \frac1{m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)}) - y^{(i)})$$
j = 1:
$$\frac\partial{\partial\theta_1}J(\theta_0, \theta_1) = \frac1{m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)}) - y^{(i)})*x^{(i)}$$

### 4.5 梯度下降法的证明

1、如果优化函数存在解析解。例如我们求最值一般是对优化函数求导，找到导数为0的点。如果代价函数能简单求导，并且求导后为0的式子存在解析解，那么我们就可以直接得到最优的参数。

2、如果式子很难求导，例如函数里面存在隐含的变量或者变量相互间存在耦合，互相依赖的情况。或者求导后式子得不到解释解，或者未知参数的个数大于方程组的个数等。这时候使用迭代算法来一步一步找到最优解。

• 当目标函数是凸函数时，梯度下降法的解是全局最优解
• 一般情况下，其解不保证是全局最优解

#### 凸函数

$$f(\frac{x_1+x_2}{2}) \le \frac{f(x_1)+f(x_2)}{2}$$

$$f(px_1+(1-p)x_2) \le pf(x_1)+(1-p)f(x_2)$$

# 要解决的问题

json 反序列化 bean 时，当某个字段在 json 中为 null 时，使用 bean 中声明的默认值。

Person 类我们改造下：

# 解决方案

## 2. JsonCreator 可行吗？

debug 过程：

com.fasterxml.jackson.databind.deser.SettableBeanProperty#deserialize，这个函数的实现是：

Person 类改为：

Person 类如下：

json:

json 反序列化是从

(补充自 liwei)

# 结论

Lombok 的 @AllArgsConstructor 注解导致 Jackson 反序列化时调用了全参构造函数，将没有出现的字段都赋值为 null 了。

1. 不使用 @AllArgsConstructor
2. 使用 @AllArgsConstructor 但是不让其在全参构造函数上加入 ConstructorProperties 注解，声明方式改为 @AllArgsConstructor(suppressConstructorProperties = true)

1. 服务异常的处理流程
2. 负载
3. 内存
4. 服务指标
5. 工具

# 2. 负载

## 2.2 查找 cpu 占用率高的线程

top -p 25603 -H
printf 0x%x 25842
jstack 25603 | grep 0x64f2

cat /proc/interrupts

（1）CPU
（2）Memory
（3）IO
（4）Network

（1）中断；
（2）上下文切换；
（3）可运行队列；
（4）CPU 利用率。

# 3. 内存

## 3.1 系统内存

free 命令
[root@server ~]# free

• total:总计物理内存的大小。
• used:已使用多大。
• free:可用有多少。
• Shared:多个进程共享的内存总额。
• buffers: 磁盘缓存的大小。
• cache:磁盘缓存的大小。
• -/+ buffers/cached): used:已使用多大，free:可用有多少。
• 已用内存 = 系统used memory - buffers - cached
（47000 = 3250000-201000-3002000）
• 可用内存 = 系统free memory + buffers + cached
（3213000 = 10000+201000+3002000）

#### 什么是buffer/cache？

• buffer 指 Linux 内存的：Buffer cache，缓冲区缓
• cache 指 Linux内存中的：Page cache，页面缓存

page cache
page cache 主要用来作为文件系统上的文件数据的缓存来用，尤其是针对当进程对文件有 read／write 操作的时候。如果你仔细想想的话，作为可以映射文件到内存的系统调用：mmap是不是很自然的也应该用到 page cache？在当前的系统实现里，page cache 也被作为其它文件类型的缓存设备来用，所以事实上 page cache 也负责了大部分的块设备文件的缓存工作。

buffer cache
buffer cache 主要用来在系统对块设备进行读写的时候，对块进行数据缓存的系统来使用。这意味着某些对块的操作会使用 buffer cache 进行缓存，比如我们在格式化文件系统的时候。一般情况下两个缓存系统是一起配合使用的，比如当我们对一个文件进行写操作的时候，page cache 的内容会被改变，而 buffer cache 则可以用来将 page 标记为不同的缓冲区，并记录是哪一个缓冲区被修改了。这样，内核在后续执行脏数据的回写（writeback）时，就不用将整个 page 写回，而只需要写回修改的部分即可。

#### 系统如何回收cache？

Linux内核会在内存将要耗尽的时候，触发内存回收的工作，以便释放出内存给急需内存的进程使用。一般情况下，这个操作中主要的内存释放都来自于对buffer／cache的释放。尤其是被使用更多的cache空间。既然它主要用来做缓存，只是在内存够用的时候加快进程对文件的读写速度，那么在内存压力较大的情况下，当然有必要清空释放cache，作为free空间分给相关进程使用。所以一般情况下，我们认为buffer/cache空间可以被释放，这个理解是正确的。

## 3.2 进程内存

### 3.2.1 进程内存统计

/proc/[pid]/status

cat /proc/[pid]/status

### 3.2.2 JVM 内存分配

java内存组成介绍：堆(Heap)和非堆(Non-heap)内存

1. JVM本身需要的内存，包括其加载的第三方库以及这些库分配的内存
2. NIO的DirectBuffer是分配的native memory
3. 内存映射文件，包括JVM加载的一些JAR和第三方库，以及程序内部用到的。上面 pmap 输出的内容里，有一些静态文件所占用的大小不在Java的heap里，因此作为一个Web服务器，赶紧把静态文件从这个Web服务器中人移开吧，放到nginx或者CDN里去吧。
4. JIT， JVM会将Class编译成native代码，这些内存也不会少，如果使用了Spring的AOP，CGLIB会生成更多的类，JIT的内存开销也会随之变大，而且Class本身JVM的GC会将其放到Perm Generation里去，很难被回收掉，面对这种情况，应该让JVM使用ConcurrentMarkSweep GC，并启用这个GC的相关参数允许将不使用的class从Perm Generation中移除， 参数配置： -XX:+UseConcMarkSweepGC -X:+CMSPermGenSweepingEnabled -X:+CMSClassUnloadingEnabled，如果不需要移除而Perm Generation空间不够，可以加大一点： -X:PermSize=256M -X:MaxPermSize=512M
5. JNI，一些JNI接口调用的native库也会分配一些内存，如果遇到JNI库的内存泄露，可以使用valgrind等内存泄露工具来检测
6. 线程栈，每个线程都会有自己的栈空间，如果线程一多，这个的开销就很明显了
7. jmap/jstack 采样，频繁的采样也会增加内存占用，如果你有服务器健康监控，记得这个频率别太高，否则健康监控变成致病监控了。

### 3.2.4 JVM 内存分析

#### 查看 JVM 堆内存情况

jmap -heap [pid]

VSZ是指已分配的线性空间大小，这个大小通常并不等于程序实际用到的内存大小，产生这个的可能性很多，比如内存映射，共享的动态库，或者向系统申请了更多的堆，都会扩展线性空间大小，要查看一个进程有哪些内存映射，可以使用 pmap 命令来查看：
pmap -x [pid]

RSZ是Resident Set Size，常驻内存大小，即进程实际占用的物理内存大小， 在现在这个例子当中，RSZ和实际堆内存占用差了2.3G，这2.3G的内存组成分别为：

#### 查看 JVM 堆各个分区的内存情况

jstat -gcutil [pid]

#### 分析 JVM 堆内存中的对象

jmap -histo:live [pid]

dump 内存
jmap -dump:format=b,file=heapDump [pid]

jhat -port 5000 heapDump

# 4. 服务指标

## 4.5 CPU利用率

CPU Load Average < CPU个数 核数 0.7

Context Switch Rate

Context Switch Rate = Interrupt Rate + TPS* N

CSR减掉IR，就是进程/线程的切换，假如主进程收到请求交给线程处理，线程处理完毕归还给主进程，这里就是2次切换。也可以用CSR、IR、TPS的值代入公式中，得出每次事物导致的切换数。因此，要降低CSR，就必须在每个TPS引起的切换上下功夫，只有N这个值降下去，CSR就能降低，理想情况下N=0，但是无论如何如果N >= 4，则要好好检查检查。另外网上说的CSR<5000，我认为标准不该如此单一。

uptime

dmesg

top

vmstat

iostat

sar

mpstat

netstat

iptraf

tcpdump

mpstat

tcptrace

netperf

dstat

# 1. HBase 简介

## 1.1 HBase 的优点

1. 高可扩展性
HBase 是真正意义上的线性水平扩展。数据量累计到一定程度(可配置)，HBase系统会自动对数据进行水平切分，并分配不同的服务器来管理这些数据。这些数据可以被扩散到上千个普通服务器上。这样一方面可以由大量普通服务器组成大规模集群，来存放海量数据(从几个 TB 到几十 PB 的数据)。另一方面，当数据峰值接近系统设计容量时，可以简单通过增加服务器的方式来扩大容量。这个动态扩容过程无需停机，HBase系统可以照常运行并提供读写服务，完全实现动态无缝无宕机扩容。
2. 高性能
HBase 的设计目的之一是支持高并发用户数的高速读写访问。这是通过两方面来实现的。首先数据行被水平切分并分布到多台服务器上，在大量用户访问时，访问请求也被分散到了不同的服务器上，虽然每个服务器的服务能力有限，但是数千台服务器汇总后可以提供极高性能的访问能力。其次，HBase 设计了高效的缓存机制，有效提高了访问的命中率，提高了访问性能。
3. 高可用性
HBase 建立在 HDFS 之上。HDFS 提供了数据自动复制和容错的功能。HBase 的日志和数据都存放在 HDFS 上，即使在读写过程中当前服务器出现故障(硬盘、内存、网络等故障)，日志也不会丢失，数据都可以从日志中自动恢复。HBase 系统会自动分配其他服务器接管并恢复这些数据。因此一旦成功写入数据，这些数据就保证被持久化并被冗余复制，整个系统的高可用性得到保证。

## 1.2 数据模型

• 数据量：一张表可以有数十亿行，上百万列。
• 最大版本数：通常是3，如果对于更新比较频繁的应用完全可以设置为1，能够快速的淘汰无用数据，对于节省存储空间和提高查询速度有效果。不过这类需求在海量数据领域比较小众。
• 压缩算法：可以尝试一下最新出炉的snappy算法，相对lzo来说，压缩率接近，压缩效率稍高，解压效率高很多。
• inmemory：表在内存中存放，一直会被忽略的属性。如果完全将数据存放在内存中，那么hbase和现在流行的内存数据库memorycached和redis性能差距有多少，尚待实测。
• bloomfilter：根据应用来定，看需要精确到rowkey还是column。不过这里需要理解一下原理，bloomfilter的作用是对一个region下查找记录所在的hfile有用。即如果一个region下的hfile数量很多，bloomfilter的作用越明显。适合那种compaction赶不上flush速度的应用。
1. 无模式
每行都有一个可排序的主键和任意多的列，列可以根据需要动态的增加，同一张表中不同的行可以有截然不同的列；

2. 面向列
面向列（族）的存储和权限控制，列（族）独立检索；
3. 稀疏
对于空（null）的列，并不占用存储空间，表可以设计的非常稀疏；
4. 数据多版本
每个单元中的数据可以有多个版本，默认情况下版本号自动分配，是单元格插入时的时间戳；
5. 数据类型单一
HBase中的数据都是字符串，没有类型。
6. 存储单元 Cell
由{rowkey, colomnFamily:colomnQualifier, version} 确定的唯一单元，存储的数据是byte[]类型的。

# 2. HBase 的设计与实现

## 2.1 HBase 的架构

1. Client
Client主要通过ZooKeeper与Hbaser和HRegionServer通信，对于管理操作：client向master发起请求，对于数据读写操作：client向regionserver发起请求
2. ZooKeeper
zk负责存储root表的地址，也负责存储当前服务的master地址,regsion server也会将自身的信息注册到zk中，以便master能够感知region server的状态，zk也会协调active master，也就是可以提供一个选举master leader,也会协调各个region server的容灾流程
3. HMaster
master可以启动多个master，master主要负责table和region的管理工作，响应用户对表的CRUD操作，管理region server的负载均衡，调整region 的分布和分配，当region server停机后，负责对失效的regionn进行迁移操作
4. HRegionServer
region server主要负责响应用户的IO请求，并把IO请求转换为读写HDFS的操作

## 2.2 HBase 的架构详解

https://www.mapr.com/blog/in-depth-look-hbase-architecture#.VdMxvWSqqko

# 3. HBase, Mysql 的比较

Mysql 是关系型数据库，对于数据量不大(百万级别)，强依赖事务的业务，使用Mysql。
HBase 适用于对大数据进行随机、实时访问的场合，支持海量数据，扩展性好。
HBase 不适用的场景：

• 对分布式事务支持的不好
• 不支持多表的联合查询
• 对于复杂查询，需要扫描全表，且不支持索引

# 4. 设计 HBase 表

## 4.1 RowKey 的设计

Rowkey唯一原则，必须在设计上保证其唯一性。但是还有几点需要注意的地方：

### 4.1.1 RowKey 长度的设计

Rowkey是一个二进制码流，可以是任意字符串，最大长度64KB，实际应用中一般为10~100bytes，存为byte[]字节数组。

1. 定长
定长的好处是 RowKey 排序时是按字典序且不受不同长度的影响

2. 不要超过16个字节。
• 数据的持久化文件 HFile 是按照 KeyValue 存储的，如果 Rowkey 过长比如100个字节，1000万列数据光 Rowkey 就要占用100*1000万=10亿个字节，将近1G数据，这会极大影响 HFile 的存储效率；
• MemStore 将缓存部分数据到内存，如果 Rowkey 字段过长内存的有效利用率会降低，系统将无法缓存更多的数据，这会降低检索效率。
3. 16个字节
目前操作系统是都是64位系统，内存8字节对齐。控制在16个字节，8字节的整数倍利用操作系统的最佳特性。

### 4.1.2 RowKey 含义的设计

RowKey 虽然是越短越好，但也需要考虑 RowKey 的含义。由于 HBase 是按字典序存储，所以 RowKey 设计的合理可以提高查询效率(因为这会提高 RegionServer 的缓存命中率)，并且有意义的 RowKey 也便于在 scan 表的时候确定 startRow 和 stopRow。

1. RowKey 包含时间
不要将时间放在二进制码的前面，建议将 RowKey 的高位作为散列字段（或者本身就已经是散列的其他id，例如userId），低位放时间字段。否则最新的数据都集中放在某个 RegionServer，而访问量又都集中在最新的数据上，将会导致 Hotspotting 现象，降低了访问速度，同时也增加了 RegionServer Crash 的概率。
但考虑到是按字典序存储，如果想让最新的数据在最前面，可以使用 Long.MAX_VALUE – timestamp 作为 RowKey 的一部分。
2. RowKey 包含多个含义时
各个含义用某种分隔符分开，比如包含用户，类型，时间三种含义的 RowKey, 可以设计为 userId#type#timestamp，这样如果需要查找某个用户某段时间的数据，scan 时只需要根据 userId 设置 startRow 和 stopRow 即可。

### 4.1.3 RowKey 性能的设计

RowKey 是按照字典序存储，利用这个排序特点，将经常一起读取或者最近可能被访问到的数据存储到一块可以提高查询效率。

1. Hotspotting
It is always advisable not to use sequential row keys, even though you get better scan results. More info here.
Salting Row Key. To prevent hot spotting on writes, the row key may be “salted” by inserting a leading byte into the row key which is a mod over N buckets of the hash of the entire row key. This ensures even distribution of writes when the row key is a monotonically increasing value (often a timestamp representing the current time).
2. Length of row key
For each cell, rowkey details, column family, and qualifier details are stored. So it is always advisable to keep them as shot as possible, mainly because the same information is repeated on large scale.
3. So whats next
salt usage and its prefixing will help to distribute the rows among region servers.This can help you.

## 4.2 ColumnFamily 的设计

### 4.2.1 ColumnFamily 的长度

The column family and column qualifier names are repeated for each row. Therefore, keep the names as short as possible to reduce the amount of data that HBase stores and reads. For example, use f:q instead of mycolumnfamily:mycolumnqualifier.

### 4.2.2 ColumnFamily 的数量

On the number of column families
HBase currently does not do well with anything above two or three column families so keep the number of column families in your schema low. Currently, flushing and compactions are done on a per Region basis so if one column family is carrying the bulk of the data bringing on flushes, the adjacent families will also be flushed though the amount of data they carry is small. When many column families the flushing and compaction interaction can make for a bunch of needless i/o loading (To be addressed by changing flushing and compaction to work on a per column family basis). For more information on compactions, see compaction. (具体的细节见第2节)

Try to make do with one column family if you can in your schemas. Only introduce a second and third column family in the case where data access is usually column scoped; i.e. you query one column family or the other but usually not both at the one time.

Where multiple ColumnFamilies exist in a single table, be aware of the cardinality (i.e., number of rows). If ColumnFamilyA has 1 million rows and ColumnFamilyB has 1 billion rows, ColumnFamilyA’s data will likely be spread across many, many regions (and RegionServers). This makes mass scans for ColumnFamilyA less efficient.

## 4.3 Column 的设计

### 4.3.1 Column 的长度

The column family and column qualifier names are repeated for each row. Therefore, keep the names as short as possible to reduce the amount of data that HBase stores and reads. For example, use f:q instead of mycolumnfamily:mycolumnqualifier.

### 4.3.2 Column 的数量

Column mapping: one to many
You can map a single HBase entity (row key or a column) to multiple SQL columns. This kind of mapping is called one to many. HBase stores a lot of information for each value. If you stored each SQL column individually, the required storage space would be very large. For the best performance, put columns that are queried together into a single dense HBase column to help reduce the data that is fetched from HBase. A dense column is a single HBase column that maps to multiple SQL columns.

For example, if table T1 has nine columns with 1.5 million rows. and you use a one-to-one mapping, this table requires 522 MB of storage. However, if table T1 uses a one-to-many mapping, the table requires only 276 MB of storage.

# 5. 读 HBase 的性能

## 5.1 HBase Pool

Use pool of workers to parallel requests. You may find useful HTablePool class for managing connections in workers.

## 5.3 Scan

1. Scanner Caching
hbase.client.scanner.caching配置项可以设置HBase scanner一次从服务端抓取的数据条数，默认情况下一次一条。通过将其设置成一个合理的值，可以减少scan过程中next()的时间开销，代价是 scanner需要通过客户端的内存来维持这些被cache的行记录。
2. Scan AttributeSelection
scan时指定需要的Column Family，可以减少网络传输数据量，否则默认scan操作会返回整行所有Column Family的数据。
3. Close ResultScanner
通过scan取完数据后，记得要关闭ResultScanner，否则RegionServer可能会出现问题（对应的Server资源无法释放）。

## 5.4 PrefixFilter

### 5.4.1 PefixFilter Vs Scan

• HBase filters - even row filters - are really slow, since in most cases these do a complete table scan, and then filter on those results.
• Row key range scans however, are indeed much faster - they do the equivalent of a filtered table scan. This is because the row keys are stored in sorted order (this is one of the basic guarantees of HBase, which is a BigTable-like solution), so the range scans on row keys are very fast.

### 5.4.2 Convert PrefixFilter to Scan

PrefixFilter: abc
Scan ‘mytable’, {STARTROW => ‘abc’, ENDROW => ‘abd’}

# 6. 如何解决事务

1. transactions over hbase
The way HBase works is that locks are held in the regionserver (not in the client) when the Puts are applied to make sure that rows are written in an atomic block but it does not provide snapshot isolation (you need to use something like omid if you want that).

Since HBase does not guarantee any consistency between regions (and each region is hosted at exactly one RegionServer) all MVCC data structures only need to be kept in memory on every region server.

I would probably not use HBase for a use case like this. but if you must you can lock the row, read, update if needed - read more about lock and some of its problems here ngdata.com/hbase-row-locks . Again, I’d try to rethink the scenario for instance, HBase support multiple version so you can update anyway and sort things later (e.g. in a coprocessor that runs after update)
RowLock and associated operations are deprecated in 0.94 and removed in 0.96.issues.apache.org/jira/browse/HBASE-7315 – Matt Ball

1. hbase checkAndPut
hbase checkandput performance
When you use checkAndPut() you do one RPC-call per request. So, you can’t achieve performance more then 1 / rtt requests per second (rtt is Round Trip Time). If you have rtt 1ms between your client and region server, your theoretical maximum is 1000 rps. When using batch operations like put(List) you need a lot less RPC-calls causing performance increase.

# 什么是SSL/TLS

1994年，NetScape公司设计了SSL协议（Secure Sockets Layer）的1.0版，但是未发布。
1995年，NetScape公司发布SSL 2.0版，很快发现有严重漏洞。
1996年，SSL 3.0版问世，得到大规模应用。
1999年，互联网标准化组织ISOC接替NetScape公司，发布了SSL的升级版TLS 1.0版。
2006年和2008年，TLS进行了两次升级，分别为TLS 1.1版和TLS 1.2版。最新的变动是2011年TLS 1.2的修订版。
TLS 1.0通常被标示为SSL 3.1，TLS 1.1为SSL 3.2，TLS 1.2为SSL 3.3。

# https保证安全的原理

Client端和Server端如果用非对称加密的算法进行通信肯定是绝对安全的，因为私钥和密钥没有第三方知道。但是这样的问题是性能低下。但是如果用对称加密，很容易泄露密钥，安全性得不到保证。那么https是如何做的呢？

1. Client端向Server端的443端口发出请求，带上随机数client_random和支持的加密方式列表
2. Server端返回随机数server_random ，选择的加密方式和服务器证书链
3. Client端验证这个证书是否合法，如果非法则提示用户是否“继续接受这个不可信的网站”，如果合法则使用证书中的公钥加密premaster secret发送给服务端
4. Server端使用私钥解密premaster secret，然后通过client_random，server_random 和premaster secret 生成master secret，用于对称加密后续通信内容。
5. Sever端用master secret加密最终需要返回的网站内容
6. Client端也用相同的方式生成这个master secret解密收到的消息

master_secret = PRF(pre_master_secret, “master secret”, ClientHello.random + ServerHello.random)[0..47];

1. 证书的安全性，Client端是如何验证证书合法性的，这个证书第三方无论如何都伪造不了吗？
2. 对称加密密钥的安全性，生成的master secret密钥第三方为什么拿不到？

# 为什么证书是安全的？

## 什么是证书

• 证书的版本信息；
• 证书的序列号，每个证书都有一个唯一的证书序列号；
• 证书所使用的签名算法；
• 证书的发行机构名称，命名规则一般采用X.500格式；
• 证书的有效期，通用的证书一般采用UTC时间格式，它的计时范围为1950-2049；
• 证书所有人的名称，命名规则一般采用X.500格式；
• 证书所有人的公开密钥；
• 证书发行者对证书的签名。

## 证书的类型

1、SSL证书，用于加密HTTP协议，也就是HTTPS。
2、代码签名证书，用于签名二进制文件，比如Windows内核驱动，Firefox插件，Java代码签名等等。
3、客户端证书，用于加密邮件。
4、双因素证书，网银专业版使用的USB Key里面用的就是这种类型的证书。

## 证书的安全问题

1. 如果证书自己有一个id
2. 证书的这个id无法被伪造
3. 客户端知道自己想要的证书id是多少

### 数字签名（digital signature）

1. 数字签名的签发。首先是使用哈希函数对待签名内容进行安全哈希，生成数字摘要，然后使用CA自己的私钥对数字摘要进行加密。
2. 数字签名的校验。使用CA的公钥解密签名，然后使用相同的签名函数对待签名证书内容进行签名并和服务端数字签名里的签名内容进行比较，如果相同就认为校验成功。

• 数字签名 -> CA公钥解密 -> 数字摘要1
• 待签名内容 -> 哈希 -> 数字摘要2
• 比较「数字摘要1」和「数字摘要2」是否相等

• 数字签名签发和校验使用的密钥对是 CA 自己的公私密钥，跟证书申请者提交的公钥没有关系。
• 数字签名的签发过程跟公钥加密的过程刚好相反，即是用私钥加密，公钥解密。
• 现在大的 CA 都会有证书链，证书链的好处一是安全，保持根 CA 的私钥离线使用。第二个好处是方便部署和撤销，即如果证书出现问题，只需要撤销相应级别的证书，根证书依然安全。
• 根 CA 证书都是自签名，即用自己的公钥和私钥完成了签名的制作和验证。而证书链上的证书签名都是使用上一级证书的密钥对完成签名和验证的。

CA的私钥和公钥是安全的吗？可以被冒充吗？

### CA的安全性

CA的私钥是自己靠上述方法保管的，不对外公开。
CA的公钥是厂商跟浏览器和操作系统合作，把公钥默认装到浏览器或者操作系统环境里。比如firefox 就自己维护了一个可信任的 CA 列表，而chrome 和 IE 使用的是操作系统的 CA 列表。

## 证书验证失败的原因

1、SSL证书不是由受信任的CA机构颁发的(注意这种情况并不一定说明有SSL劫持发生)
2、证书过期
3、访问的网站域名与证书绑定的域名不一致

# 涉及到的算法

HASH算法：MD5，SHA1，SHA256

# 总结

1. https如何保证安全又高效？
https使用非对称加密算法来交换对称加密的密钥，最后使用对称加密算法来进行通信。
2. 如何保证非对称加密时的安全性？
服务端发送证书来传递非对称加密的公钥。保证了公钥和私钥的保密性。
3. 客户端怎么知道证书是不是真的？
客户端根据CA证书的公钥校验证书的数字签名来保证其合法性。
4. 客户端的CA证书不会被伪造或泄露吗？
CA证书是默认预装到浏览器和操作系统中的，所以CA证书的公钥是安全的。

# Reference

## Problem Description：

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

## Solution:

### Solution1:

Dynamic Programming
Time Complexity: O(n*sqrt(n))
Space: O(n)

### Solution2:

Number Theory

• Legendre’s three-square theorem
• Lagrange’s four-square theorem

Time Complexity: O(sqrt(n))
Space: O(1)

## Refer:

https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics

## Problem Description

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Buildings Skyline Contour
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], … ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
There must be no consecutive horizontal lines of equal height in the output skyline. For instance, […[2 3], [4 5], [7 5], [11 5], [12 7]…] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: […[2 3], [4 5], [12 7], …]

https://leetcode.com/problems/the-skyline-problem/

## 算法解释

### 算法思路

1. 遍历所有的点，height用来存放每个顶点，左顶点的高度转为负数，右顶点的高度仍然是正数
2. 对height数组排序，首先按x的值排序，当x的值相等时按z排序，这样保证了即使矩形的起点一样，也是最先处理最高的点。对于[{1,2,1},{1,2,2},{1,2,3}]这样的情况会优先处理{1,2,3}这个点。
3. 使用优先级队列pq来保存当前最近buildings的高度，这个结构很重要！
4. 遍历height数组，碰到左顶点时，将高度放入pq中，否则，碰到右顶点时则将高度从pq从移除。这样做的好处是，每次走完一个矩形时，高度能回归到之前的buildings的高度。
5. 获取当前的最高高度，因为如果比当前矮的话，是不需要放入拐点中的，这点很重要！
6. 如果当前的最高高度和之前的高度不一致，说明出现了拐点。**如果当前的最高高度矮于之前的值，说明之前的很高的建筑遇到了它的右顶点从而被移除了，所以目前的最高高度即使矮于之前的点，但是是新的隔离的building了，所以可以加入。那么如果高呢？当前高度比之前高，那肯定会是拐点了。

## 总结

1. 对顶点进行排序保存，对左右顶点根据正负号来加以区分
2. 使用一个优先级队列来保存目前最高的建筑
3. 碰到右顶点时消除目前的建筑高度
4. 根据之前的高度和处理目前顶点以后(可能是加入了高度也可能是消除了之前的高度)的高度，对两者进行比较来找到拐点

## Reference

https://leetcode.com/discuss/54201/short-java-solution