5 vấn đề về tìm kiếm vectơ cứng và cách chúng tôi giải quyết chúng trong Apache Cassandra

Tìm kiếm vectơ là một thành phần quan trọng của công cụ AI tổng quát do cách tạo thế hệ tăng cường truy xuất (RAG) như thế nào BÙNG PHÁT giúp LLM kết hợp thông tin cập nhật, tùy chỉnh đồng thời tránh ảo giác . Đồng thời, tìm kiếm vectơ là một tính năng, không phải là sản phẩm – bạn cần truy vấn vectơ vì chúng liên quan đến phần còn lại của dữ liệu, không tách biệt và bạn không cần phải xây dựng quy trình để đồng bộ hóa phần còn lại của dữ liệu. data với một kho lưu trữ vector để làm điều đó.

Năm 2023 đã chứng kiến sự bùng nổ của các sản phẩm và dự án tìm kiếm vectơ, khiến việc lựa chọn trong số đó trở thành một nỗ lực nghiêm túc. Khi nghiên cứu các phương án, bạn sẽ cần xem xét các vấn đề khó khăn sau đây và các phương pháp khác nhau để giải quyết chúng. Ở đây, tôi sẽ hướng dẫn bạn vượt qua những thách thức này và mô tả cách DataStax giải quyết chúng để chúng tôi triển khai tìm kiếm vectơ cho DataStax Astra DB và Apache Cassandra.

Tổng quan về nội dung

