When delving into the realm of database technologies, particularly at scale, the differences in performance characteristics between large key-value stores and document databases become essential. Both are subsets of the broader NoSQL database systems designed to handle different types of workloads and data management scenarios. The way these databases scale, especially horizontally, is crucial for performance, resilience, flexibility, and the overall efficiency of applications at scale.

Key-Value Stores versus Document Databases

Key-value stores are the simplest form of database where each item contains keys and their corresponding values. Examples include Redis, Amazon DynamoDB, and Riak. These databases are exceptionally fast for lookups by key and are highly optimized for operations involving simple data models.

Document databases, on the other hand, store data in documents similar to JSON (JavaScript Object Notation), XML, or BSON (Binary JSON). These documents can contain many different key-value pairs, or nested documents, leading to a more complex data model. Popular examples of document databases are MongoDB, CouchDB, and Amazon DocumentDB.

Horizontal Scaling Explained

Horizontal scaling involves adding more machines or nodes to a pool to manage increased load. It contrasts with vertical scaling, which involves adding more power (CPU, RAM) to an existing machine.

Horizontal scaling is essential for large-scale applications as it allows a database to grow dynamically and accommodate an increasing number of reads and writes without a significant drop in performance.

Why Key-Value Stores Scale Better Horizontally

1. Simplicity of Data Model: In key-value stores, data does not have relationships other than associative keys and values. This simplicity allows partitions to distribute evenly across multiple nodes with minimal overhead. There’s no need to worry about complex transaction locks or joins like you would with more complex data models.
2. Predictable Data Lookup Performance: Key-value pairs are often hashed to determine their location in the distributed system. This makes data lookups very fast and avoids the overhead of searching through different request paths like those required by queries in document-based systems which may need indexing on multiple document fields.
3. Ease of Partitioning: Since key-value stores operate on a simple key-hash mechanism, data can be partitioned across multiple nodes easily by hashing the key. Each node or set of nodes can independently manage one partition, ensuring that the data is evenly and effectively distributed.
4. Lower Overhead for Distribution: Managing a distributed environment in key-value databases typically involves less overhead than document stores. In document databases, distributing documents that might have many different fields (sharding) can become complex especially when ensuring that related documents are co-located to avoid expensive join operations.

Challenges for Document Databases in Horizontal Scaling

1. Complex Queries: Document databases support more complex queries, which can span multiple documents and fields, potentially reducing performance when scaled out across many servers, as the query engine needs to consolidate data from multiple nodes.
2. Index Management: As document databases handle more complex data, maintaining indexes across multiple nodes becomes more challenging, increasing the overhead on the database.
3. Transaction Management at Scale: Document databases often need to manage multi-document transactions which become complex and resource-intensive in a distributed environment.

Summary Table

In conclusion, key-value stores naturally support horizontal scaling due to their simplicity and efficiency in data distribution and management. While document databases offer greater flexibility in the types of data they can handle, this comes at the cost of increased complexity in horizontal scaling scenarios. The choice between a key-value store and a document database will depend heavily on the specific requirements of the application, such as the need for complex queries versus the priority for scalability and performance.