El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Cerca i Ordenació en Grans Volums de Dades

Següent ►
►

Tercer cas d'estudi. A 06-01 el repte era encadenar algorismes; a 06-02, modelar un domini nou; aquí el repte és la mida: Rutalia fa anys que opera i ha acumulat 200 milions de registres històrics de lliuraments (~40 GB) que Direcció vol consolidar i analitzar. Els algorismes de cerca i ordenació del mòdul 4 continuen sent la base, però hi ha un supòsit silenciós que es trenca: que les dades caben a la RAM i que accedir a un element costa el mateix que a qualsevol altre. Quan això deixa de ser cert, la variable que governa el disseny ja no és el nombre de comparacions sinó el nombre d'accessos a disc, i d'aquest canvi de moneda neixen l'ordenació externa, els arbres B, MapReduce i les estructures probabilístiques que veurem aquí.

Contingut

  1. Quan les dades no caben a la RAM: la jerarquia de memòria
  2. Ordenació externa: runs ordenats + mescla de k vies
  3. Índexs: per què les bases de dades no fan cerca binària
  4. MapReduce: el paradigma divideix-agrupa-combina
  5. Estructures probabilístiques: el filtre de Bloom i els seus cosins
  6. Top-K en streaming: els 10 codis postals amb més lliuraments
  7. El cas complet: el pla per als 200 milions de registres

Quan les dades no caben a la RAM: la jerarquia de memòria

Tota l'anàlisi de complexitat del curs (01-01, 01-02) comptava operacions assumint un cost uniforme d'accés a memòria. La realitat del maquinari és una jerarquia amb salts de diversos ordres de magnitud:

Nivell Latència aproximada En escala humana (1 ns = 1 s)
Memòria cau L1 ~1 ns 1 segon
RAM ~100 ns ~2 minuts
SSD (lectura aleatòria) ~100 µs ~28 hores
Disc magnètic (seek) ~10 ms ~4 mesos
Xarxa entre centres de dades ~50-150 ms anys

Dues conseqüències de disseny que expliquen tot el que segueix:

  • Un accés a disc val ~1000-100 000 accessos a RAM. Un algorisme amb més comparacions però menys lectures de disc guanya. La complexitat rellevant passa a mesurar-se en operacions d'E/S (model de memòria externa).
  • L'accés seqüencial a disc és enormement més barat que l'aleatori (el disc/SSD serveix blocs contigus a gran velocitat). Els bons algorismes externs llegeixen i escriuen en fluxos seqüencials de blocs grans, mai saltant de registre en registre.

Amb aquesta moneda nova, revisitem les dues operacions del mòdul 4.

Ordenació externa: runs ordenats + mescla de k vies

Com ordenes 40 GB amb 1 GB de RAM? L'algorisme clàssic, l'external merge sort, és el mergesort (04-02) repensat per minimitzar E/S, i reutilitza dues peces que ja tens:

  1. Fase 1 — generar runs: llegeix el fitxer a trossos que capiguen a la RAM, ordena cada tros en memòria (Timsort, 04-02) i escriu-lo com un fitxer temporal ja ordenat (un run). Amb 1 GB de RAM i 40 GB de dades: 40 runs.
  2. Fase 2 — mescla de k vies: mescla els 40 runs en una sola passada amb un heap (01-04), exactament la mescla de k vies que vas fer amb heapq.merge a 04-02: en cada moment només necessites a la RAM el "front" de cada run.

Cada fase llegeix i escriu les dades una vegada: 2 passades completes ≈ 4·N/B operacions d'E/S (N dades, B mida de bloc), enfront de les ~N·log₂N lectures aleatòries d'un quicksort ingenu sobre disc, que seria milers de vegades més lent. Simulem-ho amb fitxers de veritat a petita escala:

import heapq
import os
import random
import tempfile

random.seed(3)
dir_treball = tempfile.mkdtemp()

# --- Dades: 100.000 "registres de lliurament" (id_num;minuts) desordenats ---
cru = os.path.join(dir_treball, "lliuraments.txt")
with open(cru, "w") as f:
    for i in random.sample(range(100_000), 100_000):
        f.write(f"{i};{random.randint(5, 120)}\n")

MEMORIA = 10_000   # registres que "caben a la RAM" (simulat)

# --- Fase 1: generar runs ordenats ---
def generar_runs(fitxer, memoria):
    runs = []
    with open(fitxer) as f:
        while True:
            tros = [linia for _, linia in zip(range(memoria), f)]
            if not tros:
                break
            tros.sort(key=lambda l: int(l.split(";")[0]))   # Timsort, a la RAM
            ruta = os.path.join(dir_treball, f"run_{len(runs)}.txt")
            with open(ruta, "w") as out:
                out.writelines(tros)
            runs.append(ruta)
    return runs

# --- Fase 2: mescla de k vies amb heap ---
def mesclar_runs(runs, sortida):
    fitxers = [open(r) for r in runs]
    # Cada run s'embolcalla en un GENERADOR de (clau, línia):
    # a la RAM només viu una línia de cada run alhora (el front del heap)
    def amb_clau(f):
        for linia in f:
            yield (int(linia.split(";")[0]), linia)
    with open(sortida, "w") as out:
        for _, linia in heapq.merge(*(amb_clau(f) for f in fitxers)):
            out.write(linia)
    for f in fitxers:
        f.close()

runs = generar_runs(cru, MEMORIA)
print(f"Generats {len(runs)} runs de <= {MEMORIA} registres")
ordenat = os.path.join(dir_treball, "lliuraments_ordenat.txt")
mesclar_runs(runs, ordenat)

# Verificació: el fitxer final està ordenat
with open(ordenat) as f:
    claus = [int(l.split(";")[0]) for l in f]
print("Ordenat?", all(claus[i] <= claus[i+1] for i in range(len(claus)-1)))

Fixa't que amb_clau(f) és un generador, no una llista: si materialitzessis cada run amb list(f) tornaries a ficar totes les dades a la RAM i l'algorisme perdria la seva raó de ser. La disciplina de "tot en fluxos" és la meitat de la feina en algorismes externs.

Punts fins de l'algorisme real:

  • I si hi ha massa runs? Amb RAM per a k fronts de run, la mescla admet k fluxos. Si en surten més de k, es mescla en diverses rondes (mescles de k en k): el nombre de passades és ⌈log_k(nre. de runs)⌉ — logarítmic amb base enorme (k sol ser centenars o milers), així que a la pràctica 2-3 passades basten per a gairebé qualsevol mida.
  • Aquest és, literalment, l'algorisme que executen les bases de dades en un ORDER BY que no cap en memòria, i la peça central de la fase shuffle de MapReduce (secció següent).

Índexs: per què les bases de dades no fan cerca binària

Ja tens les dades ordenades a disc. Buscar un registre amb cerca binària (04-01)? Correcte en comparacions (log₂ de 200 milions ≈ 28), desastrós en E/S: 28 lectures aleatòries de disc, cadascuna a una posició imprevisible. I pitjor: mantenir un array ordenat a disc davant d'insercions diàries és inviable (desplaçar milions de registres per cada inserció, com vas veure en analitzar la inserció en arrays a 01-02).

La solució de les bases de dades és l'arbre B (i la seva variant B+): la generalització a disc de l'arbre binari de cerca que vas conèixer a 01-04.

  • Cada node ocupa un bloc de disc (4-16 KB) i conté centenars de claus ordenades, no una.
  • Un node amb m claus té m+1 fills: l'arbre és baixíssim. Amb ramificació ~500, 200 milions de claus caben en alçada 3-4.
  • Buscar = llegir 3-4 blocs (i l'arrel i el segon nivell viuen a la memòria cau en RAM: sovint 1-2 lectures reals). Dins de cada bloc sí que es fa cerca binària (04-01) — però això és CPU, que és gratis comparada amb l'E/S.
  • L'arbre es manté equilibrat per construcció (els nodes es parteixen en omplir-se), amb insercions i esborrats en O(log n) blocs.
flowchart TD
    R["arrel: [P-08M | P-95M]<br>1 bloc, a la RAM"] --> A["[P-01M ... P-07M]"]
    R --> B["[P-09M ... P-90M]"]
    R --> C["[P-96M ... P-200M]"]
    B --> H1["fulla: registres<br>P-42.000.000 ..."]
    B --> H2["fulla: ..."]
    B --> H3["fulla: ..."]

La comparació completa, connectant amb 01-04 i 04-01:

Estructura Cerca exacta Cerca per rang Insercions Cost en E/S (cerca)
Array ordenat + cerca binària (04-01) O(log n) excel·lent O(n) — inviable ~28 lectures aleatòries
Arbre binari equilibrat (01-04) O(log n) bona O(log n) ~28 (un node per bloc desaprofitat)
Arbre B/B+ O(log n) excel·lent (fulles enllaçades) O(log n) 3-4 lectures, 1-2 a la pràctica
Índex hash (01-04) O(1) no suporta rangs O(1) amortitzat 1-2 lectures

Regla de decisió: consultes d'igualtat pura i a màxima velocitat → hash; rangs, ordenació, prefixos (WHERE data BETWEEN ...) → arbre B. Per això l'índex per defecte de gairebé totes les bases de dades relacionals és un B+; els índexs hash existeixen però són el cas especial. És la mateixa disjuntiva hash-vs-arbre de 01-04, decidida ara per la moneda de l'E/S i pel patró de consultes.

MapReduce: el paradigma divideix-agrupa-combina

Quan ni tan sols un disc no basta —o una màquina triga massa—, es reparteix la feina entre moltes. MapReduce (Google, 2004) va imposar una disciplina simple: si expresses el teu càlcul com dues funcions pures, el framework s'encarrega de distribuir, reintentar fallades i moure dades.

  • map(registre) → llista de (clau, valor): s'aplica a cada registre en paral·lel, a la màquina on ja viuen les dades.
  • shuffle (ho fa el framework): agrupa tots els valors de la mateixa clau — internament, una ordenació externa distribuïda com la de la secció 2.
  • reduce(clau, valors) → resultat: combina els valors de cada clau, en paral·lel per clau.

El "hola món" és comptar paraules; el nostre cas és idèntic amb una altra clau: total de lliuraments i retard mitjà per zona sobre l'històric. Simulem el paradigma en Python per veure el flux de dades (el valor real apareix amb centenars de màquines, però el contracte és aquest):

from collections import defaultdict

# Registres històrics ficticis: (id_comanda, zona, minuts_lliurament)
registres = [
    ("P-001", "ALM", 22), ("P-002", "CEN", 35), ("P-003", "ALM", 41),
    ("P-004", "UNI", 18), ("P-005", "CEN", 52), ("P-006", "ALM", 30),
]   # ... imagina 200 milions d'aquests

def map_fn(registre):
    _, zona, minuts = registre
    return [(zona, minuts)]                  # clau = zona

def reduce_fn(zona, valors):
    return {"zona": zona, "lliuraments": len(valors),
            "min_mitja": sum(valors) / len(valors)}

# --- El que faria el framework ---
# 1) map en paral·lel sobre trossos del fitxer
intermedis = [parell for r in registres for parell in map_fn(r)]
# 2) shuffle: agrupar per clau (= ordenació externa distribuïda)
grups = defaultdict(list)
for clau, valor in intermedis:
    grups[clau].append(valor)
# 3) reduce en paral·lel per clau
resultat = [reduce_fn(z, vs) for z, vs in grups.items()]
print(resultat)

Per què això escala i què exigeix a canvi:

  • Escala perquè map i reduce són independents per registre/clau: afegir màquines divideix el temps gairebé linealment, i l'únic punt de contacte (el shuffle) és una ordenació externa, problema ja resolt.
  • Exigeix que les funcions siguin pures i que les operacions de reduce siguin associatives a la pràctica (poder combinar parcials). Comptar, sumar, max, mitjanes (com a suma+recompte): perfecte. Algorismes amb estat global fortament acoblat: mal encaix.
  • L'hereu modern és Apache Spark, que generalitza el model (cadenes de map/filter/reduce/join mantenint les dades a la RAM entre passos) — però el model mental divideix-agrupa-combina és el mateix, i saber reconèixer quan el teu càlcul l'admet és l'habilitat transferible.

Com sempre en aquest curs: divideix i venceràs (01-03, 04-02) no era només un truc de recursió; a aquesta escala és una arquitectura.

Estructures probabilístiques: el filtre de Bloom i els seus cosins

De vegades la pregunta no exigeix exactitud. "He vist ja aquest id de comanda?" sobre 200 milions d'ids exigeix un set de diversos GB… llevat que acceptis una probabilitat petita i controlada de fals positiu. El filtre de Bloom ofereix exactament aquest tracte: memòria ~10 bits per element (independent de la mida dels ids!) a canvi que "sí que l'he vist" sigui de vegades mentida — "no l'he vist" és sempre veritat.

Mecànica: un array de m bits i k funcions hash (l'eina de 01-04). Inserir x: posar a 1 els k bits hash_i(x) % m. Consultar x: si algun dels seus k bits és 0, segur que no hi és; si els k són 1, probablement hi és (els van poder encendre altres elements — aquest és el fals positiu).

import hashlib

class FiltreBloom:
    def __init__(self, m_bits, k_hashes):
        self.m, self.k = m_bits, k_hashes
        self.bits = bytearray(m_bits // 8 + 1)

    def _posicions(self, item):
        # k hashes a partir d'un sol digest (tècnica del doble hash)
        d = hashlib.sha256(item.encode()).digest()
        h1 = int.from_bytes(d[:8], "big")
        h2 = int.from_bytes(d[8:16], "big") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def afegir(self, item):
        for p in self._posicions(item):
            self.bits[p // 8] |= 1 << (p % 8)

    def conte(self, item):
        return all(self.bits[p // 8] >> (p % 8) & 1
                   for p in self._posicions(item))

# Hem processat ja aquesta comanda? (deduplicació a la ingesta)
bloom = FiltreBloom(m_bits=1_000_000, k_hashes=7)   # ~122 KB per a 100k items
for i in range(100_000):
    bloom.afegir(f"P-{i:09d}")

print(bloom.conte("P-000000042"))    # True (hi és)
falsos = sum(bloom.conte(f"X-{i:09d}") for i in range(100_000))
print(f"Falsos positius: {falsos / 100_000:.4%}")   # típicament < 1 %

Amb m/n = 10 bits per element i k ≈ 7, la taxa de falsos positius teòrica és ≈ (1 − e^(−kn/m))^k ≈ 0,8 % — i l'experiment ho confirma. Ús canònic: filtre barat davant d'un recurs car (consulto la base de dades per aquest id? només si el Bloom diu "potser"), eliminant de cop la immensa majoria de cerques d'elements inexistents.

La família completa, per reconèixer-les quan apareguin:

Estructura Pregunta que respon Error Memòria típica
Filtre de Bloom pertany x al conjunt? falsos positius (mai negatius) ~10 bits/element
HyperLogLog quants elements diferents he vist? (clients únics de l'any) ±2 % en el recompte ~1,5 KB total, per a milers de milions
Count-min sketch quantes vegades ha aparegut x? (freqüències aproximades) sobreestima, mai no infraestima KBs, fix

El patró comú: canviar exactitud per memòria, amb l'error fitat matemàticament. És la mateixa filosofia de les heurístiques del mòdul 2 —renunciar a l'òptim amb criteri—, aplicada ara a l'espai en lloc del temps.

Top-K en streaming: els 10 codis postals amb més lliuraments

Última peça: "els 10 codis postals amb més lliuraments de l'històric". El reflex d'ordenar els ~10 000 codis postals per recompte funciona, però és un cas particular d'un patró que mereix nom, perquè apareix constantment amb streams: per a un top-K no cal ordenar-ho tot — mantén un min-heap de mida K (01-04, i la mateixa jugada de la mescla de k vies de 04-02):

import heapq
from collections import Counter

# Fase 1 (una passada, O(1) per registre): comptar per clau
recomptes = Counter()
def processar(registre):
    _, cp = registre
    recomptes[cp] += 1

# ... després de processar el stream complet ...
recomptes = Counter({f"CP-{i:05d}": random.randint(1, 1_000_000)
                     for i in range(10_000)})   # simulació

# Fase 2: top-10 amb un min-heap de mida 10 — O(n log K), no O(n log n)
top10 = heapq.nlargest(10, recomptes.items(), key=lambda kv: kv[1])
for cp, c in top10:
    print(cp, c)

heapq.nlargest fa per dins el que faries a mà: recorre els n recomptes mantenint un min-heap amb els K millors vistos; si el nou supera el mínim del heap, el substitueix. Cost O(n log K) amb memòria O(K) — amb K=10 i n=10 000, unes 15 vegades menys comparacions que ordenar, i la diferència creix amb n. I si ni tan sols els recomptes exactes no caben (claus de cardinalitat brutal, com una clau per client), es combina amb el count-min sketch de la taula anterior: recomptes aproximats + heap top-K exacte sobre ells.

El cas complet: el pla per als 200 milions de registres

Tanquem el cas de Rutalia amb el pla d'enginyeria, peça a peça:

Necessitat de negoci Solució Secció / lliçó
Consolidar els fitxers històrics per data External merge sort (runs + mescla de k vies) §2, 04-02, 01-04
Deduplicar comandes a la ingesta Filtre de Bloom davant de la comprovació exacta §5
Buscar qualsevol comanda per id o per rang de dates Arbre B+ (id) — o hash si només hi hagués igualtat §3, 01-04, 04-01
Lliuraments i retard mitjà per zona Agregació divideix-agrupa-combina (Spark en real) §4
Clients únics per trimestre HyperLogLog §5
Els 10 CP amb més lliuraments Counter + min-heap top-K §6

Res d'aquesta taula no és un algorisme nou: és el mòdul 1 i el mòdul 4 recotitzats en la moneda de l'E/S. I les sortides d'aquest pipeline no són una fi: la taula d'agregats per zona és exactament el tipus de dataset del qual van sortir els perfils de demanda de 05-05 i les matrius de cost de 06-01 — el big data d'avui alimenta l'optimització i el ML de demà.

Errors Comuns i Consells

  • Comptar comparacions quan la moneda és l'E/S. Un algorisme "òptim" en RAM pot ser milers de vegades més lent a disc que un de seqüencial "pitjor". Pregunta sempre: quantes passades sobre les dades faig i quant d'accés aleatori?
  • Materialitzar generadors. list(fitxer) sobre 40 GB mata el procés. En pipelines de dades, tot el que pugui ser generador/iterador ho ha de ser — la mescla de k vies funciona precisament perquè només el front de cada run viu a la RAM.
  • Fer servir un filtre de Bloom on els falsos positius són inacceptables. "Probablement l'he vist" està bé per saltar-se una consulta cara; està malament per decidir que un pagament està duplicat i rebutjar-lo. El Bloom filtra, la verificació exacta decideix.
  • Dimensionar el Bloom a ull. La taxa d'error depèn de m/n i k; si insereixes 10 vegades més elements dels previstos, el filtre se satura i diu "sí" a gairebé tot. Calcula m per a la n màxima esperada.
  • Ordenar-ho tot per a un top-K. O(n log n) i memòria O(n) on bastaven O(n log K) i O(K). Amb streams, a més, ordenar és directament impossible: el heap és l'eina.
  • Consell: abans de distribuir (Spark, clúster), exhaureix la màquina única — un bon external sort i un bon índex en una sola màquina resolen volums sorprenentment grans amb una fracció de la complexitat operativa.

Exercicis

  1. Passades de mescla. Tens 25 000 runs després de la fase 1 i RAM per mesclar k = 50 fluxos alhora. Quantes rondes de mescla necessites i quantes passades completes de lectura/escriptura sobre les dades suposa (comptant la fase 1)? I si dupliques la RAM (k = 100)?
  2. Dimensiona un filtre de Bloom per a 200 milions d'ids de comanda amb una taxa de falsos positius objectiu de l'1 %. Fes servir les aproximacions m ≈ −n·ln(p)/(ln 2)² i k ≈ (m/n)·ln 2. Quanta memòria és en MB i quants hashes k fas servir? Compara-la amb un set de Python d'aquests 200 milions de strings (estima ~100 bytes per entrada).
  3. Mediana aproximada en una passada. Els 200 milions de minuts_lliurament (enters 0-300) no caben a la RAM, però vols la mediana exacta. Dissenya un mètode d'una sola passada amb memòria O(1) respecte de n. Pista: la clau és en el rang dels valors, i ja vas veure la idea al counting sort (04-02).

Solucions

  1. Cada ronda divideix el nombre de runs entre k: 25 000 → 500 → 10 → 1, és a dir 3 rondes (⌈log₅₀ 25 000⌉ = 3). Passades completes: 1 (fase 1) + 3 (mescles) = 4 passades de lectura+escriptura. Amb k = 100: 25 000 → 250 → 3 → 1, continuen sent 3 rondes (⌈log₁₀₀ 25 000⌉ = 3, tot i que per molt poc: amb 10 000 runs n'haurien bastat 2). Moralitat: una k gran aplana el logaritme rapidíssim; la RAM invertida en amplada de mescla s'amortitza sencera.
  2. m ≈ −2·10⁸ · ln(0,01) / (ln 2)² ≈ 2·10⁸ · 4,605 / 0,4805 ≈ 1,92·10⁹ bits ≈ 229 MB, amb k ≈ (m/n)·ln 2 ≈ 9,6·0,693 ≈ 7 hashes. El set exacte: 200 M × ~100 B ≈ 20 GB. El Bloom fa servir ~85 vegades menys memòria a canvi d'un 1 % de "potser" que resols consultant el magatzem exacte només en aquests casos.
  3. Com que els valors viuen en un rang petit i discret (0-300), mantén un histograma de 301 comptadors (la taula del counting sort de 04-02) i actualitza'l en una passada: O(1) de memòria respecte de n. Al final, recorre acumulant fins a superar n/2: aquell valor és la mediana exacta (i de passada tens qualsevol percentil). La lliçó: "no cap a la RAM" es refereix als registres; de vegades el resum suficient de les dades és diminut — reconèixer-ho evita desplegar un clúster per a un problema de 301 enters.

Conclusió

Has vist què els passa als algorismes del mòdul 4 quan les dades desborden la RAM: la moneda canvia de comparacions a operacions d'E/S, i d'aquest canvi surten l'external merge sort (Timsort + mescla de k vies amb heap, 04-02 i 01-04, aplicats a fitxers), els arbres B (l'arbre de cerca de 01-04 engreixat a la mida d'un bloc de disc), el paradigma divideix-agrupa-combina de MapReduce/Spark (divideix i venceràs com a arquitectura), i les estructures probabilístiques —amb el filtre de Bloom implementat— que compren memòria a canvi d'un error fitat, més el top-K en streaming amb heap. El cas dels 200 milions de registres de Rutalia va quedar resolt amb una taula de decisions, no amb força bruta. I aquests agregats no són el final del camí: són la matèria primera dels models del mòdul 5. Justament allà va l'última lliçó del mòdul: què passa quan aquests models d'aprenentatge automàtic surten del notebook i entren en producció — deriva, monitoratge, fallades cèlebres i les obligacions ètiques de decidir sobre persones.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats