 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Shard" database architecture – news ·newspapers ·books ·scholar ·JSTOR(March 2021) (Learn how and when to remove this message) |
Adatabase shard, or simply ashard, is ahorizontal partition of data in adatabase orsearch engine. Each shard may be held on a separatedatabase server instance, to spread load.
Some data in a database remains present in all shards,[a] but some appears only in a single shard. Each shard acts as the single source for this subset of data.[1]
Horizontal partitioning is a database design principle wherebyrows of a database table are held separately, rather than being split intocolumns (which is whatnormalization andvertical partitioning do, to differing extents). Each partition forms part of a shard, which may in turn be located on a separate database server or physical location.
There are numerous advantages to the horizontal partitioning of data. Since tables are divided and distributed into multiple servers, the total number of rows in each table in each database is reduced. This reducesindex size, which generally improves search performance. A database shard can be placed on separate hardware, and multiple shards can be placed on multiple machines. This enables a distribution of the database over a large number of machines, greatly improving performance. In addition, if the database shard is based on some real-world segmentation of the data (e.g., European customers v. American customers) then it may be possible to infer the appropriate shard membership easily and automatically, and query only the relevant shard.[2]
In practice, sharding is complex. Although it has been done for a long time by hand-coding (especially where rows have an obvious grouping, as in the customer region example above), this is often inflexible. There is a desire to support sharding automatically, both in terms of adding code support for it, and for identifying candidates to be sharded separately.Consistent hashing is a technique used in sharding to spread large loads across multiple smaller services and servers.[3]
Wheredistributed computing is used to separate load between multiple servers (either for performance or reliability reasons), a shard approach may also be useful. In the 2010s, sharding ofexecution capacity, as well as the more traditional sharding ofdata, has emerged as a potential approach to overcome performance and scalability problems inblockchains.[4][5]
To mitigate the latency associated with cross-shard locking, novel consensus architectures have been proposed. One such approach, detailed in theProceedings of the VLDB Endowment, utilizes a method known as "braided synchronization". This technique, implemented in the Cerberus protocol, couples consensus instances to specific transaction sets rather than a linear ledger, allowing foratomic composability across multiple shards without a global lock.[6]
Horizontal partitioning splits one or more tables by row, usually within asingle instance of aschema and a database server. It may offer an advantage by reducing index size (and thus search effort) provided that there is some obvious, robust, implicit way to identify in which partition a particular row will be found, without first needing to search the index, e.g., the classic example of the 'CustomersEast' and 'CustomersWest' tables, where theirZIP code already indicates where they will be found.
Sharding goes beyond this. It partitions the problematic table(s) in the same way, but it does this across potentiallymultiple instances of the schema. The obvious advantage would be that search load for the large partitioned table can now be split across multiple servers (logical or physical), not just multiple indexes on the same logical server.
Splitting shards across multiple isolated instances requires more than simple horizontal partitioning. The hoped-for gains in efficiency would be lost, if querying the database requiredmultiple instances to be queried, just to retrieve a simpledimension table. Beyond partitioning, sharding thus splits large partitionable tables across the servers, while smaller tables are replicated as complete units.[clarification needed]
This is also why sharding is related to ashared-nothing architecture—once sharded, each shard can live in a totally separate logical schema instance / physical database server /data center /continent. There is no ongoing need to retain shared access (from between shards) to the other unpartitioned tables in other shards.[7]
This makes replication across multiple servers easy (simple horizontal partitioning does not). It is also useful for worldwide distribution of applications, where communications links between data centers would otherwise be a bottleneck.[citation needed]
There is also a requirement for some notification and replication mechanism between schema instances, so that the unpartitioned tables remain as closely synchronized as the application demands. This is a complex choice in the architecture of sharded systems: approaches range from making these effectively read-only (updates are rare and batched), to dynamicallyreplicated tables (at the cost of reducing some of the distribution benefits of sharding) and many options in between.[citation needed]
Sharding a database table before it has been optimized locally causes premature complexity. Sharding should be used only when all other options for optimization are inadequate.[according to whom?] The introduced complexity of database sharding causes the following potential problems:[citation needed]
In a database context, most recognize the term "shard" is most likely derived from either one of two sources:Computer Corporation of America's "A System for Highly Available Replicated Data",[30] which utilized redundant hardware to facilitate datareplication (as opposed to horizontal partitioning), or the 1997MMORPG video gameUltima Online.[31][32]
Richard Garriott, creator ofUltima Online, recollects the term being coined during production phase when they attempted to create a self-regulating virtual ecology system, whereby players may leverage new internet access (a revolutionary technology at the time) to interact and harvest in-game resources.[32] Although the virtual ecology functioned as intended during in-house testing, its natural balance failed "almost instantaneously" due to players killing off every living wildlife across the playable area faster than the spawning system could operate. Garriott's production team attempted to mitigate this issue by separating the global player base into separate sessions, and rewriting part ofUltima Online's fictional connection to the end ofUltima I: The First Age of Darkness, where the defeat of its antagonistMondain also led to the creation ofmultiverse "shards". This modification provided Garriott's team with the fictional basis needed to justify creating copies of the virtual environment. However, the game's sharp rise to critical acclaim also meant that the new multiverse virtual ecology system was quickly overwhelmed as well. After several months of testing, Garriott's team decided to abandon the feature altogether, and stripped the game of its functionality.[32]
Today, the term "shard" refers to the deployment and use of redundant hardware across database systems.[citation needed]
Database shards exemplify a shared-nothing architecture. This means that the shards are autonomous; they don't share any of the same data or resources.
| Types | |
|---|---|
| Concepts | |
| Objects | |
| Components | |
| Functions | |
| Related topics | |
