Page 5 of 12 for 派猴子来的救兵

27 Nov, 2019
Git Flow Practice
背景
1. 公司 APP 每个月迭代一次, 比如说每个月 15 号, 发布一个新版本
2. 当前只有一个分支, 所有代码都合并到这个分支, 比如说都合到 master 分支
3. 公司的发布系统, 发布之后可以看到每个版本使用的 branch/tag/commit hash 等(这个后面会提到)
这样会生产一个问题:

15 号发版之后, 开始开发新功能, 合到 master 上面, 这些代码会到下个月15号发到线上.
但同时, HotFix 需要马上发到线上. 如果从 master checkout 一个 hotfix 分支出来改代码, 再合回master. master上面会包括还没有测试过的新功能. 那这个hotfix发布之后可能带来问题.

最初讨论后的规划

如何在现有的基础(单分支)上解决这个问题

中间有同学提出目前这样也可以解决上面的问题: 功能开发正常推到 master , 如果有 hotfix, 到发布系统看一下当前的 Commit 或者是 Tag, 拉一个新的分支, fix 之后推上去继续发布.

但会有一些问题:
- 每次要做 hotfix, 还要去发布系统查看当前的 tag 或者是 commit
- 如果两个人同时做 hotfix, 可能后面发布的人同学会把前面那个人的覆盖掉
- 分支混乱, 每次 hotfix 后推一个新的分支上来?
会后讨论结果(实践后又有变化):

决定使用dev 和 master 两个分支
1. 日常开发推 dev, 15号之后合到 master , 打上 tag
2. 15号之后的 hotfix , 从 master 拉分支出来, fix之后合回master, 同时 cherry-pick 到 dev
3. 细节上可能会有问题, 再实践中慢慢摸索
改动

增加relese 分支

代码在真正发布到生产之后, 需要先发布到测试环境测试.
使用 dev 发布并没有问题, 但如果结合持续集成(CI), 就有些问题了.

我希望的是, 每次 Merge 之后, 会自动发布, 而不需要我每次到发布系统点点点.
显然不能把 Dev 分支配置成自动发布, 否则在新的开发周期, 会频繁做一些无用的发布.

所以需要 release 分支. 发布的时候, 直接从 dev checkout 一份最新代码, 推到远端 release, 自动发布.

15 号发布之后, 就把当前 release 代码合到 master, 并打上 tag

保留 master

如果只是为了回滚, tag 足够了. master 是为了方便的 hotfix. 想像一下没有 master, 每次发布还要查看最新的 tag 是什么, 万一再忘了打 tag 呢?

目前实践

总结一下, 实践下来, 保留 2 个主要分支, dev 和 master, 一直存在, 不能删除. 一个临时分支 release.

以一次新的迭代周期开始为例:
1. 新的功能开发推到 dev. hotfix 推到 master, 并更新版本号, 并 cherry-pick 到 dev.
2. 10 号了, 开始预发布了(一般是先到测试环境), 每次发布就把 dev 的代码合到 release, 推到远端(我一般在命令行操作), CI 会自动做发布.
3. 15 号, 发布到生产. release 代码合到 master, 并打一个 tag. (可以由项目 Owner 或者管理员手工操作)
4. 15 号之后, 回到步骤1
2020-03-30 补充

有人提到使用 release 发布太麻烦了, 应该 dev 也能发布. 现成改成了 dev 也会发布. 运行良好.

参考资料:
17 Jul, 2019
虚拟一个 Mysql 给 Django 用
我想通过 Model 生成建表的 Sql, 但是一定要有一个可用的 Mysql 才行, 觉得很麻烦. 于是找到了这个项目.

https://pypi.org/project/django-fake-database-backends/

安装:

pip install django-fake-database-backends

配置:
```
DATABASES = {
    'default': {
        'ENGINE': 'django_fake_database_backends.backends.mysql',
    }
}
```
17 Jul, 2019
django 连 Mysql 报2059错误
参考https://blog.csdn.net/xiaoyaosheng19/article/details/82643729

