#193 - Tiki xây dựng hệ thống Cross Device Sessions Realtime như thế nào?

Oct 18, 2021

Trong số này chúng ta cùng tìm hiểu về: WebRTC và cách thiết lập 1 kết nối peer-to-peer; Mạng neuron tích chập (Convolutional Neural Network) là gì; Hệ thống kiểm tra chất lượng dữ liệu tại Wealthfront; Tiki xây dựng hệ thống Cross Device Sessions Realtime như thế nào; Các thuật toán trong một CDN; Tìm hiểu về các khái niệm data warehouse, data lake, data lakehouse; Và cuối cùng, cùng tìm lời giải cho bài toán reverse nodes in k-group.

Những bài viết hay

Understanding Web Real-Time Communication (WebRTC)

WebRTC là một dự án mã nguồn mở hiện đang được phát triển với mục đích cung cấp giao tiếp peer-to-peer, thời gian thực giữa các ứng dụng web. Đây chính là công nghệ được Google Meet/Hangout, Facebook Messenger và Discord sử dụng.

WebRTC cung cấp các API JavaScript giúp các nhà phát triển dễ dàng xây dựng các ứng dụng web với khả năng truyền tải dữ liệu, video và âm thanh theo thời gian thực. Những phát triển gần đây trong WebRTC cũng đã cho phép nó được tích hợp vào các ứng dụng native.

Về cơ bản, để thiết lập một kết nối WebRTC, chúng ta cần thực hiện hai bước:

Bước 1: Xác định vị trí của một peer
Bước 2: Thông báo cho một thiết bị để thiết lập kết nối WebRTC

Bước 1 giống như khi bạn cần nói chuyện với ai đó qua điện thoại, bạn cần biết số điện thoại của người đó và thực hiện cuộc gọi đến họ. Tuy nhiên, đối với việc giao tiếp giữa các thiết bị thông qua mạng internet, quá trình này không dễ dàng như vậy. Bởi vì, hầu hết các máy tính hiện nay khi truy cập vào internet đều nằm sau một lớp Network Address Translator (NAT). Do sự hiện diện của NAT, một thiết bị không thể biết được Public IP của chính nó mà chỉ biết Private IP do NAT chỉ định. Và do đó, nó không thể chia sẻ địa chỉ IP công cộng của nó với một thiết bị khác để chấp nhận kết nối. Để khắc phục điều này, WebRTC sử dụng một giao thức được gọi là Interactive Connectivity Establishment (ICE). Công việc của ICE là tìm ra con đường tốt nhất có thể để kết nối 2 thiết bị với nhau. ICE hoạt động dựa trên 2 loại máy chủ được gọi là Session Traversal Utilities for NAT (STUN) và Traversal Using Relays around NAT (TURN).

Máy chủ STUN về cơ bản cho phép một thiết bị tìm ra Public IP của chính nó. Tuy nhiên tuỳ vào độ phức tạp mà độ bảo mật mà NAT được thiết lập, thì ngay cả STUN cũng không thể tìm và cung cấp Public IP chính xác. Trong những trường hợp như vậy, ICE dựa vào TURN để thiết lập kết nối. TURN (Traversal Using Relays around NAT), như tên gọi của nó cho thấy, nó là một máy chủ chuyển tiếp và hoạt động như một trung gian để truyền dữ liệu, âm thanh, video giữa 2 thiết bị.

Đối với bước 2, WebRTC không xác định bất kỳ tiêu chuẩn nào để thực hiện một cơ chế thông báo giữa các thiết bị để nó cho nhà phát triển tạo ra một cơ chế do họ lựa chọn.

Mời bạn đọc bài viết gốc để hiểu rõ hơn về cơ chế hoạt động của WebRTC.

Convolutional Neural Networks for Visual Recognition

Mạng neuron tích chập (Convolutional Neural Network) giống với mạng neuron bình thường, chúng đều được cấu thành từ nhiều neuron chứa weight (trọng số) và bias (độ lệch) có thể học được.

