View profile

#161 - Lợi dụng Dependency Confusion để hack vào Apple, Microsoft

Revue
 
 

Grokking Newsletter

March 8 · Issue #162 · View online

Tuyển tập những bài viết hay cùng sự kiện bổ ích dành cho kĩ sư phần mềm tại Việt Nam.


Những bài viết hay
FOQS: Scaling a distributed priority queue FOQS: Scaling a distributed priority queue
Những Architectural Patterns quan trọng nhất bạn cần biết Những Architectural Patterns quan trọng nhất bạn cần biết
Lợi dụng Dependency Confusion để hack vào hệ thống của các công ty hàng đầu thế giới Lợi dụng Dependency Confusion để hack vào hệ thống của các công ty hàng đầu thế giới
Góc Database
Cấu trúc dữ liệu dạng đồ thị (graph) có thể được xem là một trong các loại CTDL có ứng dụng rộng rãi nhất trong Khoa học máy tính hiện đại. Đồ thị được sử dụng để biểu diễn mạng xã hội (social network), mạng tri thức (knowledge graph), mạng máy tính, …
Sự phát triển ngày càng mạnh của các hệ thống thông minh, chi phí lưu trữ rẻ cũng dẫn đến các đồ thị cũng ngày càng phình to về mặc kích cỡ đôi khi lên đến hàng Tera-bytes, Peta-bytes. Lượng dữ liệu lớn như thế này cũng thường được chia ra lưu trữ trên nhiều server thay vì tập trung vào một server duy nhất, điều này khiến cho các thuật toán đồ thị truyền thống vốn dựa trên việc tính toán trên memory trở nên thiếu hiệu quả.
Trong bài báo này, các tác giả giới thiệu về PEGASUS, một thư viện chạy trên nền Hadoop, được xây dựng nhằm giúp cho các tác vụ trên đồ thị trở nên dễ dàng hơn với khối lượng lớn.
Nội dung bài báo bao gồm:
  1. Giải thích về GIM-V, một cách mô tả thuật toán nhân ma trận tổng quát hoá từ nhiều thuật toán đồ thị khác nhau.
  2. Cơ chế cài đặt của GIM-V và mối tương quan với các thuật toán đồ thị phổ biến như PageRank (dùng trong cỗ máy tìm kiếm của Google), RWR (Random Walk with Restart), ước tính bán kính, …
  3. Phân tính về performance của thuật toán
  4. Ứng dụng thuật toán trong quá trình phân tích đồ thị web được tạo ra bởi Yahoo, một trong các đồ thị có kích thước thuộc hàng lớn nhất ở thời điểm bài báo được đưa ra.
Góc Data Warehouse
Apache ORC (Optimized Row Columnar) được thành lập vào năm 2013 từ sự hợp tác giữa các đội ngũ kỹ sư ở Facebook và HortonWorks - công ty chuyên phát triển và bảo trì những dự án liên quan tới Apache Hadoop. Apache ORC là một trong những định dạng tập tin theo việc lưu trữ cột dữ liệu (columnar-storage file format) phổ biến cho các data warehouse hiện giờ, đặc biệt là cho các warehouse dựa trên Apache Hive.
Mỗi ORC file sẽ được chia ra thành nhiều phần nhỏ với mỗi phần chứa 256MB, gọi là stripe. Trong mỗi stripe, ORC sẽ dùng một vài cách thức mã hóa cho các giá trị ở mỗi cột dữ liệu và sau đó sẽ nén những cột dữ liệu này với các thư viện codec nổi tiếng như là zlib hoặc snappy. Một ví dụ điển hình như là các cột dữ liệu theo dạng string thường thì sẽ được mã hóa theo dạng dictionary encoding khi mà các giá trị string riêng biệt của cột đó được chứa trong một dictionary và các giá trị ở mỗi cột sẽ có một pointer nhỏ chỉ về giá trị trong dictionary này. Từ đó, dictionary encoding có thể giảm dung lượng chứa cho từng giá trị dữ liệu ở mỗi cột do không cần phải sao chép các giá trị trùng lặp nhiều lần. Do ORC sẽ nén các giá trị mã hóa này sau khi mã hóa xong nên mỗi stripe ở ORC đều được tối ưu hóa đáng kể.
Đồng thời, để giúp cho các big data compute engines như là Presto và Spark có thể truy vấn dữ liệu một cách hiệu quả, mỗi ORC stripe thường sẽ chứa index cho mỗi 10k dòng dữ liệu cùng với giá trị nhỏ nhất và lớn nhất ở mỗi cột. Từ đó mà các compute engines có thể bỏ qua các stripe không cần thiết nếu SQL query có các điều kiện sàng lọc ở một cột. Do đa phần thì các data engineers chỉ cần truy vấn vài cột trong các bảng dữ liệu ở data warehouse, việc dùng column-storage file format giúp cải thiện hiệu suất đáng kể so với row-storage file format. Các bạn có thể tham khảo thêm về specification của Apache ORC ở đây và có thể tham khảo thêm cách mà các đội ngũ kỹ sư ở Facebook áp dụng ORC như thế nào để giúp scale data warehouse của họ tới 300PB vào năm 2014 tại đây
Code & Tools
This Week Sponsors
POPS is a creative, innovative & hyper-growth working environment where storytelling meets technology.
POPS is the leading digital entertainment company in Southeast Asia. With over 12 years in entertainment, we provide thousands of exclusive, high-quality, carefully curated local and international contents and bring a unique entertainment experience through POPS Original series, concerts, movies, comics, esports and more.
We are on a journey to find talents who are passionate about technology and love to develop POPS APP the digital entertainment product with the latest technologies such as: OTT, Video On Demand, Microservices, etc. to give end users in the region great experiences with an all-inclusive digital entertainment platform. 
Góc Tuyển Dụng
Quotes
“How did you know so much about computers? I didn’t, it was the first one”
- Grace Hopper
Did you enjoy this issue?
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.
Powered by Revue
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam