Skip to content

Go如何测试标准库

部分的Go的标准库由于使用了internal这个包,所以,没有办法进行测试。
而之前在写adler32时,我用了个投机的方法,先测试完,再进行移植,其实不算完整的冒烟,毕竟可能会有什么移植的代码搞错了。
每次都跑./all.bash太费时间。所以到底怎么单独测试标准库呢?

直到我发现了Go: Testing Standard Library Changes

# Path that the Go repo was cloned to.
$ GODEV=$HOME/godev
# Move into the src directory.
$ cd $GODEV/src
# Set the bootstrap Go install to the current installation.
$ GOROOT_BOOTSTRAP=$(go env GOROOT) ./make.bash
[output omitted]
# Use the newly built toolchain to run the test.
$ $GODEV/bin/go test -v go/types
[output truncated]
=== RUN ExampleInfo
--- PASS: ExampleInfo (0.00s)
PASS
ok go/types 7.129s

其实就是Go怎么判断自己能不能用internal的标准就是前缀路径是不是一致的(太暴力了)。
这样编译的话,你开发的环境路径就和Go工具链的路径一致了~

使用Go制作USB温控风扇

项目地址

本文将涉及

  • 基础电路
  • Go交叉编译(cross compile)
  • USB原理和驱动
  • Wireshark抓USB包
  • 一些吐槽

前因

最近发现路由器的温度在负载高时(Time Machine备份时),常常能飙升到80C,于是我从X宝上买了一对5V USB电压驱动的风扇。
发现降温效果不错,能降到55C,但是负载低时,路由器的温度才65C左右,又不需要风扇了。再到X宝上搜索USB可程控的开关或者风扇,发现压根没有,于是萌生了自己做一个Go版本的温控风扇的想法,当然最好是不用拆机,直接用USB供电.

说干就干!原理其实很简单,就是USB控制一个开关。电路图如下:

蛋疼的现实

上X宝,随便买了一个USB 免驱 继电器

USB免驱继电器

电路部分不难~

结果货到的时候发现,对方没有开源技术资料,所谓免驱,只是这个继电器用的是USB HID(就是驱动鼠标键盘)的接口。而真正的控制驱动代码是Windows版的……还是闭源的DLL……
页面上还有一个明显是复制粘贴来的公告……

我们提供应用程序和C++二次开发库代码,没有VB代码,但是都是dll文件,所以能否在VB上操作,需要熟悉VB的朋友自己尝试。由于工程师出深造,没法给您提供技术支持,所以拍前请先看资料
里面是产品所有的资料,已经很详细了,看是否有您需要的东西再考虑购买,给您带来不便请多包涵。

坑爹呢!

经过一番搜索,发现被坑的不止我一个,国外的哥们都被Ebay上的这个所谓外贸产品(共同点是USB ID 16c0:05df)坑惨了,还专门写了一个项目USB Relay HID,来驱动这些免驱的USB继电器。

