• Shared-Memory
• Shared-Disk
• Shared-Nothing

Summary of the Architectural Discussion

  Traditionally, architectures for parallel DBMS were categorised by the way in which processors share hardware resources like disk devices and memory. This categorisation initially appeared in [Stonebraker, 1986] and was mainly meant to be a discussion around the most appropriate parallel hardware architecture. Many researchers have participated in this discussion in the following years; see e.g. [Bhide and Stonebraker, 1988], [DeWitt and Gray, 1990], [Hua et al., 1991], [DeWitt and Gray, 1992], [Bergsten et al., 1993], [Valduriez, 1993b], [Baru et al., 1995], [Gray, 1995] and many others, base their arguments on it. In this section, we briefly describe the architectural categories and summarise the conclusions that have been drawn. We note that many arguments that were brought forward are of a historical nature because they reflect on the state of the technology in the late 1980s and early 1990s and do not consider recent developments. The categories are:

• shared-memory, 
• shared-disk, 
• shared-nothing. 

Shared-Memory

Shared-memory  (SM)  - some authors, like [Hua et al., 1991] or [Bergsten et al., 1993], prefer the equivalent term shared-everything  - means that all disks and all memory modules are shared by the processors as shown in figure 8.3. This means that all disks are equally accessible by all processors and that there is a global address space for main memory. The latter can be implemented as a physically distributed memory in which each processor has a local memory which forms a part of the global memory . There are two forms for accessing this distributed shared memory [Tannenbaum, 1994]:

• There is a uniform access memory (UMA)  in which uniformity is guaranteed by a hardware-driven caching mechanism. This means that, in theory, accesses to any location in memory are at the same costs. In practice, however, caching cannot entirely extinguish the difference between local and remote memory access costs but it makes this difference bearable. The caching hardware, however, is complex and expensive and limits SM-architectures to a small number of processors.
• The alternative is a non-uniform memory access (NUMA)  in which access to local memory is typically 10 times faster than to a remote access to an address space which is located at another node. Remote accesses are avoided either by the software or by the operating system which aims to shift memory pages to the location from which it is most frequently accessed. In contrast to UMA, the NUMA approach is scalable, much cheaper and more flexible at the expense of leaving the memory access optimisation to the operating system.

The following arguments have been raised when discussing SM-architectures: It is said that SM is simple to program, essentially because of the global address space in main memory. Load balancing  can be arranged relatively easily because each processor has equal access to all disks. Communication among the processors is fast (and incurs low overhead) as they can cooperate via main memory. However, system costs are high for big systems because the bus becomes a bottleneck and various hardware mechanism have to be employed to tackle this problem. Conflicting accesses to main memory can decrease the performance. It is also argued that access to main memory is the reason why SM-architectures do not scale up very well: [Bhide and Stonebraker, 1988] showed that beyond a certain number of processors, access to main memory can become a bottleneck that limits the system's processing speed. SM systems are therefore limited to a small number of processors ([Valduriez, 1993a] mentions 20; [Baru et al., 1995] argues that the limit is around 10 RISC System/6000 processors).

Shared-Disk

In a shared-disk  (SD)  system, each processor has its private memory. The access to disks, however, is shared by all of them. Figure 8.4 shows this architecture. Actually it shows the way in which the SM  is frequently implemented, namely as a distributed shared memory  with each processor holding one part of the global memory. For that reason SD and SM can be considered as synonymous nowadays.

In the following, we summarise the arguments that have been brought up in favour or against SD systems: It is argued that the costs for SD system are relatively low as the interconnect could be a bus system based on standard technology. It is also argued that load balancing is also relatively easy for the same reason as in the SM case, and that the availability of data is higher than in an SN system (see below) as a crash on one processor does not result in the data of a particular disk being unavailable. Software from uniprocessor systems can be easily migrated since the data on disk need not be reorganised [Valduriez, 1993a]. Much of the down-side of SD systems is said to relate to an increase in complexity, e.g. caused by the cache coherency control mechanisms that are necessary to maintain consistent disk pages in the processors' individual caches. A centralised lock management is also required. All this limits the scalability of a SD system. Finally, the access to the shared disks might result in a bottleneck through a limited interconnect capacity.

Shared-Nothing

In a shared-nothing  (SN)  system, each processor has its private memory and has at least one disk connected; the processor acts as a server for the data on this disk. Figure 8.5 shows this type of architecture.

The arguments around the SN-architecture are as follows: It is said that the costs of a SN system are low because it can essentially be constructed from commodity components. Theoretically, SN can scale and speed up linearly; in practice it is argued that the interconnect becomes saturated beyond a certain volume of communication. Availability is also often considered to be a serious problem. Load balancing is another problem: it is argued that data skew  can cause serious imbalances. Furthermore, load imbalance  can be caused by the the execution of operations being in some way predetermined by the data placement on the disks and the necessity to avoid huge data shipping through the network to other processors.

For a long time, SN has been considered as the best parallel architecture, mainly because of its allegedly unlimited scalability. There are two reasons why this advantage has not manifested itself in practice:

• As already mentioned above, the interconnect gets saturated beyond a certain point. Academics often pointed to Teradata machines as an example of a commercial SN product that would allegedly scale up to systems with ``over 1000 processors'' [DeWitt and Gray, 1992]. However, Teradata itself admitted that its interconnect, the YNET, would not scale to the maximum, physically feasible configuration of 1000 processors [Witkowski, 1993].
• As a matter of fact, there is a trend which offers an alternative to scalability: processor speed doubles roughly every 18 months [Gray, 1995]. Therefore, instead of adding quantity (i.e. more processors) one can add quality (i.e. faster processors), thus avoiding the problem of the interconnect saturation. We used the workload and performance model provided in [Hua et al., 1991] to compare these two possibilities with respect to join processing times. Starting with an initial SN architecture with 10 processors we multiplied the number of processors by a scaling factor . Using the same initial architecture we did the same experiment but this time we magnified the overall computing power by using processors that were times faster. The result can be seen in figure 8.6 and proves that adding faster processors is preferable. This means that in practice scalability is actually a characteristic that is not as important as it is frequently claimed by many academic researchers. This also explains the fact that there are so few parallel computer systems on the market nowadays that employ a large number of simple processors - such as the Connection Machine [Hillis, 1985] or the MasPar MP-1 [Blank, 1990] - but a relatively small number - e.g. the Cray T3D [Cray Research, 1993] - or a handful - e.g. servers such as Sun's SPARCcenter 2000 and derived products [Cekleov et al., 1993] - of powerful processors.