View profile

#172 - Mô hình vách ngăn (Bulkhead Pattern) trong thiết kế Microservice

Grokking Vietnam
Grokking Vietnam
Những bài viết hay
Góc Distributed System
Vấn đề timing trong Redlock, thuật toán distributed lock của Redis.
Redis được sử dụng rộng rãi chủ yếu để các máy chủ chia sẻ các loại dữ liệu biến đổi liên tục (fast-changing), không yêu cầu độ chính xác tuyệt đối, và tạm thời. Ví dụ dữ liệu cache, hoặc dữ liệu đếm (trong bài toán rate limiting). Bài viết này đưa ra lo ngại của Martin Kleppmann, tác giả cuốn Design Data-Intensive Applications, là việc Redis đã phát triển quá nhiều vượt xa mục tiêu thiết kế ban đầu. Trong đó bài toán distributed lock là một ví dụ, nhất là khi Redis chạy ở mô hình cluster. Redis đã phát triển thuật toán Redlock để xử lý bài toán này, tuy nhiên có nhiều điểm không vững.Tìm hiểu thuật toán Redlock ở đây: https://redis.io/topics/distlock
Đối với thiết kế lock thông thường, sẽ có 1 chương trình lock service thực hiện việc trao quyền được lock (lease) cho các client yêu cầu nó, theo thứ tự ai yêu cầu trước được trước, với 1 khoảng thời gian expired cố định. Thiết kế này có nhiều lỗ hổng, ví dụ client lấy được lease nhưng bị tạm dừng (eg. Do GC). Khi lease hết hạn, client khác sẽ lấy được lease và thay đổi dữ liệu, khi đó client cũ nếu thực hiện tiếp sẽ gây xung đột dữ liệu.
Cách Redlock xử lý là bên cạnh lease, lock service sẽ cung cấp thêm 1 token định danh cho việc lấy lease đó. Token này đơn giản là 1 số nguyên tăng dần, cho mỗi lượt truy vấn lấy lease. Client với lease cũ sẽ có token thấp hơn client khác, nên không thể gây ra xung đột dữ liệu được.
Tuy nhiên bài toán tiếp theo là làm sao thiết kế việc generate token trong điều kiện phân tán:
  • Nếu chỉ 1 Redis node sinh ra token, node đó có thể bị fail.
  • Nếu 1 cluster Redis sinh ra token, cần phải có cơ chế sync và đồng thuận.
Redlock đã khéo léo sử dụng time để giải quyết bài toán đồng thuận. Cụ thể:
  • Mỗi Redis node vẫn tiến hành sinh lease, và generate token như bình thường.
  • Các redis node không cần đồng bộ token với nhau. Thay vào đó, Redlock yêu cầu client cùng một lúc gửi yêu cầu lấy lease ở tất cả các Redis node, với 1 khoảng timeout đủ nhỏ so với thời gian auto-release lease để đảm bảo quá trình không bị block.
  • Nếu N/2+1 node trả kết quả OK trong thời gian timeout, client đó thắng lease và được quyền lock. Toàn bộ N node sẽ đồng loạt cập nhật token.
  • Nếu client không nhận đủ kết quả OK từ N/2 + 1 node, hoặc bị timeout, client sẽ đồng loạt gửi bản tin unlock.
  • Một số khía cạnh khác của thuật toán được mô tả cụ thể trong bài gốc về Redlock, bạn tìm hiểu kĩ bên đó, phạm vi bài này không mô tả.
  • Redis sử dụng hàm gettimeofday để xác định việc token bị hết hạn. Hàm này điều chỉnh thời gian tăng giảm theo sự khác biệt giữa thời gian hệ thống với NTP server (code cụ thể ở đây)
  • Redlock đảm bảo mỗi node sẽ giữ token trong một khoảng chiều dài thời gian (duration) bằng nhau. 
Mọi thứ có vẻ hoạt động tốt, tuy nhiên RedLock có một giả định:
  • Timeout của việc lấy lease được set đủ dài hơn thời gian network delay và process bị dừng, thậm chí dài hơn cả clock drift giữa các node. => là một giả định rất nguy hiểm trong môi trường asynchronous.
