April 5, 2019

介绍一下snowflake和rc4

snowflake是twitter公司开源的生成唯一ID的网络服务,具有很强的伸缩性,这里只取用生成唯一ID的算法部分。rc4(Rivest Cipher 4)是一种流加密算法,密钥长度可变,它的加解密使用相同的密钥,因此也属于对称加密算法。

snowflake是twitter公司开源的生成唯一ID的网络服务,具有很强的伸缩性,这里只取用生成唯一ID的算法部分。 rc4(Rivest Cipher 4)是一种流加密算法,密钥长度可变,它的加解密使用相同的密钥,因此也属于对称加密算法。

为啥要介绍这两种算法?

其一,snowflake可以生成唯一ID,而相比与UUIDsnowflake生成的ID更加“好用”,这个放在后面解释。 其二,UUIDsnowflake虽然可以生成唯一ID,但是无法适用于所有场景,譬如说“生成推广码”。生成推广码的时候,希望尽可能短而精,很明显唯一ID都不太短。

snowflake

snowflake的唯一ID是一个64bit的int型数据,相较于UUID来说耗费空间更小,可以更方便的作为数据库主键来索引和排序。

snowflake

生成过程:

  • 置0不用
  • timestamp(41bits)精确到ms。
  • machine-id(10bits)该部分其实由datacenterId和workerId两部分组成,这两部分是在配置文件中指明的。datacenterId(5bits)方便搭建多个生成uid的service,并保证uid不重复。workerId(5bits)是实际server机器的代号,最大到32,同一个datacenter下的workerId是不能重复的。
  • sequence-id(12bits),该id可以表示4096个数字,它是在time相同的情况下,递增该值直到为0,即一个循环结束,此时便只能等到下一个ms到来,一般情况下4096/ms的请求是不太可能出现的,所以足够使用了。

优势和缺陷:

  • 速度快,无依赖,原理和实现简单,也可以根据自己的需求做算法调整
  • 依赖机器时间,如果时间回拨可能导致重复的ID

rc4

RC4加密算法也是一种基于密钥流的加密算法。

首先,rc4根据明文和密钥生成的密钥流,其长度和明文的长度是相等的,也就是说明文的长度是500字节,那么密钥流也是500字节,这也是我们用来生成推广码的原因之一了;其次,rc4是是对称加密完全可以通过密文得到明文,也就是说在生成码的时候把必要信息放在明文中,在使用密文的时候可以不用查库也能得到相关的信息,譬如用户ID,这是原因之二。

使用场景

现在需要生成一种码,短小易记,且唯一,但并不需要大量。

上述的snowflake和UUID都很容易实现唯一,但是短小就不符合要求了。因为并不需要大量生成这种码,因此我们考虑用自增ID + RC4来实现:

package main

import (
	"crypto/rc4"
	"encoding/hex"
	"fmt"
	"log"
)

func main() {
	cipher, err := rc4.NewCipher([]byte("thisiskey"))
	if err != nil {
		log.Fatalf("wrong with NewCipher: %v", err)
	}

	c := map[string]bool{}
	for i := 0; i < 1000; i++ {
		src := []byte(fmt.Sprintf("%7d", i))
		dst := make([]byte, len(src))
		cipher.XORKeyStream(dst, src)
		s := toString(dst) // 密文是不可读的字节流,这里采用hex编码
		println(s)         // 形如:a09def6b6e4797
		c[s] = true
	}

	println(len(c)) # 1000
}

func toString(src []byte) string {
	return hex.EncodeToString(src)
}

参考