Introduction

Trong phần 2, chúng ta đã nắm được một kĩ thuật cơ bản và quan trọng để tạo ra search-engine, đó chính là kĩ thuật tách chữ (Tokenize), thông qua 2 phương pháp chính là N-gram và Morphological Analysis. Nhờ có kĩ thuật này mà văn bản gốc sẽ được bóc tách thành các kí tự, sau đó sẽ được lưu trữ dưới dạng Inverted Index như đã giới thiệu ở phần 1.

Trong bài viết này, chúng ta sẽ tìm hiểu là làm thế nào, mà khi được cung cấp đầu vào là một chuỗi truy vấn (query string), search engine sẽ cung cấp được cho chúng ta kết quả phù hợp nhất. Về cơ bản, để tìm kiếm bên trong một khối dữ liệu khổng lồ đã được index dưới dạng “Inverted Index”, search-engine sẽ sử dụng “Boolean Logic”.

Boolean Logic và tại sao Search Engine lại sử dụng Boolean Logic

Khi nhắc đến Boolean Logic, các bạn sẽ hình dung ra trong đầu những hình ảnh như thao tác AND/OR/XOR với bit, mạch logic trong điện tử số, hay biểu đồ ven. Đối tượng thao tác của Boolean Logic có thể là bit, cổng logic, hay là tập hợp (set). Trong bài này, Boolean Logic sẽ được nhắc đến với đối tượng là tập hợp (set), và hình ảnh dễ hình dung nhất khi thao tác với đối tượng này chính là biểu đồ Ven.

Để tìm hiểu mối liên quan giữa Boolean Logic và Search Engine, chúng ta hãy thử hình dung cơ chế của Search Engine. Khi được cung cấp một chuỗi truy vấn (query string), việc đầu tiên Search Engine sẽ phải sử dụng Parser module để bóc tách chuỗi truy vấn này theo một ngữ pháp đã được qui định trước, để tạo thành các token sử dụng cho logic tìm kiếm. Việc sử dụng Parser này cũng giống như compiler hay intepreter sẽ sử dụng các cú pháp đã được định nghĩa trước của một ngôn ngữ bất kỳ để dịch một đoạn code ra mã máy hoặc là bytecode. Ngữ pháp qui định trước càng phức tạp, không chỉ dẫn đến việc parse chuỗi truy vấn trở nên phức tạp hơn, việc viết ra một câu truy vấn phức tạp hơn (ảnh hưởng đến người dùng), mà còn khiến logic tìm kiếm cũng trở nên phức tạp, qua đó làm giảm hiệu suất của việc tìm kiếm. Chính vì thế mà việc tận dụng một ngữ pháp gần giống với Boolean Logic không những sẽ giúp giữ cho độ phức tạp khi parse query string ở mức thấp, mà nó còn giúp cho người dùng tạo ra những câu truy vấn dễ hiểu hơn.

Sử dụng Boolean Logic trong Search Engine

Boolean logic sử dụng trong Search Engine thường sẽ gồm 3 phép toán chính là AND, NOT và OR Hãy trở lại ví dụ gần giống trong phần 1, chúng ta có 5 documents {D1, D2, D3, D4, D5} đã được index như sau:

1
2
3
4
5

D1 = "This is first document"
D2 = "This is second one"
D3 = "one two"
D4 = "This one is great"
D5 = "This two is great!"

1
2
3
4
5
6
7

"this" => {D1, D2, D4, D5}
"is" => {D1, D2, D4, D5}
"first" => {D1}
"document" => {D1}
"second" => {D2}
"one" => {D2, D3, D4}
"two" => {D3, D5}

Giả sử chúng ta muốn query một câu truy vấn như sau : “This one”. Sử dụng Morphological Analysis đã giới thiệu trong phần 2, chúng ta sẽ tách câu truy vấn đó thành 2 token là “This” và “one”. Bỏ qua yếu tố chữ hoa và chữ thường, thì “This” đã được index {D1, D2, D4, D5}, và “one” đã được index {D2, D3, D4}.

