Consistent checkpointing is a critical for in-memory databases (IMDBs) but its resource-intensive nature poses challenges for small- and medium-sized deployments in cloud environments, where memory utilization directly affects operational costs. Although traditional fork-based checkpointing offers merits in terms of performance and implementation simplicity, it incurs a considerable rise in memory footprint during checkpointing, particularly under update-intensive workloads. Memory provisioning emerges as a practical remedy to handle peak demands without compromising performance, albeit with potential concerns related to memory over-provisioning.In this article, we propose MDC+, a memory-efficient fork-based checkpointing scheme designed to maintain a reasonable memory footprint during checkpointing by leveraging collaboration among an IMDB, a user-level memory allocator, and the operating system. We explore two key techniques within the checkpointing scheme: (1) memory dump-based checkpointing, which enables early memory release, and (2) hint-based segregated memory allocation, which isolates immutable and updatable data to minimize page duplication. Our evaluation demonstrates that MDC+ significantly lowers peak memory footprint during checkpointing without affecting throughput or checkpointing time.

Fully homomorphic encryption (FHE) can utilize GPUs to accelerate arbitrary operations directly on encrypted data without decryption. Functions like bootstrapping which refresh noise accumulated on ciphertexts due to repeated operations require great amounts of GPU memory. Such functions cause out-of-memory (OOM) issues in retail GPUs with less than 8GB of VRAM, causing bootstrap to fail. Utilizing CUDA Unified Memory can alleviate OOM problems by allowing automatic page swapping from host to device memory. However, it usually comes with significant performance overheads. We devise a hybrid memory run-time that distinguishes between objects that are allocated asynchronously, or with managed memory. Our initial implementation was to statically determine in code the type of allocation method each GPU object would use. For a more general solution, we created a run-time scheduler which profiles and automatically determines the method of allocation each GPU object should use, without requiring static changes in library code. We then expanded upon this by creating a dynamic scheduler which forecasts the lifetime of future GPU objects without profiling. Our static method increases bootstrapping performance by ~31 % for large parameter sizes when memory is oversubscribed. Our profiling scheduler improves Res Net performance compared to manual swapping by ~22 %. Finally, our pure dynamic scheduler gives performance that is similar to our static solution, and up to 50 % better performance in bootstrapping than the base unified case.

A graph engine should possess adaptability to ensure efficient processing despite a variety of graph data and algorithms. In terms of out-of-core graph engines, which exploit a hierarchical memory structure, an adaptive caching scheme is necessary to sustain effectiveness of memory usage. A caching policy selectively stores data likely to be used in the upper-layer memory based on its own expectation about the future workload. However, the graph workload contains a complexity of memory access according to graph data, algorithm, and configurations. This makes it difficult for a static caching policy to respond to the changes in workload. In this paper, we propose a graph-adaptive caching scheme which ensures consistent effectiveness under the changing workloads. Our caching scheme employs an adaptive policy that responds to changes in real-time workloads. To detect the changes, we adopt the competition procedures between two contrasting properties-locality and regularity-that appear in graph workloads. In addition, we combine two window adjustment techniques to alleviate the overhead from competition procedures. The proposed caching scheme is applicable to different types of graph engines, achieving better efficiency in memory usage. Our experimental results prove that our scheme improves the performance of graph processing by up to 65% compared to existing schemes.

Parallel file systems (PFS) are used to distribute data processing and establish shared access to large-scale data. Despite being able to provide high I/O bandwidth on each node, PFS has difficulty utilizing the I/O bandwidth due to a single connection between the client and server nodes. To mitigate the performance bottleneck, users increase the number of connections between the nodes by modifying PFS or applications. However, it is difficult to modify PFS itself due to its complicated internal structure. Thus, PFS users manually increase the number of connections between the nodes by employing several methods. In this paper, we propose a user-transparent I/O subsystem, MulConn, to make users exploit high I/O bandwidth between nodes. To avoid the modifications of PFS and user applications, we have developed a horizontal mount procedure and two I/O scheduling policies, TtoS and TtoM, in the virtual file system (VFS) layer. We expose a single mount point that has multiple connections by modifying the mount path of VFS from vertical hierarchy to horizontal hierarchy. We also introduce two I/O scheduling policies to distribute I/O requests evenly to multiple connections. The experimental results show that MulConn improves write and read performance by up to 2.6x and 2.8x, respectively, compared with those of PFS using the existing kernel. In addition, we provide the best I/O performance that PFS can provide in the given experimental environments.

In cloud ecosystems, distributed block storage systems are used to provide a persistent block storage service, which is the fundamental building block for operating cloud native services. However, existing distributed storage systems performed poorly for random write workloads in an all-NVMe storage configuration, becoming CPU-bottlenecked. Our roofline-based approach to performance analysis on a conventional distributed block storage system with NVMe SSDs reveals that the bottleneck does not lie in one specific software module, but across the entire software stack; (1) tightly coupled I/O processing, (2) inefficient threading architecture, and (3) local backend data store causing excessive CPU usage. To this end, we re-architect a modern distributed block storage system for improving random write performance. The key ingredients of our system are (1) decoupled operation processing using non-volatile memory, (2) prioritized thread control, and (3) CPU-efficient backend data store. Our system emphasizes low CPU overhead and high CPU efficiency to efficiently utilize NVMe SSDs in a distributed storage environment. We implement our system in Ceph. Compared to the native Ceph, our prototype system delivers more than 3x performance improvement for small random write I/Os in terms of both IOPS and latency by efficiently utilizing CPU cores.

Summary Edge computing focuses on processing near the source of the data. Edge computing devices using the Tegra SoC architecture provide a physically distinct GPU memory architecture. In order to take advantage of this architecture, different modes of memory allocation need to be considered. Different GPU memory allocation techniques yield different results in memory usage and execution times of identical applications on Tegra devices. In this article, we implement several GPU application benchmarks, including our custom CFD code with unified, pinned, and normal host/device memory allocation modes. We evaluate and compare the memory usage and execution time of such workloads on edge computing Tegra system‐on‐chips (SoC) equipped with integrated GPUs using a shared memory architecture, and non‐SoC machines with discrete GPUs equipped with distinct VRAM. We discover that utilizing normal memory allocation methods on SoCs actually use double the required memory because of unnecessary device memory copies, despite being physically shared with host memory. We show that GPU application memory usage can be reduced up to 50%, and that even performance improvements can occur just by replacing normal memory allocation and memory copy methods with managed unified memory or pinned memory allocation.

As the size of data grows in modern applications, the efficient usage of limited resources is becoming crucial. In order to reorganize large data under memory limitations, many data-intensive applications utilize external sort as a critical component. To streamline external sort, a storage framework is especially needed since the entire dataset must be loaded and flushed a couple of times during the sorting process. Most existing frameworks have attempted to simplify the storage access pattern by associating each thread with a separate storage device. This prevents randomized and concurrent I/O requests, which impose a huge overhead for legacy drives in order to enable the parallelism needed for external sort. However, such regulations excessively restrain the capabilities of NVMe-based SSDs that deliver high throughput with abundant parallelism. In this article, we present a new framework for external sort that exploits both external and internal parallelism. Externally, any number of threads are mobilized to parallel external sort in a scalable way, even with one NVMe SSD. Meanwhile, some arbitration schemes, such as adaptive resource allocation and fairness control, are adopted to preserve the internal efficiency of storage devices. Our evaluation results demonstrate that our scheme can greatly improve both the I/O efficiency and scalability compared to the existing frameworks.

Many cloud services perform periodic database backup to keep the data safe from failures such as sudden system crashes. In the database system, two techniques are widely used for data backup and recovery: a physical backup and a logical backup. The physical backup uses raw data by copying the files in the database, whereas the logical backup extracts data from the database and dumps it into separated files as a sequence of query statements. Both techniques support a full backup strategy that contains data of the entire database and incremental backup strategy that contains changed data since a previous backup. However, both strategies require additional I/O operations to perform the backup and need a long time to restore a backup. In this paper, we propose an efficient backup and recovery scheme by exploiting write-ahead logging (WAL) in database systems. In the proposed scheme, for backup, we devise a backup system to use log data generated by the existing WAL to eliminate the additional I/O operations. To restore a backup, we utilize and optimize the existing crash recovery procedure of WAL to reduce recovery time. For example, we divide the recovery range and applying the backup data for each range independently via multiple threads. We implement our scheme in MySQL, a popular database management system. The experimental result demonstrates that the proposed scheme provides instant backup while reducing recovery time compared with the existing schemes.