Điểm khác biệt là mạng tích chập đặt giả định rõ ràng rằng dữ liệu đầu vào sẽ là ảnh, điều này cho phép chúng ta mã hóa các đặc tính nhất định vào trong kiến trúc mạng, giúp các hàm truyền xuôi (forward function) thực thi hiệu quả hơn và giảm đáng kể số lượng tham số trong mạng. Cụ thể là, không giống như mạng neuron thông thường, các lớp của mạng tích chập có các neuron được sắp xếp dưới dạng 3 chiều: rộng, cao, sâu.

Mạng tích chập bao gồm nhiều lớp được chồng lên nhau. Mỗi lớp là một API đơn giản: biến đổi khối đầu vào 3 chiều sang khối đầu ra 3 chiều khác bằng các hàm số có thể đạo hàm được, có thể chứa nhiều hoặc không chứa tham số. Các lớp trong mạng thuộc một trong ba dạng chính: lớp tích chập (Convolutional Layer, viết tắt: CONV), lớp chứa/tổng hợp (Pooling Layer, viết tắt: POOL) và lớp nối kín (Fully-Connected Layer, viết tắt: FC).

Lớp tích chập là cấu phần chính của mạng tích chập, chịu trách nhiệm cho phần lớn tính toán nặng. Các tham số của lớp tích chập bao gồm một chuỗi các bộ lọc (filter) có thể học được. Mỗi bộ lọc sẽ rất nhỏ về mặt không gian (theo chiều rộng và chiều cao) nhưng sẽ kéo dài theo toàn bộ chiều sâu của khối dữ liệu đầu vào.

Với lớp pooling, thông thường, ta sẽ định kì thêm chúng vào giữa các lớp tích chập trong mạng. Vai trò của chúng là từ từ giảm chiều không gian của các giá trị biểu diễn để giảm số lượng tham số và phép tính trong mạng, do đó kiểm soát hiện tượng overfitting.

Với lớp nối kín, mỗi neuron sẽ kết nối với toàn bộ giá trị kích hoạt ở lớp phía trước, như thường thấy ở mạng neuron thông thường, được tính toán bằng các phép tính ma trận cùng với bias offset.

Dựa trên việc kết hợp các loại lớp trên, ta có thể tạo được nhiều kiểu mạng tích chập khác nhau. Dạng phổ biến nhất của mạng tích chập là chồng vài lớp CONV-RELU, theo sau là lớp POOL, lặp lại dạng mẫu này cho tới khi hình ảnh được hợp trên không gian để thành một kích cỡ nhỏ hơn. Tiếp đó là các lớp nối kín. Lớp nối kín cuối cùng sẽ giữ giá trị output như điểm phân loại (class scores):

INPUT -> [[CONV -> RELU]*N -> POOL?]*M -> [FC -> RELU]*K -> FC

trong đó:

- * nghĩa là lặp lại

- POOL? nghĩa là lớp pooling không bắt buộc.

- Thông thường: N >= 0 (và N <= 3), M >= 0, K >= 0 (và K < 3).

Điểm nghẽn cổ chai lớn nhất khi xây dựng mạng neuron tích chập là ở dung lượng bộ nhớ (memory). Nhiều GPU hiện đại chỉ có bộ nhớ 3/4/6GB, GPU tốt nhất có khoảng 12GB. Phần lớn bộ nhớ được sử dụng để lưu các giá trị kích hoạt ở các lớp trong mạng neuron.

Mời các bạn đọc bài viết gốc để có thêm thông tin chi tiết, ví dụ và ảnh minh họa.

Automating Data Quality Checks on External Data

Tại Wealthfront, việc sử dụng dữ liệu do bên thứ ba cung cấp rất quan trọng chẳng hạn như thông tin về các giao dịch ngân hàng của những khách hàng liên kết hoặc tài liệu thuế. Bài viết này sẽ nói về cách họ thiết kế hệ thống một cách tự động để có khả năng xử lý trước mọi dữ liệu không nhất quán:

Dữ liệu không được định dạng như mong đợi.
Dữ liệu được xử lý thủ công.
Dữ liệu phi logic và giá trị sai.
Thông tin dữ liệu bị thiếu.
Ý nghĩa của dữ liệu bị thay đổi.

Có 3 phương pháp được áp dụng để kiểm tra và giám sát dữ liệu từ bên thứ ba cung cấp

Lưu trữ dữ liệu nguồn (dữ liệu từ bên thứ 3 cung cấp). Họ lưu trữ dữ liệu gốc: file, thông tin trả về của API hoặc bất kì thông tin gì họ thu thập được từ bên thứ ba nhằm mục đích kiểm tra và phát hiện lỗi về sau. Bên cạnh đó giúp trả lời cho câu hỏi: liệu rằng lỗi đến từ bên thứ ba hay do chính họ gây ra.
Chuyển đổi và xác minh: Sau khi dữ liệu được lưu trữ vào hệ thống, họ tiến hành chuyển đổi dữ liệu theo lược đồ cơ sở dữ liệu của họ và tiến hành kiểm tra 1 số thông tin đã định nghĩa trước đó như độ dài của số tài khoản phải là 5, khoản tiền phải lớn hơn 0 và ngày hiệu lực phải nhỏ hơn hoặc bằng ngày hiện tại. Nếu như thông tin trong dữ liệu thừa họ có thể bỏ qua hoặc không họ có thể đưa ra 1 số cảnh báo hoặc lỗi và chỉ đến nguồn dữ liệu trực tiếp của lỗi đó.
Thông báo và xử lý lỗi trong quá trình xác minh: Sử dụng những thông tin khác của dữ liệu để suy ngược lại những thông tin đã sai trước đó. Nếu không thể làm được gì từ phía mình, họ sẽ tự động hoá quy trình cảnh báo hoặc gửi email đến bên thứ 3.

Cách áp dụng:

Lưu trữ dữ liệu nguồn: Trước đây họ chỉ lưu trữ thông tin về metadata và kéo dữ liệu trực tiếp từ API vào các quy trình hạ nguồn. Nhận thấy việc lưu trữ dữ liệu nguồn theo thời gian là có ý nghĩa, họ đã cập nhật đầy đủ những dữ liệu trả về từ API vào hệ thống của họ.
Chuyển đổi và xác minh: Liệu dữ liệu đã được cập nhật để có thể thông báo cho khách hàng của mình hay chưa. Thay vì họ cập nhật dữ liệu được vào ngày cập nhật thì giờ đây họ đã có dữ liệu lưu trữ đầy đủ và có thể so sánh trực tiếp các trường thông tin 1 cách rõ ràng.
Thông báo và xử lý lỗi trong quá trình xác minh: Bỏ qua bất kỳ bản cập nhật nào không chứa bất kỳ thay đổi và thông báo về các bản cập nhật có thay đổi. Thêm những tài liệu cho việc cập nhật và chỉnh sửa.

Những đánh đổi khi họ áp dụng những phương pháp này.

Dữ liệu lưu trữ cực kì lớn
Dữ liệu sẽ có 1 độ trễ nhất định khi áp dụng những quy trình.
1 số chính sách của bên thứ ba về việc bảo mật thông tin

Tiki xây dựng hệ thống Cross Device Sessions Realtime như thế nào?

Session (phiên truy cập) là một chuỗi hành động của người dùng tương tác trên website trong một khung thời gian cụ thể. Một người dùng khi truy cập vào website được gọi là một session. Trong một session người dùng có thể thực hiện rất nhiều tương tác trên website như xem sản phẩm, thêm sản phẩm vào giỏ hàng, thanh toán sản phẩm,... Đặc biệt, trong thương mại điện tử chỉ số này sẽ thể hiện rất nhiều điều, ví dụ như là cho biết được khách hàng đến từ nguồn quảng cáo nào. Với chỉ số doanh thu của từng nguồn này, công ty thương mại điện tử có thể dễ dàng nắm được sự hiệu quả của từng nguồn. Sau đó, đem ra quyết định đầu tư một cách chính xác và có chiến lược.

Việc tính toán session cùng với các metrics khác trên trang thương mại điện tử ở cùng một thiết bị mang đến thử thách rất lớn với người làm hệ thống, cũng như dữ liệu. Ở Tiki độ khó của bài toán này còn tăng lên khi mà người dùng truy cập từ nhiều thiết bị điện tử và từ nhiều nguồn để tới trang web của Tiki. Lúc này, sẽ phát sinh ra bài toán tính session cross device, mục đích chính của bài toán này là giúp liên kết được dữ liệu từ nhiều thiết bị và hoạt động của người dùng từ nhiều session khác nhau. Từ đó, giúp ta xây dựng nên một bức tranh toàn cảnh về thói quen của khách hàng. Điều này sẽ giúp công ty có thể biết được nên làm gì phù hợp trong từng giai đoạn của quá trình chuyển đổi conversion — từ đó giúp ta giữ chân được những khách hàng tiềm năng này thành khách hàng thân thiết.