Thông thường để cho dễ hiểu và phù hợp với logic của người dùng, thì space sẽ tương đương với logic AND, hay là việc tìm kiếu “This one” sẽ tương đương với kết tìm kiếm “This” AND với kết quả tìm kiếm “one”. Hay như trong ví dụ này thì kết quả tìm kiếm sẽ là kết quả AND của 2 set {D1, D2, D4, D5} và {D2, D3, D4}. Kết quả này có thể thấy dễ dàng là {D2, D4}

1

{D1, D2, D4, D5} OR {D2, D3, D4} = {D1, D3, D5}

1
2
3

Độ phức tạp của parse query string(1) 
+ Độ phức tạp của Index lookup(2) 
+ Độ phức tạp của thao tác boolean Logic dựa trên kết quả của Index lookup(3)

(1) thường sẽ không lớn do query string do user input khá ngắn, và trong trường hợp query string được generate phức tạp khi sử dụng lucene hoặc solr, thì việc sử dụng boolean logic rất đơn giản cũng làm độ phức tạp khi parse query string là không cao.

(2) Độ phức tạp của Index lookup tương đương với việc tìm kiếm giá trị của một key trong Hash table, chỉ khác là trên HDD, tuy nhiên so sánh với việc tìm kiếm trên BTree của MySQL thì performance của xử lý này là hoàn toàn vuợt trội.

(3) Thao tác này có thể được optimize rất nhiều dựa vào các lý thuyết tập hợp, hay các thư viện toán học cho big number.

Như vậy chúng ta có thể thấy bài toán tìm kiếm ban đầu đã được đưa về 3 bài toán nhỏ hơn, dễ optimize hơn.

Kết luận

Bài viết đã giới thiệu về việc sử dụng Boolean Logic trong Full Text Search Engine. Qua đó các bạn chắc đã hình dung ra phần nào khi các bạn gõ một câu lệnh tìm kiếm vào ô tìm kiếm của Google, những gì sẽ xảy ra đằng sau (mặc dù trên thực tế những gì google làm sẽ phức tạp hơn rất nhiều).

Tham khảo:

• Make Findspot

Giới thiệu

Các bạn là fan của tính toán phân tán chắc hẳn đều biết Werner Vogels (CTO của amazon) cũng như trang blog All Things Distributed của ông. Một trong những loạt bài viết mà cá nhân tôi rất thích là loạt bài viết có tựa đề: Back-to-Basic của Vogels. Trong loạt bài viết này, Vogels giới thiệu những paper nổi tiếng mà những người làm tính toán phân tán cần đọc và tất cả đều hết sức cơ bản.

Lấy cảm hứng từ trùm bài viết đấy, mình quyết định sẽ viết trùm bài có tựa đề “Trở lại cơ bản” tổng hợp lại những kiến thức cơ bản, trước hết là để cho bản thân và sau đấy để là để chia sẻ cho mọi người (có những thứ bạn nghĩ là cơ bản nhưng không phải ai cũng biết ;) ).

Bài viết tuần này sẽ nêu khái lược khái niệm độ tin cậy, cách tính độ tin cậy.

Độ tin cậy là gì?

Độ tin cậy có thể hiểu là độ bền của sản phẩm hoặc dịch vụ . Sản phẩm (dịch vụ) của bạn càng bền, chạy càng lâu mà không hỏng hóc gì, thì độ bền của sản phẩm càng cao, và do đó độ tin cậy vào sản phẩm của bạn nói riêng và của người dùng nói chung vào sản phẩm càng cao. Đối với dịch vụ (cloud, website) thì độ tin cậy có thể đo bằng thời gian hệ thống sẵn sàng phục vụ bạn (không bị dừng vì sự cố hay hỏng hóc).

Với cách hiểu trên, một vấn đề đặt ra là làm thế nào cân đo đong đếm độ tin cậy. Ví dụ khi một hãng phần cứng bán cho bạn 1 chiếc ổ cứng và họ bảo đảm với bạn rằng phần cứng của họ có độ tin cậy cao, thì họ dựa vào điều gì để nói như vậy?

