Elasticsearch from The Bottom Up

8
Nguyễn Dức Hải viết hơn 5 năm trước

Introduction

Elasticsearch là một công cụ tìm kiếm dựa trên nền tảng Apache Lucene. Nó cung cấp một bộ máy tìm kiếm dạng phân tán, có đầy đủ công cụ với một giao diện web HTTP có hỗ trợ dữ liệu JSON. Elasticsearch được phát triển bằng Java và được phát hành dạng nguồn mở theo giấy phép Apache.

Elasticsearch đã cung cấp các APIs để chúng ta sử dụng nó một cách dễ dàng. Tuy nhiên để sử dụng nó hiệu quả chúng ta cần hiểu cách mà nó hoạt động, cũng giống như việc một tay đua giỏi thì cũng phải có hiểu động cơ của chiếc xe đó hoạt động thế nào để ra những quyết định đúng đắn :) Bài viết này sẽ trình bày một chút kiến thức về nền tảng của Elasticsearch, cấu trúc dữ liệu mà nó sử dụng.

Chúng ta sẽ bắt đầu với một cấu trúc index đơn giản: inverted index. Đây là một cấu trúc dữ liệu hiệu quả cho việc đánh index, rất dễ sử dụng và dễ hiểu. Cấu trúc này đã được thư viện Apache Lucene triển khai và có khả năng tùy biến cao. Bài viết sẽ không diễn giải chi tiết về việc Lucene tạo index mà chỉ giới thiệu về cách inverted index được tạo và cách sử dụng nó.

Bắt đầu từ "bottom", chúng ta sẽ tìm hiểu một số vấn đề:

  • Thực hiện tìm kiếm trên inverted index thế nào?
  • Một số kiểu search mà inverted index có thể thực hiện và không thể thực hiện, cách giải quyết các kiểu search không dựa trên string prefix
  • Tại sao việc xử lý văn bản đầu vào rất quản trọng
  • Index được tạo ra và lưu trữ, thực hiện việc tìm kiếm thế nào
  • Cấu trúc của Lucene Index
  • Elasticsearch shard và index

Inverted Indexes and Index Terms

alt text

Bắt đầu, chúng ta có 3 văn bản đơn giản: "Winter is comming", "Ours is the fury", "The choice is your" sau một số kĩ thuật xử lý văn bản đơn giản: chuẩn hóa lowercase, xóa bỏ từ dừng (stop word), stemming,... Ta sẽ chọn được các term có giá trị (trong ví dụ có các term: choice, comming. fury, your, the, is, winter)

Sau đó các term này sẽ được inverted index ánh xạ tới những document mà nó chứa. Bảng inverted index sẽ sắp xếp các term theo thứ tự từ điển, vì vậy chúng ta có thể dễ dàng tìm kiếm các term và lấy được danh sách các văn bản mà nó xuất hiện.

Một truy vấn tìm kiếm đơn giản với nhiều term sẽ được thực hiện bằng cách tìm kiếm tất cả các văn bản mà nó xuất hiện với các phép AND và OR để lọc các văn bản. Những kiểu truy vấn phức tạp hơn cũng bắt đầu tìm kiếm dựa trên bảng inverted index để chọn ra những văn bản phù hợp sau đó tiếp tục tìm kiếm.

Như vậy, một index term sẽ là một đơn vị của việc tìm kiếm. Các term được tạo ra sẽ quyết định hiệu quả của việc tìm kiếm. Tuy nhiên, việc tìm kiếm như trên chỉ hiệu quả khi chúng ta tìm kiếm các term từ những chữ cái bắt đầu (prefix). Việc tìm một xâu con trong term sẽ trở nên tốn kém hơn nhiều khi độ phức tạp là O(n.k), trong khi việc tìm kiếm với prefix chỉ là O(log(n))

