Fast, Open Source Search
typesense.org
typesense.org
Some quick context: we are a small bootstrapped team that's been working on Typesense since 2015. It started out as a nights-and-weekends project, out of personal frustration with ElasticSearch's complexity for doing seemingly simple things. So we set out (maybe naively at the time), to see what it would take to build our own search engine, just to scratch our intellectual curiosity. Over the years, we've realized that it takes a LOT of nuanced effort to build a search engine that works well out of the box.
Our goal with Typesense is to democratize search technology on two fronts:
1. Simplify and reduce the amount of developer effort it takes to build a good search experience that works well out of the box. To this end, we pore over API design to make it intuitive and set sane defaults for all parameters.
2. Make good instant-search technology accessible to individuals and teams of all sizes. To this end, we decided to open source our work and make it completely free to self-host. We also optimize for reducing the operational overhead it takes to deploy Typesense to production (eg: single binary with no runtime dependencies, one-step clustering, etc).
In 2020, I left my full-time job and my co-founder left his full-time job a month ago, and we're now both working full-time on Typesense.
Happy to answer any questions!
At the heart of Typesense is a `token => documents` inverted index backed by an Adapative Radix Tree (https://db.in.tum.de/~leis/papers/ART.pdf), which is a memory-efficient implementation of the Trie data structure. ART allows us to do fast fuzzy searches on a query.
All indices are stored in-memory, while the documents are stored on disk on RocksDB. All underlying data structures were carefully designed, benchmarked and optimized to exploit cache locality and utilize all cores efficiently.
do you have any metric regarding the memory usage of your ART implementation ?
I tried to implement one for the database I'm currently working on, however I feel that I am using way too much memory.
Basically, with my current implementation a dictionary containing about distinct 2857086 words would require 341MB.
As far as Typesense goes though, I found that the actual posting lists, document listings, and other faceting/sorting related indexing data structures is where the bigger overhead is, especially for larger datasets.
I'm currently considering using compressed pointers on some part of the tree to reduce the memory footprint as much as I can. Let's see how it goes...
Also, after a quick look through the codebase, it really resembles how Algolia deals with indexes:
https://www.algolia.com/blog/engineering/inside-the-algolia-...
And distributed search:
http://highscalability.com/blog/2015/3/9/the-architecture-of...
Amazing project, hopefully gets a lot of traction.
a) While Algolia (from what is available publicly) has indices which are pre-sorted on a set of ranking factors, Typesense allows dynamic, on-the-fly sorting.
b) Also I believe Algolia memory maps their indices, but Typesense stores the raw JSON documents on-disk and constructs the index from scratch on start-up.
If you just want the fuzzy-search part (query string -> list of matching document ids) and don't want to pay for GBs of RAM, sonic [1] seems to be an interesting project. It's very fast (μs) and uses very little RAM but doesn't offer DB-like features such as sorting, schemas/fields, scoring etc. It's more of a low-level primitive for building your own search feature than an integrated search db that's ready to use out of the box.
I've now updated the demo to send queries to a node that's closest to the user, so it shouldn't jump around any more.
Essentially something like the result of indexing a json row of field/value pairs for a bunch of csvs (with different fields) that would lead to being able to do faceted search on an individual field across rows/datasets, or being able to find the bits related to a needle deep in the dataset haystack.
It is quite powerful and you can even choose to "stringify" or co-erce types automatically to deal with dirty data.
How it would work if there were incompatible fields in the schemas across different datasets? (unless it was basically a stringify operation across the whole thing. )
If record1 has {field1: 32, field2: true, field3: '22'} and record2 has {field1: "32", field2: 'true', field3: 22}
When record1 is indexed, the data type for field1 is set to int, field2 is set to bool and field3 is set to string.
Then when record2 shows up, field1 is coerced to an int, field2 is coerced to a bool and field3 is coerced to a string.
If a coercion is not possible, you can configure it to be ignored or error out.
re: facets, you can use a regex field name and set for example all fields that end with `.*_facet` to be a facet.
A crawler is probably not the best tool for this if you use some form of site generation, as you can also use it to generate the information that goes into Typesense.
There are libraries that let you do the conversion:
Dynamic synonyms will require more thought given the machine learning aspects involved. May require domain specific models. And I also wonder how "off-the-shelf" it will really be in practice.
Are your SDKs (python) thread safe?
Asking as current user of meilisearch which is a great product and I would give it 8/10 because of some quirks. Considering trying typesense. Thanks.
I don't have comparative benchmarks, but here are some Typesense benchmarks:
A dataset containing 2.2 Million recipes (recipe names and ingredients):
- Took 3.6mins to index all 2.2M records
- On a server with 4vCPUs, Typesense was able to handle a concurrency of 104 concurrent search queries per second, with an average search processing time of 11ms.
A dataset containing 28 Million books (book titles, authors and categories):
- Took 78mins to index all 28M records
- On a server with 4vCPUs, Typesense was able to handle a concurrency of 46 concurrent search queries per second, with an average search processing time of 28ms.
With a dataset containing 3 Million products (Amazon product data), Typesense was able to handle a throughput of 250 concurrent search queries per second on an 8-vCPU 3-node Highly Available Typesense cluster.