工作归档 - 一只安静的猫

virtualbox 网络桥接

virtualbox的默认方式是NAT，用宿主机对虚拟机做端口转发。在组建本地的集群环境时，使用这种方式是不行的。可以使用桥接网卡的方式，使得虚拟机分配到一个宿主机局域网内的ip地址。

首先，修改/etc/network/interfaces文件。

这个文件原来的内容如下：

# This file describes the network interfaces available on your system
# and how to activate them. For more information, see interfaces(5).

source /etc/network/interfaces.d/*

# The loopback network interface
auto lo
iface lo inet loopback

# The primary network interface
auto enp0s3
iface enp0s3 inet dhcp

修改成如下：

# This file describes the network interfaces available on your system
# and how to activate them. For more information, see interfaces(5).

source /etc/network/interfaces.d/*

# The loopback network interface
auto lo
iface lo inet loopback

# The primary network interface
auto enp0s3
#iface enp0s3 inet dhcp
iface enp0s3 inet static
address 192.168.0.100
gateway 192.168.0.1
netmask 255.255.255.0

注意这里的address和gateway的网段要和宿主机网段一致。比如我的宿主机ip为192.168.0.8。

注意这里还要修改一下dns，不然会出现无法解析域名的问题，编辑/etc/resolvconf/resolv.conf.d/base

添加一下的nameserver:

nameserver 8.8.8.8
nameserver 1.1.1.1

执行sudo resolvconf -u使dns的配置生效。

然后修改虚拟机的设置，在VirtualBox的菜单栏中：设备->网络->网络->连接方式：桥接网卡。

然后重启网络

sudo /etc/init.d/networking restart

如果网络还是有问题，可以尝试重启虚拟机。

之后在终端之中输入ifconfig，网络信息如下：

enp0s3    Link encap:Ethernet  HWaddr 08:00:27:f1:6d:fd  
          inet addr:192.168.0.100  Bcast:192.168.0.255  Mask:255.255.255.0
          inet6 addr: fe80::a00:27ff:fef1:6dfd/64 Scope:Link
          UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1
          RX packets:304 errors:0 dropped:0 overruns:0 frame:0
          TX packets:173 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:1000 
          RX bytes:28254 (28.2 KB)  TX bytes:28063 (28.0 KB)

虚拟机的ip已经变成192.168.0.100。使用ping 192.168.0.8检查和宿主机的通信是否正常。

问题描述

业务中有一个测试服务器，里面运行了好几个任务队列。但是自从将任务队列从redis迁移到rabbitmq上后，一直会在运行一段时间后停止运行。一般这种情况下，要么是进程退出了，要么是连接断开了。但是检查后发现，进程是正常运行的，并且通过netstat发现，连接也一直存在。如果是连接断开，我的代码中也做了断线重连的机制。

问题排查

一开始以为是php-amqplib这个库的问题，就去找它的issue，看看有没有类似的问题。这里没有找到类似的bug。

然后去复现了一个最小的demo，这个问题一直都是出现在运行相当长的时间之后。于是决定对测试服务器上已经出现问题的代码进行抓包。新push的任务，任务队列的进程就是接收不到，但是netstat结果，任务队列到rabbit服务的连接又确实是存在的。

没有办法就去随便翻翻《UNIX网络编程》的TCP章节，然后想到TCP的全双工特性。全双工特性就是说在一个给定的连接上应用可以在任何时候在进出两个方向上既发送数据又接收数据。建立一个全双工连接后，需要的话可以把它转换成一个单工连接。于是用netstat检查rabbit服务的连接，发现是没有到任务队列的连接的。所以问题就是出现在这里。**但是仔细思考一下，这里的问题并不能用全双工特性去解释，因为全双工转成单工是tcp的一个特性，但是在这个问题中，应该是一个异常情况。全双工是需要双端协商的，而我这里的问题应该是：

服务器关闭了连接，但是任务队列却没有收到关闭的Fin报文，很多时候被称为半打开。

问题解决

解决这个问题很简单，启用php-amqplib的心跳包机制即可。

参考

TCP half-open
半连接、半打开、半关闭

ABNF格式说明

一、简介

ABNF全称是Augmented Backus-Naur Form，广泛用于很多的互联网文档说明中。主要作用就是以简洁的字符串来描述某些规范。使用了ABNF的标准说明有:电子邮件的标准说明[RFC733]和之后的[RFC822]，HTTP1.1协议的[RFC7230]。因此，要想阅读这些文档，必须了解ABNF的格式。ABNF在RFC5234中进行了详细的说明。

二、规则定义

2.1 规则命名

ABNF中规则的命名是大小写不敏感的，由字母开头，后面跟上字母、数字或连字符

2.2 规则格式

一个规则是如下格式定义的：

name = elements crlf

name指的是规则名，elements是一个或多个规则名，或者是终端字符，crlf也就是我们常说的\r\n

2.3 终端值

一个规则被解释成一个字符串。每个字符都是一个非负的数字（比如ASCII码中a对应十进制的97）。终端值就是这些数字。目前定义了以下几种进制:

b     = binary          ;二进制
d     = decimal         ;十进制
x     = hexadecimal     ;十六进制

因此:

CR = %d13
CR = %x0D

使用”.”号来分割字符

CRLF = %d13.10

2.4 额外的编码

根据编码不同，所显示的值可能也不同。比如7-bit的US-ASCII和16-bit的unicode编码，结果是截然不同的。目前7-bit的US-ASCII编码是最常用的。

三、运算符

3.1 连接: `Rule1 Rule2`

连接的意思就是值一个规则可能由其他规则连接而成。比如

foo = %x61 ; a
bar = %x62 ; b
mumble = foo bar foo

因此规则mumnle = aba

3.2 选择: `Rule1 / Rule2`

选择就是多选一的意思。比如

rule = foo / bar

那么rule是foo或者bar都接受的

3.3 扩展的选择: `Rule1 =/ Rule2`

ruleset = rule1 / rule2
ruleset =/ rule3
ruleset =/ rule4 / rule5

那么ruleset最终为

ruleset = rule1 / rule2 / rule3 / rule4 / rule5

3.4 范围选择: `%c##-##`

DIGIT = %x30-39

等价于

DIGIT = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"

3.5 序列组: `(Rule1 Rule2)`

序列组主要是为了阅读上的方便

elem (foo / bar) blat

等价于

(elem foo blat) or (elem bar blat)

而

elem foo / bar blat

等价于

(elem foo) or (bar blat)

3.6 变量重复: `*Rule`

完整的格式为：<a>*<b>element
<a>和<b>是可选的数字值，代表最少a个，最多b个

因此：

*<element> 0到任意多个
1*<element> 至少1个
3*3<element> 只能是3个
1*2<element> 1到2个

3.7 指定的重复: `nRule`

n<element>等价于n*n<element>

3.8 可选的序列: `[Rule]`

[Rule]代表这个规则可有可无。因此[foo bar]等价于*1[foo bar]

3.9 注释: `;Comment`

使用;来表示注释

3.10 运算符优先级

运算符优先级从上往下排序如下：

规则名, 单值, 终端值
注释
范围取值
重复
组, 可选
连接
选择

四、使用ABNF定义ABNF

rulelist = 1*( rule / (*c-wsp c-nl) )

rule = rulename defined-as elements c-nl
; continues if next line starts
; with white space

rulename = ALPHA *(ALPHA / DIGIT / "-")

defined-as = *c-wsp ("=" / "=/") *c-wsp
; basic rules definition and
; incremental alternatives

elements = alternation *c-wsp

c-wsp = WSP / (c-nl WSP)

c-nl = comment / CRLF
; comment or newline

comment = ";" *(WSP / VCHAR) CRLF

alternation = concatenation
*(*c-wsp "/" *c-wsp concatenation)

concatenation = repetition *(1*c-wsp repetition)

repetition = [repeat] element

repeat = 1*DIGIT / (*DIGIT "*" *DIGIT)

element = rulename / group / option /
char-val / num-val / prose-val

group = "(" *c-wsp alternation *c-wsp ")"

option = "[" *c-wsp alternation *c-wsp "]"

char-val = DQUOTE *(%x20-21 / %x23-7E) DQUOTE
; quoted string of SP and VCHAR
; without DQUOTE

num-val = "%" (bin-val / dec-val / hex-val)

bin-val = "b" 1*BIT
[ 1*("." 1*BIT) / ("-" 1*BIT) ]
; series of concatenated bit values
; or single ONEOF range

dec-val = "d" 1*DIGIT
[ 1*("." 1*DIGIT) / ("-" 1*DIGIT) ]

hex-val = "x" 1*HEXDIG
[ 1*("." 1*HEXDIG) / ("-" 1*HEXDIG) ]

prose-val = "<" *(%x20-3D / %x3F-7E) ">"
; bracketed string of SP and VCHAR
; without angles
; prose description, to be used as
; last resort

附录：核心规则

ALPHA = %x41-5A / %x61-7A ; A-Z / a-z

BIT = "0" / "1"

CHAR = %x01-7F
; any 7-bit US-ASCII character,
; excluding NUL

CR = %x0D
; carriage return

CRLF = CR LF
; Internet standard newline

CTL = %x00-1F / %x7F
; controls

DIGIT = %x30-39
; 0-9

DQUOTE = %x22
; " (Double Quote)

HEXDIG = DIGIT / "A" / "B" / "C" / "D" / "E" / "F"

HTAB = %x09
; horizontal tab

LF = %x0A
; linefeed

LWSP = *(WSP / CRLF WSP)
; Use of this linear-white-space rule
; permits lines containing only white
; space that are no longer legal in
; mail headers and have caused
; interoperability problems in other
; contexts.
; Do not use when defining mail
; headers and use with caution in
; other contexts.

OCTET = %x00-FF
; 8 bits of data

SP = %x20

VCHAR = %x21-7E
; visible (printing) characters

WSP = SP / HTAB
; white space

RFC5234地址：https://tools.ietf.org/html/rfc5234

Canvas性能优化小结

简介

H5中引入了对canvas的支持，使得网页的表达能力更加丰富了。程序员可以通过canvas来绘制复杂的图形，甚至是游戏。因为工作中的需求，需要使用canvas在网页上绘制家谱。具体的算法可以看之前的一篇总结：树的可视化以及家谱绘制的算法
。当家谱中的数据量变大之后，整个绘制过程会变的很卡（800左右人物的家谱1000次绘制居然需要25s左右）。但是在做完优化后，1000次绘制只需要0.15s左右。

家谱示例

目前的家谱绘制共有两部分。一个是家谱的主体，用户可以通过鼠标、滚轮去任意的浏览；一个是左上角的小地图功能，帮助用户了解到当前浏览的位置，小地图中的有色方块就是用户整个屏幕显示的内容。

优化措施一：缓存

缓存是在绝大多数系统中经常用到的提升性能的方法，典型的以空间换时间。在canvas中当然也可以使用缓存。在家谱的每一次绘制中，都要遍历所有的人物，然后计算他们的位置大小，然后绘制到界面上，然后还要遍历所有的路径再次进行绘制。而使用缓存的目的就是避免这一部分的计算。因此，在任何复杂计算后的绘制，都能使用缓存来提升性能。

在canvas中有这样一个方法，CanvasRenderingContext2D.drawImage(image, dx, dy)，image参数代表要绘制的图片源，不仅仅可以是一个image对象，还可以是一个canvas对象。所以如果我们将一个复杂的图形作为canvas对象缓存起来，然后直接使用drawImage方法去绘制到画面上，就能减少很多的重复计算，来提升性能。

例如以下的伪代码

function paintPerson() {
    // paint 
}

function paintFamilyTree() {
    for(var i = 0; i < 10000; i++) {
        paintPerson()
    }
}

// 用户移动鼠标就需要重绘族谱
dom.addEventListener("mousemove", function() {
    paintFamilyTree()
}

用户每一次移动鼠标，都需要10000次的循环去画。所以我们使用下面的方法，使得只需要计算一次

function paintPerson() {
    // paint 
}

function paintFamilyTree() {
    for(var i = 0; i < 10000; i++) {
        paintPerson()
    }
}

var canvasObj = cache(paintFamilyTree) // 缓存这次绘制的结果。

dom.addEventListener("mousemove", function() {
    ctx.drawImage(canvasObj,0,0)
}

那么如何去缓存这个 canvas 对象呢？可以使用document.createElement('canvas')来创建一个不在页面上显示的 canvas 对象，一般也称它为离屏画布，这里用变量 offScreenCanvas 来称呼。然后将绘制的图形画在这个 canvas 上，之后调用 ctx.drawImage(offScreenCanvas,0,0) 即可。

在创建这个离屏画布的时候，我们也要设置合适的宽高，这样也有助于提升性能。

可以参考这个例子来感受一下性能差距：
离屏画布缓存来提升页面性能
例子代码如下：

<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <title>离屏canvas实例</title>
        <style>
            .main-wrapper {
                width: 800px;
                margin: 10px auto;
            }
        </style>
    </head>

    <body onload="init()">
        <div class="main-wrapper">
            <canvas width="800" height="600" style="border: 1px solid #ccc" id="canvas">
                你的浏览器不支持canvas
            </canvas>
            <br><br><br><br><br><br><br><br><br>
            <div id="result"></div>
            <br>
            渲染次数:<input type="number" id="times" value="1000">,共耗时(ms)<span id="time_used">0</span><br>
            <button onclick="doTest(false,false)">不使用离屏canvas</button>
            <button onclick="doTest(true,false)">使用离屏canvas</button>
            <button onclick="doTest(true,true)">使用离屏canvas并设置正确的高度</button>
        </div>
        <script>
            /**
             * 离屏缓存，num为缓存canvas的数量
             */
            var OffScreenCache = function (num) {
                this.canvases = [];
                for (i = 0; i < num; i++) {
                    this.canvases.push(document.createElement("canvas"));
                }
            }
            OffScreenCache.prototype = {
                pop: function() {
                    return this.canvases.pop();
                },
                push: function(canvas) {
                    this.canvases.push(canvas);
                },
                destroy: function() {
                    this.canvases = null;
                }
            }
            var Ball = function (color) {
                this.radius = 50;
                this.lineWidth = 4;
                this.cache = null;
                this.color = color;
            }
            Ball.prototype = {
                paint: function(ctx, x, y) {
                    ctx.save();
                    ctx.lineWidth = this.lineWidth;
                    ctx.strokeStyle = this.color;
                    for (i = 1; i < this.radius; i+= this.lineWidth) {
                        ctx.beginPath();
                        ctx.arc(x, y, i, 0, Math.PI*2,true); // 绘制
                        ctx.stroke();
                    }
                    ctx.restore();
                },
                useCache: function (cacheCanvas, autoSet) {
                    if (autoSet) {
                        cacheCanvas.width = this.radius * 2;
                        cacheCanvas.height = this.radius * 2;
                    }
                    cacheCtx = cacheCanvas.getContext('2d')
                    this.paint(cacheCtx, cacheCanvas.width / 2, cacheCanvas.height / 2)
                    this.cache = cacheCanvas
                }
            }
            /******************** 下面是执行代码 **************************/
            var g_canvas, g_ctx;
            var g_width = 800;
            var g_height = 600;
            function init() {
                g_canvas = document.getElementById("canvas");
                g_ctx = g_canvas.getContext('2d');
            }
            function getRandomPos() {
                var x = Math.random() * g_width
                var y = Math.random() * g_height
                return {x:x, y:y}
            }
            function showResult(ballCount) {
                var dom = document.getElementById("result");
                dom.innerHTML = "";
                var str = "";
                for (var key of Object.keys(ballCount)) {
                    str += "<span>" + key + "ball：" + ballCount[key] + "</span>    "
                }
                dom.innerHTML = str;
            }
            function doTest(useCache, autoSet) {
                g_ctx.clearRect(0, 0, g_width, g_height)
                var startTime = Date.now();
                var times = document.getElementById("times").value
                var colorArray = ['red', 'blue', 'green', 'black', 'pink']   // 共绘制5种颜色
                var ballCount = {};
                colorArray.forEach(function(color) {
                    ballCount[color] = 0;
                })
                if (useCache) {
                    var colorBall = [];
                    var cacheCanvases = new OffScreenCache(colorArray.length);
                    for (var i = 0; i < colorArray.length; i++) {
                        var ball = new Ball(colorArray[i]);
                        var cacheCanvas = cacheCanvases.pop();
                        ball.useCache(cacheCanvas, autoSet)
                        colorBall.push(ball)
                    }
                    for (var i = 0; i < times; i++) {
                        ball = colorBall[i % 5]
                        ballCount[ball.color]++;
                        var pos = getRandomPos()
                        g_ctx.drawImage(ball.cache, pos.x, pos.y)       // 开始画
                    }
                } else {
                    for (var i = 0; i < times; i++) {
                        var color = colorArray[i % 5];
                        var ball = new Ball(color)
                        var pos = getRandomPos()
                        ball.paint(g_ctx, pos.x, pos.y)               // 开始画
                        ballCount[color]++;
                    }
                }
                var endTime = Date.now();
                document.getElementById("time_used").innerText = endTime - startTime;
                showResult(ballCount)
            }
        </script>
    </body>
</html>

优化措施二：分层

在上述的族谱图片中，左上角的小地图其实是有两个canvas重叠而成。底层的canvas绘制族谱的缩略图，上层的canvas绘制小方框。这样在小方框移动时，只需清空上层canvas的局部画布重绘小方框即可，不需要重绘底层的缩略图。

接口请求速率（接口防刷）限制方案

1.场景

当前业务中接口防刷的场景有:

1.短信/邮件接口。这个接口不做好防刷策略，损失是很大的。
2.涉及到安全问题的接口调用。比如注册接口，登录接口等等。过于频繁的请求可能代表着用户的批量注册，用户密码的暴力破解（需要考虑到可能是用户忘记密码了)等等。

2.要求

1.与当前业务系统解耦合
2.可以很方便的对不同的接口设置不同的请求频率限制
3.具有较好的性能。在大并发的情况下，需要有正确的结果

3.方案提出

3.1 token bucket（令牌桶）

token bucket算法的如下图：

token_bucket

描述如下:

1.假设有一个桶，不断的向桶中投放token，并且我们也可以从桶中取出token。
2.投放token的速率是恒定的r1，桶满了token数量则不会再增长。
3.取出的速率是随机的r2。如果桶是空的，则无法取出token。
4.所有的请求都必须从桶中取出token才是有效的。否则该请求会被拒绝。

