0

I need to chose the best solution (software and algorithm) to solve my problem. I need to store up to million strings and data associated with them. Strings are search queries and data is cached search result. So the operations I'm going to perform are:

  • get a query from user
  • look for cached result in DB (exact match)
  • if found - return it
  • if not - perform a search and store the result

Some other facts:

  • As it is cache rows will expire over time.
  • Lookup and insert speed is a priority.
  • This string field is most probably the only one to search by.
  • I'm using PHP

Looks like hashing the string is a good idea, collisions are not a problem, if I get it I will just assume it's a cache miss and perform a new search. So I'm thinking of the following options:

  • MySQL with hash stored in binary field
  • MySQL with hash as string with index
  • MongoDB (maybe with capped collection instead of expiration time field)
  • some other solution (specialized key-value storage or something) I don't have experience with if it's good enough and worth learning for the project

I also have used Sphinx search when I needed almost the same thing but with partial match also. For exact search it seems to be an overkill.

So is hashing a good idea at all? Which hash algorithm would you recommend? Which option if better and why? Does the answer change if I need to store 5 million rows? What if I add hits field to get most popular rows from time to time?

1

PostgreSQL is perfectly fine for this. You got a couple of options to make this work.

First of all: PostgreSQL has a special index type for that called GIN (http://www.cybertec.at/gin-just-an-index-type/). It is perfect for full-text-search in general.

The cool thing is: In the latest version of PostgreSQL there is support for a thing called jsonb. You can put your string into a JSON document and search on EACH field in the JSON in a nice way using GIN and a couple of cool operators (see http://www.postgresql.org/docs/9.4/static/datatype-json.html). JSONB is really really fast, very powerful and it definitely kills MongoDB on the performance side. In addition to that a couple million of rows are no real big deal for PostgreSQL anyway. There is one more cool thing: PostgreSQL can do fuzzy search on strings (through Nearest-Neighbour search).

0

I wouldn't suggest using capped collections: they scale badly, as they can't be sharded as of the time of this writing and maybe never. See the according feature request on MongoDB's JIRA.

I would use a different approach.

  1. Use the users query string as _id. Since the exact query is what identifies your records, there is no need to hash it on the client side. Plus, the _id is created anyway.
  2. Use the hashed version of that string as your shard key as described in "Create a Hashed Index" in the MongoDB docs. The reason for doing this is that your query strings might have a low cardinality and the way scaling with MongoDB works, choosing a shard key with low cardinality is a Very Bad Idea™. Another shard key may be a viable solution, however.
  3. Issue an upsert incrementing the hits counter with write concern "unacknowledged" on the document identified by the incoming query string before querying the database for that string. Though it can't be guaranteed that the result of the query will contain the increment to the hits counter, it will be eventually added. The advantage of this approach is that the command will not block and therefor delay your search in the database. If the search is already stored in the db, you can simply return the result. If you have to perform the search, you can upsert the existing document with the hit counter of 1.

Following these steps should give you what you want. You can find the documents by the exact query string, the solution is scalable (depending on your resources to several billion query strings), you can expire data using TTL indices which makes it obsolete to have an expiration logic maintained and triggered by you.

There are several different approaches you could use, for example implementing meta searches using text indices. But the approach as described is the easiest one to implement.

  • I wouldn't presume that storing a million strings requires sharding; you should be able to comfortably wrangle that on a modern laptop :). I would also not recommend unacknowledged write concerns if you care about the data. A difference between default (acknowledged) writes and unacknowledged is that unack'd writes ignore insertion errors (for example, duplicate key exceptions). A more appropriate approach for speeding up insertion would be to use Bulk Inserts. – Stennie Aug 20 '14 at 0:07
  • Capped collections also aren't relevant for sharding as they are a fixed-size FIFO collection optimised for fast writes and sequential reads. You can't delete documents from a capped collection, and the documents are maintained in insertion order. If you need to scale writes beyond a single server, you should use a normal sharded collection. – Stennie Aug 20 '14 at 0:15
  • Stennie, I am very aware of the implications of unacknowledged write concern and capped collections. And you should really show me how an upsert should trigger a duplicate key exception. I am curious on how that should work. Bulk inserts, on the other hand, have the problem that a bulk insert for a single document simply doesn't make sense. And the OP asked about capped collections, if you read closely, so this is a topic to be covered in the answer, how misguided the notion of capped collection may be in this context. – Markus W Mahlberg Aug 20 '14 at 0:37
  • Plus, it is not that a hit counter needs to be one with extreme precision. For 99.999% of the use cases the order of magnitude is by far enough, and if it was a key feature for this application, I am pretty sure that it wouldn't have been mentioned in a half sentence, would it? – Markus W Mahlberg Aug 20 '14 at 0:44
  • You're correct that duplicate key exceptions don't apply to upserts. My comment was that in general it doesn't seem sensible to recommend unacknowledged writes if you care about the data (in this case, maybe the OP does not). With regards to capped collections, your answer could be clearer that they aren't fit for the use case (FIFO vs the comments on scaling/sharding which seem a misdirection). I mentioned bulk inserts as an alternative to speeding up insertions (assuming that's the only reason you want unacknowledged writes). It seems implicit that bulk inserts are for multiple docs :). – Stennie Aug 20 '14 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.