What is the best way to design a heavy lookup web app?

Question

I am facing a bit of a conundrum with how I can structure my application, as I try to balance speed, cost, and efficiency.

I currently have a website, algfinder.com, which solves states of rubik's cubes. The computation runs purely on the client, and can sometimes crash on mobile devices due to too large of memory demand, as the algorithm to solve the cube takes up a lot of memory.

I would therefore like to implement a backend to do the heavy computation, but have a few notes and concerns.

Notes:

1. If I preprocess data, my computations will become very fast. For instance, the average query make take 20 seconds to calculate now, but with 20 GB of preprocessed data, may take < 1 second on average.
2. I would like to limit server payments to as little as possible.

The options I see:

1. I keep the code as is, have the client do computation, and artificially cap the size of a query a user can make. This is free and easy, but also makes the app slower and less useful.
2. I load a very large amount of preprocessed data (20GB+) in an s3, which is cheap. The problem is I will need to make hundreds of thousands of requests to the data, and even at low GET requests rates, this will become expensive.
3. I load a medium amount of preprocessed data into my backend server ram (<5GB), but this is also expensive as I am paying for RAM then, though no db / s3 lookups.
4. Have artificial constraints on the app, and provide the user the option to download preprocessed data (~1GB) to their machine to speed up computation.

Does anyone know of a better way to approach this problem? I am a completely new self-taught developer and this is the first project I have ever made so I am a little lost on how I can approach this.

Also, I kindly ask to avoid suggesting to make the algorithm faster or more efficient, it is already decently optimized for the specific use case I am targeting.

Thanks.

Answer 1

Your computations will require a certain amount of CPU and memory resources, regardless whether they run on a large server or multiple clients. CPU and memory will always produce costs which one can try to lower to some degree, but they won't vanish. You surely don't want to pay these costs by yourself, especially not with an increasing user base.

So when you offer your users a backend which does parts of the computation for them, sooner or later you will have to ask your users for payment (which could heavily decrease your user base), or you have to put advertisements on the site (with the risk this will not be sufficient).

Hence, I don't see any realistic alternative to let users of your site spend as much of their own computing power as they have for doing the computations - that is their investment or "payment" to use your service. When they use some insufficient hardware, it is their problem, not yours.

What you can improve is the user experience. Don't let your program just crash when the amount of memory is insufficient. Instead, you may

• monitor memory and stop the calculation with a graceful error message when available memory is getting low, or
• limit the amount of memory used by the algorithm beforehand (for example, by restricting the size of the queue inside the breadth-search to a maximum size, where the latter can be configured by the user). Of course, this may reduce the quality of the results.
• try to modify the algorithm to trade memory for speed when memory is low. Your option #4 looks like this approach, but there may be different approaches like using DFS instead of BFS for parts of the search tree.