Bên cạnh đó, việc tính toán traffic session không chỉ phục vụ cho vấn đề marketing của Business Team mà còn là nền tảng để giải quyết những bài toán thử thách phát sinh khác như: Fraud Detection Service, Coupon Delivery Service, Customer Data Platform...

Sau khi nhận thấy thử thách và tiềm năng đó, đội ngũ kỹ sư Team Data của Tiki đã phát triển một hệ thống tính toán session real-time mang tên Observer với thiết kế kiến trúc có thể dễ dàng scale ngang từng service độc lập, chịu được tải tốt đáp ứng được lượng traffic khổng lồ trong những đợt peak event như 11.11, Black Friday,…

Bài viết có nêu rõ về các lý do mà Team Data xây dựng hệ thống, làm rõ được các bước xử lý và cách tối ưu khi tính toán cross device sessions real-time. Để biết thêm chi tiết, mời các bạn đọc đầy đủ nội dung của bài viết tại đây.

Techtalk

Four Languages from Forty Years Ago

Thập kỷ 70 là một thời kỳ vàng của những ngôn ngữ lập trình mới, nhưng chúng có còn ảnh hưởng đến cách chúng ta lập trình ngày nay? Chúng ta còn có thể học những gì từ những ngôn ngữ đó? Với video này, Scott Wlaschin - người tạo ra trang web F# for fun and profit sẽ nói về 4 ngôn ngữ từ 50 năm trước: SQL, Prolog, ML và Smalltalk. Ông sẽ bàn về triết lý design của mỗi ngôn ngữ, cách các ngôn ngữ đó thay đổi cách suy nghĩ về lập trình cũng như sự khác biệt so với các ngôn ngữ phổ biến hiện nay. Chúng ta sẽ được nghe về những nguyên lý cơ bản mà chúng ta có thể sử dụng hàng ngày. Và cũng có khả năng, bạn sẽ có một cách nhìn mới về lập trình sau khi xem xong video này.

Góc Distributed System

Các thuật toán khi xây dựng hệ thống CDN

CDN - content delivery network là thành phần quan trọng khi xây dựng hệ thống để phục vụ khách hàng trải rộng trên toàn thế giới, đặc biệt với các hệ thống phục vụ các chức năng về media như Netflix, Youtube. Hiện tại có các công ty làm về CDN lớn như Akamai, CloudFlare, Fastly. Vì khối lượng request rất nhiều, đồng thời phải phục vụ các khách hàng trải rộng trên toàn thế giới với yêu cầu latency thấp, do vậy các bài toán điển hình mà một hệ thống CDN cần giải quyết thường là:

Làm sao để chọn server hợp lí để phục vụ khách hàng: giảm latency (dựa trên khoảng cách địa lí) và phân tải đồng đều giữa các node.
Xây dựng mạng overlay để truyền tải data từ origin server đến edge server

Từ đấy cần phải sử dụng một số thuật toán như Stable Marriage, Consistent Hashing, Overlay Routing ... Paper được giới thiệu trong bài viết được viết bởi các kĩ sư ở Akamai. Paper không chỉ trình bày về các thuật toán, mà thêm những điểm tối ưu cần có cho các thuật toán đề ra.

http://www.sigcomm.org/sites/default/files/ccr/papers/2015/July/0000000-0000009.pdf

Góc Database

Data Warehouse - Data Lake - Data Lakehouse

Nhu cầu về Business Intelligence vốn dĩ đã có từ lâu, từ trước khi các thuật ngữ thời thượng như Big data, AI, Cloud Computing được ra đời. Ở những thời kỳ đầu, thậm chí BI report còn được tạo ra một cách thủ công.

