Bông tuyết cô độc

Nghe tin Hà  Nội sắp đón cơn gió lạnh đầu mùa (http://vnexpress.net/tin-tuc/thoi-su/mien-bac-sap-don-khong-khi-lanh-3458332.html) mà lòng tôi lại bồi hồi xao xuyến, những cảm xúc tràn về mãnh liệt khi chứng kiến những khung cảnh đượm buồn của tiết trời đông

da771b55-fd45-435e-93c6-11145e16bd76

Nhiều lần thầm nghĩ nếu Hà Nội của tôi bây giờ có tuyết thì sao. Trong cái trời mùa đông lạnh giá mà có cả tuyết nữa để lứa đôi nắm tay nhau đi quanh bờ Hồ. Thật là lãng mãn quá đi

GIFSec.com

Nhưng tôi biết những mong ước đó thật là xa vời. Hà Nội bây giờ chỉ cần có 1 một bông tuyết thôi đã là điều hiếm thấy. Tôi gọi đó là Bông tuyết cô độc. Nghe thật buồn phải không. Một bông tuyết duy nhất tồn tại, cô độc giữa bầu trời Hà NỘi lộng gió.

Vâng đó là điều tôi muốn nói về chủ đề trong bài viết hôm nay chính là thuật toán SNOWFLAKE (bông tuyết) dùng cho việc sinh ID duy nhất (cô độc) trong các hệ thống phân tán :))

snowflakes

SNOWFLAKE là cái gì?

SNOWFLAKE là thuật toán được Twitter đưa ra vào năm 2010 nhằm giải quyết vấn đề tạo ID cho hệ thống của họ, thuật toán này được áp dụng cho việc sinh ID cho các tweet, photo, status….Cái này thì cũng được OpenSource rồi anh em nào thích thì đều có thể kiếm sourcecode trên mạng khá là dễ dàng.

Vì sao lại sử dụng SNOWFLAKE

Anh em nà o làm hệ thống cũng biết việc chúng ta áp dụng khóa chính cho việc thiết kế DB chủ yếu vẫn là Int (32 bit) với chế độ AutoIncrement. Cách thiết kế này thì đáp ứng tốt vấn đề lưu trữ và hiệu năng tuy nhiên khi mà hệ thống lớn dần thì với 2 tỷ ID là chưa đáp ứng được chưa kể việc khi phân tán thì không đảm bảo được tính duy nhất.

Haizz thế thì nghe vẻ hơi gay nhi? THế áp dụng kiể UUID thì sao. UUID thì là kiể dữ liệu dùng 128 bit để quy định được sinh random bởi địa chỉ MAC cùng với 1 số loằng ngoằng khác. Cái này nó có thể sinh trên mỗi máy mà không yêu cầu điều kiện gì quá cao siêu cả.

527b711c-ae90-46cc-bf85-564f354753dd

Có trang web sinh online nữa này

https://www.uuidgenerator.net/

SỐ lượng ID mà UUID có thể sinh ra là 5.3 * 10^36

Đánh mã đến từng hạt cát trên Trái đất cũng chả hết ấy chứ. Dùng UUID thì anh em có thể đánh từng giây từ khi Vụ trụ được hình thành (1.1*10^19). THẬT VÃI QUÁ!!!!!

gdhjb1

Anh chàng này thì thừa sức đáp ứng được cái duy nhất cho các hệ thống phân tán thế nhưng anh ấy lại quá tốn bộ nhớ :(( Hệ thống chưa lớn thì chả sao chứ mà lớn rồi thì thôi. Phình quá sức

Không có anh nào hoàn hảo  à :(( Sao số tôi hẩm hiu vậy. :((

Kiếm được anh nhà giàu thì không đẹp giai, đẹp giai thì lại không giàu. Không có anh nào Soái ca như PHong Đằng trong Samsam đã đến ăn nè 😦 Vừa đẹp giai, vừa galang, vừa giàu có

sam-sam-den-day-an-ne-khoe-canh-om-sau-lung-lang-man-8b7638

Chính vì thế mà Twitter đã đưa ra 1 cách giải quyết đó là triệu hồi soái ca TÂY MÔN XUY TUYẾT (SNOWFLAKE).

nhung-mi-nam-co-trang-dep-trai-nhat-man-anh-hoa-ngu-2-image3

 

Soái cả này chỉ sử dụng 64 bit để định dạnh ID, ID sinh ra sẽ là kiểu số, được sắp xếp và có quy tắc:

  • timestamp – 42bit (được tính bằng epoch)
  • worker id – 10 bit (ID máy)
  • sequence number – 12 bit (number được tăng liên tiếp, đảm bảo tại một thời điểm, mỗi máy có thể sinh được 4096 ID)

Ta sẽ có

77669839702851584

=  (timestamp << 22) | (machine << 12) | sequence

Theo như twitter thì với thuật toán này họ có thể sinh 1000ID/s. Đáp ứng tốt khả năng cho hệ thống của họ.

Ngoài ra thì mỗi hệ thống lại có 1 cách sinh ID khác nhau, anh em có thể tham khảo

Instagram: http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram

Flickr: http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

Yeller: http://yellerapp.com/posts/2015-02-09-flake-ids.html

Sourcecode phần này thì khá là nhiều. Mình đưa link cho cái .NET còn các ngôn ngữ khác anh em tự tìm nhé

https://github.com/RobThree/IdGen

KẾT

Sau khi nghe trình bày xong rồi thì anh em nào thiết kế hệ thống xem có nên áp dụng BÔNG TUYẾT vào cho mình không nhé. Còn mấy anh lơn như anh Youtube có sử dụng như một bước trung gian sinh ID cho video khi ta tiến hành upload, anh Facebook thì dùng để đánh đối tượng trong DB với GraphAPI…

Tặng anh em 1 bài hát về bông tuyết khá sâu lắng cho ngày hè rạng rỡ này :))

 

 

Thảm khảo

https://github.com/twitter/snowflake

https://github.com/RobThree/IdGen

http://blog.paracode.com/2012/04/16/fast-id-generation-part-1/

 

Advertisements

One thought on “Bông tuyết cô độc

  1. Pingback: Tối ưu SQL (phần 10): Lại là câu chuyện về GUID ID | Code, code and more code

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s