Scalable and Contemporary Structures

Introduction

Classical data structures assume that data is available in the computer’s main memory and that one program controls the computation. Modern platforms violate both assumptions. Search engines, payment systems, social networks, sensor platforms, and cloud services process datasets larger than RAM, data that arrives continuously, and requests handled simultaneously by many threads or machines.

This chapter examines structures and techniques designed for these conditions: external-memory processing, streaming algorithms, Bloom filters, caching, concurrent collections, immutable structures, and distributed-data design. These tools do not replace arrays, linked lists, trees, hash tables, and graphs; rather, they extend their principles to systems where latency, memory capacity, concurrency, failure, and network cost dominate performance.

A central engineering principle is that the best structure depends on the cost model. In an in-memory program, a random access may be inexpensive. In an external-memory or distributed system, the same access may require a disk operation or a network round trip. Scalable design therefore considers not only asymptotic CPU time, but also bytes transferred, number of I/O operations, contention, coordination, fault tolerance, and accuracy guarantees.

Learning Objectives

By the end of this chapter, a learner should be able to:

1. Explain why external-memory and streaming models are required for large datasets.
2. Compare exact and approximate structures, including Bloom filters.
3. Design basic cache policies and reason about cache consistency.
4. Select suitable concurrent collections in Java and Python.
5. Explain the performance and safety benefits of immutable structures.
6. Identify distributed-data trade-offs involving partitioning, replication, consistency, and failure.
7. Apply these ideas to a realistic cloud-based platform.

1. Rethinking the Cost Model

Traditional complexity analysis often measures the number of elementary operations as a function of input size n. This remains useful, but large-scale systems require additional measures.

A storage device transfers data in blocks rather than individual records. Let B be the number of records per block. An algorithm that scans N records performs approximately N/B block transfers, rather than N meaningful disk operations. This observation motivates external-memory algorithms, whose complexity is commonly expressed in terms of block transfers.

For a balanced external-memory search tree, such as a B-tree, the height is approximately log_{B} N when each internal node has a large fan-out. Thus a search may require O(log_{B} N) block reads. The logarithm base matters: a high fan-out tree is much shorter than a binary tree when each node corresponds to a storage block.

The external-memory model assumes a fast internal memory of capacity M records, a slower storage system divided into blocks of B records, and a cost dominated by transfers between the two. The model is an abstraction; real systems also involve buffering, prefetching, SSD behavior, operating-system caches, and parallel storage.

2. External-Memory Processing

2.1 B-trees and indexed storage

A B-tree maintains sorted keys in nodes sized to use storage blocks efficiently. Internal nodes contain separator keys and child references; leaves contain records or record references. All leaves occur at approximately the same depth, so searches, insertions, and deletions have bounded height.

Compared with a binary search tree, a B-tree reduces the number of expensive block transfers by storing many keys per node. B+ trees, widely used in databases, usually store records or record pointers in leaves and link the leaves for efficient range scans.

A B-tree is appropriate when:

• data must persist across program executions;
• exact searches and range queries are required;
• updates occur regularly; and
• the dataset exceeds main memory.

A hash index may provide excellent equality lookup, but it does not naturally support ordered traversal or range queries. The choice is therefore determined by query shape, not by a universal ranking of structures.

2.2 External sorting

Sorting a dataset larger than RAM typically uses external merge sort. The process has two stages:

1. Read as much data as fits in memory, sort it, and write a sorted run to storage.
2. Merge the sorted runs using buffers, producing one final sorted sequence.

Suppose N records are stored, memory holds M records, and each block contains B records. The number of initial runs is approximately ⌈N/M⌉. In a simple two-pass analysis, the data is read and written during run formation and then read and written during merging. The total transfer volume is approximately 4N records, subject to the number of merge passes and available buffers. In block transfers, this is approximately 4N/B for two passes.

The two-pass estimate applies only when all initial runs can be merged in one merge pass. If there are too many runs, several merge passes are necessary. External sorting illustrates an important principle: sequential access is often substantially more efficient than many random accesses.

2.3 Practical Java and Python considerations

Java applications may use buffered streams, memory-mapped files, database indexes, or libraries such as java.nio. Python programs can use buffered file objects, generators, temporary files, and external tools such as database engines. A generator avoids loading every record into memory, but it does not by itself make an algorithm external-memory efficient: an algorithm that repeatedly seeks randomly through a file may still perform poorly.

Professional implementations should specify record format, block size assumptions, failure handling, temporary-file cleanup, and whether sorting is stable. They should also measure peak memory and I/O throughput rather than relying only on CPU benchmarks.

3. Streaming Algorithms

A streaming algorithm processes a sequence of items, usually in one pass or a small number of passes, while using memory much smaller than the input size. It is useful for logs, click events, telemetry, financial transactions, and message queues.

Streaming algorithms commonly provide one of three guarantees:

• Exact: the result is always correct, but memory may grow with the number of distinct items.
• Approximate with error bounds: memory is bounded and the algorithm quantifies possible error.
• Probabilistic: the answer has a stated probability of being correct or of avoiding a particular error.

3.1 Exact streaming aggregates

A running sum and count can be maintained in constant space. For observations x₁, x₂, …, xₙ, the mean is:

Here x̄ is the sample mean, xᵢ is an observation, and n is the number of observations. A streaming implementation need only maintain n and the running sum. For numerical stability, especially with floating-point values, algorithms such as compensated summation may be preferable.

The exact number of distinct users generally requires a set whose size can grow with the number of users. Approximate cardinality structures, such as HyperLogLog, trade small estimation error for bounded memory. Their detailed analysis is beyond this chapter, but the design pattern is important: store a compact statistical summary rather than the entire stream.

3.2 Windows and time

Many questions concern a recent interval, such as requests in the last five minutes. A tumbling window divides time into non-overlapping intervals; a sliding window moves continuously; a session window groups events separated by less than a specified inactivity period.

Windowed systems must define event time, processing time, lateness, and duplicate handling. In distributed environments, an event may arrive after the window that logically contains it has closed. Watermarks and allowed lateness policies make this behavior explicit, but no policy eliminates the underlying uncertainty.

3.3 Sampling

When retaining every event is impossible, reservoir sampling can select a uniform sample of fixed size k from a stream of unknown length. After the first k items, the item at position i (for i > k) is selected with probability k/i and, if selected, replaces a uniformly chosen retained item. This gives every item seen so far equal probability k/i of being in the reservoir, assuming independent random choices.

Sampling is useful for monitoring and exploration, but it may underrepresent rare events. Production systems often combine sampling with exact counters for high-risk categories.

4. Bloom Filters and Probabilistic Membership

A Bloom filter is a compact structure for testing set membership. It consists of an array of m bits and k hash functions. To insert an item, each hash function identifies a bit, which is set to 1. To query an item, all corresponding bits are checked.

A Bloom filter has no false negatives under normal operation: if it reports “not present,” the item was definitely not inserted. It can have false positives: a query may report “possibly present” because other items set the same bits. Deletion is not supported safely by an ordinary Bloom filter, because clearing a bit may remove evidence belonging to another item. Counting Bloom filters replace bits with small counters to support deletion, at additional memory cost.

For n inserted items, m bits, and k independent, uniformly distributed hash functions, the approximate false-positive probability is:

Here e is the base of natural logarithms. The approximation assumes a sufficiently large filter and suitably independent hash behavior. The value of k that minimizes p for fixed m and n is approximately:

The corresponding approximate minimum false-positive probability is:

The ratio m/n is measured in bits per inserted item. These equations are planning estimates, not guarantees; real hash correlation, poor sizing, duplicate inserts, and a changing n affect performance.

Worked example: sizing a Bloom filter

Suppose a service expects n = 1,000,000 distinct keys and can tolerate p = 0.01. The required bits per item can be estimated from:

Since −ln(0.01) ≈ 4.605 and (ln 2)² ≈ 0.480, m/n ≈ 9.6 bits per item. Thus m ≈ 9,600,000 bits, or about 1.2 MB before implementation overhead. The optimal number of hash functions is approximately k ≈ 9.6 × 0.693 ≈ 6.6, so six or seven functions may be selected and evaluated experimentally.

A Bloom filter should normally guard an authoritative store, not replace it. For example, a cache can consult the filter before attempting an expensive database lookup. A false positive causes an unnecessary lookup; a false negative would be dangerous, which is why ordinary Bloom filters are suitable for this role.

5. Caching

A cache stores frequently or recently used data closer to the consumer. It may be located inside a process, on the same host, in a local network, or at a global content-delivery edge.

Important cache policies include:

The average access time of a two-level system can be approximated by:

Here h is the cache-hit ratio, T_c is cache access time, and T_b is the time on a miss, including the cache check if that is not already included in the measurement. The expression assumes two outcomes and stable average costs. It is a simplified model: real systems may include refresh, retries, serialization, and queueing delays.

A cache can be faster but less current than its source. Common consistency strategies are:

• Cache-aside: the application reads the cache and loads the source on a miss; writes update the source and invalidate or refresh the cache.
• Read-through: the cache itself loads missing data.
• Write-through: writes go synchronously to the cache and source.
• Write-back: writes reach the source later, improving latency but increasing data-loss risk.
• Refresh-ahead: popular entries are refreshed before expiry.

Invalidation is difficult because a stale value may remain after an update, and distributed invalidation messages may be delayed or lost. TTL limits staleness duration but does not guarantee freshness. Sensitive data also requires careful authorization: caching a response without including the correct user or tenant identity in the cache key can cause a confidentiality breach.

A cache stampede occurs when many clients request an expired item simultaneously. Mitigations include request coalescing, randomized expiration (jitter), stale-while-revalidate behavior, and rate-limited refresh.

6. Concurrent Collections

Concurrency allows multiple tasks to make progress during overlapping time periods. Parallelism executes tasks simultaneously on multiple processing units. A concurrent data structure must define behavior when operations overlap, not merely protect individual statements.

6.1 Java

Java provides several useful structures in java.util.concurrent:

• ConcurrentHashMap supports concurrent access and efficient atomic methods such as computeIfAbsent.
• ConcurrentLinkedQueue provides a non-blocking queue suitable for multiple producers and consumers.
• BlockingQueue coordinates producers and consumers, allowing operations to wait when the queue is empty or full.
• CopyOnWriteArrayList is effective when reads greatly outnumber writes, because writes copy the underlying array.
• ConcurrentSkipListMap provides a concurrent sorted map with expected logarithmic operations.
• AtomicInteger, AtomicLong, and related classes support atomic updates for selected values.

A compound action such as “if key is absent, then insert” is not necessarily safe when implemented as separate containsKey and put calls. An atomic library operation or an explicit synchronization strategy is required.

6.2 Python

Python’s built-in structures have implementation-dependent thread-safety properties. In CPython, the Global Interpreter Lock (GIL) prevents simultaneous execution of many Python bytecode instructions in one interpreter, but it does not make multi-step application logic atomic, and it does not solve multiprocessing or distributed coordination. Future Python implementations may have different execution models.

The queue module provides synchronized queues for threads. threading.Lock, RLock, Condition, and Semaphore support coordination. The multiprocessing package provides process-based communication, while asyncio supports cooperative asynchronous tasks. For shared state across processes or machines, explicit mechanisms such as managers, databases, message brokers, or distributed stores are needed.

6.3 Correctness properties

A race condition occurs when the result depends on an uncontrolled timing order. Atomicity means an operation appears indivisible. Visibility concerns whether one thread can observe another’s updates. Linearizability requires each operation to appear to take effect at one instant between invocation and response. Lock-free algorithms guarantee system-wide progress under specified assumptions, whereas wait-free algorithms guarantee per-operation completion in a bounded number of steps.

Locks remain appropriate, but they require a consistent acquisition order to reduce deadlock risk. Shared mutable state should be minimized, and performance should be measured under realistic contention rather than inferred from single-thread tests.

7. Immutable and Persistent Structures

An immutable object cannot be changed after construction. An update creates a new value rather than modifying the old one. This approach simplifies reasoning because references can be shared without fear that another component will alter the object unexpectedly.

A persistent data structure preserves previous versions while allowing new versions to share unchanged parts. Structural sharing can make an update much cheaper than copying the complete structure. For example, an immutable linked list can prepend an item in O(1) time by creating one new node whose tail points to the old list. A persistent balanced tree usually creates new nodes along the modified path, giving update cost proportional to tree height while sharing the remaining subtrees.

Immutability offers:

• safer sharing between threads;
• easier caching and memoization;
• simpler rollback and versioning;
• fewer defensive copies; and
• clearer reasoning about time and state.

It can also increase allocation and garbage-collection pressure. A large immutable object updated frequently may be inefficient unless structural sharing or batching is used. Java records and unmodifiable collection views can support immutable APIs, but an unmodifiable view is not necessarily immutable if the underlying collection remains mutable. Python tuples and frozen data classes help, but an immutable container may still reference mutable objects.

8. Distributed-Data Considerations

A distributed data structure is partitioned across machines connected by a network. Network delay, partial failure, clock differences, duplicate messages, and independent process failure become normal conditions.

8.1 Partitioning and replication

Partitioning divides records among nodes. Hash partitioning balances many equality lookups; range partitioning supports ordered scans but can create hotspots when requests concentrate in one range. Consistent hashing can reduce remapping when nodes join or leave, though it does not automatically solve uneven key popularity.

Replication stores multiple copies. It improves availability and read capacity but introduces consistency and coordination costs. Replicas may be synchronous, where a write waits for acknowledgements, or asynchronous, where replicas catch up later. Replication factor is not a guarantee of durability unless the failure model, storage medium, and acknowledgement policy are also defined.

8.2 Consistency and ordering

Strong consistency makes a successful read observe the latest committed write according to the system’s contract. Eventual consistency allows temporary divergence but promises convergence if updates stop and communication continues. Session guarantees such as read-your-writes can provide useful user-facing behavior without requiring every read to be globally linearizable.

Distributed counters illustrate a subtle issue. If two nodes independently increment a value and later overwrite one another’s result, an update is lost. Safer approaches include atomic server-side increments, commutative merge operations, or conflict-free replicated data types (CRDTs). A CRDT is designed so that replicas can merge states or operations predictably under defined assumptions, often using monotonic information and an appropriate join operation.

The CAP theorem is frequently summarized as a choice between consistency and availability during a network partition in a system capable of partition tolerance. It does not state that a system can never be consistent and available in ordinary operation, nor does it eliminate design choices involving latency, scope, and consistency levels.

8.3 Idempotency and failure

A network request may be delivered, processed, and then time out before the client receives the response. Retrying can duplicate an operation. An idempotent operation has the same intended effect when repeated, such as setting a resource to a specified state. For non-idempotent actions, an idempotency key or transaction identifier allows the server to recognize retries.

Distributed systems should use explicit timeouts, bounded retries with backoff, durable logs where appropriate, dead-letter handling, and observability of lag and failure. “Exactly once” is usually an end-to-end effect requiring coordinated state and deduplication, not a magical property supplied by a transport protocol.

9. Integrated Case: An Illustrative Cloud Marketplace

Background

Consider an illustrative online marketplace serving millions of product searches, seller updates, and checkout requests. Product information is distributed across regions, while inventory changes rapidly.

Problem

The platform must answer common product queries with low latency, avoid unnecessary database reads, process click events continuously, and prevent overselling when several customers purchase the last units simultaneously.

Analysis

Product pages are read far more often than they are changed, indicating strong read locality. Search indexes and range queries require ordered structures. A cache can reduce database load, but stale price or inventory information can cause financial and customer-service problems. Clickstream data is too large to retain entirely in application memory. Concurrent checkout requests require atomic inventory updates and idempotent payment handling.

Approach and solution

The platform uses a B+ tree or search index for ordered product retrieval and partitions data by product or seller identifier. A cache-aside layer stores product descriptions with short, jittered TTLs. Inventory is not treated as an ordinary eventually consistent cache value: the authoritative service performs an atomic conditional decrement, such as “decrease stock only if stock is at least the requested quantity.”