原因：最新的mysql8.0对用户密码的加密方式为caching_sha2_password, django暂时还不支持这种新增的加密方式。只需要将用户加密方式改为老的加密方式即可。
```
use mysql;
alter user 'root'@'localhost' identified with mysql_native_password by 'yourpassword';
flush privileges;
```

26 Jun, 2019

8皇后问题

问题是8皇后问题有多少种解法(只需要一个总数, 不需要每一个具体的解决方案)

据说是目前效率最高的代码, 使用位运算操作.

#include<stdio.h>

int succ, ans;

void sol(int cp, int lp, int rp) {
    if (cp == succ) {
        ++ans;
        return;
    }
    int p = succ & (~(cp | lp | rp));
    while (p) {
        int bit = p & (-p);
        sol(cp | bit, (lp | bit) << 1, (rp | bit) >> 1);
        p &= (p - 1);
    }
}

int totalNQueens(int n){
    ans = 0;
    succ = (1 << n) - 1;
    sol(0, 0 ,0);
    return ans;
}

int main(){
    int ans;
    ans = totalNQueens(4);
    printf("%d\n", ans);
}

自己看了很久没看明白, 网上搜索了一下资料后才理解, 其实挺简单的. 不记得资料 URL 了, 也不去再找了, 默默致谢一下.

一步步来, 先不管上面的代码, 不管是不是使用位来操作, 先按一个简单的思路写下伪代码.

sol(depth, pos) { // depth 是当前要处理第几行, pos 是前面已经安放好的位置, 也就是上面 depth-1 行的数据

	 // 如果 N 排数据都已经安置好了, ans 加1
	if depth == N+1 {
		ans++
	}

	p = 根据 pos 计算当前行可以放的所有位置

	while ( p 中还有位置可以尝试 ) {
		next = 取当前行的下一个位置
		sol(depth+1, pos.update(next))
		update(p)
	}
}

我们如果想使用 BIT 记录数据(包括已经安放的位置, 以及当前行可以尝试的位置等等), 以及使用位运算加速, 需要考虑几个问题:

如何表示已经安放的位置
如何根据问题 1 计算出当前行可以安放的位置

直接看一下上面的代码是如何解决这些问题的.

它并没有直接使用一个变量记录”已经安放的位置”, 而是使用了三个变量间接实现的, 理解了这三个变量就理解这个代码了.

cp 用来记录”只考虑直上直下的冲突, 前面所有行安放的棋子会导致 depth 这一行哪些位置不能放”, 就是说, 第一行放左数第一个位置, 那么第二行就不能再放左数第一个位置了. 拿”八”皇后举例说明, 第一行棋子放在左数第三个位子, 那在计算第二行的位置时, cp = 0b00100000 . 继续在第二行的左数第一个位置放棋子, 计算第三行的位置时, cp = 0b00100000

0b10000000 = 0b10100000 . 很自然的, cp 的初始值应该是 0b00000000

lp 用来记录”右上-左下这条对角线上的冲突, 前面所有行安放的棋子会导致 depth 这一行哪些位置不能放”, 就是说, 第一行放左数第二个位置, 那么第二行就不能再放左数第一个位置了. 拿”八”皇后举例说明, 第一行棋子放在左数第三个位子, 那在计算第二行的位置时, lp = 0b00100000

0b01000000 = 0b01100000 .

rp 和 lp 类似, 只是记录 “左上-右下” 这条对角线.

搞清楚这三个变量, 再回头看一下问题1和2 . 问题1并不是一定要解决的, 因为”记录已经安放的位置”也只是为了解决问题2, 我们使用这三个变量有两个好处, 一是可以快速算出问题2, 二是可以使用位运算快速更新三个变量本身

然后, depth 这个变量并不是必需的, 可以使用 cp 取得一样的效果. cp 里面有多少个1, 就代表处理了几行了.

29 May, 2019
Waitgroup In Golang
下面这段代码是模拟一个工作任务: goroutine里面做任务, 主进程里面等任务完成才退出, 避免一个任务因进行中退出. 实际代码肯定会复杂, 这两种线程可能散落在多个文件中.
```
package main

import "sync"

var wg sync.WaitGroup

func work() {
	for {
		wg.Add(1)
		// ... work here
		// time.Sleep(time.Second)
		wg.Done()
	}
}

func main() {
	go work()
	defer wg.Wait()
}
```
乍一看好像也没问题, 但有小概率 Panic: WaitGroup is reused before previous Wait has returned.

直接google查了好几个文章都没解释为什么, 最后还是看官方文档找到解释. 官方文档好啊, 一定要花时间撸一遍才好.
```
If a WaitGroup is reused to wait for several independent sets of events, new Add calls must happen after all previous Wait calls have returned.
```
上面代码中的 Wait 并不是原子操作, 可能 Wait 还没有结束的时候, 又再次调用到了 Add 方法, 这时候就会 Panic.
9 May, 2019
defer里面的值何时evaluate
第一个问题

我在写这个的时候只是想记录一下像标题中说的, defer 里面的 parameters 何时 evaluate, 就像下面这一个例子. (后面才发现还有 function value 何时 evaluate 的问题)

例子来自于 https://groups.google.com/forum/#!topic/golang-nuts/c7YUK65Xqgs%5B1-25%5D
```
package main
import (
    "fmt"
)
func main() {
    for i := 0; i < 10; i++ {
        defer func() {
            fmt.Printf("func(): %v\n", i)
        }()
        defer printi(i)
        defer fmt.Printf("i: %v\t", i)
    }
}
func printi(i int) {
    fmt.Printf("printi(): %v\t", i)
}
```
结果是这样的
```
OUTPUT
======
i: 9	printi(): 9	func(): 10 
i: 8	printi(): 8	func(): 10 
i: 7	printi(): 7	func(): 10 
i: 6	printi(): 6	func(): 10 
i: 5	printi(): 5	func(): 10 
i: 4	printi(): 4	func(): 10
i: 3	printi(): 3	func(): 10
i: 2	printi(): 2	func(): 10 
i: 1	printi(): 1	func(): 10 
i: 0	printi(): 0	func(): 10
```
二楼的 emepyc 说的很清楚, 我也不画蛇添足了, 直接复制过来
The key point is that the arguments to the deferred functions are evaluated and copied in the invocation of the defer. So:
```
defer  func()  {
  fmt.Printf("func():  %v\n",  i)
}()
```
No arguments to func(), so i is not copied and the final value of i is used when the deferred function is executed.
```
defer  printi(i)
defer  fmt.Printf("i:  %v\t",  i)
```
In both cases, i is the argument of the deferred function, so its value is copied and used when the deferred function is evaluated.
第二个问题

第二个问题, 在我看完之后, 并看了相关的链接资料, 发现是第一个问题的超集.

先来看一下原问题, https://stackoverflow.com/questions/51360229/the-deferred-calls-arguments-are-evaluated-immediately

这个回答里面也给出了 golang 官方资料关于 defer 的链接, 我之前在 google 搜索 golang defer 在第一页居然没有出现这个官方链接 .. https://golang.org/ref/spec#Defer_statements . 官方资料里面言简意赅的解释了 defer 的执行规则, 但是… 如果不能精确理解其中一些术语的话, 会看的很不明白, 比如我..

由三句话组成, 分别对应三个执行规则.(我是这么理解的, 不精准)
1. Each time a “defer” statement executes, the function value and parameters to the call are evaluated as usual and saved anew but the actual function is not invoked.
2. Instead, deferred functions are invoked immediately before the surrounding function returns, in the reverse order they were deferred. That is, if the surrounding function returns through an explicit return statement, deferred functions are executed after any result parameters are set by that return statement but before the function returns to its caller.
3. If a deferred function value evaluates to nil, execution panics when the function is invoked, not when the “defer” statement is executed.
对于第一点, https://stackoverflow.com/questions/51360229/the-deferred-calls-arguments-are-evaluated-immediately 这里有非常好的解释了.

第二点, 在 Defer, Panic, and Recover 中第三个例子有解释
```
func c() (i int) {
    defer func() { i++ }()
    return 1
}
```
像上面这段代码, 是返回2

在 https://golang.org/ref/spec#Defer_statements 也有例子

第三点是说, 如果 deferred function value 返回了nil, 不会马上出错, 而是等到外层函数返回之后调用到defer函数的时候才会panic, 如下:
```
package main

import "fmt"

func def(s string) func() {
	fmt.Println("tier up")
	fmt.Println(s)
	return nil
}

func main() {
	defer def("defered line")()
	fmt.Println("main")
}
```
执行结果
```
% go run a.go
tier up
defered line
main
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x10528e8]

goroutine 1 [running]:
main.main()
	/private/tmp/1577163316/a.go:14 +0xc8
exit status 2
```
8 May, 2019
搭建Kafka集群时, 对ZooKeeper认证与权限控制
废话写在最前
1. 公司需要部署一套kafka, 放在公网服务, 所以就查查资料, 尝试部署一套有SSL加密传输的, 而且有认证和权限控制机制的Kafka集群.
2. 我之前对ZK的认证机制不了解, 也几乎不在JAVA生态圈有过经验, 所以对JAAS完全不了解. 对SASL也是首次接触. 因为kafka官方文档写的实在太简单(仅仅是指https://kafka.apache.org/documentation.html#zk_authz_new这一节), 在尝试和翻阅了好多(过时的)资料之后, 终于算是成功部署了. 但依然很多不知其所以然的地方.
3. 对SSL有一定了解, 对Listenr配置也有一定了解了 . 所以打算先看一下Zookeeper的认证权限控制, 这个之前还没有接触过.
对ZooKeeper认证与权限控制目的

大的目的很简单, 因为提供对公的服务, 相比公司内部使用来说, 有安全隐患, 需要做一定的安全保护措施, 也就是上面提到的, “有SSL加密传输的, 而且有认证和权限控制机制的Kafka集群”.

具体怎么样做到”更安全”这个目的呢?(也就是我们的更精确一些的目的是什么呢?) 引述一下kafka官方文档中一段话.
```
The metadata stored in ZooKeeper for the Kafka cluster is world-readable, but can only be modified by the brokers.
The rationale behind this decision is that the data stored in ZooKeeper is not sensitive, but inappropriate manipulation of that data can cause cluster disruption.
We also recommend limiting the access to ZooKeeper via network segmentation (only brokers and some admin tools need access to ZooKeeper).
```
字面意思很明确, ZK 中存的元信息是任何人都可读的, 但是只能被 Kafka Broker 修改, 因为这些信息不是敏感信息, 但随意改动却可能对 Kafka 造成破坏. 另外建议在网络层面隔离 ZK (因为只有 Broker 和一些管理工具才需要访问Zk )

我的理解是, 官方建议网络层面隔离ZK, 但是 ZK 本身也会有这样一种选择: 不能匿名登陆, 只可以让认证用户登陆. 但是实践下来, 并非如此. (此处存疑, 后面需要查阅ZK文档). 实践下来的”结论”比较奇怪: ZK 通过 JAAS 设置了用户(以及密码), Kafka 需要使用配置过的用户连接 ZK 并设置ACL. 但是, 1, 匿名用户依然可以连接 ZK, 也可以创建 Znode, 以及对 Znode 设置权限. 只是对 Broker 已经创建并设置好ACL的 Znode 只有只读权限. 2. Kafka 一定要是 JAAS 中配置用户(以及相对应的密码), 否则就会创建 Znode 失败. 1和2两点似乎是矛盾的.

配置步骤

首先感谢 RedHat 的这篇文档 https://access.redhat.com/documentation/en-us/red_hat_amq/7.2/html/using_amq_streams_on_red_hat_enterprise_linux_rhel/configuring_zookeeper#assembly-configuring-zookeeper-authentication-str

配置 ZK 的认证

ZK 的认证配置可以参考(这个文档是说ZK节点之间的认证, 但Kafka到ZK的认证也就多了一步) https://cwiki.apache.org/confluence/display/ZOOKEEPER/Server-Server+mutual+authentication, 这里有详细的权威的步骤以及说明, 我简单记录一下吧.

我想提前先提一下 JAAS 配置, 因为这里有个还不明白的地方. ZK 以及 Kafka, 他们的 JASS 配置文件的格式都是一样的, 但简单看了一下 JAAS 的文档, 并没有看到针对这种格式的说明, 所以不明白这种格式是标准, 还是只是 ZK/Kafka 自己定义的格式. 另外, 对于里面的参数, 比如 username=XXX, 是有一个标准, 还是大家各自实现自己的, 也不清楚. [存疑]

zoo.cfg 配置

将下面配置写入 zoo.cfg. 先提一下注意点, 里面的第2行第3行是 Zk 节点之间的认证开关, 并不影响 Kafka 到 ZK 的认证.
```
quorum.auth.enableSasl=true
quorum.auth.learnerRequireSasl=true
quorum.auth.serverRequireSasl=true
quorum.auth.learner.loginContext=QuorumLearner
quorum.auth.server.loginContext=QuorumServer
#quorum.auth.kerberos.servicePrincipal=servicename/_HOST
quorum.cnxn.threads.size=20
```
因为我们没有使用 kerberos, 所以把第6行注释了.

解释一下各行的意思:

quorum.auth.enableSasl=true

打开sasl开关, 默认是关的

quorum.auth.learnerRequireSasl=true

ZK做为leaner的时候, 会发送认证信息

quorum.auth.serverRequireSasl=true

设置为 true 的时候, learner 连接的时候需要发送认证信息, 否则拒绝.

quorum.auth.learner.loginContext=QuorumLearner

JAAS 配置里面的 Context 名字.

quorum.auth.server.loginContext=QuorumServer

JAAS 配置里面的 Context 名字.

quorum.cnxn.threads.size=20

建议设置成 ZK 节点的数量乘2

bin/zkEnv.sh 添加 jvm 选项
```
SERVER_JVMFLAGS="-Djava.security.auth.login.config=/path/to/server/jaas/file.conf"
```
具体的路径自己配置一下, 另外最好确认一下 SERVER_JVMFLAGS 是不是被使用了, 因为版本不断迭代, 后面也许会有变化.

JAAS 配置
```
Server {
    org.apache.zookeeper.server.auth.DigestLoginModule required
	    user_super="123456"
		user_kafka="123456"
		user_someoneelse="123456";

};

QuorumServer {
       org.apache.zookeeper.server.auth.DigestLoginModule required
       user_zookeeper="123456";
};

QuorumLearner {
       org.apache.zookeeper.server.auth.DigestLoginModule required
       username="zookeeper"
       password="123456";
};
```
QuorumServer 和 QuorumLearner 都是配置的 ZK 节点之间的认证配置, 我们叫他 Server-to-Server authentication , 并不影响 Kafka 的连接认证. Server 是配置的Kafka连接需要的认证信息, 我们叫他 Client-to-Server authentication

按我的理解说一下配置意思, 不一定准确.

QuorumServer 和 QuorumLearner 是指 Context 名字, 默认是这样的, 但可以通过上面提到的配置更改默认名字.

QuorumServer 里面的 user_zookeeper=”123456” , 是特定格式, 代表一个密码为123456的用户, 用户名是zookeeper, Learner 连接的时候需要使用这个用户/密码认证.

QuorumLearner 里面的配置是说, 做为 learner 连接的时候, 使用配置的用户名/密码认证.

下面是我还不明白的地方, 现在只能不负责任的说一下. [存疑]

org.apache.zookeeper.server.auth.DigestLoginModule 应该是指的认证方式, 有些文章中说, 和 Kafka 的 JAAS 配置需要一致, 但我测试下来并非如此.
我自己实践下来, ZK 中一定要使用 org.apache.zookeeper.server.auth.DigestLoginModule, 但Kafka中可以使用 org.apache.zookeeper.server.auth.DigestLoginModule, 也可以使用 org.apache.kafka.common.security.plain.PlainLoginModule

对机制并不明白, 所以也是云里雾里.

对于 Server Context 配置, RedHat 文章中说, super 用户自动获得管理员权限. 我也不明白为啥, 在这里可以配置多个用户, Kafka 选一个用就可以了, 一般我们起名叫 kafka.

打开 Client-to-Server authentication

把下面的配置写到 zoo.cfg
```
requireClientAuthScheme=sasl
authProvider.<IdOfBroker1>=org.apache.zookeeper.server.auth.SASLAuthenticationProvider
authProvider.<IdOfBroker2>=org.apache.zookeeper.server.auth.SASLAuthenticationProvider
authProvider.<IdOfBroker3>=org.apache.zookeeper.server.auth.SASLAuthenticationProvider
```
这里的IdOfBroker是指ZK节点的myid. 后面的 org.apache.zookeeper.server.auth.SASLAuthenticationProvider 是指什么还不明白 [存疑]

ZK 的配置就到这里了, 权限控制(ACL)是另外一个话题. 后面再说.

紧接着说一下 , 如何配置 Kafka 使用认证连接 ZK.

Kafka 需要的配置

打开开关

在 config/server.properties 里面添加下面一行配置
```
zookeeper.set.acl=true
```
JVM选项中配置JAAS配置文件路径信息

在合适的地方, 添加下面这样的配置, 我在 bin/kafka-run-class.sh 添加的
```
KAFKA_OPTS="-Djava.security.auth.login.config=./config/jaas.conf"
```
配置 JAAS

jaas.conf 配置中添加如下内容
```
Client {
    org.apache.kafka.common.security.plain.PlainLoginModule required
	username="kafka"
	password="123456";

};
```
这样起来之后, Kafka 创建和使用的 Znode 都会被设置了ACL, 其他用户只能看, 不能修改.

15 Dec, 2018

算法导论笔记 6-3 建堆

先写一个 go 语言的程序如下

package main

import (
	"fmt"
	"math"
	"math/rand"
	"strings"
	"time"
)

func maxHeapify(A []int, i int) {
	var (
		size  = len(A)
		left  int
		right int
		max   int
	)

	for {
		left = 2*i + 1
		right = 2*i + 2
		max = i

		if left < size && A[i] < A[left] {
			max = left
		}
		if right < size && A[max] < A[right] {
			max = right
		}

		if max == i {
			return
		}
		A[i], A[max] = A[max], A[i]
		i = max
	}
}

func buildMaxHeap(A []int) {
	length := len(A)
	for i := length/2 - 1; i >= 0; i-- {
		maxHeapify(A, i)
	}
}

func GA(N int) (A []int) {
	A = make([]int, 10)
	for i := 0; i < N; i++ {
		A[i] = N - i
	}
	A[0] = 0
	return
}
func RGA(N int) (A []int) {
	rand.Seed(time.Now().UnixNano())

	A = make([]int, 10)
	for i := 0; i < N; i++ {
		A[i] = rand.Intn(N * N)
	}
	return
}

func isHeap(A []int) bool {
	size := len(A)
	for i := 0; i < size; i++ {
		left := 2*i + 1
		right := 2*i + 1
		if left < size && A[left] > A[i] {
			return false
		}
		if right < size && A[right] > A[i] {
			return false
		}
	}
	return true
}

func printTree(A []int) {
	var (
		currentHeight      = 0
		startOfCurrentLine = 0
		height             = int(math.Ceil(math.Log2(float64(len(A)) + 0.5)))
	)
	for i := 0; i < len(A); i++ {
		if i == startOfCurrentLine {
			jstring := make([]string, height-currentHeight)
			for j := 0; j < height-currentHeight; j++ {
				jstring[j] = " "
			}
			currentHeight++
			fmt.Printf("\n%s", strings.Join(jstring, ""))
			startOfCurrentLine = 2*startOfCurrentLine + 1
		}
		fmt.Printf("%d ", A[i])
	}
	fmt.Println("\n")
}

func main() {
	count := 100
	for i := 0; i < count; i++ {
		A := RGA(10)
		//printTree(A)
		buildMaxHeap(A)
		fmt.Println(isHeap(A))
		//printTree(A)
	}
}

6.3-1

略

6.3-2

我们的算法是基于上一节的 Max-Heapify 基础之上的, 即: 对每一个结节做 Max-Heapify 的时候, 需要他的子树已经是最大堆了. 自上而下不满足这个前提条件.

6.3-3

这个是为了证明建堆的时间复杂度是O(n) , 先不证了, 略

15 Dec, 2018
算法导论笔记 6.2 章 - 维护堆的性质
6.2-1

略

6.2-2

略

6.2-3

会停止比较, 不进入递归, 直接返回

6.2-4

因为 left 和 right 都大于 heap-size , 所以不会进去递归, 直接返回了

6.2-5
```
func maxHeapify(A []int, i int) {
	var (
		size  = len(A)
		left  int
		right int
		max   int
	)

	for {
		left = 2*i + 1
		right = 2*i + 2
		max = i

		if left < size && A[i] < A[left] {
			max = left
		}
		if right < size && A[max] < A[right] {
			max = right
		}

		if max == i {
			return
		}
		A[i], A[max] = A[max], A[i]
		i = max
	}
}
```
6.2-6

对于已经倒排排序的数组A, 把A[-1]提到最前面, 这个时候, max_heapify 的运行时间就是 ln(n), 像 [1,9,8,7,6,5,4,3,2]
12 Dec, 2018
算法导论第6章堆
写在最前
1. 节点A的高度 h 的定义是, A到叶子节点的边的个数. 所以 1,2,3 这个堆的高度是1
2. 证明 i 的子节点是 2i+1 和 2i+2 , 可以用数据归纳法证明. 如果对于 i 成立, 那么 i+1 的子节点是 2i+2+1, 2i+2+2 , 所以对 i+1 也成立. 所以 i 的父节点是 floor(i/2)
6.1-1

先来计算高度为 h 的完全二叉树, 元素个数为多少.

第 i 层的元素个数是 2**(i-1) , 设总元素个数 S = 1 + 2 + 4 + ... + 2**(n-1)

2 * S = 2 + 4 + ... + 2**n

S= 2S-S= 2**n-1

因为高度 h=n-1, 所以高度为 h 的堆中, 元素最多是 2**(h+1) - 1 个, 最少是 2**h 个

6.1-2

由 6.1-1 可知, 2**h <= n <= 2**(h+1) - 1 => h <= ln(n) < h+1 => h<=ln(n) && h > ln(n)-1 , 所以 h = ln(n).floor

6.1-3

略吧

6.1-4

叶子结点上

6.1-5

是的, 因为满足定义 A[parent(i)] >= A[i]

6.1-6

不是 6 < 5

6.1-7

i 的父节点是 floor(i/2), 所以从 floor(i/2)+1 的节点都是没有子节点的, 也就是叶子节点

背景

最初讨论后的规划

如何在现有的基础(单分支)上解决这个问题

会后讨论结果(实践后又有变化):

改动

增加relese 分支

保留 master

目前实践

2020-03-30 补充

参考资料:

第一个问题

第二个问题

废话写在最前

对ZooKeeper认证与权限控制目的

配置步骤

配置 ZK 的认证

zoo.cfg 配置

quorum.auth.enableSasl=true

quorum.auth.learnerRequireSasl=true

quorum.auth.serverRequireSasl=true

quorum.auth.learner.loginContext=QuorumLearner

quorum.auth.server.loginContext=QuorumServer

quorum.cnxn.threads.size=20

bin/zkEnv.sh 添加 jvm 选项

JAAS 配置

打开 Client-to-Server authentication

Kafka 需要的配置

打开开关

JVM选项中配置JAAS配置文件路径信息

配置 JAAS

6.3-1

6.3-2

6.3-3

6.2-1

6.2-2

6.2-3

6.2-4

6.2-5

6.2-6

6.1-1

6.1-2

6.1-3

6.1-4

6.1-5

6.1-6

6.1-7