Tự động hoàn tất phía máy chủ

Question

Cách nhanh chóng và hiệu quả để triển khai thành phần phía máy chủ cho tính năng tự động hoàn thành trong hộp nhập html là gì?

Tôi đang viết dịch vụ để tự động hoàn tất truy vấn người dùng trong hộp tìm kiếm chính của giao diện web của chúng tôi và các lần hoàn thành được hiển thị trong menu thả xuống được hỗ trợ ajax. Dữ liệu mà chúng tôi đang chạy truy vấn chỉ đơn giản là một bảng lớn các khái niệm mà hệ thống của chúng tôi biết, phù hợp với bộ tiêu đề trang wikipedia. Đối với dịch vụ này tốc độ rõ ràng là vô cùng quan trọng, vì sự đáp ứng của trang web rất quan trọng đối với trải nghiệm người dùng.

Triển khai hiện tại chỉ cần tải tất cả các khái niệm vào bộ nhớ trong một tập hợp đã sắp xếp và thực hiện tra cứu nhật ký đơn giản (n) trên một phím tắt người dùng. Cái đuôi sau đó được sử dụng để cung cấp các trận đấu bổ sung ngoài trận đấu gần nhất. Vấn đề với giải pháp này là nó không mở rộng quy mô. Nó hiện đang chạy với giới hạn không gian máy ảo (tôi đã thiết lập -Xmx2g, đó là phần lớn chúng ta có thể đẩy trên các máy 32 bit), và điều này ngăn cản chúng ta mở rộng bảng khái niệm của chúng ta hoặc thêm nhiều chức năng hơn. Chuyển sang máy ảo 64 bit trên các máy có nhiều bộ nhớ hơn không phải là tùy chọn ngay lập tức.

Tôi đã do dự khi bắt đầu làm việc trên một giải pháp dựa trên đĩa vì tôi lo ngại rằng thời gian tìm kiếm đĩa sẽ giết hiệu suất. Có giải pháp nào có thể cho phép tôi mở rộng quy mô tốt hơn, hoặc hoàn toàn trong bộ nhớ hoặc với một số triển khai nhanh được hỗ trợ trên đĩa không?

Chỉnh sửa:

@Gandalf: Đối với trường hợp sử dụng của chúng tôi, điều quan trọng là các autocompletion là toàn diện và không phải là sự giúp đỡ chỉ thêm cho người sử dụng. Đối với những gì chúng tôi đang hoàn thành, nó là một danh sách các cặp kiểu khái niệm. Ví dụ: các mục có thể là [("Microsoft", "Công ty phần mềm"), ("Jeff Atwood", "Lập trình viên"), ("StackOverflow.com", "Trang web")]. Chúng tôi đang sử dụng Lucene cho tìm kiếm đầy đủ khi người dùng chọn một mục từ danh sách tự động hoàn thành, nhưng tôi chưa chắc Lucene sẽ làm việc tốt cho chính bản thân tự hoàn thành.

@Glen: Không có cơ sở dữ liệu nào đang được sử dụng tại đây. Khi tôi nói về một bảng, tôi chỉ có nghĩa là biểu diễn có cấu trúc của dữ liệu của tôi.

@Jason Day: Việc triển khai ban đầu của tôi cho vấn đề này là sử dụng Trie, nhưng bộ nhớ sưng lên với điều đó thực sự tồi tệ hơn bộ được sắp xếp do cần một số lượng lớn tham chiếu đối tượng. Tôi sẽ đọc trên cây tìm kiếm thứ ba để xem nó có thể được sử dụng hay không.

Answer 1

Với bộ lớn, tôi sẽ thử thứ gì đó giống như chỉ mục Lucene để tìm cụm từ bạn muốn và đặt tác vụ hẹn giờ được đặt lại sau mỗi lần nhấn phím, với độ trễ 0,5 giây. Bằng cách này, nếu người dùng gõ nhiều ký tự nhanh, nó sẽ không truy vấn chỉ mục mỗi đột quỵ, chỉ khi người dùng tạm dừng trong một giây. Kiểm tra khả năng sử dụng sẽ cho bạn biết khoảng thời gian tạm dừng đó sẽ như thế nào.

Timer findQuery = new Timer(); 
... 
public void keyStrokeDetected(..) { 
    findQuery.cancel(); 
    findQuery = new Timer(); 
    String text = widget.getEnteredText(); 
    final TimerTask task = new TimerTask() { 
     public void run() { 
     ...query Lucene Index for matches 
     } 
    }; 
    findQuery.schedule(task, 350); //350 ms delay 
} 

Một số pseduocode ở đó, nhưng đó là ý tưởng. Ngoài ra nếu các cụm từ truy vấn được đặt, chỉ mục Lucene có thể được tạo trước và tối ưu hóa.

Answer 2

Nếu bạn không thể tải tất cả dữ liệu vào RAM thì bạn sẽ phải xử lý một số dữ liệu trên đĩa.

Bạn đang sử dụng DB nào?

Ví dụ: Oracle có tùy chọn nơi bạn có thể giữ toàn bộ bảng trong bộ nhớ và thực hiện truy vấn của bạn dựa vào đó.

MySQL cũng tuyên bố có một số khả năng trong bộ nhớ, nhưng tôi không biết nhiều về MySQL.

Sau đó, bạn có thể xóa bỏ bộ nhớ cache dựa trên java của mình hoặc bạn có thể sử dụng bộ nhớ cache cho các tìm kiếm phổ biến nhất/gần đây nhất. Rõ ràng là khi bạn hết RAM, một số dữ liệu sẽ có trên đĩa khi bạn truy vấn nó, nhưng tùy thuộc vào tải trên hệ thống, điều này sẽ chỉ là vấn đề cho lần bấm phím đầu tiên, chứ không phải vấn đề tiếp theo. , vì hàng sẽ nằm trong bộ nhớ sau đó.

Nếu đĩa tìm kiếm đang làm chậm bạn xuống, thì bạn có thể điều tra bằng cách sử dụng ổ SSD để tăng tốc độ đọc của bạn.

Answer 3

Tôi có yêu cầu tương tự.

Tôi đã sử dụng cơ sở dữ liệu quan hệ với một bảng tổng hợp được lập chỉ mục duy nhất (tránh tham gia và xem để tăng tốc độ tra cứu) và bộ nhớ trong (Ehcache) để lưu trữ các mục nhập được sử dụng nhiều nhất.

Bằng cách sử dụng bộ nhớ cache MRU, bạn có thể có thời gian phản hồi nhanh cho hầu hết các lần tra cứu và có thể không có gì có thể đánh bại cơ sở dữ liệu quan hệ trong cột truy cập được lập chỉ mục trong một bảng lớn được lưu trữ trên đĩa.

Đây là giải pháp cho bộ dữ liệu lớn mà bạn không thể lưu trữ trên máy khách và nó hoạt động khá nhanh (tra cứu không được lưu trong bộ nhớ cache luôn được truy xuất dưới 0,5 giây trong trường hợp của tôi). Nó cũng có thể mở rộng theo chiều ngang - bạn luôn có thể thêm các máy chủ và máy chủ cơ sở dữ liệu bổ sung.

Bạn cũng có thể chơi với bộ nhớ đệm chỉ các kết quả được sử dụng nhiều nhất trên máy khách, đặc biệt nếu bạn đã triển khai nó. Trong trường hợp của tôi, giải pháp phía máy chủ đủ nhanh và thời gian tải của khách hàng đủ chậm, vì vậy nó không được bảo hành.

P.S. Chỉ có truy vấn của khách hàng khi người dùng tạm dừng trong một khoảng thời gian nhất định để tránh tra cứu lặp lại như được đề xuất là giải pháp tốt. Trên máy khách của tôi, tôi truy vấn cơ sở dữ liệu chỉ sau ba ký tự đầu tiên được nhập vào, vì nhỏ hơn trả về quá nhiều kết quả trong tất cả các cá thể.

Answer 4

Có lẽ tôi đã hiểu nhầm câu hỏi của bạn nhưng bạn không thể sử dụng plugin JQuery để Ajax thông tin cho ứng dụng của bạn?