The graphics processing unit (GPU) is extensively used in diverse domains, such as finance, machine learning, and image processing. The GPU can be underutilized as multiple applications may not share the same GPU concurrently owing to a memory oversubscription issue. For example, when applications that require fewer computational resources but a larger GPU memory are running instantaneously, the GPU memory may be insufficient; consequently, the number of GPU applications running simultaneously is restricted, decreasing GPU utilization. Further, it can even stop the execution of applications that are running on the GPU. To this end, we propose FlexGPU, which schedules the kernels of the GPU applications that run on the same GPU according to their features. This framework 1) schedules the kernel at the launching time according to its features to improve GPU utilization and 2) temporarily checkpoints and restores non-dependent content in the GPU memory to/from the host memory, which avoids oversubscription of the GPU when out-of-memory failure occurs and allows more kernels to run concurrently on the GPU. The experimental results show that compared to existing methods, our approach demonstrates a 7 times improvement in performance in terms of execution time and enables a 2.5 times increase in the concurrent execution of applications.

Read-copy update (RCU) can provide ideal scalability for read-mostly workloads, but some believe that it provides only poor performance for updates. This belief is due to the lack of RCU-centric update synchronization mechanisms. RCU instead works with a range of update-side mechanisms, such as locking. In fact, many developers embrace simplicity by using global locking. Logging, hardware transactional memory, or fine-grained locking can provide better scalability, but each of these approaches has limitations, such as imposing overhead on readers or poor scalability on non-uniform memory access (NUMA) systems, mainly due to their lack of NUMA-aware design principles.

Most modern multi-core processors provide a shared last level cache (LLC) where data from all cores are placed to improve performance. However, this opens a new challenge for cache management, owing to cache pollution. With cache pollution, data with weak temporal locality can evict other data with strong temporal locality when both are mapped into the same cache set. In this article, we propose page reusability-based cache partitioning (PRCP) for multi-core systems to maximize cache utilization by minimizing cache pollution. To achieve this, PRCP divides pages into two groups: (1) highly-reused pages and (2) lowly-reused pages. The reusability of each page is collected online via periodic page table scans. PRCP then dynamically partitions the shared cache into two corresponding areas using page coloring technique. We have implemented PRCP in Linux kernel and evaluated it using SPEC CPU2006 benchmarks. The results show that our scheme can achieve comparable performance to the optimal offline MRC-guided process-based cache partitioning scheme without a priori knowledge of workloads.

As flash-based solid-state drive (SSD) becomes more prevalent because of the rapid fall in price and the significant increase in capacity, customers expect better data services than traditional disk-based systems. However, the order of magnitude performance provided and new characteristics of flash require a rethinking of data services. For example, backup and recovery is an important service in a database system since it protects data against unexpected hardware and software failures. To provide backup and recovery, backup/recovery tools or backup/recovery methods by operating systems can be used. However, the tools perform time-consuming jobs, and the methods may negatively affect run-time performance during normal operation even though high-performance SSDs are used. To handle these issues, we propose an SSD-assisted backup/recovery scheme for database systems. Our scheme is to utilize the characteristics (e.g., out-of-place update) of flash-based SSD for backup/recovery operations. To this end, we exploit the resources (e.g., flash translation layer and DRAM cache with supercapacitors) inside SSD, and we call our SSD with new backup/ recovery functionality BR-SSD. We design and implement the functionality in the Samsung enterprise-class SSD (i.e., SM843Tn) for more realistic systems. Furthermore, we exploit and integrate BR-SSDs into database systems (i.e., MySQL) in replication and redundant array of independent disks (RAID) environments, as well as a database system in a single BR-SSD. The experimental result demonstrates that our scheme provides fast backup and recovery but does not negatively affect the run-time performance during normal operation.

In cloud computing, I/O-intensive workloads can be co-located with other applications or virtual machines on a single physical machine. In this case, copy-based I/O (buffered I/O) can lead to severe performance interference to other memoryintensive workloads. It is because that the buffered I/O consumes memory bandwidth during memory copy even though it benefits from caching. To address this problem, many zero-copy I/O schemes have been proposed but none of them provides both 1) transparent copy avoidance through read/write system calls and 2) benefits of kernel-level caching at the same time. To this end, this paper presents z-READ, an efficient and transparent zero-copy read I/O scheme based on page remapping and copy-on-write techniques. In our scheme, we introduce several optimizations that minimize the overheads of page remapping by reducing the number of remote TLB shootdown.We implement z- READ prototype in memory management of Linux kernel 4.12.9. Our experimental results show that the performance of the colocated memory-intensive workloads can be negatively affected by I/O-intensive workloads in the case of copy-based I/O (up to 1.96x slowdown in-memory configurations) while z-READ incurs only up to 1.07x slowdown for the respective configuration.

Modern data centers aim to take advantage of high parallelism in storage devices for I/O intensive applications such as storage servers, cache systems, and key-value stores. Key-value stores are the most typical applications that should provide a highly reliable service with high-performance. To increase the I/O performance of key-value stores, many data centers have actively adopted next-generation storage devices such as Non-Volatile Memory Express (NVMe) based Solid State Devices (SSDs). NVMe SSDs and its protocol are characterized to provide a high degree of parallelism. However, they may not guarantee predictable performance while providing high performance and parallelism. For example, heavily mixed read and write requests can result in performance degradation of throughput and response time due to the interference between the requests and internal operations (e.g., Garbage Collection (GC)). To minimize the interference and provide higher performance, this paper presents IsoKV, an isolation scheme for key-value stores by exploiting internal parallelism in SSDs. IsoKV manages the level of parallelism of SSD directly by running application-driven flash management scheme. By storing data with different characteristics in each dedicated internal parallel units of SSD, IsoKV reduces interference between I/O requests. Also, IsoKV synchronizes the LSM-tree logic and data management in SSD to eliminate GC. We implement IsoKV on RocksDB and evaluate it using Open-Channel SSD. Our extensive experiments have shown that IsoKV improves overall throughput and response time on average 1.20× and 43% compared with the existing scheme, respectively.

The importance of physically contiguous memory has increased in modern computing environments, including both low- and high-end systems. Existing physically contiguous memory allocators generally have critical limitations. For example, the most commonly adopted solution, the memory reservation technique, wastes a significant amount of memory space. Scatter/Gather direct memory access (DMA) and input-output memory management units (IOMMUs) avoid this problem by utilizing additional hardware for address space virtualization. However, additional hardware means an increase in costs and power consumption, which is especially disadvantageous for small systems and they do not provide real contiguous memory. Linux Contiguous Memory Allocator (CMA) aims to provide both contiguous memory allocation and to maximize memory utilization based on page migration, but they suffer from unpredictably long latency and a high probability of allocation failure. Therefore, we introduce a new solution to this problem, the guaranteed contiguous memory allocator (GCMA). This guarantees efficient memory space utilization, short latency, and successful allocation. The GCMA uses a reservation scheme and increases memory utilization by sharing the memory with immediately discardable data. Our evaluation of a GCMA on a Raspberry Pi 2 finds a latency that is 15-130 times lower compared to a CMA, and a latency that is up to 10 times lower when taking a photo. Using a large working set in a memory-fragmented high-end system, the GCMA is able to produce a 2.27× speedup.

The log-structured merge (LSM) tree is designed to provide efficient indexing for data that is frequently updated by using the log-structured approach. It defers merge operations for reordering data, propagating the index changes from a memory-resident component through one or more disk components. Thus, LSM-based storage engines can achieve good write performance. However, processing merge operations incurs high write amplification and memory consumption, ultimately having an adverse effect on system performance. In this paper, we propose the Ranged Log-Structured Merge (RLSM) tree to mitigate the problems of the LSM tree. To reduce the write amplification and memory overhead, RLSM simplifies the logical layout of storage and keeps data as an unsorted order. In addition, we prevent read performance from declining by partitioning data on the disk into multiple files with non-overlapping ranges. We implement our schemes on HBase, one of the most popular key-value storage engines, and evaluate our system by using YCSB benchmark. Our experimental results show that RLSM consequently reduces write amplification by a factor of 3, and memory consumption by up to 24%.

As modern computer systems face the challenge of managing large data, filesystems must deal with a large number of files. This leads to amplified concerns of metadata and data operations. Filesystems in Linux manage the metadata of files by constructing in-memory structures such as directory entry (dentry) and inode. However, we found inefficiencies in metadata management mechanisms, especially in the path traversal mechanism of Linux file systems when searching for a dentry in the dentry cache.

Scale-out distributed storage systems can uphold balanced data growth in terms of capacity and performance on an on-demand basis. However, it is a challenge to store and manage large sets of contents being generated by the explosion of data. One of the promising solutions to mitigate big data issues is data deduplication, which removes redundant data across many nodes of the storage system. Nevertheless, it is non-trivial to apply a conventional deduplication design to the scale-out storage due to the following root causes. First, chunk-lookup for deduplication is not as scalable and extendable as the underlying storage system supports. Second, managing the metadata associated to deduplication requires a huge amount of design and implementation modifications of the existing distributed storage system. Lastly, the data processing and additional I/O traffic imposed by deduplication can significantly degrade performance of the scale-out storage. To address these challenges, we propose a new deduplication method, which is highly scalable and compatible with the existing scale-out storage. Specifically, our deduplication method employs a double hashing algorithm that leverages hashes used by the underlying scale-out storage, which addresses the limits of current fingerprint hashing. In addition, our design integrates the meta-information of file system and deduplication into a single object, and it controls the deduplication ratio at online by being aware of system demands based on post-processing. We implemented the proposed deduplication method on an open source scale-out storage. The experimental results show that our design can save more than 90% of the total amount of storage space, under the execution of diverse standard storage workloads, while offering the same or similar performance, compared to the conventional scale-out storage.

Flash-based NVMe storage devices dramatically improve I/O latency as well as I/O throughput. However, existing scale-out storage systems are designed for targeting hard disk drives and this design limitation causes significant performance degradation when they are used with NVMe devices. In this paper, we analyzed the performance of an existing scale-out storage system and identified lack of data locality and excessive lock contentions. To mitigate these problems, we present a new design based on locality aware lock contention avoidance (LALCA). LALCA proposes two techniques for scale-out storage system on high speed storage device: (1) locality-aware thread control to minimize processor context switching overhead and relevant performance degradation and (2) lock contention avoidance to remove locking problems in existing scale-out distributed storage system. With evaluation, LALCA shows not only up to 9 times performance improvement but also up to half CPU usage reduction when servicing small random I/Os.

A large number of cloud datastores have been developed to handle the cloud OLTP workload. Double caching problem where the same data resides both at the user buffer and the kernel buffer has been identified as one of the problems and has been largely solved by using direct I/O mode to bypass the kernel buffer. However, maintaining the caching layer only in user-level has the disadvantage that the user process may monopolize memory resources and that it is difficult to fully utilize the system memory due to the risks of the forced termination of the process or the unpredictable performance degradation in case of memory pressure. In this paper, we propose a new I/O mode, DBIO, to efficiently exploit OS kernel buffer as a victim cache for user-level file content cache, enjoying the strengths of kernel-level cache rather than just skipping it. DBIO provides the new file read/write function calls, which enable user programs to dynamically choose the right I/O behavior based on their context when issuing I/Os instead of when opening the file. On the cloud key-value store workloads and the traditional OLTP workloads with the modified version of MySQL/InnoDB, DBIO improves the in-memory cache hit ratio and the transaction performance compared to both buffered and direct I/O mode, fully utilizing the user buffer and the kernel buffer without double caching.

With the growth of online services, a large amount of files have been generated by users or by the service itself. To make it easier to service users with different network environments and devices, online services usually keep different versions of the same file with various sizes. For users with high speed network and top of the line displays, a large size file with high precision can be supplied while users with mobile devices typically receive a smaller file with less precision. In some cases, a large file can be divided into small files to make it easier to transmit over the wide area networks. As a result, underlying filesystem should efficiently maintain a large number of small files. Providing such a huge number of files to applications is one of new challenges of existing filesystems. In this paper, we propose techniques to efficiently manage a large number of files in digital archives using data characteristics and access patterns of the application. Based on the knowledge we have of the upper layer applications, we have modified both in-memory and on-disk inode structure of the existing filesystem and were able to dramatically reduce the number of storage I/O operations to service the same files. Our experimental results show that the proposed methods significantly reduce the number of storage I/O operations both for reading and writing files, especially for small-sized ones. Moreover, we demonstrated that proposed techniques reduce the application-level latency as well as improve file operation throughput, using several synthetic- and microbenchmarks.

Backup and recovery is an important feature of database systems since it protects data against unexpected hardware and software failures. Database systems can provide data safety and reliability by creating a backup and restoring the backup from a failure. Database administrators can use backup/recovery tools that are provided with database systems or backup/recovery methods with operating systems. However, the existing tools perform time-consuming jobs and the existing methods may negatively affect run-time performance during normal operation even though high-performance SSDs are used. In this paper, we present an SSD-assisted backup/recovery scheme for database systems. In our scheme, we extend the out-of-place update characteristics of flash-based SSDs for backup/recovery operations. To this end, we exploit the resources (e.g., flash translation layer and DRAM cache with supercapacitors) inside SSDs, and we call our SSD with new backup/recovery features BR-SSD. We design and implement the backup/recovery functionality in the Samsung enterprise-class SSD (i.e., SM843Tn) for more realistic systems. Furthermore, we conduct a case study of BR-SSDs in replicated database systems and modify MySQL with replication to integrate BR-SSDs. The experimental result demonstrates that our scheme provides fast recovery while it does not negatively affect the run-time performance during normal operation.

Fast non-volatile memory (NVM) technologies (e.g., phase change memory, spin-transfer torque memory, and MRAM) provide high performance to legacy storage systems. These NVM technologies have attractive features, such as low latency and high throughput to satisfy application performance. Accordingly, fast storage devices based on fast NVM lead to a rapid increase in the demand for diverse computer systems and environments (e.g., cloud platforms, web servers, and database systems) where they are expected to be used as primary storage. Despite the promised benefits provided by fast storage devices, modern file systems do not take advantage of the storage's full performance. In this article, we analyze and explore existing I/O strategies in read, write, journal I/ O, and recovery paths between the file system and the storage device. The analysis shows that existing I/O strategies are an obstacle to get maximum performance of fast storage devices. To address this issue, we propose efficient I/O strategies that enable file systems to fully exploit the performance of fast storage devices. Our main idea is to transfer requests from discontiguous host memory buffers in the file systems to discontiguous storage segments in one I/O request to get maximize I/O performance. We implemented our scheme to read, write, journal I/O and recovery operations in the EXT4 file system and the JBD2 module. We demonstrate the implication of our idea in terms of application performance through well-known benchmarks. The experimental results show that our optimized file system achieves better performance than the existing file system, with improvements of up to 1.54 ×, 1.96×, and 2.28× on ordered mode, data journaling mode, and recovery, respectively.

The proliferation of the big data analysis and the wide spread usage of public/private cloud services make it important to expand the storage capacity as the demand is increased. The scale-out storage is gaining more attention since it can inherently provide scalable storage capacity. The flash SSD, on the other hand, is getting popular as the drop-in replacement of the slow HDD, which seems to boost the system performance somewhat at least. However, the performance of traditional scale-out storage system does not get much better even though its HDD is replaced with the flash based high performance SSD since the whole system is designed based on HDD as its underlying storage device. In this paper, we identify performance problems of a representative scale-out storage system, Ceph, and analyze that these problems are caused by 1) Coarse-grained lock, 2) Throttling logic, 3) Batching based operation latency and 4) Transaction Overhead. We propose some optimization techniques for flash-based Ceph. First, we minimize coarse-grained locking. Second, we introduce throttle policy and system tuning. Third, we develop non-blocking logging and light-weight transaction processing. We found that our optimized Ceph shows up to 20 times improvement in the case of small random writes and it also shows more than two times better performance in the case of small random read through our experiments. We also show that the system exhibits linear performance increase as we add more nodes.

In most file systems, performance is usually sacrificed in exchange for crash consistency, which ensures that data and metadata are restored consistently in the event of a system crash. To escape this trade-off between performance and crash consistency, recent researchers designed and implemented the transactional functionality inside Solid State Drives (SSDs). However, in order to investigate its benefit in a more realistic and standard fashion, this scheme should be re-evaluated in enterprise storage with standard interface. This paper explores the challenges and implications of a transactional SSD with extensive experiments. To evaluate the potential benefit of transactional SSD, we design and implement the transaction functionality in Samsung enterprise-class and SATA-based SSD (i.e., SM843TN) and name it TxSSD. We then modify the existing file systems (i.e., ext4 and btrfs) on topof TxSSD, making both file systems crash-consistent without redundant writes. We perform performance evaluation of two filesystems by using file I/O and OLTP benchmarks with a database. We also disclose and analyze the overhead of transactional functionality inside SSD. The experimental results show that TxSSD-aware file systems exhibit better performance compared to crash-consistent modes (i.e., data journaling mode of ext4 and cow mode of btrfs) but worse performance compared to weak consistent modes (i.e., ordered mode of ext4 and no datacow mode of btrfs).

In modern operating systems, memory-mapped I/O ( mmio ) is an important access method that maps a file or file-like resource to a region of memory. The mapping allows applications to access data from files through memory semantics (i.e., load/store) and it provides ease of programming. The number of applications that use mmio are increasing because memory semantics can provide better performance than file semantics (i.e., read/write). As more data are located in the main memory, the performance of applications can be enhanced owing to the effect of a large cache. When mmio is used, hot data tend to reside in the main memory and cold data are located in storage devices such as HDD and SSD; data placement in the memory hierarchy depends on the virtual memory subsystem of the operating system. Generally, the performance of storage devices has a direct impact on the performance of mmio . It is widely expected that better storage devices will lead to better performance. However, the expectation is limited when fast storage devices are used since the virtual memory subsystem does not reflect the performance feature of those devices. In this article, we examine the Linux virtual memory subsystem and mmio path to determine the influence of fast storage on the existing Linux kernel. Throughout our investigation, we find that the overhead of the Linux virtual memory subsystem, negligible on the HDD, prevents applications from using the full performance of fast storage devices. To reduce the overheads and fully exploit the fast storage devices, we present several optimization techniques. We modify the Linux kernel to implement our optimization techniques and evaluate our prototyped system with low-latency storage devices. Experimental results show that our optimized mmio has up to 7x better performance than the original mmio . We also compare our system to a system that has enough memory to keep all data in the main memory. The system with insufficient memory and our mmio achieves 92% performance of the resource-rich system. This result implies that our virtual memory subsystem for mmap can effectively extend the main memory with fast storage devices.

Emerging high-performance storage devices have attractive features such as low latency and high throughput. This leads to a rapid increase in the demand for fast storage devices in cloud platforms, social network services, etc. However, there are few block-based file systems that are capable of utilizing superior characteristics of fast storage devices. In this paper, we find that the I/O strategy of modern operating systems prevents file systems from exploiting fast storage devices. To address this problem, we propose several optimization techniques for block-based file systems. Then, we apply our techniques to two well-known file systems and evaluate them with multiple benchmarks. The experimental results show that our optimized file systems achieve 32% on average and up to 54% better performance than existing file systems.

Since 1990's, Snapshot Isolation (SI) has been widely studied, and it was successfully deployed in commercial and open-source database engines. Berenson et al. showed that data consistency can be violated under SI. Recently, a new class of Serializable SI algorithms (SSI) has been proposed to achieve serializable execution while still allowing concurrency between reads and updates.

Current key value stores rely on DRAM based inmemory architectures where scalability is limited by high power and low density of DRAM. As an alternative, flash SSDs has been explored because of the merits of low power, high density and high internal parallelism. However, the unpredictable latency caused by SSD internal resource conflicts challenges the use of flash SSDs. To address this issue, we present HIOPS-KV a storage I/O software stack for key value stores. HIOPS-KV exploits multiple solid-state drives (SSDs) to control the latencies. With replicas, HIOPS-KV avoids structural collisions which cause long latency operations by spreading colliding operations to distinct devices. For evaluation, we integrated HIOPS-KV into memcached on a low cost high IOPS SSD system built with PC components. At 32 YCSB clients, our system was capable of 117k ops/sec with 263 us average latency showing approximately 4ms at the 99th percentile latency.

Storage I/O in VM (Virtual Machine) environments, which requires low latency, becomes problematic as the fast storage such as SSDs (Solid-State Drives) is currently in use. The low performance problem in the VM environment is caused by 1) the presence of additional software layer such as guest OS, 2) context switching between VM and host OS, and 3) scheduling delay for I/O process. These factors do not cause serious problems in the case of using HDD which leads to high latency batching. However, there will be significant performance degradation when fast storage devices are used. To address this problem, we have proposed the following methods to improve the performance of I/O stack in the VM environments by attempting to optimize the I/O stack: one is pipelined polling, and the other is multiple issues and multiple completions. We have found via experiments that our approach leads to increases in the performance of SSDs in a VM environment by up to 50% when multiple VM storage devices are used, and that it leads to improvements in the performance by more than 80% when a single VM storage device is used, with the CPU utilization reduced by up to 25%.

Fast storage devices are an emerging solution to satisfy data-intensive applications. They provide high transaction rates for DBMS, low response times for Web servers, instant on-demand paging for applications with large memory footprints, and many similar advantages for performance-hungry applications. In spite of the benefits promised by fast hardware, modern operating systems are not yet structured to take advantage of the hardware’s full potential. The software overhead caused by an OS, negligible in the past, adversely impacts application performance, lessening the advantage of using such hardware. Our analysis demonstrates that the overheads from the traditional storage-stack design are significant and cannot easily be overcome without modifying the hardware interface and adding new capabilities to the operating system. In this article, we propose six optimizations that enable an OS to fully exploit the performance characteristics of fast storage devices. With the support of new hardware interfaces, our optimizations minimize per-request latency by streamlining the I/O path and amortize per-request latency by maximizing parallelism inside the device. We demonstrate the impact on application performance through well-known storage benchmarks run against a Linux kernel with a customized SSD. We find that eliminating context switches in the I/O path decreases the software overhead of an I/O request from 20 microseconds to 5 microseconds and a new request merge scheme called Temporal Merge enables the OS to achieve 87% to 100% of peak device performance, regardless of request access patterns or types. Although the performance improvement by these optimizations on a standard SATA-based SSD is marginal (because of its limited interface and relatively high response times), our sensitivity analysis suggests that future SSDs with lower response times will benefit from these changes. The effectiveness of our optimizations encourages discussion between the OS community and storage vendors about future device interfaces for fast storage devices.

Modern implementations of DBMS software are intended to take advantage of high core counts that are becoming common in high-end servers. However, we have observed that several database platforms, including MySQL, Shore-MT, and a commercial system, exhibit throughput collapse as load increases into oversaturation (where there are more request threads than cores), even for a workload with little or no logical contention for locks, such as a read-only workload. Our analysis of MySQL identifies latch contention within the lock manager as the bottleneck responsible for this collapse. We design a lock manager with reduced latching, implement it in MySQL, and show that it avoids the collapse and generally improves performance. Our efficient implementation of a lock manager is enabled by a staged allocation and deallocation of locks. Locks are preallocated in bulk, so that the lock manager only has to perform simple list manipulation operations during the acquire and release phases of a transaction. Deallocation of the lock data structures is also performed in bulk, which enables the use of fast implementations of lock acquisition and release as well as concurrent deadlock checking.

Storage area network (SAN) is one of the most popular solutions for constructing server environments these days. In these kinds of server environments, HDD-based storage usually becomes the bottleneck of the overall system, but it is not enough to merely replace the devices with faster ones in order to exploit their high performance. In other words, proper optimizations are needed to fully utilize their performance gains. In this work, we first adopted a DRAM-based SSD as a fast backend-storage in the existing SAN environment, and found significant performance degradation compared to its own capabilities, especially in the case of small-sized random I/O pattern, even though a high-speed network was used. We have proposed three optimizations to solve this problem: (1) removing software overhead in the SAN I/O path; (2) increasing parallelism in the procedures for handling I/O requests; and (3) adopting the temporal merge mechanism to reduce network overheads. We have implemented them as a prototype and found that our approaches make substantial performance improvements by up to 39% and 280% in terms of both the latency and bandwidth, respectively.