Các hãng bán máy tính đều đưa ra chế độ bảo hành cho sản phẩm của họ, với lời quảng cáo rằng trong thời gian bảo hành họ sẵn sàng thay thế sản phầm của họ nếu sản phẩm của họ bị lỗi. Độ tin cậy như vậy có thể đo bằng thời gian bảo hành. Qua thời gian bảo hành, sản phẩm có thể bị hỏng hóc và hãng sẽ không chịu trách nhiệm cho những hỏng hóc đó. Ví dụ máy tính apple thường có thời gian bảo hành 1 năm.

Đối với các sản phẩm là dịch vụ trên internet, người ta thường đưa ra các Service Level Agreements (SLA) hoặc Service Level Objectives (SLO) để quảng cáo cho độ tin cậy của dịch vụ, và họ sẵn sàng bồi thường cho khách hàng nếu sản phẩm của họ không đáp ứng được những “đồng ý” này. Amazon EC2 cam kết trong Amazon SLA rằng họ đảm bảo EC2 99.95% có uptime thời gian trong 1 tháng. Nếu họ không đáp ứng điều kiện này, họ sẽ có chính xác bồi thường cho người dùng. Giống như vậy, các công ty dịch vụ cloud khác nhưng rackspace cũng đều có Rackspace SLA của riêng họ. Ngược lại việc hãng cloud như heroku không có một đảm bảo SLA nào ngoài Heroku Promise, làm cho độ tin tưởng vào sản phẩm của họ giảm hẳn.

Đo độ tin cậy thế nào?

Chắc chắn amazon sẽ không ngu gì đưa ra 1 cam kết không tưởng 100% uptime, nhưng họ cũng không thể đưa ra con số quá thấp được vì điều đó sẽ làm giảm khả năng cạnh tranh với các công ty khác. Apple cũng không dại gì đưa ra số năm bảo hành cao hơn vì nó sẽ làm giảm lợi nhuận của họ. Vậy các hãng đưa ra các con số trên như thế nào?

Mỗi công ty cung câp dịch vụ sẽ có nhiều chỉ số riêng để đánh giá và tính toán trước khi đưa ra con số của dịch vụ của họ, tuy vậy các tính toán đề dựa vào cách tính cơ bản trình bày dưới đây.

Để tính toán độ tin cậy, ta chia hệ thống làm 2 trạng thái tương ứng như được ghi trong SLA:

• Thời gian phục vụ như cam kết
• Thời gian dừng dịch vụ (do hỏng hóc)

Hệ thống thay đổi giữa 2 trạng thái này là: hỏng hóc và phục hồi. Để đo được độ tin cậy của hệ thống, ta cần đo được thời gian hệ thống ở 1 trong 2 trạng thái trên. Một hệ thống được xây dựng từ nhiều modules, do vậy độ tin cậy của hệ thống sẽ liên quan đến độ tin cậy của từng module trong hệ thống. Trước hết ta tìm hiểu các chỉ số tương ứng với 2 trạng thái trên.

Độ tin cậy của 1 thành phần (module) được đo bằng thời gian phục vụ liên tục từ lúc bắt đầu được sử dụng đến lúc hỏng hóc gọi là MTTF (Mean Time to Failure). Nghịch đảo của con số này chính là tỉ lệ hỏng hóc FIT (Failures in time) và thường được đo bằng số hỏng hóc / 1 tỷ giờ vận hành.

Độ hỏng hóc (hỏng nặng hay nhẹ) được đo bằng MTTR (Mean Time To Repair) hay thời gian từ lúc hệ thống hỏng hóc cho đến lúc được phục hồi.

Thời gian giữa 2 lần hỏng hóc

MTBF (Mean Time Between Failures) = MTTF + MTTR

Tính sẵn sàng của 1 modules (Module availability) được đo bởi thời gian hoạt động cho đến lúc hỏng hóc trên tổng thời gian giữa 2 lần hỏng hóc:

Module Availability = MTTF / (MTTF + MTTR)

Từ công thức trên, ta có thể đo được tính sẵn sàng của hệ thống dựa vào tính tin cậy của từng module dùng để xây dựng nên hệ thống.

Áp dụng

Tính MTTF của 1 hệ thống Giả sử ta có 1 hệ thống được xây dựng bởi

• 10 đĩa cứng, mỗi đĩa có MTTF 1000000 giờ
• 1 bộ điều khiển SCSI có MTTF 500000 giờ
• 1 bộ nguồn có MTTF 200000 giờ
• 1 quạt làm mát có MTTF 200000 giờ
• 1 cáp SCSI có MTTF 1000000 giờ.

Hãy tính MTTF của cả hệ thống.

Lời giải

Tỉ lệ hỏng hóc của toàn hệ thống:

Failure rate = 10 / 1000000 + 1/500000 + 1/200000 + 1/200000 + 1/1000000
             = (10 + 2 + 5 + 5 + 1) / 1000000 = 23 / 1000000 = 23000 / 1000000000

hệ thống sẽ có tỉ lệ hỏng hóc 23000FIT. MTTF của hệ thống sẽ bằng nghịch đảo con số trên

MTTF = 1000000000 / 230000 = 43450 giờ (khoảng 5 năm)

Từ con số trên, ta có thể thấy mặc dù MTTF của từng module khá lớn, nhưng MTTF của cả hệ thống nói chung chỉ là 5 năm. MTTF của các module trong máy tính cá nhân có lẽ thấp hơn nhiều. Có lẽ vì vậy mà các công ty bán phần cứng không bao giờ đưa ra thời gian bảo hành lâu quá 2, 3 năm! Từ con số này các công ty làm dịch vụ internet cũng phải có cách lập kế hoạch bảo trì thay mới máy chủ để đảm bảo tính tin cậy của dịch vụ của mình. Trong trường hợp công ty mình, tất cả các máy chủ đều được thay mới sau 5 năm (Và giờ bạn đã hiều tại sao phải thay và con số 5 này từ đâu ra :) ).

Kết luận

Qua bài viết này, chúng ta đã có thể lý giải và cân đong đo đếm được độ tin cậy của hệ thống dựa trên các chỉ số MTTF, MTTR, FIT, cũng như lý giải được ý nghĩa của SLA của 1 dịch vụ.

Tham khảo

• Computer Architecture A quantitative Approach

Introduction

Trong phần 1, chúng ta đã tìm hiểu sơ qua về khái niệm Full Text Search, cũng như về Inverted Index. Qua bài viết đầu tiên, các bạn đã nắm được tại sao Inverted Index lại được sử dụng để tăng tốc độ tìm kiếm trong một “Full Text Database”. Đồng thời ở ví dụ của phần một, các bạn cũng đã thấy, để tạo ra Inverted Index thì các bạn phải tách được một string ra thành các term, sau đó sẽ index string đó theo term đã tách được. Chính vì thế việc tách string, hay còn gọi là Tokenize là một bài toán con quan trọng nằm trong bài toán lớn của Full Text Search. Ở bài này, chúng ta sẽ tìm hiểu về 2 kĩ thuật Tokenize cơ bản là:

• N-Gram
• Morphological Analysis

N-gram

N-gram là kĩ thuật tokenize một chuỗi thành các chuỗi con, thông qua việc chia đều chuỗi đã có thành các chuỗi con đều nhau, có độ dài là N. Về cơ bản thì N thường nằm từ 1~3, với các tên gọi tương ứng là unigram(N==1), bigram(N==2), trigram(N==3). Ví dụ đơn giản là chúng ta có chuỗi “good morning”, được phân tích thành bigram:

1

"good morning" => {"go", "oo", "od", "d ", " m", "mo", "or", "rn", "ni", "in", "ng"}

Từ ví dụ trên các bạn có thể dễ dàng hình dung về cách thức hoạt động của N-gram. Để implement N-gram, chỉ cần một vài ba dòng code như sau, như ví dụ viết bằng python như sau:

