1

I'm trying to write a new API that can support many devices. There will be at least 50k devices in the beginning that will connect to the server using an HTTP API on a daily basis to receive updates.

The number of devices increases with time (with new installations).

The devices need to contact the server once per day to get information.

The time for making this call doesn't matter.

I want to ensure that the request calls from devices are randomly distributed so as to balance the load on the server.

Suppose that in response to the API call, I have information regarding the next request datetime.

What is a good way to find the optimal time for making this call (within next 24 hrs)? Once suggested, all devices should continue calling at that given time every day.

As this will be a global solution, I plan to pick a time much later after regular working hours for the given device. Let's say 10 PM to 5 AM is the suggested time for each region.

Within those 7 hours, how can I evenly distribute the time for any given device?

Some additional info:

  • Time will be allocated for the device when it is making a valid request for the first time
  • You can manually force the device to make the call using client software, but that does not change the default settings. But it will also be possible to change the time from the server manually (force entry- no logic required).

I have devised a crude way of tracking the log per minute [minuteofday], [frequency], by selecting the one with the lowest frequency. This should log with respect to a constant of 1440 entries. There is always a chance for race situations.

I also need to assign additional resource when needed.

7
  • Suggestion: pick randomly to begin with, but then have a small probability of assigning the device to the least busy timeslot. A small probability, because if it had a large probability then you'd just assign all the devices to that timeslot and overload it.
    – user253751
    Dec 22, 2020 at 15:30
  • 2
    Alternative suggestion: keep track of the number of devices assigned to each timeslot; when you reassign a timeslot, add -1 to the old timeslot and +1 to the new timeslot. But when the timeslot actually happens, overwrite the score with the number of devices that actually contacted the server in the timeslot. Then you can deterministically move devices to the least busy timeslot.
    – user253751
    Dec 22, 2020 at 15:31
  • The requirement to avoid working hours makes it a lot more complicated, since a very busy region's update window could partially overlap with less-busy regions' windows.
    – user253751
    Dec 22, 2020 at 15:34
  • @user253751 - you are correct , there are going to be overlaps.even if one goes by regions like North America, South , Europe and Middle East.. to limit regions i can already see 3 to 4 hrs overlap. Thanks for your comments
    – TheMar
    Dec 22, 2020 at 21:01
  • 1
    You can let the device itself choose a time at pseudo-random. Seed the pseudo-random algorithm most likely already present in your programming language with information unique to the device and map the resulting number between 0 and 1 into an hour and minute. MAC adresses and serial numbers would be good candidates. Dec 24, 2020 at 12:12

3 Answers 3

1

From your question I understand you like to

I want to make sure that the request calls from devices are as randomly distributed so as to make the load on the server as even as possible.

So I would start with giving each device the ability to randomly select the time it should contact the server, and not enforcing this on the server side.

You like your devices to call the API during a 7 hours window starting at 10 PM.

7 hours -> 25200 seconds.

So each device will have a time pick up logic like

if (I already selected my date){
    keep on using it
} else {
   Random number between 0 and 25200;
   10 PM + random number;
   store above time  
}
1
  • -I don't have ability to control when the device will first access server. Depends on physical installation. It is part of a network equipment installation, so there is a high probability it will happen during the said 7-hour window. One thing I am concerned about is 'random' selection. I use random functions heavily and seen that random functions are not really random (dot net) over a large set. Just relying on random may not be enough.
    – TheMar
    Dec 24, 2020 at 17:16
0

You are essentially trying to hash a lot of devices into very few buckets (time slots). You are guaranteed to have some collisions.

I mean, even mathematically: with 50k starting devices and even utilizing the entire 24 hours in a day, you'll get at most 1.728 seconds to service each device.

Also, there are a lot of things that can happen, which will cause a device not to honor your request to only call in at the specified time.

So, since conflicts are unavoidable, I'd suggest implementing your API in such a way, that it first checks how busy you are, and either quickly responds asking to come back in 5 minutes (or at the specified time slot, that you expect is going to be less busy) or services the device right away.

You can even simply drop the request without handling it to save time, and have device retry automatically after a random internal timeout elapses.

Although, I'd avoid looking for randomness when it comes to balancing a load like this—random does not necessarily mean equally spread out.

1
  • Thank you for your answer. First your statement about "device not honoring request to call" is a know issue at work . Didnt want to add it and complicate my question. I am OK with conflicts. I am also not going to seconds as want to give device its own time to make the call. . let us say web server is able to handle 1000 calls per second that would lessen impact because of any conflicts. but at the same time I dont want 20K systems trying call at the same time,if avoidable .503 is still my last bet
    – TheMar
    Dec 22, 2020 at 21:16
0

"The time for making this call doesn't matter."

Then why not just let the clients call the API ?

"I want to ensure that the request calls from devices are randomly distributed so as to balance the load on the server."

You cannot randomly distribute calls which has not yet been activated - that would be controlling the future.

1
  • I made a mistake , I will remove the statement "The time for making this call doesn't matter.". I cannot control when the device willmake its first call. Depends on installation. But subsequent calls can be controlled. response to first call will contain suggested slot (time) that device must use from there on.
    – TheMar
    Dec 28, 2020 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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