Diseñar un contador de visitas

Diseñe un contador de visitas que cuente el número de visitas recibidas en los últimos 5 minutos.

Fuente: experiencia de entrevista de Microsoft

Muchas empresas, incluida Dropbox, han planteado recientemente el problema del «contador de visitas de diseño» y la pregunta es más difícil de lo que parece. Incluye un par de temas como el diseño básico de estructuras de datos, varias optimizaciones, concurrencia y contador distribuido.

Debe admitir las siguientes dos operaciones: hit y getHits .

hit (marca de tiempo) : muestra un hit en la marca de tiempo dada.

getHits(timestamp) – Devuelve el número de hits recibidos en los últimos 5 minutos (300 segundos) (desde currentTimestamp).

Cada función acepta un parámetro de marca de tiempo (en segundos de granularidad) y puede suponer que las llamadas se realizan al sistema en orden cronológico (es decir, la marca de tiempo aumenta monótonamente). Puede suponer que la marca de tiempo más antigua comienza en 1.

Ejemplos:

HitCounter counter = new HitCounter();

// hit at timestamp 1.
counter.hit(1);

// hit at timestamp 2.
counter.hit(2);

// hit at timestamp 3.
counter.hit(3);

// get hits at timestamp 4, should return 3.
counter.getHits(4);

// hit at timestamp 300.
counter.hit(300);

// get hits at timestamp 300, should return 4.
counter.getHits(300);

// get hits at timestamp 301, should return 3.
counter.getHits(301);

Preguntado en: Microsoft, Amazon, Dropbox y muchas empresas más.

1. Solución simple (enfoque de fuerza bruta):

Podemos usar un vector para almacenar todos los hits. Estas dos funciones se explican por sí mismas.

vector<int> v;
  
/* Record a hit.
   @param timestamp - The current timestamp (in 
                      seconds granularity).  */
  
void hit(int timestamp)
{
    v.push_back(timestamp);
}
  
// Time Complexity : O(1)
  
/** Return the number of hits in the past 5 minutes.
    @param timestamp - The current timestamp (in
    seconds granularity). */
int getHits(int timestamp)
{
    int i, j;
    for (i = 0; i < v.size(); ++i) {
        if (v[i] > timestamp - 300) {
            break;
        }
    }
    return v.size() - i;
}
  
// Time Complexity : O(n)

2. Solución optimizada para el espacio:

Podemos usar una cola para almacenar los resultados y eliminar las entradas en la cola que no sirven. Ahorrará nuestro espacio.
Estamos eliminando los elementos adicionales de la cola.

queue<int> q;
  
/** Record a hit.
    @param timestamp - The current timestamp 
                   (in seconds granularity). */
void hit(int timestamp)
{
    q.push(timestamp);
}
  
// Time Complexity : O(1)
  
/** Return the number of hits in the past 5 minutes.
   @param timestamp - The current timestamp (in seconds
   granularity). */
int getHits(int timestamp)
{
    while (!q.empty() && timestamp - q.front() >= 300) {
        q.pop();
    }
    return q.size();
}
// Time Complexity : O(n)

3. La solución más optimizada:

¿Qué pasa si los datos vienen desordenados y varios hits tienen la misma marca de tiempo?

Dado que el enfoque de la cola no funcionaría sin datos ordenados, esta vez use arrays para almacenar el recuento de visitas en cada unidad de tiempo.

Si estamos rastreando hits en los últimos 5 minutos en segundos con una granularidad de 300 segundos, cree 2 arreglos de tamaño 300.
int[] hits = new int[300];

TimeStamp[] veces = new TimeStamp[300]; // marca de tiempo del último hit contado
Dada una entrada, modifique su marca de tiempo en 300 para ver dónde se ubica en la array de hits.

int idx = marca de tiempo % 300; => hits[idx] mantiene el conteo de hits que tuvo lugar en este segundo

Pero antes de que aumentemos el recuento de hits en idx en 1, la marca de tiempo realmente pertenece al segundo que hits[idx] está rastreando.
timestamp[i] almacena la marca de tiempo del último hit contado.
Si timestamp[i] > timestamp, esta coincidencia debe descartarse ya que no sucedió en los últimos 5 minutos.
If timestamp[i] == timestamp, entonces hits[i] aumentan en 1.
If timestamp[i] currentTime – 300.

vector<int> times, hits;
  
times.resize(300);
hits.resize(300);
  
/** Record a hit.
   @param timestamp - The current timestamp
   (in seconds granularity). */
void hit(int timestamp)
{
    int idx = timestamp % 300;
    if (times[idx] != timestamp) {
        times[idx] = timestamp;
        hits[idx] = 1;
    }
    else {
        ++hits[idx];
    }
}
  
// Time Complexity : O(1)
  
/** Return the number of hits in the past 5 minutes.
    @param timestamp - The current timestamp (in 
    seconds granularity). */
int getHits(int timestamp)
{
    int res = 0;
    for (int i = 0; i < 300; ++i) {
        if (timestamp - times[i] < 300) {
            res += hits[i];
        }
    }
    return res;
}
// Time Complexity : O(300) == O(1)

¿Cómo manejar requests concurrentes?

Cuando dos requests actualizan la lista simultáneamente, puede haber condiciones de carrera. Es posible que la solicitud que actualizó la lista primero no se incluya eventualmente.

La solución más común es usar un candado para proteger la lista. Cada vez que alguien quiera actualizar la lista (ya sea agregando nuevos elementos o eliminando la cola), se colocará un candado en el contenedor. Una vez finalizada la operación, la lista se desbloqueará.

Esto funciona bastante bien cuando no tiene un gran volumen de requests o el rendimiento no es una preocupación. Colocar un bloqueo puede ser costoso en algunos momentos y cuando hay demasiadas requests simultáneas, el bloqueo puede bloquear el sistema y convertirse en un cuello de botella de rendimiento.

Distribuir el contador

Cuando una sola máquina recibe demasiado tráfico y el rendimiento se convierte en un problema, es el momento perfecto para pensar en una solución distribuida. El sistema distribuido reduce significativamente la carga de una sola máquina al escalar el sistema a múltiples Nodes, pero al mismo tiempo agrega complejidad.

Digamos que distribuimos las requests de visita a varias máquinas por igual. Primero me gustaría enfatizar la importancia de la distribución equitativa. Si determinadas máquinas reciben mucho más tráfico que el resto de las máquinas, el sistema no alcanza su pleno uso y es muy importante tener esto en cuenta al diseñar el sistema. En nuestro caso, podemos obtener un hash del correo electrónico de los usuarios y distribuirlo por hash (no es una buena idea usar el correo electrónico directamente ya que algunas letras pueden parecer mucho más frecuentes que otras).

Para contar el número, cada máquina funciona de forma independiente para contar sus propios usuarios desde el último minuto. Cuando solicitamos el número global, solo necesitamos sumar todos los contadores.

Referencias: Lo había publicado originalmente aquí .
https://aonecode.com/getArticle/211