Database Sharding — Senior chuqurlik

Consistent hashing vs Virtual buckets

Consistent hashing (4 va 5-mavzularda ko‘rgan halqa + virtual node’lar) — kesh va LB uchun ajoyib. Lekin ma’lumotlar bazasi shardingida amaliyroq yondashuv — virtual buckets (logik shardlar): kalitni katta, fiksal sondagi bucket’ga (masalan 1024) xeshlaysan, bucket’larni esa fizik shardlarga taqsimlaysan.

// VIRTUAL BUCKETS: kalit -> bucket (O'ZGARMAS) -> shard (o'zgaruvchan MAP)
const TOTAL_BUCKETS = 1024;                  // ko'p, fiksal son (shard sonidan katta)

function keyToBucket(key: string): number {
  return crc32(key) % TOTAL_BUCKETS;         // bu hech qachon o'zgarmaydi
}

// Bucket -> shard MAP'i. Resharding = shu map'ni o'zgartirish (bucket'larni ko'chirish),
// kalitlarni qayta-hash qilish EMAS.
const bucketMap: Record<number, string> = {
  // 0..340   -> 'shard-0'
  // 341..681 -> 'shard-1'
  // 682..1023-> 'shard-2'
};
function shardForKey(key: string): string {
  return bucketMap[keyToBucket(key)];
}

Online resharding bosqichlari

1. Tayyorlash: yangi shardni qo‘sh, ko‘chiriladigan bucket’larni belgila. 2. Backfill: mavjud ma’lumotni fonda eski sharddan yangisiga nusxalashni boshla. 3. Dual-write: backfill davomida yangi yozuvlarni ikkala shardga yoz (ma’lumot orqada qolmasin):

// CUTOVER paytida DUAL-WRITE: migratsiya davomida ikkala shardga ham yozamiz
async write(key: string, data: any) {
  const bucket = keyToBucket(key);
  if (this.migratingBuckets.has(bucket)) {
    // bu bucket ko'chirilmoqda -> ESKI va YANGI shardga birga yoz
    await Promise.all([
      this.oldShard(bucket).upsert(data),
      this.newShard(bucket).upsert(data),
    ]);
  } else {
    await this.shardForKey(key).upsert(data);   // normal
  }
}

4. Verify + cutover: ikkala shard mosligini tekshir, so‘ng bucketMap’ni atomik yangilab, o‘qishni yangi shardga o‘tkaz. 5. Cleanup: dual-write’ni to‘xtatib, eski sharddagi ko‘chirilgan ma’lumotni o‘chir.

Vitess — MySQL uchun (YouTube, Slack, GitHub)

Vitess MySQL ustiga shardlash qatlamini qo‘yadi. vtgate — so‘rov routeri (ilova bitta nuqtaga ulanadi, sharding’ni sezmaydi), VReplication — downtime’siz resharding, cross-shard so‘rov, ulanish pooling — hammasini boshqaradi. Ulkan masshtabda isbotlangan.

Citus — PostgreSQL uchun (sizning stack‘ingizga mos)

Citus — PostgreSQL kengaytmasi: oddiy Postgres’ni taqsimlangan bazaga aylantiradi. Coordinator node so‘rovlarni worker node’larga tarqatadi. Eng kuchli tomoni — siz baribir oddiy SQL yozasiz, Citus uni shardlar bo‘ylab bajaradi:

-- CITUS (PostgreSQL extension) — sharding'ni Postgres ICHIDA beradi
-- jadvalni taqsimlash kaliti (distribution column) bo'yicha shardlash
SELECT create_distributed_table('orders', 'user_id');

-- bog'liq jadvalni BIR XIL kalit bo'yicha -> ular bir shardda -> LOKAL JOIN ishlaydi
SELECT create_distributed_table('order_items', 'user_id', colocate_with => 'orders');

-- kichik, kam o'zgaradigan jadval -> HAMMA node'ga nusxa (reference table)
SELECT create_reference_table('countries');

Pushdown va qisman agregatsiya

Cross-shard agregatsiyada ishni har shardga itarib (pushdown), natijalarni app tomonida birlashtirasan (map-reduce uslubi). Lekin har agregatsiya teng emas:

• Oson (bo‘linadigan): COUNT, SUM, MIN, MAX — har sharddan olib qo‘shasan.
• O‘rtacha: AVG = SUM/COUNT — alohida yig‘ib hisoblaysan (har shard AVG’ini o‘rtachalab bo‘lmaydi!).
• Qiyin: DISTINCT COUNT (HyperLogLog bilan taxminiy), median/percentile — to‘liq ma’lumotsiz aniq hisoblab bo‘lmaydi.

// PUSHDOWN: filtr/agregatsiyani HAR shardda bajarib, natijani app'da birlashtir
// count, sum, min, max -> bo'linadigan (decomposable) -> oson
async totalRevenue(): Promise<number> {
  const partials = await Promise.all(
    this.shards.all().map((db) => db.order.aggregate({ _sum: { total: true } })),
  );
  return partials.reduce((acc, p) => acc + (p._sum.total ?? 0), 0);
}
// AVG = SUM/COUNT (alohida yig'ib hisobla). DISTINCT COUNT, median, percentile -> QIYIN.

Cross-shard saralash va pagination — eng qiyin

// CROSS-SHARD PAGINATION: OFFSET yomon (har sharddan offset+limit olib, merge kerak).
// KEYSET (cursor) pagination -> har sharddan "cursor'dan keyingi N" ni ol, merge-sort qil
async page(cursor: string, limit: number) {
  const perShard = await Promise.all(
    this.shards.all().map((db) =>
      db.order.findMany({
        where: { createdAt: { lt: cursor } },
        orderBy: { createdAt: 'desc' },
        take: limit,                       // har sharddan limit ta
      }),
    ),
  );
  return mergeSort(perShard.flat()).slice(0, limit);   // birlashtirib, kesib ber
}

Global secondary index

Yechim — alternativ kalit bo‘yicha shardlangan alohida index jadval: u alternativ kalitdan asl shard key’ga (email → user_id) yo‘l ko‘rsatadi. Ikki "hop" bo‘ladi, lekin scatter-gather o‘rniga aniq nishon:

// MUAMMO: orders user_id bo'yicha shardlangan. Lekin EMAIL bo'yicha qidirish kerak.
// email shard key emas -> har so'rov hamma shardga borishi kerak (scatter) ✕

// YECHIM: global secondary index — EMAIL bo'yicha shardlangan alohida jadval,
// u user_id'ni qaytaradi. Keyin asl shardga boramiz (2 hop, lekin scatter yo'q).
async findUserByEmail(email: string) {
  const idxShard = this.shardForEmail(email);            // index email bo'yicha shardlangan
  const row = await idxShard.emailIndex.findUnique({ where: { email } });
  if (!row) return null;                                  // 1-hop: email -> userId
  const dataShard = this.shardForUser(row.userId);
  return dataShard.user.findUnique({ where: { id: row.userId } });  // 2-hop
}

Aniqlash → yumshatish

Avval aniqla: per-shard va per-key metrikalar (QPS, CPU, ulanish). Keyin yumshatish strategiyalari:

• Hot shardni bo‘lish (split): bucket dizayni tufayli oson — hot sharddagi bucket’larning bir qismini bo‘sh/yangi shardga ko‘chirasan (2-bo‘limdagi online resharding).
• Hot key’ni sub-shardlash: bitta juda issiq kalitni yanada bo‘lish — user_id o‘rniga user_id + sub_bucket (yulduz foydalanuvchining ma’lumoti bir necha shardga tarqaladi).
• Kesh oldiga qo‘yish: hot key’ni Redis/L1’ga (4-mavzu) — Redis’ga ham bormaslik.
• Hot shardga replika: o‘qish yukini replikalarga (7-mavzu) taqsimlash.

Sharding faqat so‘rov emas — butun operatsiya o‘zgaradi. Senior bularni oldindan rejalashtiradi:

Global unique va foreign key

Global noyoblik (email unique) — bitta shardda tekshirib bo‘lmaydi. Yechim: 5-bo‘limdagi global indexni unique sifatida ishlatish yoki app darajasida tekshirish. Foreign key shardlar aro ishlamaydi — bog‘liqlikni app majburlaydi yoki colocation bilan bir shardda saqlaysan.

ID generatsiyasi — Snowflake

Auto-increment shardlarda konflikt beradi. UUID — global noyob, lekin tasodifiy (indeks fragmentatsiyasi, tartibsiz). Snowflake ID — global noyob va vaqt bo‘yicha tartibli (yaxshi indeks lokalligi):

// SNOWFLAKE ID (64-bit): koordinatsiyasiz global noyob + vaqt bo'yicha SARALANADI
// [ 41 bit: timestamp ][ 10 bit: worker/machine ][ 12 bit: sequence ]
//  -> ~69 yil          -> 1024 ta worker        -> ms ichida 4096 ta ID
// auto-increment'dan farqli: shardlar koordinatsiya qilmaydi, lekin ID'lar tartibli.

Schema migration va backup

Senior sharding arxitekturasi — yig‘ma ko‘rinish

Yetuk shardlangan tizim odatda shu qismlardan iborat:

Senior tayyorlik cheklisti