局部敏感哈希介绍

传统的Hash当源数据有些许的变化的时候生成的哈希值差异也非常的大, 比如:

1
2
3
4
5
6
7
8
9
10
func main() {
s1 := []byte("你好世界")
s2 := []byte("你好,世界")
hash1 := md5.Sum(s1)
hash2 := md5.Sum(s2)
fmt.Println(hex.EncodeToString(hash1[:]))
fmt.Println(hex.EncodeToString(hash2[:]))
}

s1的哈希值是65396ee4aad0b4f17aacd1c6112ee364、s2的哈希值是27444ee2d245c3e8e11ed8b9b035c43b,源数据仅仅是一个逗号的区别,但是哈希值完全不一样。这是我们使用Hash的常见的场景,输出的哈希值经常被称为消息摘要(message digest)或摘要(digest)。

局部敏感哈希(Locality-sensitive hashing, 简称LSH)则不同, LSH则希望相似的源数据计算出来的哈希值越相近越好。
LSH经常用在判重、文章摘要、聚类、相似搜索、近邻查找等场景, 用来减少高维度的数据的维度,相近的数据放在同一个桶中。 比如大规模异常滥用检测:基于局部敏感哈希算法——来自Uber Engineering的实践

阅读全文

创建最小的Go docker 镜像

虽然曾有一些文章介绍了如何创建一个最小的Go Docker镜像,我也曾写过一篇文章,但是随着Go的新的版本的发布, 以及docker本身的进化,有些技巧已经发生了变化, 本文介绍了最新的创建超小的Go镜像的方法。

阅读全文

[译]Go HttpServer 最佳实践

这是 Cloudflare 的 Filippo Valsorda 2016年发表在Gopher Academy的一篇文章, 虽然过去两年了,但是依然很有意义。

先前 crypto/tls 太慢而net/http也很年轻, 所以对于Go web server来说, 通常我们明智的做法把它放在反向代理的后面, 如nginx等,现在不需要了。

在Cloudflare我们最近试验了直接暴漏纯Go的服务作为主机。 Go 1.8的net/httpcrypto/tls 提供了稳定的、高性能并且灵活的功能。

然后,需要做一些调优的工作,本文我们将展示怎么去调优和使web服务器更稳定。

阅读全文

完全静态编译一个Go程序

在Docker化的今天, 我们经常需要静态编译一个Go程序,以便方便放在Docker容器中。 即使你没有引用其它的第三方包,只是在程序中使用了标准库net,你也会发现你编译后的程序依赖glic,这时候你需要glibc-static库,并且静态连接。

不同的Go版本下静态编译方式还有点不同,在go 1.10下, 下面的方式会尽可能做到静态编译:

1
CGO_ENABLED=0 go build -a -ldflags '-extldflags "-static"' .

有一个提案请求给编译加一个static,如果接收了的话也许在将来的go中直接使用static

参考文档

  1. http://blog.wrouesnel.com/articles/Totally%20static%20Go%20builds/
  2. https://github.com/golang/go/issues/9344
  3. https://github.com/golang/go/issues/26492

ldd、objdump、nm、strings、strip等工具

最近在做Docker镜像的时候发现镜像文件非常大,需要找出程序的依赖库,减少程序的大小,所以整理了一下相关的工具。基本上这些工具都在GNU Binutils中。

GNU Binary Utilities或binutils是一整套的编程语言工具程序,用来处理许多格式的目标文件。当前的版本原本由在Cygnus Solutions的程序员以Binary File Descriptor library(libbfd)所撰写。这个工具程序通常搭配GCC、make、和GDB这些程序来使用。

它包含20个左右的工具,本文介绍了我在创建Docker镜像的时候的使用的几种工具。

ldd

ldd不是GNU Binutils工具集中的一个工具,但是却是一个非常有用的工具, 它可以显示程序或者共享库所需的共享库。

例如:

