Consider ditching concurrent handler execution

[ebkalderon]

Background

In order for the framework to support both standard streams and TCP transports generically, we need a way to interleave both client-to-server and server-to-client communication over a single stream. This topic has been the subject of a previous issue. The current strategy used by tower-lsp (and lspower in turn) to accomplish this is somewhat simplistic:

1. Incoming messages (requests to server, responses from client) are read sequentially from the input stream
2. Each message is routed to its respective async handler
3. Pending tasks are buffered and executed concurrently on a single thread, maximum four (4) tasks at a time, preserving order
4. Outgoing messages (responses from server, requests from client) are serialized into the output stream

The third step above is particularly significant, however, and has some unintended consequences.

Problem Summary

A closer reading of the "Request, Notification and Response Ordering" section of the Language Server Protocol specification reveals:

Responses to requests should be sent in roughly the same order as the requests appear on the server or client side. [...] However, the server may decide to use a parallel execution strategy and may wish to return responses in a different order than the requests were received. The server may do so as long as this reordering doesn’t affect the correctness of the responses.

This is concerning to me because tower-lsp unconditionally executes pending async tasks concurrently without any regard for the correctness of the execution. The correct ordering of the outgoing messages is preserved, as per the spec, but the execution order of the handlers is not guaranteed to be correct. For example, an innocent call to self.client.log_message().await inside one server handler might potentially prompt the executor to not immediately return back to that handler's yield point, but instead start processing the next incoming request concurrently as it becomes available.

As evidenced by downstream GitHub issues like denoland/deno#10437, such behavior can potentially cause the state of the server and client to slowly drift apart as many small and subtle errors accumulate and compound over time. This problem is exacerbated by LSP's frequent use of JSON-RPC notifications rather than requests, which don't require waiting for a response from the server (see relevant discussion in microsoft/language-server-protocol#584 and microsoft/language-server-protocol#666).

It's not really possible to confidently determine whether any particular "state drift" bug was caused by the server implementation of tower-lsp without stepping through with a debugger. However, there are some things we can do to improve the situation for our users and make such bugs less likely.

Possible solutions

For example, we could process client-to-server and server-to-client messages concurrently to each other, but individual messages of each type must execute in the order they are received, one by one, and no concurrency between individual LanguageServer handlers would be allowed.

This would greatly decrease request throughput, however. Perhaps it would be beneficial to potentially allow some handlers to run concurrently where it's safe (with user opt-in or opt-out), but otherwise default to fully sequential execution. To quote the "Request, Notification and Response Ordering" section of the Language Server Protocol specification again:

For example, reordering the result of textDocument/completion and textDocument/signatureHelp is allowed, as these each of these requests usually won’t affect the output of the other. On the other hand, the server most likely should not reorder textDocument/definition and textDocument/rename requests, since the executing the latter may affect the result of the former.

If choose to go this route, we may have to determine ahead of time which handlers are usually safe to reorder and interleave and which are not. I imagine this would introduce a ton of additional complexity to tower-lsp, though, so I'd rather leave such responsibilities to the server author to implement themselves, if possible.

Below are a few key takeaways that we can start adding now to improve the situation:

1. Execute server request/notification handlers sequentially in the order in which they were received, no concurrency.
2. Process client-to-server and server-to-client messages concurrently with each other.

The matters of optional user-controlled concurrency are still unanswered, however, and will likely require further design work.

Any thoughts on the matter, @silvanshade?

[ebkalderon]

I have found some interesting information regarding the Language Server Protocol's consistency requirements that could help inform our future design moving forward.

First, the specification describes the correct server behavior of textDocument/didChange notifications as follows:

<snip>
To mirror the content of a document using change events use the following
approach:

• start with the same initial content
• apply the 'textDocument/didChange' notifications in the order you receive them.
• apply the TextDocumentContentChangeEvents in a single notification in the order you receive them.

This is obvious and makes intuitive sense. We must process text document change notifications strictly in the order in which they are received to ensure state consistency on the server side.

We do indeed process these events in order, thanks to Stream::buffered, but there is a risk that multiple notifications may be processed concurrently (because Buffered<St> is implemented in terms of FuturesOrdered<T> which races futures to completion in parallel but yields results in the original order), and as a generic LSP framework, we cannot guarantee that all downstream LanguageServer trait implementers will behave sanely when multiple changes are processed concurrently. As such, we should consider processing all incoming JSON-RPC notifications sequentially (but still asynchronously), or at least make the concurrency level configurable.

For reference, rust-analyzer appears to always process notifications sequentially (see handle_event() & on_notification() in main_loop.rs) while request processing is largely performed in parallel, with the exception of only two standard LSP requests: shutdown and textDocument/selectionRange. This, along with the Notification Message section of the LSP specification, lends credence to the idea that all notification messages should be handled sequentially and in the order in which they are received, while requests may be freely handled concurrently.

[samscott89]

Hey! Thanks for working on this project. It's super helpful.

I wanted to add some example use cases to this. One thing we want to implement is a custom request that can be used to interrogate the LSP client. For example, suppose we want to ask the client to fetch all workspace symbols across all language. Then we end up with the following flow:

. Source.

Relevant to this discussion, you can see that within handling the initial request (id=0), a few things happen:

1. The server makes a custom request back to the client (id=1). Processing this request will actually block handling the initial request (id=0). So request 0 cannot complete until id=1 does.
2. The client asks ALL language servers for workspace symbols. This includes our server running tower-lsp (that's id=2). So now request 0 depends on request 1 which depends on request 2. The client blocks until id=2 completes on the server (although in vscode for example, this will timeout after ~1s).

So basically, there's a point in time where there are three pending futures on the server:

id=0: the original request from the client
id=1: the server's custom request to the client
id=2: the new request from the client

And these need to be handled in reverse order.

I have this implemented, and it was blocking until I made this change. Which is probably what you would expect to happen:

diff --git a/src/transport.rs b/src/transport.rs
index 0b4a647..69c4802 100644
--- a/src/transport.rs
+++ b/src/transport.rs
@@ -95,11 +95,12 @@ where

         let mut framed_stdin = FramedRead::new(self.stdin, LanguageServerCodec::default());
         let framed_stdout = FramedWrite::new(self.stdout, LanguageServerCodec::default());
-        let responses = receiver.buffered(4).filter_map(future::ready);
+        let responses = receiver.buffer_unordered(4).filter_map(future::ready);
         let interleave = self.interleave.fuse();

Does this make sense? Or am I using custom request wrong? Because without the above change, I'm struggling to see how sending a server->client request could ever make progress?

[davidhalter]

I agree with @samscott89 that having concurrency should probably be possible. However it would probably be nice for some language servers to have no concurrency at all, because that might make the whole thing a bit simpler.

Most language servers will not be able to do a lot concurrently anyway. Calculating diagnostics (which is typically the most expensive operation) can usually not be done at the same time as calculating completions, because they access the same data structures. Although, most of the time caches can be used to avoid recalculating everything.

So IMO unless you have a more fancy architecture like @samscott89 you probably want no concurrency at all and this should probably be the default. However I don't see why users should not also be able to work with concurrency.

[ebkalderon]

Thanks for the suggestions and helpful discussion! However, there is unfortunately trouble associated with the use of buffer_unordered(), as described in commit 456856b which makes it undesirable. The issue is that while client-to-server and server-to-client messages should indeed be processed concurrently and in any order (as the transport is a full duplex channel), the individual client-to-server requests and server-to-client requests must return their responses in the order in which they were received, regardless of whether concurrency is used or not, as per specification. The current design interleaves server-to-client and and client-to-server communication over a single async channel, which means that neither buffered() nor buffer_unordered() will truly yield the correct behavior in this instance.

One possible solution that could solve the problem while preserving the specification invariants might be, as described in the issue description, to have two separate channels for server-to-client and client-to-server communication. Each of these channels would use buffered() by a certain amount to preserve the output ordering of client requests and server requests, respectively. However, these two channels would then be selected upon and process their respective messages without ordering to ensure that server-to-client and client-to-server communication can be buffered independently without either one blocking the other.

This still doesn't solve the data integrity issues caused by allowing servers to have concurrent handlers (which is the original subject of this issue), but it may at least fix the blocking problems @samscott89 described caused by client-to-server and server-to-client requests accidentally blocking on each other, I think.

I do like @davidhalter's suggestion of making the buffered concurrency configurable by the user and possibly disabled by default, though. Perhaps that may be the best route forward: come out of the box with concurrent processing of client-to-server and server-to-client messages, but each direction processing handlers sequentially in the order in which they were received.

[davidhalter]

the individual client-to-server requests and server-to-client requests must return their responses in the order in which they were received, regardless of whether concurrency is used or not, as per specification.

This is not how I understand the spec. The spec says:

However, the server may decide to use a parallel execution strategy and may wish to return responses in a different order than the requests were received. The server may do so as long as this reordering doesn’t affect the correctness of the responses.

I understand that this means that reording/rename requests may not be reordered, but I would say that even there there are exceptions: For example a local definition lookup could in theory be reordered with a rename in a different part of the code. That is still correct behavior according to the specification.

What do you think?

[samscott89]

I agree with @davidhalter's reading of things. But even so

The server may do so as long as this reordering doesn’t affect the correctness of the responses.

sounds like a brutal invariant to attempt to support generically! So even if technically it should be allowed, I could see a good argument for not supporting it in a higher-level framework like tower-lsp. For my specific use case, it would be more than reasonable to not support handling client requests out of order. But it is still a problem that a server cannot request information from the client during handling a client request. In the above diagram, the original id=0 request will block while waiting on id=1, but id=1 is behind id=0 in the buffer.

As far as I can tell, your proposed solution would achieve that:

However, these two channels would then be selected upon and process their respective messages without ordering to ensure that server-to-client and client-to-server communication can be buffered independently without either one blocking the other.

with that in place, you would see:

• the id=2 request from the client cannot complete while the server is still processing id=0. <-- IMO this is a reasonable restriction. Otherwise you need to support infinitely nested client-server interactions.
• but the id=1 request from the server to the client would complete before id=0 is finished, which would allow id=0 to continue and compute the response.

[Timmmm]

Sounds like it should be non-concurrent by default with opt-in to concurrency? I can't imagine there are many extensions that would really benefit from concurrency anyway.

[ebkalderon]

That's certainly a possibility, @Timmmm. Though it would be a shame to disallow scenarios such as @samscott89 described in this server. I do feel like this use case should be better supported by tower-lsp without too much fiddling, somehow.

I think I've devised a vague idea for how to proceed, though. If you check the work-in-progress support-custom-server-requests branch opened as part of #256, you may notice that the internal JSON-RPC implementation was completely reworked to support defining custom requests on LSP servers.

I can see a possible future where the interface for registering JSON-RPC methods also requires the user to specify a concurrency mode which essentially tells the Server (or LspService; haven't decided yet) whether to execute the incoming client-to-server request sequentially or concurrently. With this design:

1. Incoming client-to-server request handlers are marked either "sequential" or "concurrent."
2. "Sequential" request handlers are executed sequentially and must complete before the next incoming request can be processed, while one or more "concurrent" can be buffered together and executed concurrently to each other without any defined ordering.
   • TODO: Should we opt to use buffered() or buffered_unordered() for this? Tradeoff between delayed/ordered vs. rapid/unordered returning of responses.
3. Responses from the "sequential" request stream and the "concurrent" request stream are serialized into the output stream using future::stream::select() as they become available (along with any server-to-client request messages as well).
4. Incoming responses from server-to-client requests are always processed immediately as they come in, concurrently with the incoming client-to-server requests.

Whether tower-lsp should ship by default with all standard LSP methods configured to "sequential" or some sensible mixture of "sequential" and "concurrent" based on a conservative reading of the original spec is up for debate. But no matter the approach taken, these settings should probably be customizable by the end user when constructing the Server or LspService (depending on, again, where this request buffering functionality should ideally live).

In the example that @samscott89 gave above, one would explicitly define the custom id=0 request or notification on "Server" to be of the "concurrent" type, which would allow that async task to stick around and wait while the server processes the workspace/symbols id=3 request alongside it and the response to id=1 is received. This is precisely the behavior that we want.

How does this approach sound to all of you? I'd appreciate it if you could try to poke holes in this design.

[samscott89]

Thanks for the thoughtful response @ebkalderon!

In our case, we ended up scoping back the functionality to avoid needing to do that additional back-and-forth work. I don't know enough about what other LSPs are doing, but I wouldn't be surprised if what I was trying to do has a bit of a "code smell" to it.

If it's not super common, the risk is that supporting these esoteric use cases is going to add a bunch of complexity, so it might not be worth it?

Putting that aside though, what you described sounds like a cool way to make it work :)

[Timmmm]

If I understand it right you're saying commands are executed exactly in order, except if they're marked "concurrent" and then they can be executed concurrently with any commands in the same contiguous group of concurrent commands?

That sounds like a decent plan to me.