A Bloom filter containing known product identifiers is placed before an expensive lookup. A false positive creates extra work, but a false negative is avoided. Click events enter a durable log. Streaming consumers maintain exact short-window counters for critical operational metrics and approximate sketches for large cardinality reports. A bounded queue applies backpressure when consumers fall behind.

Java services use ConcurrentHashMap for local metadata and BlockingQueue for worker coordination. Python services use asyncio for network-bound tasks and synchronized queues where threads are employed. Immutable request objects and explicit event records reduce accidental mutation. Each checkout request carries an idempotency key, and payment outcomes are recorded durably.

Outcome

The design reduces repeated database reads, limits memory growth, and makes overload visible through queue lag rather than allowing unbounded accumulation. It accepts that product descriptions may be briefly stale while preserving stronger guarantees for inventory and payment. Monitoring includes cache hit ratio, Bloom-filter estimated load, stream lag, rejected updates, retry counts, and consistency incidents.

Learning points

1. Different data domains require different consistency guarantees.
2. Approximate structures are valuable only when their error behavior is acceptable.
3. A cache is a consistency component, not merely a performance component.
4. Concurrency control must protect compound business operations.
5. Partitioning, observability, and failure handling are part of data-structure design in distributed systems.

10. Limitations, Governance, and Best Practices

Approximation can be unsafe in legal, medical, financial, or safety-critical decisions. A Bloom filter should not be the final authority for access control or payment settlement. Sampling can hide rare but important events. Cache data may contain personal information and therefore require retention limits, encryption, access control, and tenant isolation.

Teams should document error bounds, staleness limits, failure modes, and recovery procedures. They should test duplicate events, reordered messages, partial writes, clock skew, full caches, unavailable replicas, and sudden traffic spikes. Capacity plans should include headroom rather than sizing exactly to average demand.

Contemporary systems increasingly combine batch, streaming, and interactive workloads; use specialized hardware or managed cloud services; and apply AI models to ranking, anomaly detection, and capacity forecasting. AI does not remove the need for reliable structures. A model-serving platform still needs bounded queues, caches, immutable model versions, feature consistency, and controls against data leakage. Automated decisions should be auditable, and approximate or stale features should be disclosed where they affect consequential outcomes.

Chapter Summary

Scalable data structures adapt familiar ideas to storage, streams, concurrency, and distribution. External-memory algorithms minimize block transfers and favor high-fan-out indexes and sequential processing. Streaming algorithms process unbounded input with exact summaries, samples, windows, or probabilistic estimates. Bloom filters offer compact membership tests with possible false positives but no false negatives under normal use; their sizing depends on bits per item and hash-function count.

Caches improve latency and reduce load, but introduce freshness, invalidation, security, and stampede problems. Java and Python provide different concurrency tools, and compound operations must be made atomic rather than assumed safe. Immutable and persistent structures simplify sharing and versioning through structural sharing, although allocation costs remain. Distributed data requires decisions about partitioning, replication, consistency, idempotency, retries, and failure. The professional goal is not maximum speed in isolation, but a structure whose performance, correctness, availability, and governance match the application’s risk and workload.

Key Terms

External-memory algorithm: An algorithm designed to minimize transfers between main memory and secondary storage.

Block transfer: Movement of a storage block between external storage and faster memory.

B-tree: A balanced, high-fan-out search tree optimized for block storage.

External merge sort: A sorting method that creates sorted runs and merges them using limited memory.

Streaming algorithm: An algorithm that processes sequential input with bounded or sublinear memory.

Sliding window: A continuously moving interval over recent events.

Reservoir sampling: Uniform sampling of a fixed-size set from a stream of unknown length.

Bloom filter: A compact probabilistic membership structure allowing false positives but not normal false negatives.

False positive: A report that an item may be present when it is absent.

Cache hit ratio: The proportion of cache requests served successfully by the cache.

Cache-aside: A pattern in which application code loads the source after a cache miss.

Cache stampede: Excessive simultaneous source requests caused by expiration of a popular cached item.

Concurrent collection: A collection designed for safe or coordinated access by overlapping operations.

Atomicity: The property that an operation appears indivisible.

Immutable object: An object whose state cannot change after construction.

Structural sharing: Reuse of unchanged components between data-structure versions.