举个例子，假设桶的容量是10，每秒放2个token进去。

如果现在每秒2个请求，那么所有这样的请求都是没有问题的，都会拿到token。
如果现在每秒4个请求,10 + 2x = 4x。也就是x=5秒后请求就没法及时拿到token，被丢弃。

总结出以下特点:
– 如果请求速率过快，到一段时间后会受到限制
– 允许突发请求

3.2 redis数据库

使用redis数据库完全是因为方便以及速度。只要注意这其中存在的CAS问题即可

4.具体实现

首先，为了解决redis中检查和存储数据存在的CAS问题，我们需要使用lua脚本。因此，对于token bucket的主要实现是用lua脚本实现,然后通过php调用。

local function mysplit(inputstr, sep)
    if sep == nil then
            sep = "%s"
    end
    local t={} ; 
    local i=1
    for str in string.gmatch(inputstr, "([^"..sep.."]+)") do
            t[i] = str
            i = i + 1
    end
    return t
end

local res = redis.pcall('get',KEYS[1])

if (res == false) then
    -- bucket不存在，初始化为capacity - 1
    local str = string.format("%d %d",ARGV[1] - 1,ARGV[2])  
    return redis.pcall('set',KEYS[1],str)
end

local arr_str = mysplit(res, " ")

local num = arr_str[1]
local timestamp = arr_str[2]

-- 根据时间戳来计算num，这里一秒2个令牌
num = num + (ARGV[2] - timestamp) * ARGV[3]
-- 不超过10个令牌
if num > 10 then
    num = 10
end

if (tonumber(num) > 0) then
    -- 拿到token并减一
    local str = string.format("%d %d",num - 1,ARGV[2])
    return redis.pcall('set', KEYS[1], str)
else 
    -- 没有拿到token
    return false
end

<?php

 $sha = '2ff7ad2d1b49da8430e5adc8675e'; /** * 初始化lua脚本 */ function initScript($ redis) {
    global  $sha; //不存在脚本，load进去$ script = file_get_contents('check_and_set.lua');
     $sha =$ redis->script('load',  $script); if($ redis->getLastError() !== NULL){
        echo "出错了：". $redis->getLastError().'\n'; } echo "初始化的脚本sha:".$ sha.PHP_EOL;
}

function getTokenFromBucket( $redis,$ bucket) {
    global  $sha;$ capacity = 10;
     $time = time();$ inputRate = 2;     //一秒2个token
     $params = array($ bucket,  $capacity,$ time,  $inputRate);$ result =  $redis->evalSha($ sha,  $params, 1); if($ redis->getLastError() !== NULL){
        echo "出错了：". $redis->getLastError().'\n'; } return$ result;
}

 $redis = new Redis();$ redis->pconnect("127.0.0.1");

initScript( $redis);$ start = microtime(true) * 1000;