Tôi đã sử dụng này trước:

Ajax Auto Suggest v2

Answer 5

Tôi đã làm điều này cho các tập dữ liệu nhỏ sử dụng một Ternary search tree. Mã DDJ không quá khó để chuyển đổi sang Java, nhưng nó giả định toàn bộ tập dữ liệu sẽ khớp với bộ nhớ. Có các triển khai trên đĩa của cây tìm kiếm Ternary (here là một trong python), nhưng tất nhiên chúng sẽ kém hiệu quả hơn. Vì các cây tìm kiếm bậc ba vượt trội so với các trận đấu một phần, mặc dù hiệu suất có thể phù hợp với nhu cầu của bạn.

Answer 6

Có giải pháp khả thi mà sẽ cho tôi mở rộng tốt hơn

Vâng, Oracle. Đây là loại cơ sở dữ liệu được xây dựng cho. Chỉ cần lập chỉ mục các cột có liên quan. Nếu bạn đang chạy chống lại các bức tường của các giải pháp trong bộ nhớ, sau đó thương mại-off với thời gian tìm kiếm đĩa hoặc độ trễ mạng có lẽ là tranh luận. Đặc biệt nếu bạn chèn một lớp đệm vào giữa.

Ngoài ra, bạn có thể giảm số lần truy cập nếu bạn chỉnh sửa mã phía máy khách một chút. Chẳng hạn như đặt số ký tự loại tối thiểu trước khi một truy vấn chạy hoặc thiết lập một phần của độ trễ thứ hai sau khi người dùng ngừng nhập.Nếu bạn đã sử dụng chúng, hãy đặt chúng cao hơn một chút.

Answer 7

Tôi đã kết thúc việc giải quyết vấn đề này thông qua Lucene; các thử nghiệm hiệu suất ban đầu dường như đủ cho trường hợp sử dụng của chúng tôi. Một chút hack là cần thiết để làm cho các truy vấn tiền tố hoạt động, vì tôi đã chạy vào ngoại lệ TooManyClauses khi mở rộng các truy vấn như "Jeff At *". Tôi đã kết thúc gói IndexReader của mình với một FilterIndexReader và đặt giới hạn cứng về số lượng các thuật ngữ được trả lại trên một lời gọi tiền tố hạn. Dưới đây là mã của tôi:

Directory directory = FSDirectory.getDirectory(indexDir); 
IndexReader reader = IndexReader.open(directory); 
FilterIndexReader filteredReader = new FilterIndexReader(reader) { 
    @Override public TermEnum terms(Term t) throws IOException { 
    final TermEnum origEnum = super.terms(t); 

    return new TermEnum() { 
     protected int count = 0; 
     @Override public boolean next() throws IOException { 
     if (count++ < (BooleanQuery.getMaxClauseCount() - 10)) 
      return origEnum.next(); 
     else return false; 
     } 

     @Override public Term term() { 
     return origEnum.term(); 
     } 

     @Override public int docFreq() { 
     return origEnum.docFreq(); 
     } 

     @Override public void close() throws IOException { 
     origEnum.close(); 
     } 
    }; 
    } 
}; 

IndexSearcher searcher = new IndexSearcher(filteredReader); 

Answer 8

Đối với những người vấp ngã khi câu hỏi này ...

Tôi chỉ đăng tải một server-side autocomplete implementation trên Google Code. Dự án bao gồm một thư viện java có thể được tích hợp vào các ứng dụng hiện có và một máy chủ tự động hoàn thành HTTP AJAX độc lập.

Hy vọng của tôi là cho phép mọi người kết hợp tự động hoàn thành hiệu quả vào ứng dụng của họ. Đá lốp!

Answer 9

Tôi đã sử dụng hashtable và mmap() Và danh sách từ 10.000.000+ bản ghi không phải là vấn đề. Xem bản demo ở đây: http://olegh.ath.cx/autocomplete.html

Answer 10

sử dụng Trie cấu trúc dữ liệu ở đây là wiki http://en.wikipedia.org/wiki/Trie