• Lời nguyền của chiều
• Vấn đề 1: Mở rộng quy mô
• Vấn đề 2: Thu gom rác hiệu quả
• Thanh bên: Khối lượng công việc ứng dụng đám mây
• Vấn đề 3: Đồng thời
• Vấn đề 4: Sử dụng đĩa hiệu quả
• Vấn đề 5: Khả năng kết hợp
• Gói (lại

Lời nguyền của chiều

Cốt lõi của những vấn đề khó khăn này nằm ở cái mà các nhà nghiên cứu gọi là “ lời nguyền của chiều .” Điều này có nghĩa trong thực tế là các thuật toán hoạt động để tìm kiếm vectơ chính xác trong không gian 2-D hoặc 3-D, như cây kd , sẽ tan rã khi bạn đạt đến kích thước 10 hoặc 100 hoặc 1000 trong vectơ của mình. Kết quả là không có lối tắt để tìm kiếm độ tương tự chính xác với các vectơ nhiều chiều; để có được kết quả theo thời gian logarit, chúng ta cần sử dụng thuật toán lân cận gần nhất (ANN), thuật toán này mang đến những thách thức trong các lĩnh vực sau.

Vấn đề 1: Mở rộng quy mô

Nhiều thuật toán tìm kiếm vectơ được thiết kế cho các tập dữ liệu vừa với bộ nhớ trên một máy và đây vẫn là kịch bản duy nhất được thử nghiệm bởi ann-điểm chuẩn . (Các điểm chuẩn của Ann còn hạn chế việc kiểm tra nó ở một lõi duy nhất!) Điều này có thể ổn đối với công việc học tập với hàng triệu tài liệu hoặc hàng, nhưng đã nhiều năm rồi điều đó mới có thể được coi là đại diện cho khối lượng công việc trong thế giới thực.

Giống như bất kỳ miền nào khác, việc mở rộng quy mô yêu cầu cả sao chép và phân vùng, cũng như các hệ thống con để xử lý việc thay thế các bản sao đã chết, sửa chữa chúng sau khi phân vùng mạng, v.v.

Đây là một điều dễ dàng đối với chúng tôi: sao chép mở rộng quy mô là bánh mì và bơ của Cassandra và kết hợp điều đó với SAI mới trong Cassandra-5.0 (Lập chỉ mục đính kèm lưu trữ - xem CEP-7 về cách nó hoạt động và tài liệu SAI về cách sử dụng nó) đã cung cấp cho chúng tôi khả năng mở rộng quy mô mạnh mẽ một cách hiệu quả và miễn phí.

Vấn đề 2: Thu gom rác hiệu quả

Khi nói “thu gom rác”, ý tôi là loại bỏ thông tin lỗi thời khỏi chỉ mục - dọn sạch các hàng đã xóa và xử lý các hàng có giá trị vectơ được lập chỉ mục đã thay đổi. Điều này có vẻ không đáng nhắc đến – nó ít nhiều đã được giải quyết trong bốn mươi năm trong thế giới cơ sở dữ liệu quan hệ – nhưng các chỉ mục vectơ là duy nhất.

Vấn đề chính là tất cả các thuật toán mà chúng tôi biết cung cấp cả tìm kiếm có độ trễ thấp và kết quả có khả năng thu hồi cao đều dựa trên biểu đồ. Có rất nhiều thuật toán lập chỉ mục vector khác có sẵn – THẤT BẠI triển khai nhiều giải pháp trong số đó – nhưng tất cả đều quá chậm để xây dựng, quá chậm tìm kiếm hoặc đưa ra mức thu hồi quá thấp (và đôi khi cả ba giải pháp đó!) để trở thành một giải pháp có mục đích chung. Đó là lý do tại sao mọi cơ sở dữ liệu vectơ sản xuất mà tôi biết đều sử dụng chỉ mục dựa trên biểu đồ, trong đó đơn giản nhất là HNSW. Đồ thị Thế giới nhỏ có thể điều hướng theo cấp bậc là được giới thiệu bởi Yury Malkov và cộng sự vào năm 2016 ; bài báo khá dễ đọc và tôi đánh giá cao nó. Thông tin thêm về HNSW bên dưới.

Thách thức với các chỉ mục biểu đồ là bạn không thể tách nút cũ (liên quan đến vectơ) khi một hàng hoặc tài liệu thay đổi; nếu bạn làm điều đó nhiều lần, biểu đồ của bạn sẽ không còn có thể thực hiện mục đích hướng BFS (tìm kiếm theo chiều rộng) tới các khu vực có độ tương tự cao hơn với vectơ truy vấn.

Vì vậy, tại một thời điểm nào đó, bạn sẽ cần phải xây dựng lại các chỉ mục của mình để thực hiện việc thu thập rác này, nhưng khi nào—và làm cách nào—bạn sắp xếp nó? Nếu bạn luôn xây dựng lại mọi thứ khi thực hiện thay đổi, bạn sẽ tăng đáng kể số lần ghi vật lý được thực hiện; cái này được gọi là khuếch đại ghi. Mặt khác, nếu bạn không bao giờ xây dựng lại thì bạn sẽ phải thực hiện thêm công việc lọc ra các hàng lỗi thời tại thời điểm truy vấn (“đọc khuếch đại”).

Đây là một vấn đề khác mà Cassandra đã nghiên cứu trong nhiều năm. Vì các chỉ mục SAI được gắn vào vòng đời lưu trữ chính nên chúng cũng tham gia vào Cassandra sự nén chặt , làm tăng logarit các đơn vị lưu trữ để mang lại sự cân bằng lành mạnh giữa đọc và ghi.

Thanh bên: Khối lượng công việc ứng dụng đám mây

DataStax Astra DB xây dựng trên Apache Cassandra để cung cấp nền tảng cho khối lượng công việc ứng dụng đám mây.

Điều đó có nghĩa là khối lượng công việc:

• Đồng thời hàng nghìn đến hàng triệu yêu cầu mỗi giây, thường chỉ truy xuất một vài hàng mỗi yêu cầu. Đây là lý do tại sao bạn không thể chạy Netflix trên Snowflake, ngay cả khi bạn có đủ khả năng: Snowflake và các hệ thống phân tích tương tự được thiết kế để chỉ xử lý một số yêu cầu đồng thời, mỗi yêu cầu chạy trong nhiều giây đến vài phút hoặc thậm chí lâu hơn.

  
  

• Lớn hơn bộ nhớ Nếu tập dữ liệu của bạn vừa với bộ nhớ trên một máy thì việc bạn sử dụng công cụ nào gần như không quan trọng. Sqlite, MongoDB, MySQL – tất cả đều hoạt động tốt. Mọi thứ trở nên khó khăn hơn khi không phải như vậy – và tin xấu là các phần nhúng vectơ thường có kích thước vài KB hoặc lớn hơn một bậc so với các tài liệu cơ sở dữ liệu thông thường, do đó, bạn sẽ đạt được dung lượng lớn hơn bộ nhớ tương đối nhanh chóng.

  
  

• Cốt lõi của ứng dụng Nếu bạn không quan tâm liệu mình có bị mất dữ liệu hay không, vì dữ liệu đó không quan trọng lắm hoặc vì bạn có thể xây dựng lại dữ liệu đó từ nguồn bản ghi thực tế, thì một lần nữa, việc bạn sử dụng công cụ nào không quan trọng. Các cơ sở dữ liệu như Cassandra và Astra DB được xây dựng để giữ cho dữ liệu của bạn luôn sẵn sàng và bền vững bất kể điều gì.

Vấn đề 3: Đồng thời

Tôi đã đề cập ở trên rằng điều nổi tiếng ann-điểm chuẩn so sánh giới hạn tất cả các thuật toán vào một lõi duy nhất. Mặc dù điều này tạo ra một sân chơi bình đẳng nhưng nó cũng gây bất lợi cho những ai có thể tận dụng nguồn cải tiến phần cứng chính trong hai thập kỷ qua.

Một vấn đề liên quan là ann-benchmarks chỉ thực hiện một loại hoạt động tại một thời điểm: đầu tiên, nó xây dựng chỉ mục, sau đó truy vấn chỉ mục đó. Việc xử lý các bản cập nhật xen kẽ với các tìm kiếm là tùy chọn - và thậm chí có thể là một điểm yếu; nếu bạn biết rằng bạn không cần phải xử lý các bản cập nhật, bạn có thể đưa ra nhiều giả định đơn giản hóa có vẻ phù hợp trên các điểm chuẩn nhân tạo.

Nếu bạn quan tâm đến khả năng thực hiện nhiều thao tác đồng thời với chỉ mục của mình hoặc cập nhật chỉ mục sau khi được tạo, thì bạn cần xem xét sâu hơn một chút để hiểu cách thức hoạt động và những cân bằng liên quan.

Đầu tiên, tất cả các cơ sở dữ liệu vectơ có mục đích chung mà tôi biết đều sử dụng các chỉ mục dựa trên biểu đồ. Đó là vì bạn có thể bắt đầu truy vấn chỉ mục biểu đồ ngay khi vectơ đầu tiên được chèn vào. Hầu hết các tùy chọn khác yêu cầu bạn xây dựng toàn bộ chỉ mục trước khi truy vấn nó hoặc ít nhất thực hiện quét sơ bộ dữ liệu để tìm hiểu một số thuộc tính thống kê.

Tuy nhiên, vẫn có những chi tiết triển khai quan trọng ngay cả trong danh mục chỉ mục biểu đồ. Ví dụ: lúc đầu, chúng tôi nghĩ rằng mình có thể tiết kiệm thời gian bằng cách sử dụng triển khai chỉ mục HNSW của Lucene, giống như cách MongoDB Elastic và Solr thực hiện. Nhưng chúng tôi nhanh chóng biết được rằng Lucene chỉ cung cấp cấu trúc chỉ mục đơn luồng, không đồng thời. Nghĩa là, bạn không thể truy vấn nó khi nó đang được xây dựng (đó là một trong những lý do chính để sử dụng cấu trúc dữ liệu này!) cũng như không cho phép nhiều luồng xây dựng nó đồng thời.

Bài báo của HNSW gợi ý rằng phương pháp khóa chi tiết có thể hoạt động, nhưng chúng tôi đã làm tốt hơn và xây dựng chỉ mục không chặn. Đây là nguồn mở trong JVector .

JVector chia tỷ lệ cập nhật đồng thời một cách tuyến tính thành ít nhất 32 luồng. Biểu đồ này được chia tỷ lệ log trên cả trục x và y, cho thấy rằng việc nhân đôi số lượng luồng sẽ giảm một nửa thời gian xây dựng.

Quan trọng hơn, tính năng đồng thời không chặn của JVector mang lại lợi ích cho khối lượng công việc thực tế hơn bằng cách kết hợp các tìm kiếm với các bản cập nhật. Dưới đây là so sánh hiệu suất của Astra DB (sử dụng JVector) so với Pinecone trên các bộ dữ liệu khác nhau. Mặc dù Astra DB nhanh hơn khoảng 10% so với Pinecone đối với tập dữ liệu tĩnh, nhưng nó nhanh hơn từ 8 đến 15 lần trong khi lập chỉ mục dữ liệu mới. Chúng tôi đã chọn cấp nhóm tốt nhất hiện có với Pinecone (Loại nhóm: p2 và Kích thước nhóm: x8, với 2 nhóm trên mỗi bản sao) dựa trên đề xuất của họ để có thông lượng cao hơn và độ trễ thấp hơn. Pinecone không tiết lộ tài nguyên vật lý này tương ứng với những gì. Về phía Astra DB, chúng tôi đã chọn mô hình triển khai PAYG mặc định và không phải lo lắng về việc chọn tài nguyên vì nó không có máy chủ. Các thử nghiệm được thực hiện bằng cách sử dụng NoSQLBench .

Astra DB thực hiện điều này trong khi vẫn duy trì khả năng thu hồi và độ chính xác cao hơn ( F1 là sự kết hợp giữa thu hồi và chính xác ) :

Vấn đề 4: Sử dụng đĩa hiệu quả

Chúng tôi bắt đầu với Thuật toán lập chỉ mục đồ thị HNSW bởi vì nó nhanh chóng xây dựng chỉ mục, truy vấn nhanh, có độ chính xác cao và dễ triển khai. Tuy nhiên, nó có một nhược điểm nổi tiếng: nó đòi hỏi nhiều bộ nhớ.

Chỉ số HNSW là một chuỗi các lớp, trong đó mỗi lớp phía trên lớp cơ sở có số lượng nút nhiều hơn khoảng 10% so với lớp trước. Điều này cho phép các lớp trên hoạt động như một danh sách bỏ qua, cho phép tìm kiếm về 0 ở vùng lân cận bên phải của lớp dưới cùng chứa tất cả các vectơ.

Tuy nhiên, thiết kế này có nghĩa là (chung với tất cả các chỉ mục biểu đồ) bạn không thể nói "Bộ nhớ đệm trên đĩa sẽ cứu chúng ta" bởi vì, không giống như khối lượng công việc truy vấn cơ sở dữ liệu thông thường, mọi vectơ trong biểu đồ đều có cơ hội gần như bằng nhau có liên quan đến một tìm kiếm. (Ngoại lệ là các lớp trên mà chúng tôi có thể thực hiện bộ nhớ đệm.)

Đây là hồ sơ cung cấp tập dữ liệu vectơ 100M của các đoạn bài viết trên Wikipedia (khoảng 120GB trên đĩa) trông như thế nào trên máy tính để bàn của tôi với 64GB RAM, quay lại khi chúng tôi đang sử dụng Lucene:

Cassandra dành gần như toàn bộ thời gian để chờ đọc vectơ từ đĩa.

Để giải quyết vấn đề này, chúng tôi đã triển khai một thuật toán nâng cao hơn có tên DiskANN và mã nguồn mở nó dưới dạng một công cụ tìm kiếm vector nhúng độc lập, JVector . (Cụ thể, JVector triển khai phiên bản tăng dần của DiskANN được mô tả trong FreshDiskANN giấy.) Tóm lại, DiskANN sử dụng biểu đồ một cấp có cạnh dài hơn HNSW và cách bố trí vectơ và lân cận được tối ưu hóa để giảm IOPS của đĩa và giữ biểu diễn nén của vectơ trong bộ nhớ để tăng tốc độ tính toán tương tự. Điều này dẫn đến tăng gấp ba lần thông lượng của khối lượng công việc Wikipedia.

Đây là giao diện của HNSW so với DiskANN trong một kịch bản được nhúng hoàn toàn không có thành phần máy khách/máy chủ. Điều này đo tốc độ tìm kiếm tập dữ liệu Deep100M trong Lucene (HNSW) và JVector (DiskANN). Chỉ mục Lucene là 55GB, bao gồm chỉ mục và vectơ thô. Chỉ số JVector là 64GB. Việc tìm kiếm được thực hiện trên chiếc MacBook 24GB của tôi, có bộ nhớ bằng khoảng một phần ba lượng cần thiết để giữ chỉ mục trong RAM.

Vấn đề 5: Khả năng kết hợp

Khả năng kết hợp trong bối cảnh hệ thống cơ sở dữ liệu đề cập đến khả năng tích hợp liền mạch các tính năng và khả năng khác nhau một cách mạch lạc. Điều này đặc biệt quan trọng khi thảo luận về việc tích hợp một loại khả năng mới, như tìm kiếm vectơ. Các ứng dụng không phải đồ chơi sẽ luôn yêu cầu cả cổ điển CRUD các tính năng cơ sở dữ liệu cũng như tìm kiếm vector mới.

Hãy xem xét sự đơn giản Chatbot AI ứng dụng mẫu cho Astra DB. Đây gần như là một ứng dụng RAG thuần túy như bạn sẽ thấy, sử dụng tìm kiếm vectơ để hiển thị tài liệu phù hợp cho LLM nhằm trả lời các câu hỏi của người dùng. Tuy nhiên, ngay cả một bản demo đơn giản như thế này vẫn cần thực hiện các truy vấn “bình thường”, không phải vectơ tới Astra DB để truy xuất lịch sử hội thoại, lịch sử này cũng phải được đưa vào mọi yêu cầu tới LLM để nó có thể “ghi nhớ” những gì đã có. đã diễn ra. Vì vậy, các truy vấn chính bao gồm:

1. Tìm tài liệu (hoặc đoạn tài liệu) phù hợp nhất cho câu hỏi của người dùng
2. Truy xuất 20 tin nhắn cuối cùng từ cuộc trò chuyện của người dùng

Trong trường hợp sử dụng thực tế hơn, một trong những kỹ sư giải pháp của chúng tôi gần đây đã làm việc với một công ty ở Châu Á muốn thêm tìm kiếm ngữ nghĩa vào danh mục sản phẩm của họ nhưng cũng muốn bật tính năng so khớp dựa trên thuật ngữ. Ví dụ: nếu người dùng tìm kiếm [van bi “đỏ”] thì họ muốn giới hạn tìm kiếm ở các mục có mô tả khớp với thuật ngữ “đỏ”, bất kể các vectơ nhúng tương tự về mặt ngữ nghĩa như thế nào. Do đó, truy vấn mới quan trọng (ngoài chức năng cổ điển như quản lý phiên, lịch sử đặt hàng và cập nhật giỏ hàng) là: Giới hạn sản phẩm ở những sản phẩm chứa tất cả các cụm từ được trích dẫn, sau đó tìm cụm từ tương tự nhất với tìm kiếm của người dùng

Ví dụ thứ hai này làm rõ rằng không chỉ các ứng dụng cần cả chức năng truy vấn cổ điển và tìm kiếm vectơ mà chúng còn cần có khả năng sử dụng các phần tử của từng chức năng trong cùng một truy vấn.

Công nghệ tiên tiến hiện tại trong lĩnh vực còn non trẻ này là cố gắng thực hiện những gì tôi gọi là truy vấn cổ điển trong cơ sở dữ liệu “bình thường”, truy vấn vectơ trong cơ sở dữ liệu vectơ và sau đó kết hợp cả hai lại với nhau theo kiểu đặc biệt khi cả hai đều được yêu cầu cùng một lúc. Điều này dễ xảy ra lỗi, chậm và tốn kém; Ưu điểm duy nhất của nó là bạn có thể làm cho nó hoạt động cho đến khi bạn có giải pháp tốt hơn.

Trong Astra DB, chúng tôi đã xây dựng (và có nguồn mở) giải pháp tốt hơn đó, dựa trên Cassandra SAI. Bởi vì SAI cho phép tạo các loại chỉ mục tùy chỉnh gắn liền với vòng đời nén và ổn định của Cassandra, nên Astra DB có thể dễ dàng cho phép các nhà phát triển kết hợp và so khớp các vị từ boolean, tìm kiếm dựa trên thuật ngữ và tìm kiếm vectơ mà không cần tốn chi phí quản lý và đồng bộ các hệ thống riêng biệt. Điều này mang lại cho các nhà phát triển xây dựng các ứng dụng AI tổng quát khả năng truy vấn phức tạp hơn, giúp tăng năng suất cao hơn và thời gian tiếp thị nhanh hơn.

Gói (lại

Công cụ tìm kiếm vectơ là một tính năng cơ sở dữ liệu mới quan trọng với nhiều thách thức về kiến trúc, bao gồm mở rộng quy mô, thu thập rác, xử lý đồng thời, sử dụng đĩa hiệu quả và khả năng kết hợp. Tôi tin rằng khi xây dựng tính năng tìm kiếm vectơ cho Astra DB, chúng tôi có thể tận dụng khả năng của Cassandra để mang lại trải nghiệm tốt nhất cho các nhà phát triển ứng dụng AI tổng hợp. Tìm hiểu thêm về Astra DB tại đây hoặc nếu bạn muốn tìm hiểu kỹ hơn về thuật toán tìm kiếm vectơ, hãy xem JVector .

- Bởi Jonathan Ellis, DataStax