Support Elasticsearch/OpenSearch for user search

This issue has been migrated from [#14608](https://github.com/matrix-org/synapse/issues/14608).

---

## Preamble

Synapse's user search feature has a few long-standing known shortcomings when searching for display names, namely:

* It's diacritic (accents) sensitive (https://github.com/matrix-org/synapse/issues/1523)
* It works badly with foreign languages (https://github.com/matrix-org/synapse/issues/13655)
* It's case sensitive in non-latin languages (https://github.com/matrix-org/synapse/issues/14630)

Addressing these issues is non-trivial with PostgreSQL's full text search capabilities. In this writeup I am exploring integrating [Elasticsearch](https://www.elastic.co/), which is a full text search engine backed by [Apache Lucene](https://lucene.apache.org/), into Synapse.

Note that mentions of Elasticsearch in this writeup also include [OpenSearch](https://opensearch.org/), which is AWS's fork of Elasticsearch and has, as far as I can tell, compatible APIs with Elasticsearch (at least regarding the features that are relevant to us).

Also note that I am focusing specifically on user search, and am not including message search to avoid scope creep.

## Indexing

Elasticsearch's equivalent of an SQL table is called an _index_. An index contains a number of _documents_, which are freeform JSON blobs. In the context of user search, this is where we would store user profiles. This is an example of a document in an Elasticsearch index:

```json
{
"_index": "synapse_user_search_4",
"_id": "@foo:bar.baz",
"_version": 1,
"_seq_no": 5,
"_primary_term": 5,
"found": true,
"_source": {
"user_id": "@foo:bar.baz",
"display_name": "Léonard Foo",
"avatar_url": null
}
}
```

Here, we're mostly interested in two properties:

* `_id`: the document's identifier. A document can be created without identifiers, in which case Elasticsearch automatically generates one for it.
* `_source`: the document's data.

In this example, I've used the user's MXID as the document's ID (so that we can easily update it in the future), and the structure of profiles as they are returned by the [`/user_directory/search`](https://spec.matrix.org/latest/client-server-api/#post_matrixclientv3user_directorysearch) endpoint. In practice we'll probably want to remove the `user_directory` from the document's source, in order to avoid duplicating data.

### Analysis

We want our greatly improved user search to be:

* case insensitive
* diacritics insensitive

For this, we need to create the Elasticsearch index and configure it with an _analyzer_. The analyzer is in charge of looking at all new piece of data and tokenise (while also retaining the document's source) it so it's easily searchable later on.

We create our index with a custom analyzer that is both case- and diacritics-insensitive:

```json
PUT /synapse_user_directory_search

{
"settings": {
"analysis": {
"analyzer": {
"std_asciifolding": {
"tokenizer": "standard",
"filter": [ "asciifolding", "lowercase" ]
}
}
}
},
"mappings": {
"properties": {
"display_name": {
"type": "text",
"analyzer": "std_asciifolding"
}
}
}
}
```

There are a few things happening here:

* in `settings.analysis.analyzer`, we define a custom analyzer on the index. This analyzer includes two token filters: [`asciifolding`](https://www.elastic.co/guide/en/elasticsearch/reference/8.5/analysis-asciifolding-tokenfilter.html), which folds non-ASCII characters in tokens to an equivalent ASCII character (thus eliminating accents), and [`lowercase`](https://www.elastic.co/guide/en/elasticsearch/reference/8.5/analysis-lowercase-tokenfilter.html) which forces tokens into lower case.
* in `mappings.properties`, we assign our custom analyzer to the `display_name`, since this is where we might have diacritics and case variations.

### Document insertion and update

When the index is created, we can start adding documents to it:

```json
PUT /synapse_user_directory_search/_doc/@foo:bar.baz

{
"user_id": "@foo:bar.baz",
"display_name": "Léo Foo",
"avatar_url": null
}
```

Note that the request for updating an existing document is identical to the one above. When a document is updated, its `_version` property is automatically incremented.

### Search

Now we can search for users:

```json
GET /synapse_user_directory_search/_search

{
"query": {
"match_phrase_prefix": {
"display_name": {
"query": "leo"
}
}
}
}
```

(yes, this is a `GET` request with a body)

We use a [`match_phrase_prefix`](https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-match-query-phrase-prefix.html) query to ensure we start matching at the start of a sequence of tokens, instead of starting matching in the middle of a token.

Results are then provided in the following format:

```json
{
"took": 4,
"timed_out": false,
"_shards": {
"total": 1,
"successful": 1,
"skipped": 0,
"failed": 0
},
"hits": {
"total": {
"value": 1,
"relation": "eq"
},
"max_score": 0.2876821,
"hits": [
{
"_index": "synapse_user_search_5",
"_id": "@foo:bar.baz",
"_score": 0.2876821,
"_source": {
"user_id": "@foo:bar.baz",
"display_name": "Léo Foo",
"avatar_url": null
}
}
]
}
}
```

On each hit, a score is associated in the `_score` property to help sort results.

With the query previously mentioned, the same score will be attributed to every result. We will probably want to use a more elaborate query, such as a boolean compound query, which would allow attributing a higher score to exact matches (see an example [here](https://stackoverflow.com/a/53001213)). We will also probably want to tweak the query so that it also matches on MXIDs.

## Integration

First off, we will probably want to make this integration optional. While there are valid use cases for requiring better user search results than the ones provided by PostgreSQL's full text search support, PostgreSQL is also good enough for most servers catering to a community that mostly uses latin-based languages. Mandating those servers to support Elasticsearch for user search would be an unnecessary burden, both in terms of resources and, if the Elasticsearch cluster is self-hosted, in maintenance.

Technically, integrating Elasticsearch into Synapse would mean writing our own interaction layer. Elastic does provide an [official Python module](https://github.com/elastic/elasticsearch-py), which even has [async support](https://elasticsearch-py.readthedocs.io/en/latest/async.html), however this async support uses [aiohttp](https://github.com/aio-libs/aiohttp) for transport. I don't know if aiohttp is even compatible with Twisted, and I assume we will probably want to use Twisted agents to perform requests. There have been efforts in the past to write an Elasticsearch module for Twisted-based applications ([txes2](https://github.com/lextoumbourou/txes2)), but it looks widely out of date and unmaintained (and is still incompatible with Python 3).

Writing our own integration for Elasticsearch should not be very complex, however, since as demonstrated above we would only need to perform a couple of types of HTTP requests (creating/updating documents, and searching).

### Migration

How to migrate user search data from PostgreSQL to Elasticsearch and back is an area which needs further research. It will likely need a script ran manually by the server admin, similar to the existing SQLite -> PostgreSQL migration script we currently have. There might be a way to make this migration incremental to ease the pain on servers with a very large number of users, but I'm not entirely sure.

## Conclusion

Supporting Elasticsearch in Synapse looks like a pretty big amount of work, but I think it's also work that is worth putting in to enable more communities around the world to adopt Matrix. In my manual testing, most issues with user search that are caused by PostgreSQL's full text search engine seem to be resolved with Elasticsearch, apart from [one edge case](https://discuss.elastic.co/t/match-queries-and-ascii-folding/319544) which I believe to be acceptable.

It is also worth considering that, once in place, we might also want to use Elasticsearch to handle message search, which has similar issues to user search.

To be clear, I am not claiming this work should be the team's highest priority by opening this issue - I mostly wanted to compile and share the findings from spending a limited amount of time researching options to improve user search.

Start at the /user_directory/search endpoint and review the existing PostgreSQL full-text search path. Then investigate the proposed optional Elasticsearch/OpenSearch indexing, update, and search integration, including the existing SQLite-to-PostgreSQL migration approach. Done would require an agreed design covering integration, migration, and user-search behavior; this issue does not name implementation files or tests.

Written by the indexing model from the issue text.