Partitioning: Dividing data among nodes or storage regions.

Replication: Maintaining multiple copies of data.

Eventual consistency: A model in which replicas converge if updates cease and communication continues.

Idempotency: The property that repeating an operation has the same intended effect as performing it once.

Review Questions

Short Answer Questions

1. Why does a B-tree generally require fewer storage accesses than a binary search tree for the same number of keys?
2. What is the difference between a false positive and a false negative in a Bloom filter?
3. State two advantages and one limitation of immutable data structures.
4. Why can a cache improve performance while reducing data freshness?
5. What problem does an idempotency key help solve in a distributed service?

Long Answer Questions

1. Explain the external merge-sort process and identify the assumptions behind a two-pass transfer estimate.
2. Compare cache-aside, write-through, and write-back caching, including their consistency and failure implications.
3. Discuss the roles of ConcurrentHashMap, BlockingQueue, and atomic operations in a Java service.
4. Explain how partitioning and replication affect performance, availability, and consistency in a distributed database.
5. Describe streaming windows, lateness, and watermarks in an event-processing system.

Analytical / Application Questions

1. A service inserts 500,000 distinct identifiers into a Bloom filter and requires an estimated false-positive rate of 0.005. Estimate the bits per item using the sizing relationship in this chapter, and explain why the result is only a planning estimate.
2. Design a data path for a video platform that must serve popular metadata quickly, process viewing events continuously, and remain safe during a cache outage. Justify the structures and consistency policies selected.
3. Two checkout requests concurrently attempt to purchase the final unit of an item. Analyze how a naïve read-then-write implementation can oversell, and propose an atomic, idempotent distributed design.

Multiple Choice Questions with Answers

Question 1

Which structure is specifically optimized for minimizing block transfers during indexed storage operations?

A. B-tree

B. Stack

C. singly linked list

D. Binary heap

Correct Answer: A. B-tree

Question 2

A standard Bloom filter normally guarantees which property?

A. No false positives

B. No false negatives for inserted items

C. Constant-time deletion

D. Sorted iteration

Correct Answer: B. No false negatives for inserted items

Question 3

For a Bloom filter with m bits and n inserted items, the approximate optimal number of hash functions is:

A. m + n

B. n/m

C. (m/n) ln 2

D. m − n

Correct Answer: C. (m/n) ln 2

Question 4

Which cache policy removes the item that has not been used for the longest time?

A. FIFO

B. LFU

C. LRU

D. Write-through

Correct Answer: C. LRU

Question 5

Which Java collection is designed to coordinate producers and consumers through blocking operations?

A. BlockingQueue

B. HashSet

C. TreeSet

D. ArrayDeque without synchronization

Correct Answer: A. BlockingQueue

Question 6

What is a principal benefit of immutable objects in concurrent programs?

A. They eliminate all memory allocation

B. They can be shared without state mutation races

C. They guarantee network availability

D. They always use less memory than mutable objects

Correct Answer: B. They can be shared without state mutation races

Question 7

What is the main purpose of reservoir sampling?

A. To sort an entire stream in memory

B. To maintain a fixed-size uniform sample from a stream

C. To eliminate duplicate database rows exactly

D. To encrypt streaming data

Correct Answer: B. To maintain a fixed-size uniform sample from a stream

Question 8

Which operation is most naturally supported by a range-oriented B+ tree index?

A. Retrieve all keys within an ordered interval

B. Generate a cryptographic signature

C. Detect every duplicate in an unbounded stream

D. Guarantee zero cache staleness

Correct Answer: A. Retrieve all keys within an ordered interval

Question 9

Why can a distributed service use an idempotency key for payment requests?

A. To make every request faster than a local call

B. To identify and safely handle retries of the same logical operation

C. To remove the need for authentication

D. To guarantee that networks never partition

Correct Answer: B. To identify and safely handle retries of the same logical operation

Question 10

If a cache hit ratio increases while cache-hit time and miss time remain constant, what happens to the simplified average access time?

A. It generally decreases

B. It necessarily doubles

C. It remains equal to miss time

D. It becomes undefined

Correct Answer: A. It generally decreases