title: design a datastructure to return the number of connections to a web server in last 1 minute
body: <p>Asked this on cs.stackexchange.. got a downvote.. because i was not very clear.. So I will try to be more specific here..</p>
  
  <p>Q - design a datastructure to return the number of connections to a web server in last 1 minute..</p>
  
  <p>Assumptions - </p>
  
  <ol>
  <li>The server has a heavy incoming number of connection.. like Indian
  railways reservation OR a social nw site etc.. </li>
  <li>Suppose if this is a big data problem .. then I have the infra to run a big data job ..</li>
  </ol>
  
  <p>I am looking for:</p>
  
  <ol>
  <li><p>Efficiency - Is it possible to do this in O(1)? If, say, we do it in O(n).. the problem is that if it takes N milliseconds to compute the answer.. there are some more connections that have been enqueued in that N ms.. How should I tackle this.. or I can only ignore the small delay and O(n) is an OK performance</p></li>
  <li><p>Reasoning/Approach - Do we do something similar to this in any myriads of deployments we have in production? Is there a similar problem..?</p></li>
  <li><p>Is this "Big data"? Is the data for storing connections in last N (N is of order 10) minutes of the order a Big Data problem?</p></li>
  </ol>
  
  <p>My Effort:
  I know that -</p>
  
  <ol>
  <li>connections to a web server are put in a queue before being served by a thread</li>
  <li>each connection has a timestamp</li>
  </ol>
  
  <p>Approach -</p>
  
  <ol>
  <li>As soon as a connection is put in the Queue, write it to a file.. (at least its timestamp and a handle/unique identifier to the connection)</li>
  <li>As soon as client requests "give me num connections in last 1 minute" .. process the file to find out the number of connections .. we know current time in millisecs and that we have to find connections the timestamp of which fall in currentTime - 60 secs</li>
  <li>This job can be run using map reduce .. I also know that the file has sorted data (by timestamp)..</li>
  </ol>
  
  <p>I also run a daemon that removes entries/files older than 10 mins.. so that i dont store unwanted data </p>