Để giải quyết vấn đề trên, có một số cách để tìm kiếm dựa trên prefix:

  • Tìm term kết thúc với từ khóa “tastic” ta có thể đảo ngược term “fantastic” “citsatnaf” và tìm kiếm với từ khóa “citsat”
  • Tìm kiếm chuỗi con bằng cách tách term thành các “n-grams”. Ví dụ: “your” với 3-grams sẽ tách thành “^yo”, “you”, “our”, “urs”, “rs$” Tọa độ địa lý, ví dụ: (60.6384, 6.5017) có thể chuyển thành một mã hash: “u4u8gyyk” xâu hash càng dài sẽ càng dễ dàng cho việc tìm kiếm.
  • Sử dụng thuật toán phonetic matching sẽ phù hợp với việc tìm kiếm tên riêng người. Ví dụ: thuật toán Metaphone sẽ chuyển Smith thành {“SMO”, “XMT”} và Schmidt thành {“XMT”, “SMT”}
  • Khi làm việc với các dữ liệu kiểu số (và nhãn thời gian) Lucene sẽ tự động tạo ra các term với độ chính xác khác nhau theo kiểu trie-like. Ví dụ: số 123 có thể chuyển thành các term “1”-hundreds, “12”-tens, “123”
  • Để tìm kiếm term phù hợp khi người dùng đánh máy sai, Tìm kiếm term gần nhất với input của người dùng , một hàm tính khoảng cách “Levenshtein” sẽ được tạo ra và duyệt qua từ điển để tìm từ gần nhất. Việc tính toán khá phức tạp nên sẽ không được trình bày tại tài liệu này.

Xây dựng index

Khi tạo inverted index ta cần ưu tiên một số vấn đề: tốc độ tìm kiếm, khối lượng của index, tốc độ index và thời gian cập nhật index.

Tốc độ tìm kiếm và khối lượng của index liên quan phụ thuộc vào nhau: Khi tìm kiếm trên một index nhỏ, ta chỉ cần xử lý một lượng dữ liệu nhỏ có thể lưu trữ tại bộ nhớ trong. Vì vậy, cả tốc độ tìm kiếm và tốc độ index đều phụ thuộc vào tính nhỏ gọn của index.

Để giảm khối lượng của index, rất nhiều kĩ thuật nén được sử dụng. Ví dụ: khi lưu trữ dữ liệu, Lucene thực hiện các thủ thuật như mã hóa delta (delta-encoding) (ví dụ: [42,100,666] sẽ được lưu thành [42,58,566]), sử dụng các biến số dạng byte (các số nhỏ có thể lưu trữ trong một byte),..

Việc giữ cho dung lượng của index nhỏ cũng đồng nghĩa với việc sẽ khó khăn khi cập nhật các index (tốn nhiều chi phí hơn). Trên thực tế, Lucene sẽ không update các index đã được tạo: Các index đã được tạo ra là immutable (bất biến). Index này khá khác với cấu trúc B-trees có thể cập nhật khá dễ dàng. Đối với việc xóa dữ liệu, khi ta xóa một document trong elasticsearch index, document đó sẽ được đánh dấu là xóa trong một file bitmap. Sau khi xóa cấu trúc của index cũng sẽ không được cập nhật.

Kết quả là, việc update một document sẽ là xóa document đó và thêm document update vào cuối index. Cần chú ý rằng, việc cập nhật này là hết sức tốn kém, vì vậy ta không nên lưu trữ các loại dữ liệu thường xuyên thay đổi trên Lucene index. Khi một document mới được thêm vào, những thay đổi từ index sẽ được đưa vào buffer trong bộ nhớ trong (memory) cuối cùng được flush ra bộ nhớ ngoài (disk). Các files được tạo sẽ trở thành một phân đoạn chỉ mục (index segments)

Index segments

Các index segment tạo ra là bất biến, có thể coi là một “mini index”. Khi thực hiện thao tác tìm kiếm, Lucene tìm kiếm trên tất cả segment, lọc bỏ các segment đã được đánh dấu là xóa, sau đó gộp các kết quả tìm kiếm lại thành một. Ta có thể thấy rằng, các segment sẽ ngày một tăng lên và không thể xóa đi. Để quản lí các phân đoạn này, Lucene sẽ gộp các segment lại theo một số điều kiện khi một segment mới được thêm vào. Khi các segment đã được gộp lại, những documents được đánh dấu là xóa sẽ được loại trừ. Điều đó cũng lí giải tại sao việc thêm nhiều documents cũng không khiến khối lượng của index lớn hơn quá nhiều.

