Đã đăng vào thg 2 7, 2023 4:59 SA 8 phút đọc

3.1K

ID generator Snowflake, Sonyflake và NanoId

Giới thiệu

Trong bài viết này mình xin giới thiệu mọi người những thuật toán, thư viện để xây dựng ra ID generator (trình tạo ID) mà mình thường sử dụng để giải quyết các vấn đề này.

ID generator (trình tạo ID)

Trước tiên chắc chán các bạn đã hiểu về ID generator là gì, theo bé ChatGPT thì

An ID generator is a tool or software that creates unique identification numbers for entities such as individuals, products, or transactions. These IDs are used to efficiently identify and track items in databases and systems. Some common types of ID generators include sequential ID generators, random ID generators, and hash-based ID generators.

Việt sub

ID generator là một công cụ hoặc phần mềm tạo ra các số định danh duy nhất cho các đối tượng như cá nhân, sản phẩm hoặc giao dịch. Các ID này được sử dụng để xác định và theo dõi một cách hiệu quả các mục trong cơ sở dữ liệu và hệ thống. Một số loại ID generator phổ biến bao gồm ID generator tuần tự, ID generator ngẫu nhiên và ID generator dựa trên băm.

Có 3 loại ID generator phổ biến nhất hiện nay là

ID generator tuần tự : phổ biến nhất các bạn thường thấy là ID tăng dần trong các Database(Mysql, PosgreSql...), sử dụng phương pháp này ưu điểm là id nhìn xinh xắn, luôn đảm bảo được tính duy nhất. Tuy nhiên ngược điểm là các DB thường sử dụng sequence để đếm tăng dần và việc đếm này cần xử lý tuần tự khi gặp lượng request lớn sẽ là yếu điểm không "nhuốt" nổi. Phương pháp này phù hợp cho các hệ thống nhỏ/trung dữ liệu insert vào không quá lớn.
ID generator ngẫu nhiên : phương pháp này sẽ random ra các ký tự/số dựa trên input đầu vào, Tuy nhiên để đảm bảo được ID không trùng thì thường chiều dài kết quả random cần đủ lớn. Thư viện nôi tiếng nhất có mọi dev đều nghe qua có lẽ là UUID. trong bài này mình sẽ giới thiệu các bạn một thư viện khác nhẹ hơn, nhanh hơn và xịn xò hơn.
ID generator dựa trên băm(Hash) : phương pháp này xử dụng thuật toán băn bằng cách đưa dữ liệu từ nhiều nguồn, có thể là email, id server, random chuỗi.... Phương pháp kết hợp với các thuật toán khác có thể tạo ra được cách ID với độ trùng lặp cực thấp, thường được sử dụng trong các ứng dụng phân tán. bài viết này chúng ta sẽ tìm hiểu về thuật toán Snowflake của Twitter.

ID generator ngẫu nhiên

Trong bài viết này mình sử dụng Go để làm demo nhé

Theo nhà phát triển thì NanoId còn nhanh hơn cả UUID

"Nano ID is quite comparable to UUID v4 (random-based). It has a similar number of random bits in the ID (126 in Nano ID and 122 in UUID), so it has a similar collision probability -- for there to be a one in a billion chance of duplication, 103 trillion version 4 IDs must be generated"

Theo NanoID thì nếu bạn sử dụng chế độ Standard với chiều dài 21 ký tự thì mỗi 1.000.000 (1 triệu) reuquest mỗi giấy thì bạn cần hơn 40.000 năm để có 1% tỉ lệ trùng lặp.

Dưới đây là hình về tính toán khả năng trùng lặp của một tool khác của NanoID. ảo ha =))). Screenshot 2023-02-06 at 16.47.00.png

thường nếu bạn chỉ muốn dùng số không thôi từ khả năng trùng sẽ tăng lên khá nhiều, tuy nhiên nếu bạn cần sinh ID cho 1 tỉ request mỗi giây thi quên NanoID đi, còn vài chục nghìn thâm trí vài trăn nghìn thì NanoID vẫn rất tuyệt.

Ví dụ bằng Golang nhen.

func main() {

	canonicID, err := nanoid.Standard(21)
	if err != nil {
		panic(err)
	}
	id1 := canonicID()
	log.Printf("ID 1: %s", id1)
	// Makes sense to use CustomASCII since 0-9 is ASCII.
	decenaryID, err := nanoid.CustomASCII("0123456789", 12)
	if err != nil {
		panic(err)
	}
	id2 := decenaryID()
	log.Printf("ID 2: %s", id2)
}

và đây là kết quả Screenshot 2023-02-07 at 09.35.45.png

log.Printf("time start: %s", time.Now())
	for i := 0; i < 10000000; i++ {
		nanoid.Standard(21)
	}
	log.Printf("end start: %s", time.Now())

mình có thử thêm genera ra 10 triệu mã dài 21 ký tự và hết khoảng 31 giây. với việc xử lý tuần tự thì mình thấy tốc độ rất ổn.

OK! giờ test cường độ cao xem có bị trùng không nào.

Case 1: tạo tuần từ 10 triệu mã Screenshot 2023-02-07 at 09.41.19.png

m := make(map[string]int)
	log.Printf("time start: %s", time.Now())
	for i := 0; i < 10000000; i++ {
		canonicID, err := nanoid.Standard(21)
		if err != nil {
			panic(err)
		}
		m[canonicID()] = 1
	}
	log.Printf("end start: %s", time.Now())
	log.Printf("total: %d", len(m))

Screenshot 2023-02-07 at 10.22.11.png