Bài viết có đưa ra hai ví dụ có thể làm hỏng thuật toán Redlock thông qua bad timing có thể bẻ gãy giả định về time nói trên. Ví dụ 1: Giả sử có 5 node redis A,B,C,D,E và có 2 client (1,2).
  • Client 1 lấy được lease từ A,B,C. D và E do network issue nên không nhận được request.
  • Đồng hồ của node C bị sai khiến lease bị expire.
  • Client 2 lấy được lease từ C,D,E. Lúc này D và E không bị network issue nữa; A,B lại bị network issue. Và do đồng hồ node C sai nên C cho client 2 lấy lease mới.
  • Như vậy lúc này client 1 và 2 đều có lease => RedLock hoạt động sai!
Ví dụ 2: Giả sử 5 node A,B,C,D,E đều có NTP hoạt động chuẩn. 
  • Client 1 lấy được lease từ cả 5 node. 
  • Do tiến trình GC, client 1 bị pause.
  • Lock expire trên cả 5 node.
  • Client 2 lấy được lease mới.
  • Client 1 hết tiến trình GC, hoạt động trở lại. Client 1 nhận được response (bị giữ ở network buffer do tiến trình GC) rằng nó có lease.
  • Như vậy lúc này client 1 và 2 đều có lease => RedLock hoạt động sai!
Như vậy, giả định về timing của RedLock đã bị bẻ gãy. Bài viết kết luận Redlock chỉ có thể hoạt động hiệu quả trong môi trường synchronous: đó là khi clock drift, network delay và process pause đều có bounded (cận trên).
Góc Database
Các nền tảng machine learning hiện đại như Tensorflow chủ yếu được thiết kế để hỗ trợ tính toán dữ liệu song song (data parallelism), trong đó một tập các phép tính gần như giống hệt nhau (chẳng hạn như tính gradient) được thực hiện song song trên một tập hợp các đơn vị tính toán. Tuy nhiên cơ chế dữ liệu song song có những hạn chế nhất định, một trong số đó là việc giả định rằng mô hình đang được huấn luyện có thể được lưu trữ vừa trên RAM của đơn vị tính toán. Thực tế giả định này không hoàn toàn hợp lý, lấy ví dụ, 32GB RAM của GPU đời mới của NVIDIA Tesla V100 Tensor Core là không đủ để lưu trữ kích thước ma trận cho một fully-connected layer để mã hóa một vector đầu vào với 200,000 category thành một vector chứa 50,000 neuron.
Việc xử lý mô hình như trên đòi hỏi sử dụng tới cơ chế dữ liệu song song, trong đó mô hình thống kê được huấn luyện không chỉ đơn giản là cần sao chép giữa các đơn vị tính toán khác nhau mà còn cần được phân vùng, hoạt động song song và thực thi bởi một loạt các phép toán đồng bộ theo nhóm lớn(bulk-synchronous). Các hệ thống hiện có cho học máy phân tán còn đang khá hạn chế tính năng cho mô hình song song như thế này.
Các tác giả cho rằng mô hình song song có thể được thực hiện bằng cách tận dụng cơ chế dữ liệu quan hệ trong đó các phần khác nhau của mô hình có thể được lưu trữ trong một tập các bảng, và các phép tính toán trên từng phần của mô hình có thể được thể hiện thông qua một vài câu truy vấn SQL.
Lợi ích đầu tiên của việc cài đặt mô hình song song sử dụng SQL là các thuật toán huấn luyện sẽ khá tương đồng so với việc cài đặt cơ chế dữ liệu song song. Các RDBMS cung cấp giao diện lập trình khai báo nên lập trình viên chỉ cần khai báo những gì họ muốn thông qua câu lệnh truy vấn, quá trình tính toán sẽ được hệ thống tự động tạo ra, sau đó được tối ưu hóa và thực thi để phù hợp với kích thước dữ liệu, bố cục và phần cứng máy tính.
Một lợi ích khác của việc tận dụng dữ liệu quan hệ là các phép tính phân tán trong RDBMS đã được nghiên cứu trong nhiều năm nên trình tối ưu hóa câu truy vấn sẽ đạt hiệu quả cao trong việc tối ưu hóa các phép tính phân tán. Không phải ngẫu nhiên mà các nền tảng tính toán phân tán cạnh tranh như Spark đang dần phát triển theo hướng giống với một RDBMS song song hơn.
Trong bài báo này, các tác giả sẽ trình bày những nghiên cứu của mình trong việc sử dụng RDBMS để triển khai các mô hình deep learning
  • Giới thiệu các index đa chiều dạng mảng vào các bảng cơ sở dữ liệu. Khi một tập hợp các bảng dùng chung một mẫu phép tính, chúng có thể được thu gọn và thay thế bằng một bảng có nhiều phiên bản (được biểu thị bằng các index).
  • Sửa đổi trình tối ưu hóa câu truy vấn của cơ sở dữ liệu giúp xử lý các đồ thị truy vấn có kích thước rất lớn. Một đồ thị truy vấn được phân vùng thành một tập hợp các frame, chuyển đổi bài toán lát cắt trong đồ thị (graph cutting problem) thành một dạng của bài toán gán bậc hai tổng quát (generalized quadratic assignment problem).
  • Cài đặt triển khai các ý tưởng trên SimSQL - một RDBMS prototype phân tán được thiết kế đặc biệt cho xử lý tính toán thống kê quy mô lớn.
  • Kiểm thử cơ chế trên hai bài toán học sâu phân tán (một mạng nơ-ron chuyển tiếp và một cài đặt Word2Vec cùng với phân bổ Dirichlet tiềm ẩn (LDA) phân tán. Kết quả cho thấy rằng code Sim-SQL có thể scale cho mô hình kích thước lớn, vượt qua kích thước mô hình mà TensorFlow có thể hỗ trợ và SimSQL có thể hoạt động tốt hơn TensorFlow trên một số mô hình.
Góc Lập Trình
Cho trước một mảng số nguyên không âm, bạn được đặt ở vị trí đầu tiên trong mảng đó. Tại đây bạn thực hiện các bước nhảy tới các phần tử tiếp theo trong mảng. Mỗi phần tử trong mảng thể hiện độ dài “tối đa” của bước nhảy tại vị trí đó. Ví dụ ở phần tử đầu tiên có giá trị 2, thì bạn có thể thực hiện bước nhảy có độ dài 1 hoặc 2 để tới các phần tử tiếp theo trong mảng. Hãy xác định xem bạn có thể nhảy tới vị trí cuối cùng hay không.
Ví dụ 1:
Input: nums = [2,3,1,1,4]
Output: true
Giải thích: Ở vị trí đầu tiên nhảy 1 bước tới vị trí thứ 2, sau đó nhảy 1 bước có độ dài 3 để tới vị trí cuối cùng.
Ví dụ 2:
Input: nums = [3,2,1,0,4]
Output: false
Giải thích: Bạn sẽ luôn luôn nhảy tới vị trí có index 3 theo bất kỳ cách nào. Khi đó bạn không thể nhảy tiếp để tới ô cuối cùng.
(Chúng tôi sẽ cung cấp lời giải ở số tiếp theo, nhưng bạn đọc cũng có thể gửi lời giải của bạn tới email của chúng tôi, nhớ phân tích lời giải của bạn nhé)
Security
Code & Tools
  • Camply A command line tool to help you find campsites at thousands of sold out campgrounds across the USA
  • Orchest A new kind of IDE for Data Science.
This Week Sponsors
LINE đang tích cực tìm kiếm nhiều nhân tố ở các vị trí chủ chốt để đáp ứng nhu cầu phát
triển mạnh mẽ của hệ sinh thái LINE. Đặc biệt, trong vai trò Engineering Manager, các bạn sẽ có cơ hội tác động tích cực đến sự phát triển của con người, tổ chức, sản phẩm và hàng trăm triệu người dùng.
Góc Tuyển Dụng
Quotes
In pioneer days they used oxen for heavy pulling, and when one ox couldn’t budge a log, they didn’t try to grow a larger ox. We shouldn’t be trying for bigger computers, but for more systems of computers — Grace Hopper
Did you enjoy this issue? Yes No
Grokking Vietnam
Grokking Vietnam

Cảm ơn bạn đã dành thời gian đọc newsletter kỳ này và chúng tôi hi vọng rằng bạn đã khám phá ra một số điều mới mẻ từ các bài viết trên. Các bạn có thể đọc lại các số cũ tại website newsletter.grokking.org

Ngoài ra các bạn có thể gửi feedback cho Grokking Newsletter team ở https://bit.ly/3k3Jdw5 hoặc đóng góp bài viết tại https://bit.ly/2XaBUtF

If you don't want these updates anymore, please unsubscribe here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam