I built a social Android application in which users can see other users around them by GPS location. At the beginning thing went well as I had low number of users, but now that I have increasing number of users (about 1500 +100 every day) it has revealed a major problem in my design.
In my Google App Engine servlet I have static HashMap that holds all the users profiles objects, currently 1500 and this number will increase as more users register.
Why I’m doing it?
Every user that requests for the users around him compares his GPS with other users and checks if they are in his 10km radius. This happens every five minutes on average.
Consequently, I can’t get the users from db every time because GAE read/write operation quota will tear me apart.
The problem with this design is?
As the number of users increases, the Hashmap turns to null every 4-6 hours, I think that this time is getting shorter, but I’m not sure.
I’m fixing this by reloading the users from the db every time I detect that it becomes null, but this causes DOS to my users for 30 sec, so I’m looking for better solution.
I’m guessing that it happens because the size of the hashmap. Am I right?
I have been advised to use a spatial database, but that means that I can’t work with GAE any more and it means that I need to build my big server all over again and lose my existing DB.
Is there something I can do with the existing tools?
Thanks.
2
There are a couple things I might suggest, without knowing much more about the specifics of your situation. In many ways, the problem as stated is analogous to a common collision detection problem.
-
Reduce the Resolution. In a way you have already taken steps to reduce the resolution by limited the update rate (to five minutes). A second way would be to use a ‘bounding box’ concept over a specific point to identify closeness, or nearby users within an area. In your case, each user would be assigned a surrounding rectangle. If the rectangles of two users meet or interserct, then they are close enough to render/display in the same spot, and simply annotate each marker with more exact coordinates.
-
The data structure you are using might be ok, but it may need tuning. Its hard to say without seeing some degree of implementation. A possible alternative that generally works well with the bounding box concept is a quadtree; especially one that considers and handles periodic movement of contained objects.
-
Caching strategy. If you aren’t partitioning your cache into areas, or higher level quads, you may want to consider it. This way, when updates do occur at your set interval, you only have to update the cache for the partial/selected areas where you a) have users and b) the users have moved.