Background job và queue cho người nông dân

 Từ lúc học lập trình, chắc hẳn chúng ta đều đã nghe đến các khái niệm như queue, stack, linked list rồi một đống thứ hầm bà lằng ấy trong mấy môn lập trình cơ bản, kiểu dữ liệu rồi giải thuật này nọ. Nhưng hiểu được nó là một chuyện, biết nó là một chuyện, còn dùng nó trong thực tế như nào lại là một chuyện khác.

Nhưng câu chuyện dưới đây lại là ở một thế giới khác, thế giới không có queue hay stack, câu chuyện kể về một người nông dân chăn rau, à chăn lợn, nhưng lợn dạo này dịch ốm quá nên chuyển qua buôn chuối và viết blog về thời hoàng kim buôn chuối của mình. Có vậy thôi.

First things first

Vậy người nông dân đó là ai? Tất nhiên là người đang ngồi gõ những dòng chữ này cho các bạn đọc. Và cũng tất nhiên là anh ta chỉ chém gió về thời hoàng kim buôn chuối của mình. Nhưng bởi vì anh ta đâu có được đào tạo lập trình mà viết tiếp, do vậy phịa ra một câu chuyện gần gũi với anh ta hơn thì sẽ dễ mị dân hơn đúng không?

Vậy thì câu chuyện buôn chuối này của mình sẽ đem lại cho các bạn điều gì?

• Queue không cao siêu và xa vời như bạn tưởng
• Queue hoàn toàn có thể được áp dụng vào project của bạn, ngay... ngày mai

Ngay ngày mai là xạo chó đấy, mai thì chưa chắc đã được đâu

Câu chuyện trước khi có queue

Ngày đầu mở bán chuối, mình ngồi ở nhà và có 1 đơn hàng, mình hưng phấn chốt đơn với khách, ghi đơn hàng đó vào sổ, tính tiền rồi viết hóa đơn. Xong để tiết kiệm chi phí, mình còn tự mình ship chuối đến nhà khách hàng. Mất nửa buổi sáng, nhưng mình rất vui vì khởi đầu thuận lợi.

Ngày thứ 2 có 3 đơn hàng, sáng 1 đơn, chiều 1 đơn, tối 1 đơn, vẫn những công đoạn chốt đơn, ghi hàng vào sổ, tính tiền, viết hóa đơn, ship hàng. Mình thực hiện hết đơn này tới đơn khác, và mọi thứ vẫn êm ru.

Ngày thứ 3 có 5 đơn hàng, hơi overload chút xíu nhưng vì đơn vẫn trải đều khắp ngày nên mình vẫn đảm đương được.

...

Tới ngày thứ 7 thì xảy ra vấn đề. Hôm đó là mùng 1, buổi sáng sớm mình nhận được 1 đơn ở khá xa. Do mình trước nay tiết kiệm không xài 3G nên ra đường là tắt mạng. Mình làm hết mọi công đoạn xong, vừa hứng khởi bước vào nhà check tin nhắn thì nhận ra mình vừa mới bỏ lỡ ... 10 cuộc chat của khách hàng. Mình liên hệ lại với người ta, nhưng vì đã chờ mình quá lâu nên người ta đã đặt hàng nơi khác.

Và đó là cái giá phải trả cho bài học về việc xử lý kiểu chờ đợi.

Tiếp cận với queue và background job

Sau hôm ấy, mình lập tức thay đổi cách làm việc để lúc nào cũng có thể chốt đơn, không xử lý đơn hàng kiểu chờ đợi hết đơn nọ tới đơn kia vậy nữa mà xử lý theo hàng đợi, khi mình chốt deal với khách hàng xong, mình sẽ cho khách 1 cái hẹn và sẽ chỉ ghi lại đơn hàng đó vào một danh sách chờ (queue), thuê một người khác (worker) phụ trách ghi hàng vào sổ, tính tiền, viết hóa đơn (job), thuê 1 số người khác nữa (worker) làm shipper chuyên ship chuối (job) theo danh sách đơn hàng kia.

Và thế là mình đã có thể xử lý vài chục đơn hàng 1 ngày.

Trên đây chính là một ví dụ đơn giản về việc áp dụng queue và background job cho mục đích tăng tốc xử lý. Thay vì mình cứ phải chốt đơn, ghi hàng vào sổ, tính tiền, viết hóa đơn, ship hàng rồi mới lại nhận đơn mới thì mình sẽ chỉ chốt đơn, hẹn giờ ship và xử lý tất cả những việc còn lại bằng việc thuê người khác chuyên nghiệp hơn. Khách hàng của mình sẽ được phản hồi sớm hơn, và mình cũng phục vụ được nhiều khách cùng lúc hơn.

Nhưng tôi làm lập trình chứ có bán chuối đâu?

Vâng, chính vì bạn không bán chuối mà làm lập trình, nên hãy thử tưởng tượng tình huống:

• Hệ thống của bạn xử lý 1 công việc mất 0.5 giây, không có gì phải bàn.

• Hệ thống của bạn xử lý 1 công việc mất 10 giây. Và người dùng sẽ phải ngồi nhìn trình duyệt quay quay trong 10s để biết có gì xảy ra tiếp theo.
• Hệ thống cùng lúc chỉ có thể mở 100 kết nối. Vậy kết nối thứ 101 sẽ phải chờ 10s,... rồi kết nối phía sau sẽ bị chờ đợi, chờ đợi hoài, chờ đợi mãi,... rồi timeout.

Và đó là lúc bạn phải nghĩ tới queue và background job. Bạn chỉ cần mất 0.5s để ghi lại yêu cầu của khách hàng vào queue, phản hồi lại họ rằng bạn sẽ xử lý, rồi ngắt kết nối với họ và tạo các background job xử lý yêu cầu này trên các worker.

Queue là hàng đợi, rõ ràng rồi, đến trước xử lý trước (FIFO)

Background job là những công việc được thực hiện dưới nền, tức là không làm gián đoạn tương tác với người dùng (non-blocking user activities)

Worker là những thành phần riêng biệt (thường là các process riêng, service riêng,...) xử lý 1 số công việc chuyên biệt nào đó.

Khi nào thì tôi nên sử dụng hình thức này?

Mặc dù hình thức tiếp cận qua background job này giúp cho khả năng xử lý của ứng dụng tăng thêm rất nhiều, tuy nhiên không phải hệ thống nào cũng cần nó, và không phải hệ thống nào nó cũng phù hợp với nó. Sau đây là một số dấu hiệu cho thấy bạn nên sử dụng queue và background job:

• Các hệ thống chuyên ghi với cường độ lớn (như log, tracking,...). Đẩy vào xử lý queue và background job sẽ giảm nguy cơ quá tải cho database.
• Các hệ thống chuyên đọc nhưng có tính chất báo cáo, report, số lượng request ít nhưng rất mất thời gian tổng hợp.
• Các hệ thống có thời gian phản hồi lâu vì tính chất công việc, giới hạn khách quan,... Việc phản hồi cho user ngay tức thì rồi chạy trong nền sẽ tạo trải nghiệm người dùng tốt hơn. Hệ thống cũng có khả năng phục vụ nhiều user hơn.
• Các công việc phát sinh từ nghiệp vụ chính, làm việc với nhiều service ngoài nhưng không critical. Ví dụ thu thập lịch sử hệ thống, gửi email, cập nhật thông tin từ các nguồn,...
• Các công việc mang tính độc lập và ít ảnh hưởng bởi dây chuyền hay thứ tự. Đảm bảo điều này để có thể scale hệ thống bằng cách thêm nhiều worker cùng lúc.

Khi nào thì không nên dùng?

Còn sau đây là những ví dụ không khuyến khích sử dụng queue và background job trừ khi có kiến trúc phù hợp:

• Các hệ thống chuyên đọc có tính chất hoạt động như các hệ thống đọc bài viết, sản phẩm,... Các hệ thống này sẽ được optimize bằng con đường khác.
• Các công việc mang tính chất quan trọng, có tính quyết định nhưng có thời gian phản hồi không quá dài. Ví dụ các request liên quan tới việc thanh toán, tranh giành unique key hệ thống (như đặt chỗ, mua sản phẩm)

Một vài ví dụ thực tế