Increasingly, smart phones are becoming one of the most popular mobile devices in personal computing environment. As the need for a variety of mobile applications is increasing, the target mobile platform is a primary concern for mobile application developers. To reduce design complexity for different platforms and enhance the compatibility of applications on various mobile OSes, a JavaScript-based web environment became a main target framework for smart phone applications. Computing-intensive and rich graphics-based applications in a smart phone may fully utilize the CPU, and consume a large amount of the battery power accordingly. In this paper, we propose PIOS, a platform-independent offloading system, which is a delegated system for a mobile web environment. Our evaluation shows that PIOS increases the response time of the application running in the web browser, and enables a high workload application to run on relatively low-end mobile devices. Our web-based offloading architecture creates a new mobile computing environment, and can be applied various OS platforms of mobile clients.

Increasingly, smart phones are becoming one of the most popular mobile devices in personal computing environment. As the need for a variety of mobile applications is increasing, the target mobile platform is a primary concern for mobile application developers. To reduce design complexity for different platforms and enhance the compatibility of applications on various mobile OSes, a JavaScript-based web environment became a main target framework for smart phone applications. Computing-intensive and rich graphics-based applications in a smart phone may fully utilize the CPU, and consume a large amount of the battery power accordingly. In this paper, we propose PIOS, a platform-independent offloading system, which is a delegated system for a mobile web environment. Our evaluation shows that PIOS increases the response time of the application, and reduces power consumption of the device. Our web-based offloading architecture creates a new mobile computing environment.

Modern implementations of DBMS software are intended to take advantage of high core counts that are becoming common in high-end servers. However, we have observed that several database platforms, including MySQL, Shore-MT, and a commercial system, exhibit throughput collapse as load increases, even for a workload with little or no logical contention for locks. Our analysis of MySQL identifies latch contention within the lock manager as the bottleneck responsible for this collapse.

As the popularity of mobile devices increase, more and more smart phones are being utilized as main computing devices in recent years. Applications for mobile devices have been widely developing even more prevalent than those for PCs. Most mobile applications also integrate with web browsers, with JavaScript serving as an important framework for web-based mobile applications. However, these applications require great amounts of computational power and energy. In addition, relatively low-end mobile devices that pose some limitations in supporting complicated web resource are widely used in developing countries. In this paper, we propose SOME architecture, which is an offloading system for mobile applications, in an effort to reduce the computational cost of mobile devices. We design and implement a delegated system that splits the original JavaScript-based application codes into two parts: a lightweight code for the client and a computationally heavy code to run on a server machine. In our evaluation, our system shows better performance in casual turn-based applications. Overall, the SOME architecture creates a new mobile computing environment that increases the total performance and overcomes resource limitation without platform dependence of mobile clients.

Contemporary operating systems for single-ISA (instruction set architecture) multi-core systems attempt to distribute tasks equally among all the CPUs. This approach works relatively well when there is no difference in CPU capability. However, there are cases in which CPU capability differs from one another. For instance, static capability asymmetry results from the advent of new asymmetric hardware, and dynamic capability asymmetry comes from the operating system (OS) outside noise caused from networking or I/O handling. These asymmetries can make it hard for the OS scheduler to evenly distribute the tasks, resulting in less efficient load balancing. In this paper, we propose a user-level load balancer for parallel applications, called the’ capability balancer’, which recognizes the difference of CPU capability and makes subtasks share the entire CPU capability fairly. The balancer can coexist with the existing kernel-level load balancer without detrimenting the behavior of the kernel balancer. The capability balancer can fairly distribute CPU capability to tasks with very little overhead. For real workloads like the NAS Parallel Benchmark (NPB), we have accomplished speedups of up to 9.8% and 8.5% in dynamic and static asymmetries, respectively. We have also experienced speedups of 13.3% for dynamic asymmetry and 24.1% for static asymmetry in a competitive environment. The impacts of our task selection policies, FIFO (first in, first out) and cache, were compared. The use of the cache policy led to a speedup of 5.3% in overall execution time and a decrease of 4.7% in the overall cache miss count, compared with the FIFO policy, which is used by default.

Over the past decades, caching has become the key technology used for bridging the performance gap across memory hierarchies via temporal or spatial localities; in particular, the effect is prominent in disk storage systems. Applications that involve heavy I/O activities, which are common in the cloud, probably benefit the most from caching. The use of local volatile memory as cache might be a natural alternative, but many well-known restrictions, such as capacity and the utilization of host machines, hinder its effective use. In addition to technical challenges, providing cache services in clouds encounters a major practical issue (quality of service or service level agreement issue) of pricing. Currently, (public) cloud users are limited to a small set of uniform and coarse-grained service offerings, such as High-Memory and High-CPU in Amazon EC2. In this paper, we present the cache as a service (CaaS) model as an optional service to typical infrastructure service offerings. Specifically, the cloud provider sets aside a large pool of memory that can be dynamically partitioned and allocated to standard infrastructure services as disk cache. We first investigate the feasibility of providing CaaS with the proof-of-concept elastic cache system (using dedicated remote memory servers) built and validated on the actual system, and practical benefits of CaaS for both users and providers (i.e., performance and profit, respectively) are thoroughly studied with a novel pricing scheme. Our CaaS model helps to leverage the cloud economy greatly in that 1) the extra user cost for I/O performance gain is minimal if ever exists, and 2) the provider's profit increases due to improvements in server consolidation resulting from that performance gain. Through extensive experiments with eight resource allocation strategies, we demonstrate that our CaaS model can be a promising cost-efficient solution for both users and providers.

This paper proposes a scheme to enhance energy efficiency and QoS of real time network applications on smart phone. The scheme reduces energy consumption and increases the successful interaction rate between the client at smart phone and the busy server of real time network application by deploying a surrogate of the client at smart phone in cloud computing environment. All interactions among the client at smart phone, the application server and the surrogate in the cloud are controlled by tokens. The proposed scheme considers security as well as energy waste in the cloud.

The design of an end-to-end Internet congestion control protocol that could achieve high utilization, fair sharing of bottleneck bandwidth, and fast convergence while remaining TCP-friendly is an ongoing challenge that continues to attract considerable research attention. This paper presents ACP, an Adaptive end-to-end Congestion control Protocol that achieves the above goals in high bandwidth-delay product networks where TCP becomes inefficient. The main contribution of ACP is a new form of congestion window control, combining the estimation of the bottleneck queue size and a measure of fair sharing. Specifically, upon detecting congestion, ACP decreases the congestion window size by the exact amount required to empty the bottleneck queue while maintaining high utilization, while the increases of the congestion window are based on a “fairness ratio” metric of each flow, which ensures fast convergence to a fair equilibrium. We demonstrate the benefits of ACP using both ns-2 simulation and experimental measurements of a Linux prototype implementation. In particular, we show that the new protocol is TCP-friendly and allows TCP and ACP flows to coexist in various circumstances, and that ACP indeed behaves more fairly than other TCP variants under heterogeneous round-trip times (RTT).

Trust for the data created and processed on e-Science environment can be estimated with provenance. The information to form provenance, which says how the data was created and reached its current state, increases as data evolves. It is a heavy burden to trace and verify the massive provenance along the history of data in order to trust data. On the other hand, it is another issue how to trust the verification of data with provenance assuming that the provenance is believable. This paper proposes the property-based trust reasoning which cuts down the overhead to track the history and the origin of data with provenance by semantic path on Open Provenance Model(OPM). Also, the domain-based trust reasoning is adopted, which uses the domain specialty of e-Science environment. The two trust reasonings form the multi-layer trust reasoning. The effectiveness of the proposal is shown by quantitative analysis of overhead reduction as well as by qualitative analysis of trust reasoning.

Write-through caching in modern disk drives enables the protection of data in the event of power failures as well as from certain disk errors when the write-back cache does not. Host system can achieve these benefits at the price of significant performance degradation, especially for small disk writes. We present new block-level techniques to address the performance problem of write-through caching disks. Our techniques are strongly motivated by some interesting results when the disk-level caching is turned off. By extending the conventional request merging, request bridging increases the request size and amortizes the inherent delays in the disk drive across more bytes of data. Like sector interleaving, request interleaving rearranges requests to prevent the disk head from missing the target sector position in close proximity, and thus reduces disk latency. We have evaluated our block-level approach using a variety of I/O workloads and shown that it increases disk I/O throughput by up to about 50%. For some real-world workloads, the disk performance is comparable or even superior to that of using the write-back disk cache. In practice, our simple yet effective solutions achieve better tradeoffs between data reliability and disk performance when applied to write-through caching disks.

