Autocompletion and request cancellation

Problem

Imagine we’re tasked to implement a search with auto-completion support.

Because it’s an auto-completion, every time the search phrase is changed, there’s a chance to have more than one outstanding request going at a time.

How do we keep resource usage to a minimum and avoid unnecessary requests?

Possible Solutions

1. keep at most one(the latest) request going at a time
2. cancel any other(previous) requests
3. do not submit request unless user finished entering search phrase

Note: Having fast search backend is actually a must-have requirement and whole point of auto-completion, but for the sake of demonstration, a slow one is used instead.

Frontend

Auto-completion with no optimizations

In the worst, unoptimized, case auto-completion may spawn number of requests while user is entering text.

Here’s an example such auto-completion, as seen in browser’s network profiler:

Auto-completion With Cancellation

With request cancellation it’s a completely different dynamics:

Auto-completion with Deferred Input and Cancellation

With deferred input requests aren’t even started while user is entering a search phrase.

Below image is an example of a scenario when user made a brief pause after entering hello w which caused a request which then got cancelled as user continued with the input.

Comparison

Easy to see that Deferred paired with Cancellation is the winner as the most efficient approach.

Client cancellation must also be supported by the search backend. Backend that doesn’t support cancellation continues processing request even after client disconnects.

Backend

Go enables request cancellation notification with http.CloseNotifier interface.

In below example handleSearch aborts pseudoSearch when client disconnects.

// handleSearch handles search/ search cancellation requests
func handleSearch(w http.ResponseWriter, r *http.Request) {
	var (
		// abort signals other goroutine that any work needs not to be completed
		abort  = make(chan struct{})
		result = make(chan error)

		q   = r.FormValue("q")
		log = func(str string) { fmt.Printf("[%s] %s\n", q, str) }
	)

	log("starting")

	// search goroutine
	go func() {
		log("searching...")
		result <- pseudoSearch(w, q, abort)
		log("complete")
	}()

	select {
	// assuming successful type assertion
	//client diconnected
	case <-w.(http.CloseNotifier).CloseNotify():
		close(abort) // signal disconnection
	case <-result:
		// search completed
	}

	log("done")
}

// pseudoSearch is an example pseudo search implementation
// in this example it renders 40 lines prefixed with a query string
// rendering of each line is slowed down with 100ms delay to resemble some latency
func pseudoSearch(w http.ResponseWriter, q string, abort <-chan struct{}) error {
	for i := 0; i < 40; i += 1 {
		select {
		case <-time.After(100 * time.Millisecond):
			fmt.Fprintln(w, q, "result", i)
		case <-abort:
			fmt.Printf("[%s] abort!\n", q)
			return nil
		}
	}

	return nil
}

Important to note that search process in this case has to be able to stop processing(as demostrated with <-abort event). Otherwise search goroutine continues executing and consuming resource even after searchHandler terminates.

Running example

$ git clone https://gist.github.com/gmarik/5186b7a29ec48936dc10 example
$ cd example
$ go run server.go
$ open http://localhost:3030

Closing notes

At first, my idea was just to cover request cancellation with jQuery and Go, but later decided to cover deferred input which somewhat caused post grow larger than initially intended.

References

• Example code