Trước khi segment được flush xuống đĩa cứng, những thay đổi được lưu lại tại bộ đệm trên bộ nhớ trong. Ở phiên bản cũ (Lucene <2.3), mọi document mới được thêm vào đều được lưu lại tại mỗi segment rất nhỏ của riêng nó và sẽ được gộp lại khi flush xuống đĩa cứng. Tại các phiên bản mới hơn hiện tại, Lucene tạo ra một DocumentWriter, nó sẽ tạo ra một segment lớn hơn trong bộ đệm gồm nhiều document. Lucene 4 có thể xử lý mỗi segment tại một luồng, nhờ đó có thể tăng tốc độ index và flush các segment một cách đồng thời. (Trước đó mỗi khi indexing cần phải đợi quá trình flush hoàn tất)

Elasticsearch index

Một Elasticsearch index được chia thành một hoặc nhiều shard(mảnh), mỗi mảnh có thể có một hoặc nhiều bản sao (replica). Mỗi mảnh này là một Lucene index độc lập. Điều đó có nghĩa là mỗi Elasticsearch index được tạo thành từ nhiều Lucene Index tương ứng với nhiều index segment. Khi chúng ta tìm kiếm trên một Elasticsearch index, việc tìm kiếm được thực hiện trên tất cả các shard cho tới từng index segment. Điều này cũng đúng khi thực hiện việc tìm kiếm trên nhiều Elasticsearch index. Việc tìm kiếm trên hai elasticsearch index với một shard mỗi index cũng giống như việc tìm kiếm trên 1 index có 2 shard. Trong cả hai trường hợp, đều có 2 Lucene index được thực hiện tìm kiếm.

Một “shard” là một đơn vị của việc mở rộng Elasticsearch. Mỗi document được thêm vào index, nó được điều hướng tới một shard. Mặc định, việc này sẽ được thực hiện theo giải thuật round robin, dựa trên mã hash của document id.

alt text

Transaction

Khái niệm về quản trị giao dịch (transaction) khi nhiều bên cùng tham gia việc thêm sửa xóa dữ liệu chỉ được Apache Lucene xử lý. Elasticsearch không thực hiện việc này. Những hành động thêm mới và thực hiện cập nhật sẽ không cùng đồng thời được thực hiện trên tất cả các node.

Việc đảm bảo tính cô lập (isolation) của dữ liệu và trong suốt giữa các segment, caches Lucnene index giữa các node trong một hệ thống phân tán là vô cùng khó khăn. Thay vì đảm bảo các tính chất trên, Elasticsearch chỉ ưu tiên nhất về tốc độ tìm kiếm.

Elasticsearch sẽ lưu lại "transaction log": thời điểm những document được thêm mới và cập nhật. Việc ghi log transaction này có chi phí nhỏ hơn nhiều so với việc cập nhật thẳng vào các segment. Ta có thể lưu lại bản log này trên bộ nhớ ngoài, nơi mà dữ liệu đảm bảo hơn việc lưu ở buffer trong bộ nhớ trong có thể mất bất cứ lúc nào. Elasticsearch cũng cho phép chúng ta tùy chỉnh tính nhất quán của dữ liệu: luôn luôn xây cập nhật index trước khi thực hiện tìm kiếm.

Tổng kết

Bài viết đã trình bày cơ bản về cách Elasticsearch tạo index và thực hiện tìm kiếm đơn giản. Bài tiếp theo sẽ trình bày về cách phân chia dữ liệu (shard và replica), tìm kiếm và tổng hợp dữ liệu trên các node của Elasticsearch.

References

https://www.elastic.co/blog/found-elasticsearch-from-the-bottom-up

Bình luận


White
{{ comment.user.name }}
Hay Bỏ hay
{{ comment.like_count}}
White

Nguyễn Dức Hải

25 bài viết.
0 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}

  Cùng một tác giả


{{like_count}}

kipalog

{{ comment_count }}

Bình luận


White
{{userFollowed ? 'Following' : 'Follow'}}
25 bài viết.
0 người follow

 Đầu mục bài viết

 Cùng một tác giả