Đây là một số hệ thống thực tế mình đã áp dụng queue và background job. Các bạn có thể tham khảo để có cái nhìn sát hơn:

• Hệ thống tracking: client gọi lên tracking system để ghi lại các thông tin người dùng như thông tin trình duyệt, ngày giờ truy cập, ip,... Khi đó hệ thống API sẽ đẩy thông tin đó vào queue trên redis trước, sau đó response OK cho client. Sau đó worker mới lấy thông tin từ queue và ghi vào database. Do số lượng request rất lớn và lượng data ghi vào db rất nhiều nên dùng queue sẽ tránh quá tải database
• Hệ thống logging: Sau hoạt động gì đó của user với hệ thống API, như login, logout, change profile, update post, view post,... hệ thống sẽ phát sinh ra các event, nhưng các event này không được xử lý ngay mà đưa vào queue nhằm tránh block hoạt động của người dùng.
• Hệ thống notification: Hệ thống này phụ trách việc gửi thông báo, sms, email cho người dùng. Đây là công việc phát sinh từ nghiệp vụ chính, không critical và sử dụng nhiều service bên ngoài nên sẽ được đẩy vào queue và gửi lần lượt.
• Hệ thống analytic: đây là hệ thống báo cáo nội bộ, tuy số lượng báo cáo không nhiều, nhưng mỗi báo cáo lại rất tốn thời gian để phản hồi vì phải tổng hợp số liệu. Do vậy đẩy vào queue để tạo trải nghiệm người dùng tốt hơn. Người dùng sẽ gửi yêu cầu xuất báo cáo và nhận được phản hồi đang xử lý. Sau khi được các worker xử lý xong sẽ thông báo lại cho user qua notification.

Một vài điểm lưu ý và tổng kết

Qua một bài viết này, chắc các bạn cũng mong muốn xắn ngay tay áo để theo anh bán chuối làm queue đúng không? Nói đơn giản thì nói vậy chứ để các bạn có thể mai áp dụng luôn được thì cũng cần phải chú ý một số vấn đề phát sinh khi sử dụng hệ thống queue và background job:

• Job tracking: Các bạn phải có cơ chế theo dõi hoạt động của job khi áp dụng hình thức này. Xử lý background job có nghĩa là xử lý job âm thầm, mà lỗi là cũng âm thầm luôn, không đập vào mặt các bạn như ở ngoài API đâu.
• Error handling: Sau khi theo dõi được hoạt động của các job, việc tiếp theo là xử lý lỗi phát sinh như thế nào, có cơ chế retry hay rollback như thế nào, thông báo cho người có trách nhiệm ra sao,...
• Retryable job: Background job của các bạn cần được thiết kế sao cho có thể retry được, tức là lỗi hay không lỗi đều có thể chạy lại mà không xảy ra trùng lặp dữ liệu hay thừa dữ liệu.

Tất nhiên, câu chuyện mình nói ở trên về thanh niên bán chuối chỉ là câu chuyện tuyệt đối hư cấu. Các bạn đừng nên học tập mà bỏ nghề đi bán chuối giống mình nhé. Không dễ như vậy đâu =))

Design Pastebin.com (or Bit.ly)

Design Bit.ly - is a similar question, except pastebin requires storing the paste contents instead of the original unshortened url.

Step 1: Outline use cases and constraints

Gather requirements and scope the problem. Ask questions to clarify use cases and constraints. Discuss assumptions.

Without an interviewer to address clarifying questions, we'll define some use cases and constraints.

Use cases

We'll scope the problem to handle only the following use cases

• User enters a block of text and gets a randomly generated link
  • Expiration
    • Default setting does not expire
    • Can optionally set a timed expiration
• User enters a paste's url and views the contents
• User is anonymous
• Service tracks analytics of pages
  • Monthly visit stats
• Service deletes expired pastes
• Service has high availability

Out of scope

• User registers for an account
  • User verifies email
• User logs into a registered account
  • User edits the document
• User can set visibility
• User can set the shortlink

Constraints and assumptions

State assumptions

• Traffic is not evenly distributed
• Following a short link should be fast
• Pastes are text only
• Page view analytics do not need to be realtime
• 10 million users
• 10 million paste writes per month
• 100 million paste reads per month
• 10:1 read to write ratio

Calculate usage

Clarify with your interviewer if you should run back-of-the-envelope usage calculations.

• Size per paste
  • 1 KB content per paste
  • shortlink - 7 bytes
  • expiration_length_in_minutes - 4 bytes
  • created_at - 5 bytes
  • paste_path - 255 bytes
  • total = ~1.27 KB
• 12.7 GB of new paste content per month
  • 1.27 KB per paste * 10 million pastes per month
  • ~450 GB of new paste content in 3 years
  • 360 million shortlinks in 3 years
  • Assume most are new pastes instead of updates to existing ones
• 4 paste writes per second on average
• 40 read requests per second on average

Handy conversion guide:

• 2.5 million seconds per month
• 1 request per second = 2.5 million requests per month
• 40 requests per second = 100 million requests per month
• 400 requests per second = 1 billion requests per month

Step 2: Create a high level design

Outline a high level design with all important components.

Step 3: Design core components

Dive into details for each core component.

Use case: User enters a block of text and gets a randomly generated link

We could use a relational database as a large hash table, mapping the generated url to a file server and path containing the paste file.

Instead of managing a file server, we could use a managed Object Store such as Amazon S3 or a NoSQL document store.

An alternative to a relational database acting as a large hash table, we could use a NoSQL key-value store. We should discuss the tradeoffs between choosing SQL or NoSQL. The following discussion uses the relational database approach.

• The Client sends a create paste request to the Web Server, running as a reverse proxy
• The Web Server forwards the request to the Write API server
• The Write API server does the following:
  • Generates a unique url
    • Checks if the url is unique by looking at the SQL Database for a duplicate
    • If the url is not unique, it generates another url
    • If we supported a custom url, we could use the user-supplied (also check for a duplicate)
  • Saves to the SQL Database pastes table
  • Saves the paste data to the Object Store
  • Returns the url

Clarify with your interviewer how much code you are expected to write.

The pastes table could have the following structure:

shortlink char(7) NOT NULL
expiration_length_in_minutes int NOT NULL
created_at datetime NOT NULL
paste_path varchar(255) NOT NULL
PRIMARY KEY(shortlink)

We'll create an index on shortlink and created_at to speed up lookups (log-time instead of scanning the entire table) and to keep the data in memory. Reading 1 MB sequentially from memory takes about 250 microseconds, while reading from SSD takes 4x and from disk takes 80x longer.1

To generate the unique url, we could:

• Take the MD5 hash of the user's ip_address + timestamp
  • MD5 is a widely used hashing function that produces a 128-bit hash value
  • MD5 is uniformly distributed
  • Alternatively, we could also take the MD5 hash of randomly-generated data
• Base 62 encode the MD5 hash
  • Base 62 encodes to [a-zA-Z0-9] which works well for urls, eliminating the need for escaping special characters
  • There is only one hash result for the original input and Base 62 is deterministic (no randomness involved)
  • Base 64 is another popular encoding but provides issues for urls because of the additional + and / characters
  • The following Base 62 pseudocode runs in O(k) time where k is the number of digits = 7:

def base_encode(num, base=62):
    digits = []
    while num > 0
      remainder = modulo(num, base)
      digits.push(remainder)
      num = divide(num, base)
    digits = digits.reverse

• Take the first 7 characters of the output, which results in 62^7 possible values and should be sufficient to handle our constraint of 360 million shortlinks in 3 years:

url = base_encode(md5(ip_address+timestamp))[:URL_LENGTH]

We'll use a public REST API:

$ curl -X POST --data '{ "expiration_length_in_minutes": "60", \
    "paste_contents": "Hello World!" }' https://pastebin.com/api/v1/paste

Response:

{
    "shortlink": "foobar"
}

For internal communications, we could use Remote Procedure Calls.

Use case: User enters a paste's url and views the contents

• The Client sends a get paste request to the Web Server
• The Web Server forwards the request to the Read API server
• The Read API server does the following:
  • Checks the SQL Database for the generated url
    • If the url is in the SQL Database, fetch the paste contents from the Object Store
    • Else, return an error message for the user

REST API:

$ curl https://pastebin.com/api/v1/paste?shortlink=foobar

Response:

{
    "paste_contents": "Hello World"
    "created_at": "YYYY-MM-DD HH:MM:SS"
    "expiration_length_in_minutes": "60"
}

Use case: Service tracks analytics of pages

Since realtime analytics are not a requirement, we could simply MapReduce the Web Server logs to generate hit counts.

Clarify with your interviewer how much code you are expected to write.

class HitCounts(MRJob):

    def extract_url(self, line):
        """Extract the generated url from the log line."""
        ...

    def extract_year_month(self, line):
        """Return the year and month portions of the timestamp."""
        ...

    def mapper(self, _, line):
        """Parse each log line, extract and transform relevant lines.

        Emit key value pairs of the form:

        (2016-01, url0), 1
        (2016-01, url0), 1
        (2016-01, url1), 1
        """
        url = self.extract_url(line)
        period = self.extract_year_month(line)
        yield (period, url), 1

    def reducer(self, key, values):
        """Sum values for each key.

        (2016-01, url0), 2
        (2016-01, url1), 1
        """
        yield key, sum(values)

Use case: Service deletes expired pastes

To delete expired pastes, we could just scan the SQL Database for all entries whose expiration timestamp are older than the current timestamp. All expired entries would then be deleted (or marked as expired) from the table.

Step 4: Scale the design

Identify and address bottlenecks, given the constraints.

Important: Do not simply jump right into the final design from the initial design!

State you would do this iteratively: 1) Benchmark/Load Test, 2) Profile for bottlenecks 3) address bottlenecks while evaluating alternatives and trade-offs, and 4) repeat. See Design a system that scales to millions of users on AWS as a sample on how to iteratively scale the initial design.

It's important to discuss what bottlenecks you might encounter with the initial design and how you might address each of them. For example, what issues are addressed by adding a Load Balancer with multiple Web Servers? CDN? Master-Slave Replicas? What are the alternatives and Trade-Offs for each?

We'll introduce some components to complete the design and to address scalability issues. Internal load balancers are not shown to reduce clutter.

To avoid repeating discussions, refer to the following system design topics for main talking points, tradeoffs, and alternatives:

• DNS
• CDN
• Load balancer
• Horizontal scaling
• Web server (reverse proxy)
• API server (application layer)
• Cache
• Relational database management system (RDBMS)
• SQL write master-slave failover
• Master-slave replication
• Consistency patterns
• Availability patterns

The Analytics Database could use a data warehousing solution such as Amazon Redshift or Google BigQuery.

An Object Store such as Amazon S3 can comfortably handle the constraint of 12.7 GB of new content per month.

To address the 40 average read requests per second (higher at peak), traffic for popular content should be handled by the Memory Cache instead of the database. The Memory Cache is also useful for handling the unevenly distributed traffic and traffic spikes. The SQL Read Replicas should be able to handle the cache misses, as long as the replicas are not bogged down with replicating writes.

4 average paste writes per second (with higher at peak) should be do-able for a single SQL Write Master-Slave. Otherwise, we'll need to employ additional SQL scaling patterns:

• Federation
• Sharding
• Denormalization
• SQL Tuning

We should also consider moving some data to a NoSQL Database.

Additional talking points

Additional topics to dive into, depending on the problem scope and time remaining.

NoSQL

• Key-value store
• Document store
• Wide column store
• Graph database
• SQL vs NoSQL

Caching

• Where to cache
  • Client caching
  • CDN caching
  • Web server caching
  • Database caching
  • Application caching
• What to cache
  • Caching at the database query level
  • Caching at the object level
• When to update the cache
  • Cache-aside
  • Write-through
  • Write-behind (write-back)
  • Refresh ahead

Asynchronism and microservices

• Message queues
• Task queues
• Back pressure
• Microservices

Communications

• Discuss tradeoffs:
  • External communication with clients - HTTP APIs following REST
  • Internal communications - RPC
• Service discovery

Security

Refer to the security section.

Latency numbers

See Latency numbers every programmer should know.

Ongoing

• Continue benchmarking and monitoring your system to address bottlenecks as they come up
• Scaling is an iterative process