Skip to content

Latest commit

 

History

History
298 lines (181 loc) · 5.45 KB

section_scaling.md

File metadata and controls

298 lines (181 loc) · 5.45 KB
Raw

Scaling

Notes:

Scaling reasons

  • Queries per second / Traffic / Concurrency
  • Index size / Time per query
  • Resiliency

Notes:

  • Scaling reasons?

Scaling

scaling

Notes:

  • What are the two directions we can scale to?

Scaling up / Vertical

scaling up

Notes:

  • (Dis-)Advantages of Scaling up?

Scaling up

  • + Easy
  • + Little overhead (network, hardware)
  • - No fault-tolerance
  • - No concurrency
  • - Scaling limited by hardware

Notes:

Scaling out / Horizontal

scaling out

Notes:

  • (Dis-)Advantages of Scaling out?

Scaling out

  • + Fault-tolerance, resiliency
  • + Concurrency
  • + "Unlimited" scaling
  • - Complex
  • - Overhead: Network, Monitoring

Notes:

Distributed search

Distributed Search

Notes:

Distributed search

  • Partitioned index
  • Distributed queries

Notes:

Non-Partitioned index

Term Doc IDs
Book #1, #2, #3
Information #1, #2, #3
Retrieval #1
Search #2

Notes:

  • How to partition? There are two ways along the axes of the table.

Partitioned index

  • By term
  • By doc

Notes:

  • How can the index be partitioned? Think of the Inverted Index.

Term-partitioned index

­ Term-partitioned index

Notes:

  • (Dis-)Advantages of Term-partitioned index?

Term-partitioned index

  • + Single term queries are easy
  • - Uneven distribution
  • - Index updates hit all servers

Notes:

Document-partitioned index

­ Document-partitioned index

Notes:

  • (Dis-)Advantages of Term-partitioned index?

Document-partitioned index

  • + Even distribution
  • + Easy to update index
  • + Completely independent partial indices
  • - Even single query terms are complex

Notes:

Document-partitioned index

  • Number of nodes is fixed
  • $\text{node}(\text{doc}) = \text{id}(\text{doc}) , % , \text{num}(\text{nodes})$
  • $\text{node}(\text{#4}) = 4 , % , 3 = 1$

Notes:

  • How to search with document-partitioned index?

Distributed query

­ Document-partitioned query

Notes:

  • What is the performance improvement? Assume a query takes 1s on a single node.

Performance improvement

  • 1 node: $n$ documents per index $\approx$ $m$ seconds per query
  • 2 nodes: $\frac{n}{2}$ documents per index $\approx$ $\frac{m}{2}$ seconds per query
  • …

$$\text{Distributed query time} \approx \frac{\text{Non-distributed query time}}{\text{Number of nodes}}$$

What's left to scale?

  • More traffic
  • Less downtimes

Notes:

  • How?

Sharding

­ sharding

Notes:

  • Benefits of more shards?
  • Benefits of more replicas?

Sharding nomenclature

Shard
  • Slice of document collection
Master / Leader / Primary
  • Distribute requests to Replicas
  • Distribute requests to other Masters
Replica
  • Contains all documents of shard
  • Will actually handle queries
  • Can become Master

Notes:

More shards

  • More docs
  • Better query parallelization
    • A single query is faster
    • $\text{Shards} \times 2 \approx \text{Index} \div 2 \approx \text{Performance} \times 2$

Notes:

More Replicas

  • Better resiliency
  • Better concurrency
    • More queries can be handled in parallel
    • $\text{Replicas} \times 2 \approx \text{Parallel queries} \times 2$

Notes: