Vì sao tìm kiếm mã nguồn lại khó

 (blog.val.town)
1 điểm bởi GN⁺ 2024-04-12 | 1 bình luận | Chia sẻ qua WhatsApp
  • Tìm kiếm của Val Town hiện là tìm kiếm chuỗi con dựa trên Postgres ILIKE, nên gần như không có xếp hạng và cũng hỗ trợ kém cho truy vấn nhiều từ; vì vậy có rất nhiều yêu cầu cải thiện
  • Các quy tắc của tìm kiếm ngôn ngữ tự nhiên như loại bỏ stop word, stemming và lemmatization có thể phá vỡ tên biến, tên hàm và ranh giới token trong mã
  • Postgres Full Text Search có thể giúp giữ hạ tầng đơn giản, nhưng các dự án trước đây từng gặp vấn đề về khả năng mở rộng, và Val Town cũng đang thử thách giới hạn của Postgres một nút
  • Tìm kiếm v2 được soft launch dùng tìm kiếm trigram dựa trên pg_trgrm, nhưng khác với tìm kiếm regex, rất khó tinh chỉnh xếp hạng cho các truy vấn tự do đạt mức mong muốn
  • Có các lựa chọn thay thế như Elasticsearch, Meilisearch, Zoekt và ParadeDB, nhưng hạ tầng riêng, gánh nặng vận hành và việc có được hỗ trợ hosting hay không vẫn là các ràng buộc khi lựa chọn

Điểm nghẽn của tìm kiếm Val Town

  • Tìm kiếm của Val Town hiện dùng ILIKE của Postgres
    • Đây là kiểu tìm kiếm chuỗi con: nếu từ khóa xuất hiện trong mã thì nó sẽ hiện trong kết quả
    • Hầu như không có xếp hạng, và cũng không hỗ trợ tốt truy vấn nhiều từ
  • Tìm kiếm tốt hơn là một trong những tính năng được yêu cầu nhiều nhất ở Val Town
  • Việc cải thiện vẫn đang được tiến hành, nhưng họ vẫn chưa tìm ra lời giải phù hợp với yêu cầu
  • Các điều kiện đã được xác nhận đến lúc này gồm có
    • Các giải pháp tìm kiếm phổ biến chủ yếu được thiết kế cho ngôn ngữ tự nhiên
    • Những công ty lớn cần tìm kiếm mã nguồn thường đầu tư rất nhiều thời gian và chi phí vào hệ thống tìm kiếm riêng
    • Val Town đã có lượng dữ liệu lớn, nên cần một giải pháp mở rộng tốt
    • Nếu dùng dịch vụ tìm kiếm riêng thay vì mở rộng cơ sở dữ liệu, thì phải cân nhắc đánh đổi giữa hạ tầng và độ phức tạp

Vì sao quy tắc tìm kiếm ngôn ngữ tự nhiên không phù hợp với mã

  • Cấu hình full-text search (FTS) thông thường mặc định cung cấp các thuật toán nhắm vào ngôn ngữ tự nhiên như tiếng Anh
    • Loại bỏ stop word: xóa các từ quá phổ biến như “the”, “it” trước khi lập chỉ mục
    • Stemming: biến “running” thành “run” để có thể tìm thấy cả khi truy vấn “runs”
    • Lemmatization: có thể thay từ đồng nghĩa bằng từ phổ biến hơn để truy vấn “excellent” cũng tìm được tài liệu chứa “great”
  • Nếu áp dụng các quy tắc đó cho mã thì ý nghĩa sẽ bị lệch
    • Trong TypeScript, the không phải stop word mà có thể là một tên biến hợp lệ cần tìm
    • Ranh giới từ trong mã khác với ngôn ngữ tự nhiên
    • Áp dụng stemming lên tên hàm cũng khó tạo ra kết quả có ý nghĩa
  • Postgres to_tsvector('english', ...) thay đổi mạnh văn bản gốc khi lập chỉ mục câu ngôn ngữ tự nhiên
    • I am writing this example sentence sẽ được biến thành dạng như 'exampl':5 'sentenc':6 'write':3
  • Với mã, vấn đề tokenization còn rõ rệt hơn
    • function stringifyNumber(a: number): string { return a.toString() } sẽ được lập chỉ mục thành dạng như 'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2
    • Các từ như function vẫn được giữ lại, còn a.toString() không bị tách thành hai token vì . không phải ranh giới từ mặc định

Ưu và nhược điểm của Postgres Full Text Search

  • Postgres cung cấp phần mở rộng Full Text Search, và nhà cung cấp hosting của Val Town là Render cũng hỗ trợ nó
  • Từ trước đến nay Val Town đã sử dụng Postgres rất tích cực, và Postgres được đánh giá cao nhờ tài liệu tốt và hỗ trợ hosting rộng rãi
  • Với một đội ngũ nhỏ, giữ hạ tầng đơn giản nhất có thể là điều quan trọng, nên nếu giải được bằng Postgres thì sẽ có động lực lớn để dùng Postgres
  • Tuy nhiên, các dự án trước đây dùng FTS từng gặp vấn đề về hiệu năng và khả năng mở rộng
    • Observable cuối cùng đã chuyển sang Elasticsearch
    • Val Town có rất nhiều vals và đang thử thách giới hạn của cụm Postgres một nút
  • Rất khó tìm được ví dụ thành công về việc dùng FTS cho tìm kiếm mã nguồn, nên hiện tại nó vẫn được giữ như phương án dự phòng hơn là lựa chọn đầu tiên

Thử nghiệm tìm kiếm v2 dựa trên pg_trgrm

  • Thuật toán tìm kiếm v2 mà Val Town đã soft launch dựa trên pg_trgrm của Postgres
    • pg_trgrm triển khai tìm kiếm trigram trong Postgres
  • Trigram đã có các trường hợp thành công trong tìm kiếm mã nguồn
    • Bài viết năm 2012 của Russ Cox nói về việc Google Code Search dùng chỉ mục trigram và một triển khai regex đặc biệt
    • Hệ thống tìm kiếm mã mới của GitHub cũng dùng tìm kiếm trigram
    • Sourcegraph có công cụ tìm kiếm dựa trên trigram được kế thừa từ Google
  • Cách tiếp cận Postgres pg_trgrm của Val Town chịu ảnh hưởng nhiều từ bài viết của Stephen Gutekanst về lập chỉ mục kho cục bộ bằng Postgres
  • Cách triển khai là áp dụng chỉ mục GIN và gin_trgm_ops lên cột chứa văn bản tìm kiếm
  • pg_trgrm là lời giải tốt cho tìm kiếm regex, nhưng lại không hợp lắm với các truy vấn tự do hơn như phần lớn truy vấn trên Val Town
    • Hiện họ dùng word_similarity để xếp hạng tìm kiếm
    • Việc tinh chỉnh thuật toán để tiệm cận một thứ hạng hợp lý là cực kỳ khó

Các lựa chọn search engine và đánh đổi trong vận hành

  • Các phương án được xem xét gồm cả dịch vụ tìm kiếm độc lập lẫn phần mở rộng của Postgres
    • Meilisearch: độc lập, Rust, 41k sao
    • Typesense: độc lập, C++, 17k sao
    • Zoekt: độc lập, Go, 406 sao
    • ParadeDB: phần mở rộng Postgres, Rust, 3.2k sao
    • Sonic: độc lập, Rust, 19.4k sao
  • Có các công cụ chuyên cho mã nguồn, nhưng phần lớn là đóng
    • Tìm kiếm của GitHub rất xuất sắc, nhưng đó là kết quả của một đội ngũ chuyên trách cùng ngân sách thời gian thực sự lớn
  • Bản fork Zoekt do Sourcegraph duy trì khá thú vị, nhưng rất ngách và đòi hỏi đầu tư lớn vào hạ tầng mới
  • Elasticsearch có thể sẽ là lời giải khó tránh khỏi
    • Nó không có xử lý chuyên biệt cho mã nguồn, nhưng gần như có thể tùy biến vô hạn
    • Việc phải học tinh chỉnh bộ nhớ Java, đưa persistent disk storage đầu tiên vào ứng dụng, và quản lý thêm một nguồn chân lý dữ liệu nữa đều là gánh nặng
    • Dùng Elasticsearch Cloud có thể giúp giảm bớt gánh nặng bảo trì
  • Meilisearch trông có vẻ hứa hẹn như một lựa chọn thay thế Elasticsearch
    • Việc nó được viết bằng Rust là một điểm hấp dẫn
    • Trong bài so sánh của chính họ, có vẻ họ nhấn mạnh độ trễ hơn là khả năng mở rộng, nên vẫn chưa rõ gánh nặng hạ tầng có thấp hơn hay không
  • ParadeDB hấp dẫn ở chỗ hoạt động giống Elasticsearch nhưng vẫn là “chỉ là Postgres”
    • Tuy nhiên, Render hiện vẫn chưa cho dùng phần mở rộng này

Gánh nặng khi một đội ngũ nhỏ chọn hạ tầng tìm kiếm

  • Tìm kiếm mã nguồn khó hơn tìm kiếm tiếng Anh
  • Các đội ngũ nhỏ có động lực giữ hạ tầng đơn giản, làm cho thiết lập môi trường phát triển dễ dàng, và giữ dữ liệu ở cùng một nơi
  • Val Town không muốn vội vàng bị ràng buộc vào một lựa chọn đòi hỏi quản lý liên tục
  • Có lý do mà ở các công ty vừa và lớn, không chỉ có “dịch vụ” tìm kiếm mà còn có cả “đội ngũ” tìm kiếm

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-04-12
Các ý kiến trên Hacker News

  • Tôi làm ở Sourcegraph; xử lý ở quy mô lớn dĩ nhiên là cần thiết, nhưng nếu lần đầu đưa tìm kiếm mã vào sản phẩm thì đừng bắt đầu bằng chỉ mục ngay từ đầu, mà nên dùng tìm kiếm tức thời cho đến khi chạm giới hạn
    Trong trường hợp chỉ cần tìm N kết quả đầu tiên, bạn không phải quét toàn bộ đến cuối mà vẫn có thể lấp đầy bộ đệm kết quả, nên nó trụ được lâu hơn tưởng tượng. Tôi rất sẵn lòng trao đổi với những người đang xây dựng thứ như vậy, cũng như với nhóm Val Town

    • Khi cần tìm kiếm bằng chỉ mục, Zoekt là cách tốt nhất tôi tìm được
      Sourcegraph trước đây đã đảm nhận việc bảo trì Zoekt, còn Livegrep và Hound thì theo nhiều khía cạnh khá chật vật ở quy mô mà chúng tôi muốn lập chỉ mục. Sau khi chuyển từ một bản triển khai OpenGrok cũ kỹ, ọp ẹp sang Zoekt, khác biệt về cả hiệu năng lập chỉ mục lẫn hiệu năng/khả dụng tìm kiếm là rất lớn. Sourcegraph đang đặt nhiều tính năng tinh vi hơn lên trên nền tìm kiếm mã mà Zoekt cung cấp
    • Điều khiến tôi ngạc nhiên là ngay cả khi không có chỉ mục cũng có thể đi được khá xa
      Ví dụ GritQL(https://github.com/getgrit/gritql) tôi vẫn luôn nghĩ cuối cùng sẽ cần chỉ mục để có tốc độ, nhưng cho đến nay tất cả vẫn trụ khá tốt chỉ bằng tìm kiếm tức thời
    • Tôi áp dụng cách tiếp cận này cho nhiều vấn đề: bắt đầu bằng cách đơn giản với ít trạng thái nhất, rồi chỉ thay đổi sau khi chứng minh được rằng cần nghiêng về phía bộ nhớ để đạt tốc độ
      Không có cache thì việc duy trì cho đúng đơn giản hơn nhiều
    • Chỉ sau khi đã có khối lượng công việc thực tế, có quy mô và mang tính đại diện, việc chọn phương thức lập chỉ mục phù hợp mới trở nên dễ hơn nhiều
    • Một người từng xây dựng cơ sở dữ liệu chuỗi thời gian đã nén các khối đĩa rồi giải nén dạng streaming khi tìm kiếm
      Những thứ nằm vừa trong L2 cache chạy thực sự rất nhanh

  • Tìm kiếm mã thật sự khó, và một nền tảng tìm kiếm mã tốt giúp cuộc sống dễ dàng hơn rất nhiều
    Nếu rời Google, có lẽ thứ tôi nhớ nhất sẽ là tìm kiếm mã nội bộ. Nó tích hợp quá tốt với mọi luồng công việc như tìm target blaze, binding guice, v.v. đến mức khó tưởng tượng làm việc mà không có nó. Mỗi lần dùng tìm kiếm của GitHub tôi lại càng cảm nhận rõ giá trị đó; không phải vì tìm kiếm của GitHub tệ, mà vì việc xây dựng một nền tảng tìm kiếm mã đa dụng về bản chất khó hơn rất nhiều

    • Nếu rời đi, bạn có thể dùng Livegrep, được xây dựng dựa trên công việc tìm kiếm mã của Google
      Hiện tôi không dùng cá nhân, nhưng nó rất tốt và có vẻ sẽ đáp ứng hầu hết nhu cầu. https://github.com/livegrep/livegrep
    • Tính năng phân tầng binding của guice thì hay, nhưng UI có thể tốt hơn
      Sẽ tốt nếu có thể tìm ngay provider hoặc nơi sử dụng trực tiếp từ ô tìm kiếm

  • Các kỹ thuật tìm kiếm mã cơ bản thường không được dạy rõ ràng cho lập trình viên mới, nhưng có vẻ là một năng lực cốt lõi cần nắm từ sớm
    Luồng tôi khuyến nghị là học cách tìm kiếm dùng được ở mọi nơi như Ctrl+F, rồi chuyển sang ripgrep(https://github.com/BurntSushi/ripgrep). Đây không hẳn là tùy chọn, mà là một công cụ thực sự xuất sắc và dễ khám phá; việc phải mở terminal cũng lại tốt cho người mới. Nếu có thể thì cũng nên học một trình soạn thảo dòng lệnh mạnh; trước đây tôi sẽ khuyên Emacs, nhưng giờ tôi khuyên bản vim mặc định gần như được cài ở khắp nơi, vì có thể grep và chỉnh sửa trong cùng một cửa sổ. Tiếp đó hãy học các thao tác mà ripgrep làm mặc định bằng grep cũ như grep -r, grep -ri, grep -ril, và cuối cùng khi đụng giới hạn của ripgrep thì chuyển sang một công cụ tìm kiếm mã chuyên dụng thực sự dựa trên chỉ mục

    • Tính năng tìm kiếm của VSCode cũng dùng ripgrep, nên đây là điểm khởi đầu tốt
    • GitHub cũng là một công cụ tuyệt vời để tìm kiếm mã xuyên qua cả những repository bạn chưa clone, dù là repository công khai hay của tổ chức
    • Tôi tò mò ngoài tốc độ ra, khi tìm kiếm trong Git repository thì ripgrep có ưu điểm gì so với git grep

  • Thật ngạc nhiên là hound(https://github.com/hound-search/hound) không được nhắc tới
    Tôi từng nghĩ nó là một trong những giải pháp nguồn mở hàng đầu trong lĩnh vực này. Tôi đã dùng instance của Wikimedia(https://codesearch.wmcloud.org/search/) và nhìn chung hài lòng

    • Hound đã đưa ra một lựa chọn thú vị là không đặt giới hạn trên cho kết quả tìm kiếm
      https://codesearch.wmcloud.org/search/?q=test&files=&exclude... trong trường hợp của tôi mất 13 giây để tạo phản hồi JSON 55MB, rồi còn mất thêm vài giây để render lại vào DOM. Với Zoekt JSON API dùng trong neogrok, cần có giới hạn kích thước phản hồi tìm kiếm đúng nghĩa, nên chúng tôi phải bảo đảm điều này: https://github.com/sourcegraph/zoekt/pull/615

  • Đây là lý do từ lâu những người làm IDE và công cụ dành cho lập trình viên cho rằng muốn có tìm kiếm mã đúng nghĩa thì phải mở nền tảng trình biên dịch
    Bởi rất nhiều việc cần làm rốt cuộc là tái dựng các biểu diễn nội bộ mà trình biên dịch sử dụng. Tìm kiếm mã tốt cũng là nền tảng cho hỗ trợ refactoring, tự động hoàn thành và các tính năng IDE phổ biến. Tất nhiên nói thì dễ hơn làm; phía làm trình biên dịch thường đặt công cụ xuống hàng thứ yếu, JetBrains cũng từng mắc lỗi này ở giai đoạn đầu của Kotlin, và đang sửa một phần trong Kotlin 2.0 để dễ hỗ trợ những thứ như biên dịch tăng dần. Cộng đồng Rust vài năm trước cũng đã có nỗ lực lớn nhằm tăng tính thân thiện với IDE và rút ra cùng nhận thức đó. IBM từng làm rất tốt điều này trong Eclipse ngày xưa, và từ đó về sau gần như không ai bắt kịp. IntelliJ chậm hơn khoảng 2–3 bậc độ lớn, tạo ra khác biệt giữa đơn vị giây và mili giây. Eclipse có một trình biên dịch tăng dần rất nhanh cho Java, có thể biên dịch một phần ngay cả khi có lỗi cú pháp, và biểu diễn mã của IDE được nối với trình biên dịch đó. Nếu bạn gõ sai làm hỏng một phần mã, các tệp có vấn đề trong toàn bộ codebase lập tức hiện gạch chân đỏ; sửa lỗi gõ sai thì chúng biến mất không độ trễ. Điều đó chỉ có thể làm được khi có ánh xạ giữa tệp và cây cú pháp, và Eclipse làm được vì nó được nối với trình biên dịch tăng dần. IntelliJ không làm được việc này, nên trước khi build lại nó còn chủ động “đánh lừa” trạng thái đúng/sai, và khi trạng thái nội bộ lệch với đĩa thì hiển thị rất nhiều lỗi giả. Khi chạy, có vài giây trễ để biên dịch, và khi đó đôi lúc bạn mới biết trạng thái mà IDE cho là có thể chạy là sai. Trong Eclipse, vì trình biên dịch và trạng thái nội bộ được chia sẻ, tất cả những điều này đều tức thì và rõ ràng. Nó cũng có nhiều khuyết điểm và lỗi khó chịu, nhưng tính năng đó thì thật đáng nhớ

    • Tất nhiên Roslyn (trình biên dịch .NET) của Microsoft là ngoại lệ
      https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov...
      https://ericlippert.com/2012/06/08/red-green-trees/
      Tôi từng làm công cụ bằng Roslyn SDK và nó thật sự rất tốt
    • Trình biên dịch tăng dần cho Java của Eclipse thật sự rất ấn tượng, nhưng cuối cùng tôi vẫn chuyển sang IntelliJ vì tích hợp với các hệ thống build bên ngoài như Maven và Gradle tốt hơn, cũng như hỗ trợ nhiều ngôn ngữ tốt hơn
    • Trong Eclipse, mọi thứ vẫn tức thì và không mơ hồ
      Đó là lý do chính khiến nhiều người không chuyển sang IDE khác

  • Có vẻ trước đây GitHub từng “sửa” bằng cách tách a.toString() thành hai token, và việc đó khá phiền
    GitHub đang tăng cường khả năng tìm vị trí sử dụng giống IDE, nhưng vẫn chưa hoàn hảo, nên có lúc tôi muốn dùng tìm kiếm văn bản kiểu "foo.bar()" để tìm các chỗ sử dụng bị bỏ sót. Nhưng vì hành vi xử lý gốc từ như vậy, nó lại tìm cả mọi nơi foo và bar được nhắc riêng rẽ, khiến kết quả phình to

  • Tôi không hiểu vì sao lại lướt qua Zoekt
    Nó được tạo ra đúng cho mục đích này, và cũng không phải là gánh nặng hạ tầng mới lớn hơn các lựa chọn khác. Máy chủ là một binary duy nhất, bộ lập chỉ mục cũng là một binary duy nhất, khó mà đơn giản hơn thế. Tôi không thấy lý do gì để sợ Zoekt hơn Elasticsearch

  • Một trong những cách tiếp cận tìm kiếm mã thú vị nhất tôi thấy gần đây là septum: https://github.com/pyjarrett/septum
    Tôi cho rằng phần khó nhất khi làm tìm kiếm mã cho đúng là lấy được lượng ngữ cảnh xung quanh phù hợp, và septum là công cụ cố giải bài toán này ở cấp độ tệp. Một thứ nữa khiến tôi ngạc nhiên vì không được nhắc đến là stack-graphs(https://github.com/github/stack-graphs), vốn cố gắng phân giải dần các quan hệ ký hiệu trên toàn bộ codebase. Nó vận hành việc lập chỉ mục chính xác xuyên tệp của GitHub và về mặt khái niệm cũng hợp lý, nhưng tôi đã gặp khó khăn khi làm phiên bản mã nguồn mở chạy được

  • Oracle có các view USER/ALL/DBA_SOURCE, và mọi mã PL/SQL(SQL/PSM) được nạp vào cơ sở dữ liệu đều xuất hiện ở đó
    Nếu không bị cố ý làm rối mã thì tất cả đều hiện dưới dạng văn bản thuần. Có các cột owner, object name, LINE[NUMBER], TEXT[VARCHAR2(4000)], và có thể dùng LIKE hoặc regexp_like() trên mã nguồn đã lưu. Tôi tò mò liệu EnterpriseDB đã triển khai cái này trong Postgres hay cung cấp dưới dạng extension. Vì phần lớn SQL/PSM dù sao cũng xuất phát từ Oracle, đây rõ ràng là tính năng đáng mong đợi. https://en.wikipedia.org/wiki/SQL/PSM

  • Nói rằng “tìm kiếm của GitHub rất tuyệt”, nhưng thật sự vậy sao?
    Trong hầu hết trường hợp tôi thấy nó gần như vô dụng, và clone về rồi dùng ripgrep hiệu quả hơn nhiều. Có lẽ vấn đề là UX tệ hại hơn là bản thân tìm kiếm