while(true) {
     $result = getTokenFromBucket($ redis, 'bucket1');
    if (! $result) { break; } else { echo time()."--拿到令牌".PHP_EOL; usleep(250000); //每秒请求4次,10 + 2x = 4x, x = 5。5秒左右无法拿到令牌 } }$ end = microtime(true) * 1000;

echo "共耗时：".( $end -$ start)."毫秒".PHP_EOL.PHP_EOL;

 $start = microtime(true) * 1000; while(true) {$ result =  getTokenFromBucket( $redis, 'bucket2'); if (!$ result) {
        break;
    } else {
        echo "拿到令牌".PHP_EOL;
        usleep(500000);    //每秒请求2次，永远可以拿到令牌
    }
}

 $end = microtime(true) * 1000; echo "共耗时：".($ end - $start)."毫秒".PHP_EOL.PHP_EOL;

代码中主要部分概括如下:

检查redis中是否存在桶bucket1。
如果不存在，那么默认的容量是10，将bucket1设为9 timestamp(timestamp为当前的时间戳)。返回true
如果存在，则获取该bucket1的值，解析出实际token数量为num,以及上一次存储时时间戳为pre。如果rate为token的生成速率，那么现在的token数量应该是:num = num + (time() – pre) * rate。num最大为默认容量10。如果num大于0，则减一后重新设置，返回true。否则返回false。

代码的运行结果如下：

运行结果演示

5.扩展知识

与token bucket相似的算法还有leaky bucket（漏桶）。leaky bucket 就像是 token bucket的镜像一样。leaky bucket 一般用于Traffic shaping和Traffic policing等问题，与下面的两张图对应。

leaky bucket

可以描述如下:

1.有一个桶，其上方水龙头以变化的速率r1向里面滴水，桶底的水龙头则以恒定的速率向下漏水
2.水桶装满后，上方水龙头的滴水就会溢出
3.水桶空后，下方水龙头则不会滴水

这里举一个异步任务处理（任务队列的容量是有限的）的例子。

上方水龙头相当于任务投递系统，下方水龙头相当于任务处理系统。
任务投递的速率是变化的，因为不同时间段的系统负载可能不同。
任务处理系统的速率是恒定的，因为机器的处理能力是恒定的。
当任务投递的速率大于处理速率，填充满任务队列后，后面的任务都会被丢弃。

可以看出leaky bucket可以将不规则的抖动的请求序列变成规则的平滑的请求序列。leaky bucket通常有两个版本：作为一个评判的仪器(meter)或者是生成一个合法请求队列(queue)。

虽然在使用中leaky bucket和token bucket是不同的，但实际上他们是同一种思路。leaky bucket的变化的输入相当于token bucket的变化的输出，leaky bucket的恒定的输出相当于token bucket的恒定的输出。

参考文献

token bucket
leaky bucket

系统权限设计中RBAC模型的使用

什么是RBAC

RBAC，全称是Role-Based-Access-Control，可以译为基于角色的权限控制，是一种应用非常广泛的权限控制模型。

什么是角色(Role)

角色不是一个用户实体，而是代表了一组行为能力或责任的命名实体，以我们常用的QQ群为例，有以下角色：超级管理员、群主、管理员、普通成员、非群成员。

每个角色都有不同的权限:

超级管理员可以管理任何的QQ群，但是一般只能禁言、删除群，不能管理具体的某个群成员，也不能在群里聊天；
群主可以管理自己的QQ群，可以在群里聊天；
管理员可以管理自己的QQ群，可以聊天，但是不能解散群，也不能任命或撤销其他管理员；
普通成员则没有管理权限，只有在群里聊天的权限
非群成员无管理权限，也无法在群里聊天。

所以可以知道，每个角色都对应着一组行为能力或责任。

隐式的基于角色的权限控制

对于QQ群的例子来说。如果我们要做一个删除某个群成员的动作，伪代码可能如下:

if( user.hasRole('Group Owner') || user.hasRole('Group Manager') ){
    // delete the Group Member
} else {
    // Permission Denied
}

那么现在，如果腾讯的权限策略发生了改变，超级管理员也可以删除某个群的群成员来防止某些不当言论的传播，那么代码就要改为

if( user.hasRole('Group Owner') || user.hasRole('Group Manager') || user.hasRole('Super Manager') ){
    // delete the Group Member
} else {
    // Permission Denied
}

上面这种权限的管理方式，就可以称为隐式的基于角色的权限控制。因为Group Owner、Group Manager、Super Manager并不能显式的表达出：它们的角色具有删除群成员的权限。没有任何的代码显式的定义了这些角色的权限。我们只能从代码中隐式的推测出：这三个角色拥有删除群成员的权限。所以程序员们使用if/else语句来反映这些假设。

显式的基于角色的权限控制

了解了隐式的基于角色的权限控制，那么我们就可以知道，显式的基于角色的权限控制要有能力直接表达出：当前用户有权限去删除群成员。这样我们的代码可以调整如下：

if( user.isPermitted('GroupMember:delete:478') ){
    // delete the Group Member
} else {
    // Permission Denied
}

这样从代码中可以看到，如果当前用户被允许删除ID为478的群成员，那么就去删除，否则报权限不足的错误。至于isPermitted()中如何去判断权限的，可能依然是回到了哪些角色有哪些权限的问题。但是不同之处在于，应对上面的需求变更问题时，我们只需要更改user的isPermitted的判断规则，而不用去更改散布在代码中各个地方的if语句。可以做到以最小的变更来应对复杂的需求变化。

隐式 vs 显式

隐式和显式在我看来，其内在的权限控制仍然是一样的，都是基于角色在做权限判断。但对外的抽象则是截然不同的：隐式侧重于某个用户是否有某些角色，显式则直接将问题聚焦于某个用户是否有对某个资源的某个操作的权限。这在写代码中给程序员带来的影响是不一样的。截取一段项目中的代码来佐证：

//检查操作的权限
if(
    ! $familyDB->isUserForFamily($ familyId, $userId)&& !$ familyDB->isAdminForFamily( $familyId,$ userId)&&
    ! $familyDB->isOriginatorForFamily($ familyId, $userId) ){ Util::printResult($ GLOBALS['ERROR_PERMISSION'], "操作权限错误");
    exit;
}

这段代码判断了用户是否对家族有读取权限。因为我们是隐式的基于角色的权限控制，很直观的想法就是：家族成员、家族管理员、家族创始人这三个角色都有对家族的读取权限。所以这里判断了三个权限。事实上，家族创始人的判断是多余的，因为家族创始人肯定属于家族成员。但是真正在写代码的时候，很有可能考虑不到这个问题。

但如果是显式的基于角色的权限控制，这个if语句就是：

//检查操作的权限
if(
    ! $familyDB->isUserHasReadPermission($ familyId, $userId)) ){ Util::printResult($ GLOBALS['ERROR_PERMISSION'], "操作权限错误");
    exit;
}

程序员写代码时就不会做出多余的判断。可以得出，显式的抽象表达能力是明显更强的。

新的RBAC：Resource-Based-Access-Control

通过对比隐式和显式的区别，我们知道显式是直接检查某个用户对某个资源（Resource）是否有某个权限。所以不如直接抛弃角色（Role）的概念，将资源这个概念引入。这样就有了基于资源的权限控制（Resource-Based-Access-Control）。

png格式分析与压缩原理

1.简介

　png图片格式采用了一种很灵活的编码设计，支持多种编码方式来展示一张图片：灰度图片、索引彩色图像、真彩色图像、带α通道数据的灰度图像、带α通道数据的真彩色图像。因为png的编码方式灵活，使得其压缩的发挥空间非常大。

2.几种编码方式的说明

注意：这里的一个通道并不等同于1个字节或2个字节，因为png IDAT块的编码单位是bit而不是byte，具体一个通道占用的位数是靠bit depth来决定的

a.灰度图片

灰度图片一般是用来生成我们常见的黑白照片，bit depth可选值为1、 2、 4、 8、16，其一个像素点用一个通道来表示（0~255）或(0~65535)，因此这种图片的大小往往非常小

b.索引彩色图像

索引彩色图像很有意思，它可以和真彩色图像一样拥有表达彩色图片的能力，但是一张索引彩色图像上最多只有256种颜色，每种颜色用三个字节(RGB,0~255)表示。它的bit depth可选值为1、 2、4、8，它有一个调色板区域，用来记录索引颜色的值，然后像素点数据区域用一个通道(0~255)来表示调色板区域记录的颜色索引。所以对于色彩不多的图片来说，采用索引彩色来编码是很适合的。

c.真彩色图像

真彩色图像最好理解，它的bit depth为8或16，它的每个像素点都用3个字节(3个通道）来表示，分别为R(0~255),G(0~255),B(0~255)，可以表达256256256=16777216种颜色，或者使用6个字节（3个通道）来表示，分别为R(0~65535),G(0~65535),B(0~65535)，可以表达655356553565535种颜色。

d.带α通道数据的灰度图像

就是在灰度图片上增加了α通道，共2个通道,支持透明(0~255)或者(0~65535)，但是它的bit depth为8或16，因此这种编码方式一个像素点是2个字节或4个字节

e.带α通道数据的真彩色图像

就是在真彩色图像上增加了α通道,同四个通道，支持透明(0~255)或者(0~65535)，它的bit depth为8或16，因此这种编码方式一个像素点是4个字节或8个字节

3.png图片具体编码说明

png图片的编码一般如下:header,chunk,chunk,chunk….chunk。

header代表png图片的头，png文件头一般都是由固定的8个字节组成
89 50 4E 47 OD 0A 1A 0A
图片软件可以通过这8个字节来判断这个文件是不是png格式。

chunk代表png图片的数据块，数据块是有不同的类型的，记录了不同的信息。一张png图片可能包含多个数据块。
数据块的类型如下（关键部分高亮显示）:

PNG文件格式中的数据块（表1.1）

数据块符号	数据块名称	多数据块	可选否	位置限制
`IHDR`	文件头数据块	否	否	第一块
cHRM	基色和白色点数据块	否	是	在PLTE和IDAT之前
gAMA	图像γ数据块	否	是	在PLTE和IDAT之前
sBIT	样本有效位数据块	否	是	在PLTE和IDAT之前
`PLTE`	调色板数据块	否	是	在IDAT之前
bKGD	背景颜色数据块	否	是	在PLTE之后IDAT之前
hIST	图像直方图数据块	否	是	在PLTE之后IDAT之前
tRNS	图像透明数据块	否	是	在PLTE之后IDAT之前
oFFs	(专用公共数据块)	否	是	在IDAT之前
pHYs	物理像素尺寸数据块	否	是	在IDAT之前
sCAL	(专用公共数据块)	否	是	在IDAT之前
`IDAT`	图像数据块	是	否	与其他IDAT连续
tIME	图像最后修改时间数据块	否	是	无限制
tEXt	文本信息数据块	是	是	无限制
zTXt	压缩文本数据块	是	是	无限制
fRAc	(专用公共数据块)	是	是	无限制
gIFg	(专用公共数据块)	是	是	无限制
gIFt	(专用公共数据块)	是	是	无限制
gIFx	(专用公共数据块)	是	是	无限制
`IEND`	图像结束数据	否	否	最后一个数据块

png 文件中，每个数据块由4个部分组成 length | type(name) | data | CRC, 说明如下

length: 4 bytes， data的长度，不包括type和CRC
type: 4 bytes, ASCII码([A-Z,a-z])
CRC: 4bytes
CRC(cyclic redundancy check)域中的值是对Chunk Type Code域和Chunk Data域中的数据进行计算得到的。CRC具体算法定义在ISO 3309和ITU-T V.42中，其值按下面的CRC码生成多项式进行计算： x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1

除了高亮的关键数据块，还有下面比较有意思的数据块
tRNS

tRNS contains transparency information. For indexed images, it stores alpha channel values for one or more palette entries. For truecolor and grayscale images, it stores a single pixel value that is to be regarded as fully transparent.

tRNS包含透明度信息，
1.在索引图片中，它可以保存一或多个调色板像素对的alpha通道值。用来指明哪些像素需要透明，透明度是多少。然后剩下的像素透明度都被默认成255，完全不透明。

2.在灰度图片中，包含单个灰度级别值，格式如下：
Gray: 2 bytes, range 0 .. (2^bitdepth)-1
被指定的灰度值都会被当成是透明的，其他灰度值则完全不透明（如果bit depth小于16，则取最低有效位，其他位为0）

3.在真彩色图片中，包含单个RGB颜色值，格式如下：
Red: 2 bytes, range 0 .. (2^bitdepth)-1
Green: 2 bytes, range 0 .. (2^bitdepth)-1
Blue: 2 bytes, range 0 .. (2^bitdepth)-1
被指定的颜色值都会被当成是透明的，其他颜色值则完全不透明（如果bit depth小于16，则取最低有效位，其他位为0）

在带alpha通道的图片中，tRNS是被禁止使用的。

a.IHDR数据块

IHDR数据块存储了png图像的基本信息，一个图像中只能有一个IHDR数据块，并且也是png图像的第一个数据块。共有13个字节。记录的信息如下：

表1.2

域的名称	字节数	说明
Width	4 bytes	图像宽度，以像素为单位
Height	4 bytes	图像高度，以像素为单位
Bit depth	1 byte	图像深度.`索引彩色图像： 1，2，4或8 ,` `灰度图像： 1，2，4，8或16` `真彩色图像： 8或16`
ColorType	1 byte	颜色类型. `[0]：灰度图像, 1，2，4，8或16` `[2]：真彩色图像，8或16` `[3]：索引彩色图像，1，2，4或8` `[4]：带α通道数据的灰度图像，8或16` `[6]：带α通道数据的真彩色图像，8或16`
Compression method	1 byte	压缩方法(LZ77派生算法)
Filter method	1 byte	滤波器方法
Interlace method	1 byte	隔行扫描方法. `0：非隔行扫描` `1： Adam7(由Adam M. Costello开发的7遍隔行扫描方法)`

从这个表中可以得出，一张png图片最大的宽高（4294967300 × 4294967300）

这里的Bit depth一开始很难理解，引用维基百科两段话：

Pixels in PNG images are numbers that may be either indices of sample data in the palette or the sample data itself. The palette is a separate table contained in the PLTE chunk. Sample data for a single pixel consists of a tuple of between one and four numbers. Whether the pixel data represents palette indices or explicit sample values, the numbers are referred to as channels and every number in the image is encoded with an identical format.

The permitted formats encode each number as an unsigned integral value using a fixed number of bits, referred to in the PNG specification as the bit depth. Notice that this is not the same as color depth, which is commonly used to refer to the total number of bits in each pixel, not each channel. The permitted bit depths are summarized in the table along with the total number of bits used for each pixel.

The number of channels depends on whether the image is grayscale or color and whether it has an alpha channel. PNG allows the following combinations of channels, called the color type.

大意是：png图片的像素(Pixels)是调色板中样本数据的索引或者样本数据其本身，调色板是在PLTE数据块中的。单个像素的样本数据包含1~4个数字的元组。像素数据表示调色板索引或者明确的样本值，每个数字代表每个通道，每个数字都有唯一可识别的编码。

允许编码每个数字的格式是一个使用固定位数的unsigned整数值，在PNG中称为bit depth(位深)。位深和color depth(颜色深度)不同，颜色深度通常代表一个像素的总位数，不是每个通道的总位数。

通道数取决于这个图片是否是灰度图还是有alpha通道的色彩图

因此可以知道bit depth是一个通道的位数，bit depth在索引彩色图片和灰度图中使用，使得图片的一个像素点的大小可以小于一个字节

b.PLTE数据块（调色板数据块）

a.PLTE数据块在索引彩色图像中必须存在，这里记录了整张图片所有的颜色，最多为256个。这个是bit depth规定的，由表1.2可知，索引彩色图像的bit depth为1,2,4,8，共为1、4、16、256种颜色。每种颜色是3个字节（RGB)，所以PLTE数据块的length肯定是3的倍数，否则就是非法的。
b.PLTE数据块在真彩色图像或带α通道数据的真彩色图像中是可选的
c.PLTE数据块在灰度图像或带α通道数据的灰度图像中是不能存在的

c.IDAT数据块

这部分的数据块存放的就是图像的一个个像素（使用压缩算法之后生成的像素），一张图像中可以存在多个IDAT数据块，这种编码方式虽然稍微增加了图像的大小，但是可以使得PNG图像以一种流的方式生成。例如在浏览器中打开一张非常大的PNG图像，如果网络很慢，我们可以看到图片是从上到下一点点打开的，这是因为即使整张图片没有加载完，仍然可以显示局部内容。

IDAT数据块是最重要的一部分，这里的数据会被隔行扫描方法(Interlace method)、滤波器（filtering）和压缩算法(compression)处理。这三个部分会在下面详细介绍。

并且要注意的是，IDAT数据块存储的数据并不是以字节为最小单位，在灰度图片和索引彩色图片中，一个字节可能会包含多个像素点，由bit depth指定。

d.IENT数据块

这段数据块标记PNG文件或者数据流已经结束，并且必须要放在文件的尾部。

正常情况下， png 文件的结尾为如下12个字符：

00 00 00 00 49 45 4E 44 AE 42 60 82
由于数据块结构的定义，IEND数据块的长度总是0（00 00 00 00，除非人为加入信息），数据标识总是IEND（49 45 4E 44），因此，CRC码也总是AE 42 60 82

4.隔行扫描方法

隔行扫描方法是为了图片被更先进的展示出来。在图片传输过程中，可以让图片的展示有淡入的效果。虽然平均下来稍微增加了存储的大小，但是给带来用户更快的显示效果。

a.这个方法取值为0时，代表像素点是从左到右顺序存储，扫描线扫描时从上到下即可。
b.这个方法取值为1时，被称为Adam7算法
Adam7分为7个扫描步骤，可见下图：

5.过滤器

过滤器中只有一种过滤方法，但是有多种过滤类型。过滤方法并不会影响数据的大小，也不会影响丢失任何信息，过滤的目的只有一个，为压缩方法提供更好压缩的数据，IDAT数据中的每一行第一个字节定义了过滤类型，过滤类型的介绍如下:

a.过滤类型0：None

也就是不做任何过滤

b. 过滤类型1：Sub

记录当前像素和左边像素的差值。左边起第一个像素是标准值，不做任何过滤

c. 过滤类型2：Up

记录X – B的值，即当前像素和上边像素点差值。如果当前行是第1行，则当前行数标准值，不做任何过滤。

d.过滤类型3：Average

记录当前像素与左边像素和上边像素的平均值的差值。
- 如果当前行数第一行：做特殊的Sub过滤，左边起第一个像素是标准值，不做任何过滤。其他像素记录该像素与左边像素的二分之一的值的差值。
如果当前行数不是第一行：左边起第一个像素记录该像素与上边像素的二分之一的值的差值，其他像素做正常的Average过滤。

e.过滤类型4：Paeth

记录X – Pr的值，这种过滤方式比较复杂，Pr的计算方式（伪代码）如下：

p = a + b - c
pa = abs(p - a)
pb = abs(p - b)
pc = abs(p - c)
if pa <= pb and pa <= pc then Pr = a
else if pb <= pc then Pr = b
else Pr = c
return Pr

如果当前行数第一行：做Sub过滤。
如果当前行数不是第一行：左边起第一个像素记录该像素与上边像素的差值，其他像素做正常的Peath过滤。

6.压缩算法

压缩算法当前只定义了一种，值为0，是使用一个滑动窗口的deflate/inflate压缩，这个算法可以调用zlib库来实现

7.关于压缩

对于一张图片，我们可以使用以上知识来完成一次无损压缩,以及去除所有的辅助数据块。但是很多场景下，常规的无损压缩并不能带来很高的压缩比，这个时候可以考虑使用有损压缩，大概的思路就是将总体颜色数减少到256以下（使用相近的颜色来代替），然后使用索引色彩来编码整张图片，带来很高的压缩比

实际操作验证

一级压缩图片（958.8k）：https://www.myway5.com/wp-content/uploads/2017/11/output_1.png
九级压缩图片（857.0k）：https://www.myway5.com/wp-content/uploads/2017/11/output_9.png
有损压缩图片（273.0k）：https://www.myway5.com/wp-content/uploads/2017/11/test_tiny.png
原图（1.5m）：https://www.myway5.com/wp-content/uploads/2017/11/test.png)

使用vim打开原图:

8950 4e47 0d0a 1a0a是png固定的头,

0000 000d是iHDR数据块的长度，为13，4948 4452是数据块的type,为IHDR，之后紧跟着是data， 0000 02bc是图片的宽度,0000 03a5是高度，08是Bit depth，也就是一个通道是8位,06是color type,这里表示图片是真彩色，00是压缩方法，png中目前只有一种，也就是LZ77派生的算法，00是滤波器方法，表示不使用，00是隔行扫描方法，代表不扫描。8f 1434 a4是四个字节的CRC校验码。

00 0000 01是sRGB数据块的长度（???)，为1，73 5247 42是type,为sRGB，00是存储的一个字节数据，aece 1ce9是循环校验码

之后还有一个iDoT数据块，再紧接着才是IDAT数据块，下面就不分析了。

再打开9级压缩的图片

简单看一下，sRGB和iDOT数据块已经不存在了,IDAT数据块的长度发生了改变，其实就是被压缩了。这种压缩是无损的，9级压缩和1级压缩相差十几k的大小，但是压缩的越小，耗时也越长。

最后去看在tinypng上进行有损压缩的图片:

它多了一个PLTE字段，意味着这张图变成了索引彩色图片，索引彩色图片最关键的一点就是总颜色数不能超过256。如果这张图片的总颜色数没有256个，那么甚至可以说这次图片的压缩是无损的。但是一旦颜色数超过256，就需要将多个相近的颜色处理成一个颜色，也就是有损的压缩

参考

[1] png文件结构分析:http://www.360doc.com/content/11/0428/12/1016783_112894280.shtml
[2] php imagecreatefrom* 系列函数之 png：http://drops.xmd5.com/static/drops/tips-16034.html
[3] Portable Network Graphics: https://en.wikipedia.org/wiki/Portable_Network_Graphics
[4] png的故事：获取图片信息和像素内容: https://www.qcloud.com/community/article/864088
[5] https://www.w3.org/TR/2003/REC-PNG-20031110/#figure48

树的可视化以及家谱绘制的算法

一、前言

树的可视化意思就是将一颗树（数据结构的树）用图形展现出来。树的可视化有很多种用途，比如说很常见的组织结构图就是树的可视化的应用。家谱也可以算是一颗树，但是与树的可视化稍微不同的是，会有配偶这个角色，同时一个家谱可能并不是从一个根节点向下（可能存在某个家族向上追溯到某一代，之前的资料已经完全丢失了，那么这个家谱的起源应该是这一代人，而不是具体到某一个人）。

二、难点

在树的可视化过程中，难点就在于如何确定每一个节点的位置（X,Y），Y坐标相对来说是比较好确定的，可以根据它在一颗树中的第几层来确定Y的值；X的值既受到同一层其他的节点位置的影响，同时也受到其子代位置的影响。因为其子代可能会和其兄弟节点的子代交叉。所以这篇文章主要讲解的是每个点的位置的计算。

家谱的绘制和树的可视化也有前言中的一些不同之处，因为也不能完全的将树的可视化算法生搬硬套。

下面我将一步步的讲解整个树的可视化算法的过程，以及如何将这个算法应用到家谱的绘制上，并给出具体的实现代码（因为是网页上有这个需求，所以代码是js写的）。算法的主要提出者是John Q. Walker II，这里有他对这个算法的相关讲解。POSITIONING NODES FOR GENERAL TREES

三、算法介绍

图1：
示意图

1、节点属性定义

var Node = function(key,image,description){
    this.key = key;
    this.parent = null;         //父辈
    this.offspring = null;      //指向最左边的子辈
    this.leftSibling = null;    //左兄弟
    this.rightSibling = null;   //右兄弟
    this.prelim = 0;            //x坐标的预定义
    this.modifier = 0;          //调整的大小
    this.level = 0;
    this.width = 60;            //每个节点的最终宽度，如果存在配偶这个宽度是会发生改变的
    this.height = 80;           
    this.nodeWidth = 60;        //每个节点的基本宽度，不会变
    this.nodeHeight = 80;
    this.x = 0;
    this.y = 0;
    this.spouses = [];
    this.image = image||"assets/post-photo.jpg";
    this.description = description || "";
};

这里首先介绍几个重要的属性：

parent,offspring,leftSibling,rightSibling：分别是当前节点的父节点指针、最左边的孩子节点的指针、左兄弟、右兄弟。以上图为例，M点的parent是N,offspring是H,leftSibling是G,rightSibling是null。

prelim：当前点的X的预定义位置。如同在难点中所说，X的位置受到很多因素的影响，所以需要多次计算。prelim只是预定义的位置，不是最终的位置。

modifier：调整值，不过这个调整值并不是说当前点的X还要调整多少，而是当前点的后代的X还要调整的大小。

level：当前点所处的层级。

width、height、nodeWidth、nodeHeight：这些参数用来表示节点的宽和高，width和nodeWidth的区别在于，nodeWidth是画出来的节点的宽度，是一个基本属性，不会改变，width则表示这个点最终会占用的宽度。在树的可视化算法中，只需要nodeWidth和nodeHeight，width和height是专门为家谱的绘制增加的。

x：当前点的X，如何确定X的大小呢？以M为例，M.X = M.prelim + N.modifier + O.modifier。

y：当前点的y,以M为例: M.y = M.level * (每层的间隔 + M.height);

spouses:这个是专门为家谱的绘制准备的。表示当前点的配偶，一个点的配偶可以有多个，所以使用数组。

2、算法的大概流程

算法大概可以划分为：

1.倒序遍历整颗树，初次确定每个点的prelim和modifier。
2.从最底层逐级向上检查是否存在交叉，如果存在交叉则调整（这一步和我参考的算法不同，它是从上向下检查，但是我在使用中发现，如果存在子树的子树交叉的情况，那么在高层做了调整之后，这里再做一次调整就可能出现再次重叠的情况，所以改用从底层向上检查）。
(勘误：这个地方不对，应该还是从上向下遍历，这样从上方调整后，即使下方还有重叠，也可以再次检测并调整)
3.最后确定根节点的位置

3、算法详细介绍

这里我们先定义几个常量:

SiblingSeparation = 4,   //兄弟节点之间的间隔
SubtreeSeparation = 6,   //子树之间的间隔
width = nodeWidth = 2   //节点的宽度

还是以图1所示的树为例，这里先做一遍倒序遍历，初步确定每一个节点的位置：

A：因为A的左节点是null,所以

A.prelim = 0;
A.modifier = 0;

B.prelim = 0;
B.modifier = 0;

C：因为C有左节点B，所以C要在B的基础上做向右的偏移，偏移量为B的prelim加上B的宽度加上间隔大小(这个地方的处理和John Q. Walker II的算法不同，是为了家谱的显示做的更改)。所以

C.prelim = B.prelim + B.width + SiblingSeparation = 0 + 2 + 4 = 6;
C.modifier = 0;

D：因为D是B、C的父节点，同时是A的右兄弟，所以D的位置由A确定后，为了保证D应该在B和C中间，应该对B、C做调整，但是我们并不会再回头对B、C做处理，而是计算D的modifier，以此来表示D的后代需要调整的位置。并且D.modifer应该等于D.prelim – (B.prelim + C.prelim)/2。

D.prelim = A.prelim + A.width +  SiblingSeparation= 0 + 2 + 4 = 6;
D.modifier = D.prelim - (B.prelim + C.prelim) / 2 = 6 - (0 + 6) / 2 = 3;

E：因为E没有左兄弟，所以直接通过A、D来确定位置即可

E.prelim = (A.prelim + D.prelim) / 2 = (0 + 6) / 2  = 3;
E.modifier = 0;

F：

F.prelim = E.prelim + E.width + SiblingSeparation = 3 + 2 + 4 = 9;
F.modifier = 0;

G：

G.prelim = 0;
G.modifier = 0;

H：

H.prelim = 0;
H.modifier = 0;

I：

I.prelim = H.prelim + H.width + SiblingSeparation = 0 + 2 + 4 = 6;
I.modifier = 0;

J：

J.prelim = I.prelim + I.width + SiblingSeparation = 6 + 2 + 4 = 12;
J.modifier = 0;

K：

K.prelim = J.prelim + J.width + SiblingSeparation = 12 + 2 + 4 = 18;
K.modifier = 0;

L：

L.prelim = K.prelim + k.width + SiblingSeparation = 18 + 2 + 4 = 24;
L.modifier = 0;

M：

M.prelim = G.prelim + G.width + SiblingSeparation = 6;
M.modifer = M.prelim - (H.prelim + L.prelim) / 2 = -6；

N.prelim = F.prelim + F.width + SiblingSeparation = 9 + 2 + 4 = 15;
N.modifier = N.prelim - (G.prelim + M.prelim) / 2 =  12;

走到这里我们就不再向上走了，因为根节点的位置肯定是有E和N来最终确定。所以这个时候应该来调整整颗树，检查是否存在节点位置重叠的情况。检查是否重叠是一个递归，所以使用递归检查会降低很多复杂度。但是这里我们走一遍过程，并非是严格按照代码执行过程。

我们先检查最底层，也就是这颗树的第4层：
检查C和H是否有重叠（当然是最右和最左做对比了）：
C.X = D.modifier + E.modifier + C.prelim = 3 + 0 + 6 = 9;
H.X = M.modifier + N.modifier + H.prelim = -6 + 12 + 0 = 6;

所以H在C的左边3处，显然是重叠了的。所以需要将H所在的子树全部向右移offset = SubtreeSeparation - (H.X-C.X) = 9;我们一直向上找，直到C和H的祖先是兄弟时，也就是E和N，修改N.prelim、N.modifier就代表将N和其子树全体右移。

N.prelim = N.prelim + offset = 15 + 9 = 24;
N.modifier = N.modifier + offset = 12 + 9 = 21;

这时候E和N之间距离变得更大了，但是E和F的距离与F和N的距离是不同的，为了让树显示的好看一点

F.prelim = F.prelim + offset / 2 = 9 + 9 / 2 = 13.5;

F的子树也应该调整一下（虽然这里并没有）

F.modifier = F.modifier + offset / 2 = 0 + 9 / 2 = 4.5;

我们再往上看，发现已经没有重叠的了。

这时候确定根节点O的位置

O.prelim = (E.prelim + N.prelim) / 2 = (3 + 24) / 2 = 13.5;
O.modifier = 0;

四、如何将树的可视化算法应该到家谱的绘制上。

在之前已经介绍过家谱和树的结构有稍许不同，所以我们尽量将家谱做一些处理，使其变成标准的树结构。

1.配偶问题。
将某个节点的配偶不当成一个节点看待，而是这个节点的一部分，所以我们只需在有配偶的时候改变节点的width就可以了。
2.不只一个根节点的问题
既然有不只一个根节点存在，那么我们就自己定义一个虚拟的节点作为根节点，将第一层所有的点的parent都指向这个根节点即可。这样就是一个非常标准的树结构了。

五、源代码

源代码放在了github上，地址为https://github.com/joyme123/candraw

基于Jenkins的自动部署方案

一、前言

在一家小公司工作，负责开发一个项目，前台用的angular2，后台是php和c++。每天下班之前都要将当天的代码部署的线上的开发服务器上，常常也需要更新到生产服务器（项目并没有正式运行，但是老板要用项目去拉投资）。手动部署代码总有一种浪费时间的感觉（因为下班时间到了啊！！！）。使用Jenkins+shell脚本完成自动部署就可以避免这种情况了。感谢赖同学的指导

二、流程介绍

公司内网搭建了git服务器，线上的开发用的服务器部署在阿里云，但是这台服务器的配置实在是太低了，完全没法胜任在线编译部署的需求。所以我要做的是将代码提交到git服务器后，使用Jenkins从git的dev分支拉取代码，构建部署计划（手动或者使用钩子都行）。

三、Jenkins的使用

第一步:部署Jenkins，这一步很简单，直接从Jenkins的官网上wget Jenkins的war包，然后java -jar jenkins.war即可。可以配合supervisor来实现自动启动和重启。

第二步：访问http://ip:8080进行配置，第一次配置的密码是java -jar jenkins.war时，在控制台上输出的密文。然后新建项目，然后选择构建一个多配置项目

第二步：进入到一个配置界面，填一下项目名称，其他的都不用管，直接来到源代码管理。我用的是Git服务器，所以选择git,然后填入仓库地址，配置项目仓库地址可以是HTTP协议，也可以是SSH协议，然后记得在Credentials字段填入认证信息,HTTP协议可以是用户名和密码，SSH的话可以是秘钥。选择的是dev分支。之后在填写构建信息。构建命令主要就是执行一个脚本

第三步：编写自动部署的脚本，主要就是编译，然后发送到远程服务器，这里用了scp来传输文件，非常好用。

脚本很简单，具体如下：

#!/bin/bash
## 自动部署脚本

cd homepage/mobile
cnpm install
ng build -prod -aot -env=prod
scp -r dist/* root@120.26.103.174:/alidata/www/m_family

注意这里的scp传输文件到远程服务器的前提是，远程服务器上.ssh文件夹下的authorized_keys中有Jenkins所在服务器的公钥，这样才能不需要密码通过认证。

问题描述

问题排查

问题解决

更多的思考

参考

一、简介

二、规则定义

2.1 规则命名

2.2 规则格式

2.3 终端值

2.4 额外的编码

三、 运算符

3.1 连接: Rule1 Rule2

3.2 选择: Rule1 / Rule2

3.3 扩展的选择: Rule1 =/ Rule2

3.4 范围选择: %c##-##

3.5 序列组: (Rule1 Rule2)

3.6 变量重复: *Rule

3.7 指定的重复: nRule

3.8 可选的序列: [Rule]

3.9 注释: ;Comment

3.10 运算符优先级

四、使用ABNF定义ABNF

附录：核心规则

简介

优化措施一：缓存

优化措施二：分层

1.场景

2.要求

3.方案提出

3.1 token bucket（令牌桶）

3.2 redis数据库

4.具体实现

5.扩展知识

参考文献

什么是RBAC

什么是角色(Role)

隐式的基于角色的权限控制

显式的基于角色的权限控制

隐式 vs 显式

新的RBAC：Resource-Based-Access-Control

1.简介

2.几种编码方式的说明

a.灰度图片

b.索引彩色图像

c.真彩色图像

d.带α通道数据的灰度图像

e.带α通道数据的真彩色图像

3.png图片具体编码说明

a.IHDR数据块

b.PLTE数据块（调色板数据块）

c.IDAT数据块

d.IENT数据块

4.隔行扫描方法

5.过滤器

a.过滤类型0：None

b. 过滤类型1：Sub

c. 过滤类型2：Up

d.过滤类型3：Average

e.过滤类型4：Paeth

6.压缩算法

7.关于压缩

实际操作验证

参考

一、前言

二、难点

三、算法介绍

1、节点属性定义

2、算法的大概流程

3、算法详细介绍

四、如何将树的可视化算法应该到家谱的绘制上。

五、源代码

一、前言

二、流程介绍

三、Jenkins的使用

三、运算符

3.1 连接: `Rule1 Rule2`

3.2 选择: `Rule1 / Rule2`

3.3 扩展的选择: `Rule1 =/ Rule2`

3.4 范围选择: `%c##-##`

3.5 序列组: `(Rule1 Rule2)`

3.6 变量重复: `*Rule`

3.7 指定的重复: `nRule`

3.8 可选的序列: `[Rule]`

3.9 注释: `;Comment`