这下好了,我看了一下实现,都是通过libusb这个库来控制的,虽然驱动代码有了,但是是C写的,我希望用Go实现,(毕竟C苦手……

又搜索了一圈,各种Go的binding都是用了cgo,这是我一个Go爱好者无法容忍的。

要就要上纯Go!

幸好,来自乌克兰的叫Serge Zaitsev的小哥写了不太完整的纯Go的HID驱动,说只支持x86 Linux,不过没差,大不了我移植一下嘛~

更蛋疼的实现过程

我试着直接用我的Mac交叉编译一次HID驱动里的例子代码

env GOARM=5 GOARCH=arm GOOS=linux go build example/main.go

丢在路由器上,能跑!

注意一下,RT-AC68U虽然是ARMv7的,但是丫竟然没有FPU,所以直接使用GOARM=7的话,会报错

Illegal instruction

解决完编译的问题,现在来看看驱动。USB Relay HID项目好在代码量不大。最核心的代码是这段开关控制代码

if ( relaynum < 0 && (-relaynum) <= 8 ) {
mask = 0xFF;
cmd2 = 0;
if (is_on) {
cmd1 = 0xFE;
maskval = (unsigned char)( (1U << (-relaynum)) - 1 );
} else {
cmd1 = 0xFC;
maskval = 0;
}
} else {
if ( relaynum <= 0 || relaynum > 8 ) {
printerr("Relay number must be 1-8\n");
return 1;
}
mask = (unsigned char)(1U << (relaynum-1));
cmd2 = (unsigned char)relaynum;
if (is_on) {
cmd1 = 0xFF;
maskval = mask;
} else {
cmd1 = 0xFD;
maskval = 0;
}
}

啊哈!原来只需要设置一下控制位,并发送set_feature就可以开关继电器,例如打开1号继电器,只需要传递

[]byte{0, 0xff, 0x1}

我迅速地开始抄袭(误 对应的Go代码,并不能工作……
到底哪里出错了,我开始一一核对代码,还是不能理解这USB驱动代码,于是我开始找USB相关资料,看看到底这是个什么玩意。
结果在知乎上一个解释让我豁然开朗,原帖是纯文字,我觉得转化成图例应该更形象,左边是服务端开发常用的术语,右边是USB对应的名词

物理设备 -> Device
应用程序 -> Interface
应用端口 -> Endpoint

USB in nutshell 第6章中,我查询到了对应的控制数据包定义。

对应起来就是

  • bmRequestType指的是请求类型+请求对象+数据方向的一个bit-map,相当于一个UDP/IP包
  • bmRequest,相当于调用什么RPC接口
  • wValue,wIndex, wLength这些就相当于数据包的内容。

修改好代码后,还是没办法控制,于是我想到了Wireshark抓USB包的方法,来对比我的驱动代码和USB HID RELAY之间的区别。
编译好usb hid relay后
tcpdump -i usbmon -w cap.pcap
对比两个发出的数据,发现原来没有前面的0(满头黑线中= =|||

注意看最后一行,有个Data Fragment,是驱动的关键,仿造这个数据包,就驱动开关了。

但是还有一个问题,就是获取开关的状态。我试着发送GetReport指令,但是没有任何返回。再次抓包对比,发现原来这个USB驱动用的不是标准接口……

不标准的USB请求

而Go的驱动不支持不标准的请求,也就是我说不完整的原因,碰上不标准的厂商,只能抓瞎。于是我开始改造,发现很简单,只需要把原来私有的方法export出来就可以了。

+func (hid *usbDevice) Ctrl(rtype, req, val, index int, data []byte, t int) (int, error) {
+ return hid.ctrl(rtype, req, val, index, data, t)
+}

这样就可以达到自定义消息的目的了。

var dev *Relay
dev.Ctrl(0xa0, 0x01, 3<<8, 0x0, buf, 1000)

最后测试一下,完美!

Golang Control USB Relay

Build a thermal control fan by Go

Github

Why

I just bought a Asus router that sometimes it is overheat like 80C. For cooling, I bought a pair of USB powered fan and it works well, however, it’s waste of energy while CPU is idle. So I think it’s a good idea to use USB control a relay that switch on fan while CPU is hot and turn it off while it’s idle.

Here is the circle diagram, pretty simple.

bad USB driver

I bought a usb hid relay from Taobao( Chinese version of Ebay) for only $2.5

USB HID relay

Putting them together.

But when I try to coding, the vendor didn’t has any kind of opensource code nor protocol to drive this relay 🙁

WTF

After painstacking search on Google, I found a project named USB Relay HID, which is same device and implment by … well … C

I love Golang, so why not try it in Golang?

Lucky Serge Zaitsev has already written a pure USB HID driver, which only support Linux and it’s fine to me.

First, I use my Mac to do the cross compile the example code from the usb hid driver project, and scp to my router and it works!

env GOARM=5 GOARCH=arm GOOS=linux go build example/main.go

Some note, although RT-AC68U is based on ARMv7 but it don’t have FPU, so don’t try to use GOARM=7 or you will get this error:

Illegal instruction

Now we had done with compiling, let’s take a look at the driver code. Fortunately the code is simple and easy to understand, here is the core control code

if ( relaynum < 0 && (-relaynum) <= 8 ) {
mask = 0xFF;
cmd2 = 0;
if (is_on) {
cmd1 = 0xFE;
maskval = (unsigned char)( (1U << (-relaynum)) - 1 );
} else {
cmd1 = 0xFC;
maskval = 0;
}
} else {
if ( relaynum <= 0 || relaynum > 8 ) {
printerr("Relay number must be 1-8\n");
return 1;
}
mask = (unsigned char)(1U << (relaynum-1));
cmd2 = (unsigned char)relaynum;
if (is_on) {
cmd1 = 0xFF;
maskval = mask;
} else {
cmd1 = 0xFD;
maskval = 0;
}
}

After I copied the code, it just not working, what could possibly gone wrong?

I found some definition of USB requests at USB in nutshell Chapter 6 , for server engineer like me, I think this is a good analogy below.

Node in the networking -> Device
Application -> Interface
protocol port -> Endpoint

I tried to capture the USB package by Wireshark to see the diffrenece between USB HID RELAY and I own driver.
tcpdump -i usbmon -w cap.pcap

Turns out there is one byte less in the good control request. You can see that at the Data Fragment.

One more thing. Status from relay, I tried to send GetReport request, nothing came back.
I used tcpdump and Wireshark, again.

Non Standrad USB request

Well, this USB relay vendor using a non stadrad request for the reporting feature. So I have to construct a non standrad request too.

var dev *Relay
dev.Ctrl(0xa0, 0x01, 3<<8, 0x0, buf, 1000)

Compile, execute it, and it works!

Golang Control USB Relay

3分钟AC68U打造成Time Machine

最近为了100M光纤,一咬牙买了台好点的华硕AC68U路由器。
结果发现这货竟然可以当作Time Machine用,原来想过用树莓派做的,结果发现传输速度太慢,只有仅仅1Mb/s,希望这次的AC68U能给力点。

因为常见的fat32不支持4G以上的文件,NTFS系统苹果又没有自带的,Linux支持也不好,所以我就准备用AC68U格式化磁盘。

首先是登入路由器,“系统管理 -> 系统设置”

把ssh选项打开,把自己的公钥,注意是公钥!文件名以.pub结尾的!把里面的内容粘贴到上图的黑框中,然后应用设置。

接着登入路由器

ssh [email protected]

注意是用户名是admin,不是root

把移动硬盘接上。格式化成ext3,为啥是sda,因为我只接上了一个磁盘。

mkfs.ext3 /dev/sda

等格式化完成后,就可以愉快地使用咯,点击“USB 相关应用 -> Time Machine“,开启并选定我们刚才格式化好的磁盘。

打开Mac里的Time Machine,注意这里链接时需要的账号密码是路由器的管理员账号密码 ( = =)

这样就开始自动备份了~

Go零消耗debug log技巧

tL;DR, 本文末尾提供零消耗的日志代码,最高性能提升60000%。

看到题目,有人肯定会问,官方的log模块不好么?
Debug Log一般很长,在生产环境还输出的话,也很难找。
再者,log的消耗是比较大的,特别是需要打印行号时。

https://golang.org/src/log/log.go#L158

if l.flag&(Lshortfile|Llongfile) != 0 {
// Release lock while getting caller info - it's expensive.
l.mu.Unlock()
var ok bool
_, file, line, ok = runtime.Caller(calldepth)
if !ok {
file = "???"
line = 0
}
l.mu.Lock()
}

因为需要调用runtime.Caller,这样性能就有较多的损耗。
简单的benchmark,可以发现慢50%。

func BenchmarkWithLine(b *testing.B) {
logger := log.New(ioutil.Discard, "", log.Llongfile|log.LstdFlags)
tf := strings.Repeat("abcde", 1000)
b.ResetTimer()
for i := 0; i < b.N; i++ {
logger.Print(tf)
}
}
// BenchmarkWithLine-4 500000 2806 ns/op
// BenchmarkWithoutLine-4 1000000 1754 ns/op

虽然,log的性能不差,仅需要1us就能进行一次,但如果在代码中有大量的debug日志,这个损耗累积起来,那也是相当惊人的了。

那么,在生产环境,能不能不执行log语句呢?
可以的,例如

const Dev = false
func BenchmarkConst(b *testing.B) {
logger := log.New(ioutil.Discard, "", log.LstdFlags)
tf := strings.Repeat("abcde", 1000)
b.ResetTimer()
for i := 0; i < b.N; i++ {
if Dev {
logger.Print(tf)
}
}
}
// BenchmarkConst-4 2000000000 0.29 ns/op

go tool objdump查看生成的二进制文件

 log_test.go:36 0x4efc32 48890424 MOVQ AX, 0(SP)
log_test.go:36 0x4efc36 e815d4fbff CALL testing.(*B).ResetTimer(SB)
log_test.go:36 0x4efc3b 488b842480000000 MOVQ 0x80(SP), AX
log_test.go:36 0x4efc43 31c9 XORL CX, CX
log_test.go:38 0x4efc45 eb03 JMP 0x4efc4a
log_test.go:38 0x4efc47 48ffc1 INCQ CX
log_test.go:38 0x4efc4a 488b90f0000000 MOVQ 0xf0(AX), DX
log_test.go:38 0x4efc51 4839d1 CMPQ DX, CX
log_test.go:38 0x4efc54 7cf1 JL 0x4efc47
log_test.go:43 0x4efc56 488b6c2470 MOVQ 0x70(SP), BP
log_test.go:43 0x4efc5b 4883c478 ADDQ $0x78, SP
log_test.go:43 0x4efc5f c3 RET

可以看出,ResetTimer之后,仅仅是跑了个空的for循环,这是因为编译器发现if语句永远不成立,所以不编译这一段了(如果Dev是var值,那么还是会对比一下,而不是没有语句生成),不过这个方法需要每次debug时都要改代码。不想改代码可以用go build -ldflags -X方法, 但这个仅仅支持字符串,特别麻烦。

所以有没有更好的解决方案呢?有的,使用build tags
下面是例子,一共三个文件:

log.go

package main
func main() {
Debug("it's expensive")
if Dev {
fmt.Println("we are in develop mode")
}
}

log_debug.go

//+build debug
package main
import (
"fmt"
)
const Dev = true
func Debug(a ...interface{}) {
fmt.Println(a...)
}

log_release.go

//+build !debug
package main
const Dev = false
func Debug(a ...interface{}) {}

debug和release最大的差别就在文件头的//+build !debug, 意思是告诉编译器,如果有debug这个tags,那么编译的时候就略过这个文件。
比如你运行go build -tags "debug" && ./main就会输出,不设定的话,就什么都不输出。

再用go tool objdump 查看生成的可执行文件,跟之前的if Dev效果相同,压根不生成语句。这样就不用每次都改代码了来debug了,是不是很赞啊?

对于Debug函数,由于Go的函数是first class,所以Call function不可避免,不过性能损失基本上为零了。

package main
import "testing"
var a = strings.Repeat("abcde", 1024)
func BenchmarkDebug(b *testing.B) {
for i := 0; i < b.N; i++ {
Debug(a)
}
}
go test -bench=.
BenchmarkDebug-4 500000000 3.27 ns/op
go test -bench=. -tags debug
BenchmarkDebug-4 10000000 146 ns/op

总结一下,如果极度要求性能,尽量使用if Dev这种判断模式,如果要求不高,可以使用Debug函数的方法。

Yaml To Go

项目地址:Yaml-To-Go

最近工作需要把yaml配置改成Go的对象,我知道有个json-to-go,但是没有发现yaml-to-go,所以就自己搞了一套。

其实原理很简单,主要是把原来的jsonToGo函数里的解析函数全部替换成yaml的解析器。
虽然简单,但是实际上移植的时候,发现js的库太复杂了……npm 不想安装,怎么办?

Heavy NPM

可以看项目里的dist文件夹,里面会有有编译好的文件。
这样就可以用老办法,直接用script标签载入了。

两行开启Go http quic

QUIC,简单来说,就是使用UDP的传输协议,根据Google自己的报告,速度可以加快30%。
主要优点有:

1. 快速建立链接(不用3次握手和TLS4次握手)
2. 多路复用
3. 改进的流控
4. 快速SSL/TLS握手
5. 适合移动用户访问

quic-layer

这么好的性能,当然要赶紧用Go试试看。

https://github.com/lucas-clemente/quic-go

示例中的代码也很简单。

http.Handle("/", http.FileServer(http.Dir(wwwDir)))
h2quic.ListenAndServeQUIC("localhost:4242", "/path/to/cert/chain.pem", "/path/to/privkey.pem", nil)

不过在实践里,还是碰到了2个坑。

TLS配置

因为我的服务是一个http.Handler, 所以quic需要重新配置TLSconfig,否则就会报错。
下面是示例代码

quic := &h2quic.Server{Server: server}
quic.TLSConfig = &tls.Config{}
quic.TLSConfig.GetCertificate = getCertificate
pln, err := net.ListenPacket("udp", cfg.Listen)
if err != nil {
log.Fatal(err)
}
log.Print("listen quic on udp:%s", cfg.Listen)
go quic.Serve(pln)

HEADER设置

成功启用后,Chrome中的SPDY插件并没有出现绿色的标志,还是继续使用HTTP2,经过查找后,发现Google在自家的header中添加了

 writer.ResponseWriter.Header().Add("alt-svc", `quic=":443"; ma=2592000; v="38,37,36"`)

其中

  • ma是过期时间,单位是秒
  • v是指支持的quic版本
  • alt-svc是alternative-service的缩写
  • quic中是quic的端口,我指定了443

最后通过在chrome地址栏中输入

chrome://net-internals/#quic

quic-demo

Go汇编实战的坑

为啥写

Go的汇编一直是我感兴趣的地方,为了验证之前所学的汇编知识和好玩 ,我决定往Go官方提交一个性能patch。
所以到官方的标准库里搜了一圈,发现adler32并没有硬件加速的实现,而Intel已经公布了相关的SSE加速实现
https://github.com/01org/isa-l/

所以我决定把Intel的抄过来,结果不停地掉坑和爬出来,终于提交了patch(撒花)

https://go-review.googlesource.com/c/51850

希望在Go 1.10发布的时候能进入官方源:)

  1. 写法的区别
  2. Go汇编不支持
  3. 难以调试
  4. 内存越界与LEA
  5. 向官方提交代码需要注意的地方,保证Change ID一致

坑一:Intel和AT&T的写法的区别

Intel写法是:
opcode destination source

AT&T 也就是Go官方汇编语言的写法正好是反过来的:
opcode destination source

抄代码的时候有点绕

坑二 Go汇编不支持:

Go的维护者们对于新添加汇编opcode一直是很保守的,比如2001年前后就有的SSE2 里的PSHLLW()竟然不支持(= =||)。
所以得自己填BYTE,比如官方文档中的MOVQ用BYTE方式编写 https://golang.org/doc/asm

BYTE $0x0f; BYTE $0x6f; BYTE $0x00 // MOVQ (AX), M0

但这里就有一个坑,比如PSHLLD和PSHRQ的Opcode是一样的……只是按/r 寄存器类型进行区别。需要注意

坑三:调试困难

一般代码测试时,都可以直接输出日志,帮助定位问题,但是汇编不行,所以我是通过把需要的值放入某个不用的寄存器, 例如

#define debug R15
// min(a, b int) int
TEXT min(SB), NOSPLIT, $0

在需要的时候,提前把函数返回

MOVQ debug, ret+16(FP)
RET

当然应该有更好的方法,可以把所有寄存器打印出来,不过这个方法够我自己调试用了。

坑四:内存越界与LEA

一般程序中都是指针,或者直接结构体。不过,汇编这里回归本真,只有内存地址和寄存器。所以一定要小心访问数据的边界和跳转的内存地址。
这里学到了一个LEA的用法,地址计算器,把内存地址到目标寄存器里。

LEAQ 0(data)(size*1), end

具体用法

  • 0: 写死的偏移量
  • data: 偏移值
  • size: 动态偏移量,可以用乘法

坑五:

提交代码到gerrit要保持Change ID相同,要不然算一个新的Change。

附录:opcode坑

  • MOVOU: O=oct, U=unaligned, 指的是八个word,即128位,用于XXM寄存器的移动。
  • TESTQ: 对比值,并影响FLAG
  • DIVL:低位除,如果高位有数据就会出错

资料:
Go官方介绍: https://golang.org/doc/asm

[What if] 如果全国人在同一个微信群或qq群,会看到些什么内容?

本文已授权腾讯公司转载:https://www.zhihu.com/question/293021546

简单的说,什么都看不到。

为了简化,我们只说微信群。

红包

根据2014年腾讯的公开数据 1

微信和WeChat月活跃账户4.68亿,90亿条日均消息

如果全国人民在同一个群里说话,每天就是
14E8 x (90 / 4.68) = 2.6E10 条

考虑到大家一般除了睡觉8小时外,而且仅仅匀速发送的话,那就是
(14E8 x (90 / 4.68))/(86400 - 8x3600) =

467414条每秒

目前主频最高的手机CPU,高通骁龙805(APQ8084)2 有2.7GHz的处理能力,一共是4核,如不计算操作系统、显示刷新、网络IO等CPU操作的话
每条信息能分配到 2.7GHz x 4 / 467414 =

23KHz

仅仅相当于生产于1951年的第一台真空管计算机Whirlwind 3的计算能力,自然手机的CPU是处理不了这么大的数据量的。
幸好IT界有个摩尔定律,每18个月CPU性能就能翻倍(或者价钱是一半),假设等到了2025摩尔定律失效时,我们的手机应该有
2e((2025-2017)x12/18) x 2.7 = 108Ghz

看起来不错嘛,不过每条消息才能消费108GHz x4 / 467414 =

931KHz

差不多是1972年的Intel 8008 800KHz4 的水平,结果就是你等了7年,还是进不了这个全国群抢一个红包

Improve

假设我们每个人都获得了能处理消息能力的手机 5(比如说全球超算第一名的太湖之光,1千万个CPU核心)来帮忙处理微信群。
由于微信没有公布数据,因此我们只好假设平均每条消息有10个汉字,这大概相当于30 byte,算上应用层会加上一定的控制字符,再加上TCP/IP网络层的数据消耗大概是74 byte,取个整,平均每条消息有100 byte。
这时每秒数据流量是(100x8)x467414 =

373Mbps

理论上的4G网络,能支持1000Mbps6,但别忘了,是全国人民在同一个群里,很快你周围的人也接近了这个流量,这使得你所在的基站不堪重负,陷入瘫痪。
为了避免网络瘫痪导致你抢不到红包或者看群消息,你需要搬到一个周围没有人的基站,因此人口密度最低的西藏省是个不错的选择。
不过运营商的日子就不好过了,因为全国上下的流量达到了惊人的每秒373Mbps x 14E8 = 5.2E17 bps =

52 Pbps

相当于全国4月份的移动数据总流量的3%,意味着6分钟就能用完全国一年的流量 7,或者把52PB数据用2T 3.5英寸硬盘装起来,然后叠起来,有130m高

52pbs.png

当然,我相信我们抠门的国有运营商肯定会砸下重金为你建设全世界最大的宽带网络,毕竟是为了国家建设全国群,同时,好让你快乐地抢红包。

不过,接下来该花钱的就不是国有企业——腾讯。

为了处理每个人的373Mbps流量,现有的万兆交换机仅仅能支撑26个人,也就是说腾讯至少需要1346万台4口万兆交换机,目前华为4口万兆交换机售价是3927元每台,一共需要支出

1346x10000x3927 = 52,857,420,000 元

一台便宜的2U服务器则需要10000元

1346x10000x10000 = 134,600,000,000 元

仅仅这两项就相当于腾讯CEO马化腾持有的股票 9 市值10

而仅仅是把这些2U服务器叠起来就有88.9x1.346E7=1196594000mm

1196km

国际空间站的轨道高度才340km

2u_server.png

这下,你终于可以愉快地进了群。

但你惊讶地发现,屏幕上除了绿色,什么都没有……

这是因为你的眼睛没办法接收这么快的数据。
而人眼的视觉暂留时间是100-400ms11 ,我们这个群消息停留的时间只有0.002ms,相比之下,电影、电视有41ms。
因此你还没来得及看清消息,它就已经消失了,最后只留下一团绿色的色块在屏幕的正中央。

hot_phone.png

Sntpd开发日志2 Marzullo算法

实现了学生T分布之后,有趣的是,在集群中使用时发现sntpd的偏移量变化非常有规律
student-t-offset

最后我确认是两个问题引起的:

  1. s.poll 的区间设置得过长,时钟一旦偏移,要花很长的时间去校正
  2. 由于95%置信区间的设定,导致时钟源总是变化,因此总有跳变

读了一次论文之后,发现,DLM博士早就知道这事,而且在论文中也指出了这种只使用offset的方法是他们的第一版算法……但是发现由于时钟dispersion(误差)的存在,导致时钟offset不一定准确,会丢掉误差的数值,所以他们使用了Marzullo算法。

https://en.wikipedia.org/wiki/Marzullo%27s_algorithm

marzullo-example-1

看着很复杂,但是主要思想却相当简单,就是先假设所有的区间都是“好区间”,把区间值按大小排序,得出最多的夹杂着最少最大值的区间,然后在反向求最多的夹杂着最少最小值的区间。如果得不出,就缩减窗口项,好区间=所有区间减一,直到找到为止。

以下是我的Go实现

# iset 即区间拆分之后的数值
func (s *Service) marzullo(iset []Interset) (surviors []*Peer) {
sort.Sort(byOffset(iset))
nlist := len(iset) / 2
nl2 := len(iset)
var n int
low := time.Hour
high := -time.Hour
for allow := 0; 2*allow < nlist; allow++ {
n = 0
for _, set := range iset {
low = set.val
n -= set.typE
if n >= nlist-allow {
break
}
}
n = 0
for j := nl2 - 1; j > 0; j-- {
high = iset[j].val
n += iset[j].typE
if n >= nlist-allow {
break
}
}
if high > low {
break
}
}
var p *Peer
for i := 0; i < len(iset); i += 2 {
p = iset[i].peer
if high <= low || p.offset+p.rootDistance < low || p.offset-p.rootDistance > high {
continue
}
surviors = append(surviors, p)
}
return
}