Search

In an object-based network storage system, metadata access is decoupled from the data transferring path to improve system performance, scalability, and management. Designing an efficient metadata management scheme in such a system is critically important to the overall system performance and poses lots of challenges to the system designers. Traditional metadata management schemes, either partitioning the metadata statically, or using pure hashing methods, are not able to adapt to the dynamic metadata workload, and hence suffer from scalability and hotspot problems. In this paper, we propose a new metadata management strategy, referred to as Weighted Partitioning and Adaptive Replication (WPAR) scheme, taking into account the weight (CPUpower, memory capacity, network bandwidth, etc.) of each metadata server. Our objective is to efficiently distribute and dynamically replicate the metadata, based on the weights, to balance the workload and reduce hotspots within the metadata server cluster.

A real-time distributed database system (RTDDBS) must maintain the consistency constraints of objects and must also guarantee the deadline imposed by each arriving request. Servicing these requests may incur I/O costs, control-message transferring costs or data-message transferring costs. In this paper, we consider our system in the mobile computing environment, where the link bandwidth is very limited and hence the transfer of data-messages and control-messages over the wireless network incurs very high cost when compared to I/O cost. Thus, we present a mathematical model that considers the communication costs (control-message/data-message transferring cost) associated with the servicing of a request. Using this cost model, our objective is to service the arriving requests on or before their respective deadline periods and minimize the total communication cost. To this end, we design an adaptive object allocation and replication algorithm, referred to as real-time distributed dynamic window mechanism (RDDWM), that adapts to the random patterns of read-write requests. Using competitive analysis, we study the performance of RDDWM algorithm under two extreme conditions.

In this chapter, we address the issues (object allocation and replication) of OMP in the application domain of DDBSs in SCEs. In general, a DDBS consists of n nodes (as shown in Figure 1.2), denoted as p 1, p 2,…, p n ,interconnected via a communication network. Each node consists of a processor and a local memory (database). Replicas of objects are stored in the local memories. All the local memories are private and accessible only by the processors who own them. Internodes communication is carried out by passing messages through the interconnection network. As mentioned in Chapter 3, transactions on objects arriving at a DDBS can be in the form of either read or write operations, referred to as read requests or write requests, respectively. Requests originating from processors for objects are assumed to arrive at the system concurrently and there exists a concurrency control mechanism to serialize 1 them. Specifically, a read request is serviced with a replica (latest version) of the requested object, while a write request actually modifies (creates a new version) an object. Especially, in order to guarantee the object consistency among multiple replicas of an object, every change to an object must be transferred to all the other available replicas in the remote memories elsewhere. In other words, a write request for an object must be propagated to all the processors that have replicas of the object in their respective local memories. Without loss of generality, these read/write requests can arrive at the system in a random manner and they need not exhibit a regular pattern.

Databases come in many flavors. We use databases in our daily activities such as airline reservations, banking transactions via an ATM machine, searching information in the Internet by using a search engine, borrowing books from a library, etc. Have you ever thought about where and how the data are accessed and managed?

In this chapter, we will introduce Object Management Process (OMP) in a more generalized sense. As mentioned in Chapter 1, an object, in general, may refer to an indivisible entity ranging from a small text file to a large volume multimedia file, depending on the underlying application. For instance, in database systems these objects can be categorized systematically in the form of text files, audio clips, graphic files, video clips ranging from small to large sizes and can be indexed in a clever manner to aid faster retrieval. Thus, an object is an entity defined by its type and size. Further, some objects can be altered, i.e., they may be “edited” which means that the size of such objects is a varying quantity. Additionally, in a network system, transferring an object from one node to another may be required by some application which will consume a varying network bandwidth. Managing the objects on a network system is an important issue which we call Object Management Process (OMP). We will introduce some methodologies of OMP and some performance metrics that are commonly used to quantify the performance of these methodologies.

Mobile devices such as laptops, cellular phones, Personal Digital Assistants (PDAs), have recently been of immense use and particularly started getting considerable attention in database systems. Mobile users on the MHs (or mobile devices) may interact with a database system in retrieving objects or they may interact with other mobile devices via wireless network. Hence, a DDBS is expected to support a computer network comprising a number of MHs. As discussed in Chapter 1, due to the mobility and disconnection of MHs, it is important for a DDBS in a MCE to provide a continuous network connectivity to the MHs regardless of their locations [BAI94, IB92]. Additionally, it is very well known that a wireless network bandwidth availability is very limited and hence object management in a MCE poses many challenges to the database designers. Thus, in this chapter, we address the issues of OMPs in MCEs.

So far we have been describing the OMP in arbitrary networks under a specific objective, namely the (monetary) cost optimization. Chapters 4 and 5 have clearly exposed certain models that are suited for stationary and mobile computing environments and shown how the performance is influenced by several parameters. There have been numerous studies in this area of DDBS on a variety of issues and it is beyond the scope of this book to deal with all of them. However, what has not been so far mentioned is on the performance quantification for regular or known topologies. Conducting performance studies on known topologies is always a natural interest to implementation specialists and researchers. In this chapter, we will present two specific examples on known topologies, i.e., (a). star networks and (b). multi-level generic tree networks. We use the parameters defined in Chapters 4 and 5 to analyze the performance and our objective remains the same namely, the minimization of the monetary cost involved in servicing the requests. However, it may be noted that the parameters influencing the performance may differ on different topologies as each case is a special case. Also, it depends on the underlying assumptions made.

In this chapter, we address the fundamental concepts of Competitive Analysis. Competitive analysis serves as a useful analytical tool in quantifying the performance of on-line algorithms. In a way, for an algorithmic designer, this tool aids to fine-tune his/her design to get the solution as closer as possible to an optimal solution. Problems that can be considered for analysis using this analytical tool include K-Server Problem, Paging Problem, Distributed Object Management, Web-Caching 1, Load Balancing in computer networks, Disk Header Scheduling, to quote a few. We first give formal definitions of competitiveness for both deterministic on-line algorithms and randomized on-line algorithms. We then enumerate several techniques in competitive analysis such as Potential Function method, Phase Partition Technique, and so forth. Several illustrative examples are provided for the ease of understanding to elicit important competitive properties of an on-line algorithm.