Case 2: giả lập 100 request cùng tạo, mỗi request tạo 1000 mã và woww, không phát hiện trùng lặp.

func main() {
	wg := &sync.WaitGroup{}
	wg.Add(1000)
	total := 0
	startTime := time.Now()
	for i := 0; i < 1000; i++ {
		fmt.Println("* create chanel ", i)
		count := make(chan int)
		go Standard(count, wg, &total)
	}
	wg.Wait()
	log.Printf("total: %d", total)
	log.Printf("start time : %s, end time %s", startTime, time.Now())
}

func Standard(ch chan int, wg *sync.WaitGroup, total *int) {
	m := make(map[string]int)
	for i := 0; i < 10000; i++ {
		canonicID, err := nanoid.Standard(21)
		if err != nil {
			panic(err)
		}
		m[canonicID()] = 1
	}
	*total += len(m)
	wg.Done()
	ch <- len(m)
}

Screenshot 2023-02-07 at 10.55.57.png

Case 3: tạo 1 triệu channel, mỗi channel 100 request.
à à, code trển các bạn edit xíu rồi test thử nhé, máy mình không chạy nổi .

Trong một số trường hợp lập trình viên cần một ID có khả năng tăng dần thì trường hợp này NanoID có lẽ sẽ không còn được ưu tiên sử dụng đặc biệt với những hệ thống phân tán sẽ làm bài toán thật sự gian nan, Tuy nhiên xét trường hợp mã ngẫu nhiên NanoID vẫn rất đáng cân nhắc.

Distributed ID generator

như mình đã đều cập ở phần ID generator phía trên, sẽ khá nhiều bất cập nếu dùng bộ tăng dần của DB, đặc biệt với những hệ thống phân tán sẽ làm bài toán thật sự gian nan.

Thuật toán snowflake của Twitter là giải pháp điển hình trong ngữ cảnh này

Mã do thuật toán Snowflale tạo ra với giá trị 64-bit và được chia thành bốn phần:

Không sử dụng bit đầu tiên vì bit này là bit dấu.
timestamp: sử dụng 41 bit để biểu thị timestamp khi nhận được yêu cầu, tính bằng milliseconds.
datacenter_id: 5 chữ số để biểu thị id của trung tâm dữ liệu.
worker_id: 5 chữ số để biểu thị id của server.
sequence_id: cuối cùng là id tăng vòng lặp 12 bit ( tăng từ 0 đến 111111111111 rồi trở về 0).

Với cơ chế này snowfllake có thể tạo ra 2 ^ 12 = 4096 mỗi millisecond hoặc khoảng 4,096 triệu mỗi giây trên mỗi server.
timestamp lưu trữ 41 bits, vì thế theo tính toán, nó sẽ chỉ hoạt động được đến 2039/9/7 23:47:35

timestamp, datacenter_id, worker_id và sequence_id là bốn trường, riêng timestamp và sequence_id được tạo bởi chương trình khi chạy. Còn datacenter_id và worker_id cần lấy trong giai đoạn triển khai và khi chương trình đã được khởi động, nó không thể thay đổi.

Chúng ta vô demo thôi nhé, hôm nay chúng ta lại Golang tiếp nhỉ

lib: https://github.com/bwmarrin/snowflake

func main() {
	n, err := snowflake.NewNode(1)
	if err != nil {
		println(err)
		os.Exit(1)
	}

	for i := 0; i < 10; i++ {
		// tạo ID
		id := n.Generate()
		fmt.Println("id", id)
		fmt.Println(
			"node: ", id.Node(),
			"step: ", id.Step(),
			"time: ", id.Time(),
			"\n",
		)
	}
}

Screenshot 2023-02-07 at 11.41.45.png

ID được tạo ra một cách tuần tự, quá đỉnh phải ko.

Tiếp theo mình giả lập có 4 node, mỗi node có 10 request.

func main() {
	wg := &sync.WaitGroup{}
	wg.Add(4)
	for i := 0; i < 4; i++ {
		fmt.Println("* create chanel ", i)
		go gen(i, wg)

	}
	wg.Wait()
}
func gen(node int, wg *sync.WaitGroup) {
	n, err := snowflake.NewNode(int64(node))
	if err != nil {
		println(err)
		os.Exit(1)
	}
	for i := 0; i < 10; i++ {
		// tạo ID
		id := n.Generate()
		fmt.Println(
			"id: ", id,
			"node: ", id.Node(),
			"step: ", id.Step(),
			"time: ", id.Time(),
			"\n",
		)
	}
	wg.Done()
}

bạn có thể xem hình kiểm tra kết quả hoặc coppy code về thử nhé

Screenshot 2023-02-07 at 11.46.12.png

và đương nhiên ngoài việc sử dụng bạn còn có thể Custom lại vài thứ cho phù hợp như Epoch, NodeBits, StepBits...

Nhưng 2039 thì có quá ngắn với bạn không? nếu ngắn quá thì Sonyflake là giải pháp thay thế, Sonyflake có thiết kế rất giống Snowflake, tuy nhiên khác ở cách phân bố bits. Thời gian ở đây chỉ sử dụng 39 bit, nhưng đơn vị thời gian trở thành 10ms. Về mặt lý thuyết, nó dài hơn thời gian của snowflake chuẩn đến 41 bit (174 năm).

Sequence ID của Sonyflake tương đồng với Snowflake còn Machine ID là id của Node. Sự khác biệt giữa sonyflake là các tham số cấu hình trong quá trình khởi động (xem thêm tại: https://github.com/sony/sonyflake)