This article presents Athanasia, a user-transparent and fault-tolerant system, for parallel applications running on large-scale cluster systems. Cluster systems have been regarded as a de facto standard to achieve multitera-flop computing power. These cluster systems, as we know, have an inherent failure factor that can cause computation failure. The reliability issue in parallel computing systems, therefore, has been studied for a relatively long time in the literature, and we have seen many theoretical promises arise from the extensive research. However, despite the rigorous studies, practical and easily deployable fault-tolerant systems have not been successfully adopted commercially. Athanasia is a user-transparent checkpointing system for a fault-tolerant Message Passing Interface (MPI) implementation that is primarily based on the sync-and-stop protocol. Athanasia supports three critical functionalities that are necessary for fault tolerance: a light-weight failure detection mechanism, dynamic process management that includes process migration, and a consistent checkpoint and recovery mechanism. The main features of Athanasia are that it does not require any modifications to the application code and that it preserves many of the high performance characteristics of high-speed networks. Experimental results show that Athanasia can be a good candidate for practically deployable fault-tolerant systems in very-large and high-performance clusters and that its protocol can be applied to a variety of parallel communication libraries easily.

This paper focuses on large graph processing based on the remote memory system. Using our remote memory system enables applications to deal with large data sets, especially graph data, which do not fit into the machines main memory. Although recent dramatic increases in DRAM capacity now allow us to build inexpensive computers with very large amounts of main memory, the rise in brand-new Internet services has resulted in rapid increases in data size. This is especially true for on-line social network services that generate various data sets that can be represented as graphs. On the other hand, high-speed networking technologies such as Infini Band, Myrinet and 10G Ethernet now enable us to transfer data with low latency and high throughput. The advanced networking technologies reduce the latency/bandwidth gap between main memory and remote memory. Thus, remote memory based processing could now be helpful in accelerating large-scale graph process when main memory space is insufficient to store application data. In this paper, we present our design and implementation of remote memory system that efficiently processes large graph data. We also evaluate a breadth-first search of various types of graphs using our system and show that our approach is good for large graph data processing.

Phishing websites impersonate legitimate counterparts to lure users into visiting their websites. Once users visit a phishing website then the phishing website may steal users' private information or cause drive-by downloads. To detect a phishing website, human experts compare the claimed identity of a website with features in the website. For example, human experts often compare the domain name in the URL against the claimed identity. Most legitimate websites have domain names that match their identities, while phishing websites usually have less relevance between their domain names and their claimed (fake) identities. In addition to blacklists, whitelists, heuristics, and classifications used in the state-of-the-art systems, we propose to consider websites' identity claims. Our phishing detection system mimics this human expert behavior. Given a website, our system learns the identity that this website claims, and computes the textual relevance between this claimed identity and other features in the website. Our phishing detection system then uses this textual relevance as one of the features for classification, and our classifiers achieve more than 98% of true positive rate and very low false positive rate between 0.5% and 1%.

In this research, a new evaluation model to select adequate ontologies that fit user requirements is proposed. The model consists of selection criteria and measurements. The proposed model presents two novel features distinct from previous research models. First, it enables users to assign weights to the evaluation criteria based on assumed impacts on ontology selection. Second, it enables users to search keywords from multiple ontologies. In addition, new metrics for the selection criteria are proposed. For empirical analysis, a prototype was developed and experiments were performed. The experimental results indicate that our evaluation model for ontology selection is valid and works well. The ultimate goal of this research is to provide an ontology evaluation model, enabling ontology users to select adequate ontologies to user requirements.

Native Command Queueing (NCQ) is an optimization technology to maximize throughput by reordering requests inside a disk drive. It has been so successful that NCQ has become the standard in SATA 2 protocol specification, and the great majority of disk vendors have adopted it for their recent disks. However, there is a possibility that the technology may lead to an information gap between the OS and a disk drive. A NCQ-enabled disk tries to optimize throughput without realizing the intention of an OS, whereas the OS does its best under the assumption that the disk will do as it is told without specific knowledge regarding the details of the disk mechanism. Let us call this expectation discord , which may cause serious problems such as request starvations or performance anomaly. In this article, we (1) confirm that expectation discord actually occurs in real systems; (2) propose software-level approaches to solve them; and (3) evaluate our mechanism. Experimental results show that our solution is simple, cheap (no special hardware required), portable, and effective.

Recently, REpresentational State Transfer (REST) has been proposed as an alternative architecture for Web services.In the era of Cloud and Web 2.0, many complex Web service-based systems such as e-Business an de-Government applications have adopted REST. Unfortunately, the REST approach has been applied to few cases in management systems, especially for a management system for cloud computing infrastructures.In this paper, we design and implement a RESTful Cloud Management System (CMS).Managed elements can be modeled as resources in REST and operations in existing systems can be evaluated using four methods of REST or a combination of them.We also show how components of existing management systems can be realized as REST-style Web services.

This paper introduces a tele-management system as a part of SmartUM which is a ubiquitous cloud middleware for ubiquitous city (u-city). The cloud computing platform allows users to control remote devices. The users get data from a various kinds of remote sensors and scene images about the place of sensors from remote video cameras and control remote devices seeing the scene images of the remote place. Our cloud computing platform has context-awareness and can intelligently control the remote devices according to the circumstance scenario. We used ontology for the context aware intelligence processing.

Item matchmaking that finds items for users is an essential service framework in the web service infrastructure. The current way of carrying out the matchmaking procedure is the selection of items based on a user's specifications. We rethink the item matchmaking framework in such a way that a matchmaker can find items that can satisfy a specific computing demand from a user and recommend a collection of better items candidates among the identified items. This endows a user with the right of choice on deciding best-possible items. We approach the problem in the view of skyline query processing that has become one of the major topics in the database community, and present the efficient skyline algorithm that gathers interesting item candidates efficiently. To this end, we adopt (i) lattice-based indexing using a lattice composition technique,and (ii) an optimized dominance-check algorithm. Our extensive experimental results show that our algorithm outperforms the current state-of-the-art algorithm.

To provide on-demand video streaming services through the network, video objects with both high and low client request rates must be served efficiently. In this paper, we propose a dynamic scheme transition to provide on-demand streaming services efficiently regardless of video popularity. This approach can maintain quality-of-service (QoS) by transitioning the service scheme according to the request rate. The server provides services by heuristically broadcasting video segments when the video popularity is low and by a periodic broadcast when the video popularity is high. The server identifies the variations in client request rates from the number of service channels and determines transitions to more efficient service schemes autonomously. We evaluated this scheme transition for various parameters and traces from a company providing streaming services. The results show that the performance of scheme transition is very efficient.

Workflow manager is a useful tool that brings the power of computational Grid resources to the desktop, and allow them to conveniently put together and run their own scientific workflows. In existing workflow systems, individual tasks wait for input to be available perform computation,and produce output. Behind this, workflow manager automates the data movement from the data generating taskto the data consumption task. This process is referred as file staging. Generally, stage-in, process, and stage-out are serially executed and staging is treated by traditional workflow systems as a trivial step. However, as the data sizeis exponentially increasing and more and more scientific workflows require multiple processing steps to obtain the desired output, we argue that the data movement will possess high portion of overall running time and staging will become a challenging step of scientific workflow systems. In this paper, we propose a task pipelining framework for various e-Science workflow systems. Our system is a flexible and efficient tool to help the workflow systems to overlap the execution of adjacent tasks by enabling the pipelining ofthe intermediate data transfer between the interconnected tasks.

This paper proposes an efficient, scalable and secure (ESS) data management system on HVEM datagrid to ensure the security for data access as well as to balance the load of data intensive processing using active disks. When authentication and authorization are managed by a storage manager or a server on datagrid, if an attacker succeeds in assaulting the entity, he can access to the data on the disks and manipulate it easily. In addition, as data increases, so does the overhead of its processing as much. One example is to search files by image matching. So, we can let the disk take charge of the matching and the cryptographic processing for authentication, authorization and encryption/decryption beyond the simple role to keep data. Through evaluation, we show that the ESS system using disk intelligence can be very advantageous in security and cost-effectiveness.

We focus on faster and more reliable third-party transfer in the data Grid with extending existing service - reliable file transfer service.

