Come è possibile registrare un utente in un sistema con miliardi di dati simili senza ritardi?

0

Prendendo ad esempio Google mail e Facebook, entrambi hanno un enorme database di utenti. Sarebbe facile cercare attraverso un database di 100 accessi simili e trovare una corrispondenza in un secondo, ma non nel caso di Google e Facebook. Quando provi ad accedere a Facebook o a GMail, con una credenziale corretta, ti verrà effettuato il login prima ancora di premere la Enter key.

In che modo le informazioni dell'utente vengono interrogate sul mega database per fornire una risposta rapida senza indugio?

    
posta Nexima360 20.03.2016 - 10:56
fonte

5 risposte

12

Stai chiedendo in che modo Google può individuare il record per un particolare utente a miliardi di dollari così velocemente? Questa è fondamentalmente una domanda di indicizzazione . Supponiamo che tu disponga di una tabella di database di un miliardo di record e che sia necessario individuare un singolo record basato su un nome utente. Un approccio ingenuo sarebbe quello di attraversare il tavolo e per ogni record vedere se corrisponde al nome utente. Questo sarà lento, perché dovrai controllare in media mezzo miliardo di dischi prima di trovare quello che stai cercando. Questo sarà lento.

Ma se si crea un indice in cui tutti i nomi utente nel database sono ordinati alfabeticamente, è possibile utilizzare un approccio diverso. Invece di iniziare dall'inizio, si inizia nel mezzo dell'indice e si controlla se il nome utente è in ordine alfabetico prima o dopo il valore medio. Questo ti dice quale metà dell'indice contiene il valore cercato. Quindi ripeti l'operazione ancora su questa metà dell'indice. Ogni iterazione ridurrà lo spazio di ricerca a metà, il che significa che avrete bisogno di solo 30 operazioni (2 ^ 30 > 1 miliardo) prima di aver individuato il record specifico (o determinato che non esiste). Quindi un indice di database appropriato può ridurre il numero di operazioni da mezzo miliardo a 30. E 30 operazioni sull'hardware moderno avverranno più rapidamente di un battito di ciglia.

Ci sono molti modi per costruire e cercare indici, ma quanto sopra è il succo di ciò. Permette di localizzare i record molto velocemente anche in database di grandi dimensioni.

    
risposta data 20.03.2016 - 11:51
fonte
4

La convalida delle credenziali può essere eseguita in pochi millisecondi per un miliardo di utenti. Questo a causa di:

  1. Indicizzazione (riduce il numero di operazioni a soli 30, per 1 miliardo di utenti). Ulteriori dettagli: link
  2. Cache (farà in modo che queste 30 operazioni non colpiscano il disco il più delle volte)

Nel mondo reale, ciò richiederebbe 1 - 300 millisecondi (paio di accessi al disco + accodamento + concorrenza a causa di registrazioni costanti e modifiche della password).

Esempio estremo:

Se l'organizzazione può permettersi macchine con memoria di grandi dimensioni (ad esempio, macchine con una memoria da 200 GB), ciò richiederebbe un tempo quasi zero.

Pronuncia stringa contenente nome utente: password (salata + password con hash nei sistemi reali) sono memorizzati in una mappa. La ricerca di questa mappa per scoprire se una determinata combinazione di nome utente e password è valida o meno, richiederebbe quasi il non-tempo. Questo perché Hashtable può controllare la presenza o l'assenza nella complessità temporale O (1).

In altre parole, non importa se il sistema ha 100 utenti o 100 milioni o miliardi; le password possono essere convalidate in un tempo vicino allo zero.

Il codice seguente lo dimostra con un set di dati più piccolo (60 milioni di username / password e 20 milioni di utenti che si collegano). Ci sono voluti solo 0,002 millisecondi per validazione.

Sun Mar 20 18:40:11 IST 2016::Starting
Sun Mar 20 18:43:03 IST 2016::Generated test data, count 40000000
Doing 20000000 validations.
Sun Mar 20 18:43:30 IST 2016 Done in 26860 msecs.
0.001343 milliseconds per validation

Codice:

import java.util.Date;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class UserValidator {

    Set<String> validCredentials=new HashSet<>();
    long numCredentials = 1000*1000*60;
    Random rnd = new Random();
    char[] validChars=null;

    public UserValidator(){
        String chars="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!@#$%^&*~*()";
        validChars = chars.toCharArray(); 
    }

    String generateRandomString(int len){
           StringBuilder sb = new StringBuilder( len );
           for( int i = 0; i < len; i++ ) 
              sb.append( validChars[ rnd.nextInt(validChars.length) ] );
           return sb.toString();
    }

    String getRansomString(){
        int len = 4;
        len = len+rnd.nextInt(20);
        return generateRandomString(len);
    }


    void generateTestData(){
        for(long i=0;i<numCredentials;i++){
            String username=getRansomString();
            String password=getRansomString();
            String credentials=username+":::"+new String(username+":"+password).hashCode();
            validCredentials.add(credentials);
        }
    }

    boolean isValidUser(String user, String password){
        String credentials=user+":::"+new String(user+":"+password).hashCode();
        return validCredentials.contains(credentials);
    }

    public static void main(String[] args) {
        UserValidator u = new UserValidator();
        System.out.println(new Date().toString()+"::Starting");
        u.generateTestData();
        System.out.println(new Date().toString()+"::Generated test data, count "+u.validCredentials.size());
        int lookups=20*1000*1000;
        System.out.println("Doing "+lookups+" validations.");
        long timeStart = new Date().getTime();
        for(int i=0;i<lookups;i++){
            u.isValidUser(u.getRansomString(), u.getRansomString());
        }
        long timeEnd = new Date().getTime();
        long timeSpent = (timeEnd-timeStart);
        System.out.println(new Date().toString()+" Done in "+timeSpent+" msecs.");
        System.out.println((double)timeSpent/(double)lookups +" milliseconds per validation");
    }

}
    
risposta data 20.03.2016 - 15:11
fonte
1

Le buone risposte esistenti suggeriscono indici, ma per le ricerche di stringhe come questa trie funziona ancora meglio. Ignora per un secondo i nomi non alfabetici. Organizzate tutti i possibili nomi in una struttura ad albero con 27 rami per ogni livello: a-z e Fine-corda. Con un input come "john", prendi il ramo j, quindi il ramo o, il ramo h e il ramo n e infine la voce fine-stringa per ottenere la password di john. Sono solo 5 passaggi.

    
risposta data 21.03.2016 - 17:42
fonte
-5


Ho un'altra risposta spero che ti piacerebbe, hai notato che quando scrivi www.google.com nella barra degli indirizzi poi reindirizza in base alla posizione, come se vivessi in India, poi ti reindirizzerà a questo URL: www.google.co.in . Oppure, se vivi nel Regno Unito, ti reindirizzerà a questo URL www.google.co.uk . O qualcosa del genere. Questo è un trucco per rendere Google molto più veloce. Questo è un trucco chiamato tecnica divide and speed . Molti programmatori lo usano come primo trucco per la velocità.

    
risposta data 21.03.2016 - 06:04
fonte
-6

Se milioni di utenti tentano di utilizzare il database alla volta, l'utilizzo dei dati sul traffico aumenta e la connessione diventa lenta. Se provi a conservare tutti i dati in tabelle separate, diventerà molto veloce, poiché l'utilizzo dei dati sul traffico non aumenterà.

    
risposta data 20.03.2016 - 11:15
fonte

Leggi altre domande sui tag