Khi công nghệ dần phát triển hơn, đặc biệt là công nghệ về database, thuật ngữ (hay kỹ thuật) Data Warehouse bắt đầu được sử dụng. Hình dung đơn giản thì Data Warehouse giống như một "kho hàng", nơi dữ liệu sẽ được phân loại, sắp xếp, ... ngay thời điểm được nhận. Ở những giai đoạn thập niên 80 của thế kỷ trước, các Data Warehouse vẫn còn sơ khai, dữ liệu chỉ được lưu trên một server database (có thể kèm back-up), và dữ liệu từ các nguồn sẽ đổ về một cách định kỳ (cuối ngày, cuối tuần).

Data Warehouse có nhiều đặc tính, trong đó có hai đặc tính nổi bật là:

Được dùng để lưu trữ dữ liệu có cấu trúc định sẵn từ lúc ghi
Dữ liệu thường sẽ được clean trước khi vào warehouse.

Khi các hệ thống càng ngày càng phình to, nhu cầu về việc lưu trữ và quản lý dữ liệu thô (raw data) cũng ngày càng phổ biến, một kỹ thuật mới được đưa ra nhằm mở rộng hơn Data Warehouse đó là Data Lake. Hiểu một cách nôm na thì Data Lake là một bể chứa nước, nơi "nước" (dữ liệu) từ nhiều nguồn, nhiều phòng ban (department), nhiều đơn vị kinh doanh (BU) sẽ được gom về một nơi. Cũng giống như nước trong bể, dữ liệu được lưu trong Data Lake cũng sẽ trở nên đa dạng, mềm dẻo (có thể thiếu nhất quán), nhiều loại định dạng (media, text, logs, parquet, ...). So với Data Warehouse, Data Lake được xem là lớn, chứa đa dạng loại dữ liệu và "loạn" với nhiều loại dữ liệu phi cấu trúc hơn (unstructured data).

Tuỳ vào cách thiết kế mà dữ liệu từ Data Lake có thể sẽ được sàng lọc để đưa vào một Data Warehouse để đọc trên các hệ thống report hoặc có thể chạy report trực tiếp từ Data Lake mà không thông qua Data Warehouse.

Tuy nhiên, giống như nhiều bài toán khác về CS, khi Data Lake phình to, nhiều vấn đề cũng từ đó phát sinh như:

Chất lượng dữ liệu không ổn định do không được kiểm tra kỹ ở đầu ghi.
Khỏ đảm bảo được tính nhất quán của dữ liệu do nhiều ETL pipeline có thể chạy đồng thời, hoặc một pipeline đang chạy trên một nguồn dữ liệu đang được cập nhật bởi một pipeline khác.
Khó tìm được các nguồn dữ liệu phù hợp do cơ chế thừa kế phức tạp giữa các nguồn dữ liệu (complicated data lineage)

Mặc dù các vấn đề trên có thể giải quyết bằng kiến trúc riêng của từng tổ chức, nhiều công ty đã và đang xây dựng những giải pháp tổng quan hơn dựa trên một kiến trúc mới được đề xuất đó là Data Lakehouse. Nếu như trước đây (với Data Lake) dữ liệu có thể đổ vào hồ một cách thiếu kiểm soát thì với kiến trúc Lakehouse, dữ liệu cần phải thông qua một cơ chế tập trung để quản lý, phân luồng trước khi đổ vào hồ. Có thể hình dung Data Lakehouse như một nhà máy nằm ở đầu hồ nước nơi kiểm soát, sàng lọc, kiểm tra chất lượng, giúp giải quyết những vấn đề đã nêu của Data Lake.

Để hiểu thêm về kiến trúc Lakehouse, mời bạn cùng đọc bài báo của Databricks ở đây.

Góc Lập Trình

Đề tuần này:

Câu đố n-queens là bài toán xếp n quân hậu trên một bàn cờ n x n sao cho không có hai quân hậu nào tấn công nhau.

Cho một số nguyên n, trả về tất cả các nghiệm riêng biệt cho câu đố n-queens. Bạn có thể trả về kết quả theo bất kỳ thứ tự nào.

Mỗi đáp án chứa một cấu hình bảng riêng biệt vị trí của n quân hậu, trong đó 'Q' and '.' hiển thị tương ứng một nữ hoàng và một không gian trống.

Ví dụ:

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Đề bài ở Leetcode

Lời giải tuần trước:

Một Linked list là một kiểu dữ liệu đệ quy, một đoạn con bên trong cũng là một linked list. Do đó, ta có thể bắt đầu với một giải thuật reverse toàn bộ một linked list.

Có nhiều phương án để đảo ngược một linked list, chúng ta có thể thử một phương án như sau:

- Gọi head là node bắt đầu của linked list cần đảo ngược.

- rev_head là pointer tới head của reverse linked list.

- Dùng một pointer ptr để duyệt qua list ban đầu

- Với từng phần tử, ta sẽ chèn vào phần đầu của reverse list (head chính là rev_head)

- Move pointer ptr cho tới khi kết thúc list

Vậy ta đã có một phương án để reverse một linked list, ta sẽ tiếp tục với bài toán reverse theo k nodes như sau. Chúng ta sẽ bắt đầu từ head của linked list và chạy thuật toán reverse nhưng chỉ xử lý với k node.

Tuy nhiên do đề bài yêu cầu nếu có ít hơn k node trong linked list, ta sẽ không reverse chúng. Do đó ta cần đếm đủ k node trước khi thực hiện thao tác reverse. Điều đó dẫn tới ta cần ít nhất 2 lần duyệt, một để đếm, và một để reverse.

Phương án 1: Đệ quy

- Giả sử ta có một hàm reverse() để reverse linked list, với hai tham số đầu vào là head của linked list và số k. Hàm này sẽ đảo ngược k node đầu tiên của linked list.

- Ở mỗi lần gọi đệ quy, ta cần đếm có đủ k node trong linked list.

- Nếu có ít hơn k node còn lại trong list, return về node head.

- Nếu có ít nhất k node trong list, ta tiến hành reverse các node này bằng việc gọi hàm reverse đã định nghĩa ở bước đầu.

- Hàm reverse này cần trả về node head của linked list đã được đảo ngược. Đây cũng là node thứ k trong linked list.

- Mỗi lần gọi đệ quy, ta cần thực hiện reverse k node, sau đó tiếp tục gọi đệ quy trên phần còn lại. Đồng thời liên kết các phần đã đảo ngược với nhau.

Phương án này cần Time Complexity O(N) do ta cần duyệt mỗi node 2 lần. Ta có thể thực hiện 1 tối ưu nhỏ ở đây là không cần đếm đủ số node mà vẫn thực hiện reverse. Nếu ta thấy không có đủ số node, ta sẽ thực hiện reverse thêm 1 lần để đảo ngược về danh sách ban đầu.

Space Complexity cần thiết là O(N/K) do sử dụng đệ quy.

Phương án 2: Chúng ta có thể tối ưu và chỉ cần O(1) space.

Phương án này vẫn dựa trên ý tưởng giống phương án đệ quy, nhưng thay vì dùng stack ta sẽ dùng thêm một vài biến để lưu lại các kết nối. Chúng ta vẫn sẽ đếm đủ k node ở mỗi thời điểm, nếu đủ k node, sẽ tiến hành reverse chúng.

Phương án này xin dành cho bạn đọc tìm hiểu thêm.

Code: https://pastebin.com/8yd4fpR4

Code & Tools

Góc Sponsors

Fossil Vietnam, formerly Misfit, is the Center of Excellence for Wearables Research & Development of Fossil Group. We’re an innovative team that designs and engineers world-class wearables products that touch the lives of millions of people. We take pride in being innovators who are pushing the boundaries of fashion and technology.

Why you’ll love working at Fossil Vietnam

Opportunities to work with global Tech giants.
Attractive salary and performance bonus twice a year.
Premium healthcare for employees and family, even on probation.
15 days of Annual leave and 2 days of Volunteer leave, even on probation.
All tools you need: Mac/Windows, iOS/Android, Testing devices/State-of-the-art wearables, you name it.
Welcome watch after probation.
You’ll get food to get fit, we’ll take care of it all.

Join us, and you’ll contribute to the development of next-generation wearable technology that makes a difference in people’s everyday lives. View all featured positions.

Keep in touch

Facebook

Quotes

“Give a man a program, frustrate him for a day. Teach a man to program, frustrate him for a lifetime.”

― Muhammad Waseem