MapReduce is Google's programming model for easy development of scalable parallel applications which process huge quantity of data on many clusters. Due to its conveniency and efficiency, MapReduce is used in various applications (e.g., Web search services and online analytical processing). However, there are only few good benchmarks to evaluate MapReduce implementations by realistic testsets. In this paper, we present MRBench that is a benchmark for evaluating MapReduce systems. MRBench focuses on processing business oriented queries and concurrent data modifications. To this end, we build MRBench to deal with large volumes of relational data and execute highly complex queries. By MRBench, users can evaluate the performance of MapReduce systems while varying environmental parameters such as data size and the number of (map/reduce) tasks. Our extensive experimental results show that MRBench is a useful tool to benchmark the capability of answering critical business questions.

Pioneering work on Aspect Oriented Programming (AOP) has not flourished enough to enrich the design of distributed systems with the refined AOP paradigm. The more generous perspective today is that a decade of growing research on AOP has brought the paradigm into many exciting areas. We investigate two case studies that cover time-honored issues, fault tolerant computing and parallel computing, in the cluster computing world using the AOP paradigm. Aspects that we define here are simple, intuitive and reusable. We believe that our implementation is very useful in developing other cluster computing software, and AOP can be a powerful method in modularizing source codes.

Web Service has its characteristic of statelessness. But, many applications on Grid need the stateful services. The advanced search on HVEM DataGrid is one example. The search service provides a multi-depth search and an associated search. The service should trace the search states and provide the access control as well as the service security in the search process. In addition, we should remember that the Web Services or the resources can stretch multiple Virtual Organization(VO)s and Certificate Authority(CA)s. In this paper, we propose a secure stateful Web Service to satisfy the requirements stated. We describe the Stateful Web Service with the Scalable Security (S3WS) as its service environment and its protocol in detail. Through the security proof, the scalability analysis and the estimation of performance and overhead, we demonstrate the stateful Web Service proposed to be secure and light weight enough to be realistic.

The performance of computer systems depends on relatively slow disk I/O performance. In order to improve the disk I/O performance, it is required to reduce a mechanical delay induced by the disk I/O operations. Several approaches have been proposed for it. However, because hard-disk storage hides too much information to the outside world, it makes difficult to predict exact internal layout of disk storage. This paper introduces a technique which brings this black box to light empirically. The technique can be called a gray-box approach due to the use of some prior knowledge about disk drives. We propose a new algorithm that extract disk model parameters and build overall multi-dimensional disk structural model for several up-to-data IDE disk drives whose internals are known as a black-box. We validate the model accuracy through seek time analysis. We expect our modeling result can be applied to many researches optimizing disk I/O performance.

The Data Grid provides a scalable infrastructure for storage resources and data distribution management. It also supports a variety of scientific applications that require access to large amounts of data with various quality of service requirements. Replication is the process of storing data in different locations to reduce access latency, improve data locality, and increase robustness, scalability and performance for distributed applications. It is the core mechanism of the Data Grid in that it enables scalable and efficient sharing of large volumes of data. This paper focuses on finding the fastest and most reliable replica retrieval method in the Data Grid. For fast retrieval, we inspected, implemented, and tested various retrieval approaches, such as uniform, greedy, probe-based, latest-based, mean-based, and median-based. Experiments show that probe-based retrieval is the most appropriate approach for the Data Grid. For reliable retrieval, we introduce the recursive scheduling mechanism, which provides fault tolerant retrieval by rescheduling a failed subtransferring. Finally, we implemented ReCon (Replica Convoy) on Globus Toolkit version 4. The result is a fast and reliable replica retrieval service for the Data Grid.

Many areas of science currently use computing resources as a important part of their research, and many research groups adopt cluster architecture to use them efficiently and manage them easily. Therefore, faulttolerance becomes a very important property for the computing resources. However, fault-tolerant systems have not yet been widely adopted because they are either hard to deploy, hard to use, hard to manage, hard to maintain, or hard to justify. This paper proposes a practical fault-tolerant system for eScience infrastructures. Our system uses checkpoint/ restart mechanism for fault-tolerance, and provides a easy mechanism to integrate with Grid services widely used in eScience. Additionally, we run rigorous tests using scientific applications to verify that our system can be used in clusters. We also describe improvements made to our system to solve various problems that arose when deploying it on a cluster. The experimental results show that not only does our system conform to various types of running environment well, but that it can also be practically deployed in clusters.

Advances in network technology and computing power have inspired the emergence of high-performance cluster computing systems. While cluster management and hardware highavailability tools are readily available, practical and easily deployable fault-tolerant systems have not been successfully adopted commercially. We present a fault-tolerant system, Multiple fault-tolerant MPI over Myrinet (M3), that differs in notable respects from other proposed fault-tolerant systems in the literature. M3 is built on top of Myrinet since it is regarded as one of the best solutions for highperformance networks and is widely used in cluster computing systems because it can provide a high-speed switching network that is an inevitable ingredient in interconnecting clusters of workstations or PCs. M^3 is a user-transparent checkpointing system for multiple fault-tolerant MPI implementation that is primarily based on the coordinated checkpointing protocol. M3 supports three critical functionalities that are necessary for faulttolerance: a light-weight failure detection mechanism, dynamic process management that includes process migration, and a consistent checkpoint and recovery mechanism. The features of M are that it requires no modifications of application code and that it preserves much of the high performance characteristics of Myrinet. This paper describes the architecture of M3, its detailed design principles and comprehensive implementation issues. We also propose practical solutions for those involved in constructing highly available cluster systems for parallel programming systems. Experimental results substantiate our assertion that M3 can be a good candidate for practically deployable fault-tolerant systems in very-large and high-performance Myrinet clusters and that its protocol can be applied to a wide variety of parallel communication libraries without difficulty.

Two significant performance factors in Mobile Agent Planning (MAP) for distributed information retrieval are the number of mobile agents and the total execution time. Using fewer mobile agents results in less network traffic and consumes less bandwidth. Regardless of the number of agents used, the total execution time for a task must be kept to a minimum. A retrieval service must minimize both these factors for better system performance, and at the same time, it must be able to supply the required information to users as quickly as possible. In this paper, we propose heuristic algorithms, called Cost-Effective MAP (CEMAP), to minimize both the number of mobile agents and the total execution time under the condition that the turnaround time is kept to a minimum. Although these algorithms tend to slightly increase the planning cost, a simulation study shows that these algorithms enhance the system performance significantly. By adopting these algorithms, systems can maintain lower network traffic while satisfying the minimum turnaround time.

Peer-to-peer (P2P) networks are attracting considerable research interest because of their scalability and high performance relative to cost. One of the important services on a P2P network is the streaming service. However, because each node in the P2P network is autonomous, it is difficult to provide a stable streaming service on the network. Therefore, for a stable streaming service on the P2P network, a fault-tolerant scheme must be provided. In this paper, we propose two new node selection schemes, playback node first (PNF) and playback node first with prefetching (PNF-P), that can be used for a service migration-based fault-tolerant streaming service. The proposed schemes exploit the fact that the failure probability of a node currently being served is lower than that of a node not being served. Simulation results show that the proposed schemes outperform traditional node selection schemes.

Since multizone recording disks have different bandwidths and capacities depending on the zone in use, data placement schemes for traditional constant angular density disks are not suitable for multizone recording disks. In this paper, we propose a new block placement algorithm for multizone recording disks used for continuous media servers. The proposed scheme exploits the bandwidth-saving effect of smoothing variable bit rate data before storing them. The diversity of zone bandwidths in multizone recording disks enables it possible to achieve large smoothing effect using relatively small buffer space. Variable bit rate data blocks of an object are smoothed using multiple smoothing rates which are bandwidths of zones multiplied by the service time assigned to the object and are stored into the corresponding zones. This multirate smoothing technique decreases the buffer space required to provide deterministic service to clients. Simulation results show that a proper restructuring of blocks according to the smoothing algorithm results in dramatic performance enhancement in continuous media servers.

The distributed agent concept has become a new computing paradigm in Internet distributed computing, including mobile computing. Mobile agent planning is one of the most important techniques for completing a given task efficiently. The static planning technique may not be the best approach in real network environments. For better performance, it is necessary that mobile agents be more sensitive to the network conditions. We propose a dynamic planning algorithm, named n-ary agent chaining, which is based on static mobile agent planning. Mobile agents can change their itinerary dynamically according to current network status using the proposed algorithm. The proposed algorithm also takes into account the locality of target nodes on the network. Thus, with a properly chosen locality factor it can adapt to realistic network situations. Agents reproduced from the original one, named cloned agents, process the unprocessed nodes in the proposed algorithm. Since the turn-around time can be calculated mathematically with known network statistics before launching the agents, the proposed algorithm is suitable for agent problem domains with deadline constraints.