1
2
3
4
5
# ldd main
linux-vdso.so.1 => (0x00007ffc88fd4000)
libpthread.so.0 => /lib64/libpthread.so.0 (0x00007faee13b8000)
libc.so.6 => /lib64/libc.so.6 (0x00007faee0feb000)
/lib64/ld-linux-x86-64.so.2 (0x00007faee15d4000)

依照ldd得手册, 有时候ldd会通过执行程序来获取依赖信息,对于来源不明的程序,执行这些程序可能会带来风险,所以对于来源不明的程序,可以使用objdump来分析。

objdump

onjdump可以显示目标文件的信息,可以通过参数控制要显示的内容。

比如-p可以显示文件头内容, 通过grep可以查看依赖的库。

1
2
3
4
# objdump -p main|grep GLIBC
0x09691a75 0x00 02 GLIBC_2.2.5
0x09691972 0x00 03 GLIBC_2.3.2
0x09691a75 0x00 04 GLIBC_2.2.5

甚至可以查看-T可以查看动态符号表的内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# objdump -T main|grep GLIBC
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.2.5 stderr
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.2.5 fwrite
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.2.5 vfprintf
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.2.5 fputc
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.2.5 abort
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.2.5 pthread_mutex_lock
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.3.2 pthread_cond_wait
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.2.5 pthread_mutex_unlock
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.3.2 pthread_cond_broadcast
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.2.5 pthread_create
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.2.5 nanosleep
0000000000000000 DO *UND* 0000000000000000 GLIBC_2.2.5 pthread_detach
......

nm

nm显示目标文件的符号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# nm go/bin/glide |more
0000000000908680 r andMask
0000000000901d00 r bswapMask
00000000009036c0 r BSWAP_SHUFB_CTL
0000000000b000e0 B bufio.ErrAdvanceTooFar
0000000000b000f0 B bufio.ErrBufferFull
0000000000b00100 B bufio.ErrFinalToken
0000000000b00110 B bufio.ErrInvalidUnreadByte
0000000000b00120 B bufio.ErrInvalidUnreadRune
0000000000b00130 B bufio.ErrNegativeAdvance
0000000000b00140 B bufio.ErrNegativeCount
0000000000b00160 B bufio.errNegativeRead
0000000000b00170 B bufio.errNegativeWrite
0000000000b00150 B bufio.ErrTooLong
00000000004d9140 T bufio.init
0000000000b21120 B bufio.initdone.
00000000004d6510 T bufio.(*Reader).Buffered
00000000004d59d0 T bufio.(*Reader).Discard
00000000004d5590 T bufio.(*Reader).fill
00000000004d57c0 T bufio.(*Reader).Peek
00000000004d5b70 T bufio.(*Reader).Read
......

strings

strings显示文件中的可打印字符。

1
2
3
4
# strings main|grep GLIBC
GLIBC_2.2.5
GLIBC_2.3.2
GLIBC_2.2.5

strip

通过上面的工具,可以分析出文件的依赖库,创建Docker镜像的时候只需把所需的依赖库加进去即可。

如果程序本身比较大,可以将程序压缩,去掉不需要的一些数据, 比如使用strip进行裁剪。

你可以通过参数控制要丢掉的哪些符号。
比如去除符号表和行号信息:

1
strip main

解决 error creating overlay mount to /var/lib/docker/overlay2

最近在centos7.1使用docker运行redis镜像,出现下面的错误:

1
2
/usr/bin/docker-current: Error response from daemon: error creating overlay mount to /var/lib/docker/overlay2/65f3c109fb903539820f84856d2725af784f2f03f95b1f0214e34184e4d61ff7-init/merged: invalid argument.
See '/usr/bin/docker-current run --help'.

在网上搜索一番后,一个可行的方案如下(改变storage driver类型, 禁用selinux):

  1. 停止docker服务
1
systemctl stop docker
  1. 清理镜像
1
rm -rf /var/lib/docker
  1. 修改存储类型
1
vi /etc/sysconfig/docker-storage

把空的DOCKER_STORAGE_OPTIONS参数改为overlay:

1
DOCKER_STORAGE_OPTIONS="--storage-driver overlay"
  1. 禁用selinux
1
vi /etc/sysconfig/docker

去掉option的--selinux-enabled

  1. 启动docker应该就可以了
1
systemctl start docker

方案抄自 Ysssssssssssssss的博客 和 redis的讨论: error creating overlay mount to .../merged: invalid argument., 基本可以确定是启用selinux导致的。

使用 Go 实现快速排序

快速排序(quick sort)号称是二十世纪最伟大的十大算法之一(The Best of the 20th Century: Editors Name Top 10 Algorithms), 但是快速排序也是最不容易实现的排序算法之一 ()。虽然它的原理非常的简单,但实现起来很容易出错。 也曾因为快排导致腥风血雨甚至网站攻击事件。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

分治法:将问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

利用分治法可将快速排序的分为三步:

  • 在数据集之中,选择一个元素作为”基准”(pivot)。
  • 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
  • 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

快速排序平均时间复杂度为O(n log n),最坏情况为O(n2),不稳定排序。

阅读全文

搭建IPFS私有网络

IPFS (InterPlanetary File System) 是一个面向全球的、点对点的分布式版本文件系统。它用基于内容的地址替代基于域名的地址,也就是用户寻找的不是某个地址而是储存在某个地方的内容,不需要验证发送者的身份,而只需要验证内容的哈希,通过这样可以让网页的速度更快、更安全、更健壮、更持久。IPFS表示,IPFS未来将替代HTTP(以及其他的许多东西)。

IPFS 和 BitTorrent 的区别: How does it compare to BitTorrent's Project Maelstrom?

IPFS从根本上改变了用户搜索的方式。通过IPFS,用户搜索的是内容。通过HTTP浏览器搜索文件的时候,首先找到服务器的位置(IP地址),然后使用路径名称在服务器上查找文件。按照这个设计,只有文件所有者可以判断这是否是用户要找的文件。此时,必须保证托管者不会通过移除文件或者关闭服务器而对文件做任何更改。

当文件被添加到IPFS节点上,它得到一个新的名字。这个名字实际上是一个加密哈希,它是从文件内容中被计算出来。通过加密保证该哈希始终只表示该文件的内容。哪怕只在文件中修改一个比特的数据,哈希都会完全不同。

当下一步向IPFS分布式网络询问哈希的时候,它通过使用一个分布式哈希表,可以快速(在一个拥有10,000,000个节点的网络中只需要20跳)地找到拥有数据的节点,从而检索该数据,并使用哈希验证这是否是正确的数据。

不幸的是, IPFS 被了。如果你有幸能翻墙,你可以通过通过下面的命令下载并安装预编译的ipfs工具。

1
2
3
tar xvfz go-ipfs.tar.gz
cd go-ipfs
./install.sh

然后初始化仓库:

1
2
3
4
5
6
7
8
> ipfs init
initializing ipfs node at /Users/jbenet/.go-ipfs
generating 2048-bit RSA keypair...done
peer identity: Qmcpo2iLBikrdf1d6QU6vXuNb6P7hwrbNPW9kLAH8eG67z
to get started, enter:
ipfs cat /ipfs/QmYwAPJzv5CZsnA625s3Xf2nemtYgPpHdWEz79ojWnPbdG/readme

它默认会在你的Home下创建一个.ipfs文件夹。

1
ipfs cat /ipfs/QmYwAPJzv5CZsnA625s3Xf2nemtYgPpHdWEz79ojWnPbdG/readme

查看ipfs网络上的一个文件,正常你可以看到这个文件的内容。

你可以使用ipfs add上传文件,ipfs cat查看文件。当然ipfs包含很多的命令,你可以在 commands 页面查看每个命令。

默认IPFS会通过一些种子连接到IPFS全球网络, 如果你想搭建一个私有的IPFS网络,可以使用本文下面介绍的方法。

阅读全文