1
2
3
4
5
6

def split_ngram(self, statement, ngram):
    result = []
    if(len(statement) >= ngram):
      for i in xrange(len(statement) - ngram + 1):
        result.append(statement[i:i+ngram])
    return result

Morphological Analysis

Morphological Analysis, rất may mắn có định nghĩa trên [wikipedia](http://vi.wikipedia.org/wiki/H%C3%ACnh_th%C3%A1i_h%E1%BB%8Dc_(ng%C3%B4n_ng%E1%BB%AF_h%E1%BB%8Dc) bằng tiếng Việt. Định nghĩa khá dài dòng, các bạn có thể xem bằng [Tiếng Anh](http://en.wikipedia.org/wiki/Morphology_(linguistics) Về cơ bản Morphological Analysis (từ bây giờ mình sẽ gọi tắt là MA), là một kĩ thuật phổ biến trong xử lý ngôn ngữ tự nhiên (Natural Language Processing). Morphological chính là “cấu trúc” của từ, như vậy MA sẽ là “phân tích cấu trúc của từ”, hay nói một cách rõ ràng hơn, MA sẽ là kĩ thuật tokenize mà để tách một chuỗi ra thành các từ có ý nghĩa. Ví dụ như cũng cụm từ “good morning” ở trên, chúng ta sẽ phân tích thành:

1

"good morning" => {"good", "morning"}

Để có được kết quả phân tích như trên, ngoài việc phải sở hữu một bộ từ điển tốt (để phân biệt được từ nào là có ý nghĩa, và thứ tự các từ thế nào thì có ý nghĩa), MA phải sử dụng các nghiên cứu sâu về xử lý ngôn ngữ tự nhiên, mà mình sẽ không đi sâu ở đây. Thông thường các công ty lớn sở hữu các search engine của riêng họ(như Yahoo, Google, Microsoft..) sẽ có các đội ngũ nghiên cứu để tạo ra nhiều bộ thư viện MA riêng của họ, thích hợp với nhiều ngôn ngữ. Ngoài ra chúng ta cũng có thể sử dụng các bộ thư viện được open source, hoặc sử dụng các package có sẵn trong các bộ full text search engine mà tiêu biểu là lucene.

Mở rộng

Các bạn đọc đến đây chắc hẳn sẽ có suy nghĩ, để phân tách chuỗi, thì rõ ràng phân tích theo MA là quá hợp lý rồi, tại sao lại cần N-gram làm gì? Như mình đã nói ở trên, để xây dựng MA thì cần một bộ từ điển tốt, để giúp cho máy tính có thể phân biệt được các từ có nghĩa. Như thế nào là một từ điển tốt, thì về cơ bản, từ điển tốt là từ điển chứa càng nhiều từ (terms) càng tốt. Tuy nhiên ngôn ngữ thì mỗi ngôn ngữ lại có đặc trưng riêng, và không ngừng mở rộng, không ngừng thêm các từ mới. Việc chỉ sử dụng MA sẽ gây ra một tác dụng phụ là có rất nhiều từ không/chưa có trong từ điển, dẫn đến không thể index, và do đó sẽ không thể tiến hành tìm kiếm từ đó được.

Vậy cách giải quyết như thế nào? Cách giải quyết tốt nhất là chúng ta sẽ kết hợp(hybrid) cả MA và N-gram. Cách hybrid thế nào thì sẽ tuỳ vào ngôn ngữ/ hoàn cảnh sử dụng, và cả performance cần thiết nữa. Về cơ bản thì những từ nào khó/không có thể phân tích được bằng MA, thì chúng ta sẽ dùng N-gram.

Kết luận

Qua bài viết lần này, các bạn đã hiểu thêm về 2 kĩ thuật tách từ (tokenize) cơ bản là N-gram và MA.

Sử dụng 2 kĩ thuật này như thế nào để index dữ liệu đầu vào, sẽ được giới thiệu trong các bài viết sắp tới.