The reliable execution of a mobile agent is a very important design issue to build a mobile agent system and many fault-tolerant schemes have been proposed. Hence, we present the experimental evaluation of the performance of the fault-tolerant schemes for the mobile agent environment. Our evaluation focuses on the checkpointing schemes and deals with the cooperating agents.

We evaluate the performance of checkpointing and replication schemes for the fault tolerant mobile agent system. For the quantitative comparison, we have implemented an experimental system on top of the Mole mobile agent system and also built a simulation system to include various failure cases. Our experiment aims to have the insight into the behavior of agents under two schemes and provide a guideline for the fault tolerant system design. The experimental results show that the checkpointing scheme shows a very stable performance; and for the replication scheme, some controllable system parameter values should be chosen carefully to achieve the desirable performance.

A number of checkpointing and message logging algorithms have been proposed to support fault tolerance of mobile computing systems. However, little attention has been paid to the optimistic message logging scheme. Optimistic logging has a lower failure-free operation cost compared to other logging schemes. It also has a lower failure recovery cost compared to the checkpointing schemes. This paper presents an efficient scheme to implement optimistic logging for the mobile computing environment. In the proposed scheme, the task of logging is assigned to the mobile support station so that volatile logging can be utilized. In addition, to reduce the message overhead, the mobile support station takes care of dependency tracking and the potential dependency between mobile hosts is inferred from the dependency between mobile support stations. The performance of the proposed scheme is evaluated by an extensive simulation study. The results show that the proposed scheme requires a small failure-free overhead and the cost of unnecessary rollback caused by the imprecise dependency is adjustable by properly selecting the logging frequency.

The number of agents and the execution time are two significant performance factors in mobile agent planning (MAP). Fewer agents cause lower network traffic and consume less bandwidth. Regardless of the number of agents used, the execution time for a task must be kept minimal, which means that use of the minimal number of agents must not impact on the execution time unfavorably. As the population of the mobile agent application domain grows, the importance of these two factors also increases. After a careful review of these two factors, we propose two heuristic algorithms for finding the minimal number of traveling agents for retrieving information from a distributed computing environment, while keeping the latency minimal. Although agent planning, specifically MAP, is quite similar to the famous traveling salesman problem (TSP), agent planning has a different objective function from that of TSP. TSP deals with the optimal total routing cost, while MAP attempts to minimize the execution time to complete tasks of information retrieval. In this paper, we suggest two cost-effective MAP algorithms, BYKY1 (Baek-Yeo-Kim-Yeom 1) and BYKY2, which can be used in distributed information retrieval systems to find the factors mentioned above. At the end of each algorithm, 2OPT, a well-known TSP algorithm, is called to optimize each agent's local routing path. Experimental results show that BYKY2 produces near-optimal performance. These algorithms are more realistic and applicable directly to the problem domains than those of previous works.

As MZR disks have different bandwidths and capacities depending on the zone in use and the performance of continuous media servers is strongly dependent on the block placement scheme for the disks, data placement schemes for traditional CAD disks are not suitable for MZR disks. In this paper, we propose a new block placement algorithm for MZR disk arrays used for continuous media servers. The proposed scheme exploits the bandwidth-saving effect of smoothing VBR data before storing them. To fully utilize characteristics of MZR disks, VBR data are smoothed using multiple smoothing rates (multiplicity is the number of zones of MZR disk). In addition, as the service time of an object in each round is fixed during the lifetime of the stream, it is easy to determine whether the system can provide deterministic service to the new request, which simplifies admission control. Simulation results show that the proposed scheme outperforms previous schemes such as CRT and NCTT. 1.

This paper presents an efficient recovery scheme based on checkpointing and message logging for mobile computing systems. For the efficient management of checkpoints and message logs, a movement-based scheme is proposed. Mobile hosts carrying their recovery information to the nearby mobile support station can recover instantly in case of a failure, however, the cost to transfer the recovery information must be high. On the other hand, the recovery information remaining dispersed over a number of support stations visited by mobile hosts must incur very high recovery cost. To balance the failure-free operation cost and the recovery cost, in the proposed scheme, the recovery information of a mobile host remains at the visited support stations while the host moves within a certain range. Only when the host moves out of the range, the recovery information is transferred to a nearby mobile support station. As a result, the proposed scheme can control the information transfer cost as well as the recovery cost.

This paper presents a new checkpoint scheme that utilizes the memory usage profile and time series analysis for low-overhead checkpoint. The proposed checkpoint scheme checks current and future checkpoint overhead based on the on the changes of the memory size and the expected checkpoint overhead using memory profile and adaptive time series analysis when it decides whether or not to take a checkpoint. Unlike the previous works that do not utilize the memory usage profile, it is possible to reduce the total overhead of the execution time. We also present experimental results which show that the checkpoint overhead of the proposed scheme is reduced compared with the previously developed checkpoint scheme.

This paper presents region-based storage management schemes, which support the efficient implementation of checkpointing and message logging for fault tolerant mobile computing systems. In the proposed schemes, a recovery manager assigned for a group of cells takes care of the recovery for the mobile hosts within the region. As a result, the recovery information of a mobile host, which may be dispersed over the network due to the mobility of the host, can efficiently be handled.

This paper presents an asynchronous recovery scheme to provide fault-tolerance for mobile computing systems. The proposed scheme is based on optimistic message logging, since the checkpointing-only schemes are not suitable for the mobile environment in which unreliable mobile hosts and fragile network connection may hinder any kind of coordination for checkpointing and recovery. Also, in order to reduce the overhead imposed on mobile hosts, mobile support stations take charge of logging and dependency tracking, and mobile hosts maintain only a small amount of information for mobility tracking. As a result, truly asynchronous recovery for mobile systems can be achieved with little overhead.

For admission control in real time multimedia systems, buffer space, disk bandwidth and network bandwidth must be considered. Most admission control mechanisms developed to date have been based on the CBR data model and have used a static period length. These mechanisms do not use system resources effectively, since media data is usually encoded with VBR compression techniques. We propose an admission control mechanism based on a VBR data model, that has a dynamic period and considers both disk bandwidth and buffer space. Simulations show that our scheme can accept approximately twice as many streams as previous schemes based on CBR techniques and static time periods.

This paper presents a causal logging scheme for the lazy release consistent distributed shared memory systems. Causal logging is a very attractive approach to provide fault tolerance for distributed systems, since it eliminates the need for stable logging. However since interprocess dependency must causally be transferred with the normal messages, the excessive message overhead has been a drawback of this approach. In order to achieve an efficient implementation of causal logging for distributed shared memory systems, the data structures and the operations supported by the lazy release consistency memory model are utilized. For example, to implement the sender-based logging of the message contents, the diff structure is utilized, and for the causal logging of the dependency information, the operations to support the causal propagation of the write notices are utilized. As a result, the causal logging for the lazy release consistent distributed shared memory system can be implemented with a very low overhead. The simulation results using parallel applications show only 1%-4.4% increases in the execution time.

Causal message logging has many good properties such as nonblocking message logging and no rollback propagation. However, it requires a large amount of information to be piggybacked on each message, which may incur severe performance degradation. This paper presents an efficient causal logging algorithm based on the new message log structure, LogOn, which represents the causal interprocess dependency relation with much smaller overhead compared to the existing algorithms. The proposed algorithm is efficient in the sense that it requires no additional information other than LogOn to be carried in each message, while the other algorithms require extra information other than the message log, to eliminate the duplicates in log entries. Moreover, in those algorithms, as more extra information is added into the message, more duplicates can be detected. However, the proposed algorithm achieves the same degree of efficiency using only the message log carried in each message, without any extra information.

The paper presents a new logging scheme for recoverable distributed shared memory systems. In previous schemes, the logging is performed whenever a new data item is accessed or written by a process. However, in the proposed scheme, only the data item accessed by multiple processes is logged when it is invalidated by the overwritten. Moreover, the logging is performed at one process responsible for that data item, unlike the other schemes in which every process accessing the data item performs the logging. As a result, the amount and the frequency of logging can be significantly reduced. The performance of the proposed scheme is analyzed using extensive simulation study and our new logging scheme shows superior performance in various system environments.