研究者詳細 - 川島　英之

論文 - 川島　英之

分割表示 >> ／全件表示 23 件中 1 - 23 件目

Decentralization of Two Phase Locking based Protocols

Nakamori T., Nemoto J., Hoshino T., Kawashima H.

HPDC 2022 - Proceedings of the 31st International Symposium on High-Performance Parallel and Distributed Computing （HPDC 2022 - Proceedings of the 31st International Symposium on High-Performance Parallel and Distributed Computing） 281 - 282 2022年06月

Bamboo is a state-of-the-art concurrency control protocol based on the 2-phase locking protocol. One problem of Bamboo is that it requires transactions to fetch timestamps from a single centralized atomic counter. To replace the concentrated access to it, each transaction should generate timestamps independently. This paper proposes thread-ID method (TID), which dismisses the process of fetching timestamps entirely by assigning an ID to each thread, and transactions use the thread IDs as their timestamps. In high-contention settings, the performance of TID plummets, but proposed optimization FairTID sustains the performance. The experiments measured an improvement of up to 60% from Bamboo with the proposed method.

Access to Document (DOI)

Stable Low Latency Logging for Epoch-based In-memory Database

Tanaka M., Kawashima H.

Proceedings - 2022 IEEE International Conference on Big Data and Smart Computing, BigComp 2022 （Proceedings - 2022 IEEE International Conference on Big Data and Smart Computing, BigComp 2022） 167 - 170 2022年

We design and implement a logging method for the Silo concurrency control protocol and evaluate its performance. We also propose a low-latency method for Silo logging for real-time use and support threaded memory allocation for the NUMA architecture in the Silo logging implementation. The results of an experiment in which epochs were proceeded in increments of 4 ms demonstrated that the proposed method reduced the latency by 80% in exchange for a 35% reduction in throughput performance.

Access to Document (DOI)

Removing Performance Bottleneck of Timestamp Allocation in Two-Phase Locking Based Protocol

Nakamori T., Nemoto J., Hoshino T., Kawashima H.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) （Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)） 13459 LNCS 201 - 208 2022年

ISSN 03029743

Concurrency control ensures the correctness of databases when transactions are processed in parallel. Bamboo is a state-of-the-art concurrency control protocol. One problem of Bamboo is that it requires transactions to fetch timestamps from a single centralized atomic counter. To replace the concentrated access to it, each transaction should generate timestamps independently. This paper proposes two methods of decentralization to address the problem. The first is the thread-ID method (TID): transactions use thread IDs as their timestamps. In high-contention settings, the performance of TID plummets, but proposed optimization FairTID sustains the performance. The second method (RandID) allocates timestamps using random-number generators. Experiments indicated that there were up to 60% and 34% improvement in throughput from Bamboo with FairTID and RandID, respectively. In high-contention settings, TID recorded 24% degradation, but FairTID and RandID showed 19% to 31% and 12% to 22% improvement from Bamboo, respectively.

Access to Document (DOI)

Practical Effectiveness of Quantum Annealing for Shift Scheduling Problem

Hamada N., Saito K., Kawashima H.

Proceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022 （Proceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022） 421 - 424 2022年

Quantum annealing (QA) is a novel computing approach for solving computationally demanding problems more rapidly than approaches using classical computers by exploiting parallelism in the variable state updates (spin updates). A number of previous studies have shown that QA performs well in benchmarking combinatorial optimization problems, but no works have evaluated QA in the shift scheduling problem. This paper formulates it for QA and evaluates the effectiveness of QA in comparison with other methods on a classical computer. We confirmed that QA is up to about 14 times faster than classical methods in obtaining high-quality solutions for several instances.

Access to Document (DOI)

Oze: Decentralized Graph-based Concurrency Control for Real-world Long Transactions on BoM Benchmark.

Jun Nemoto, Takashi Kambayashi, Takashi Hoshino, Hideyuki Kawashima

abs/2210.04179 2022年

Access to Document (DOI)

Making ROS TF Transactional.

Yushi Ogiwara, Ayanori Yorozu, Akihisa Ohya, Hideyuki Kawashima

ICCPS 318 - 319 2022年

Access to Document (DOI)

Fast Concurrency Control with Thread Activity Management beyond Backoff.

Kosei Masumura, Takashi Hoshino, Hideyuki Kawashima

30 552 - 561 2022年

Access to Document (DOI)

Fast Accurate Discovery of Tuple Inclusion Dependencies

Shen M., Kawashima H., Saito K.

Proceedings - 2022 IEEE International Conference on Smart Computing, SMARTCOMP 2022 （Proceedings - 2022 IEEE International Conference on Smart Computing, SMARTCOMP 2022） 246 - 251 2022年

Inclusion dependencies (IND) is an important problem in relational database, relevant to data integration, query optimization and various data management tasks. The discovery of IND has been addressed by many studies following different strategies, while IND detection still needs improvement as the complexity and diversity of real-life data increase. Conventional IND is only for column-to-column dimension, which is not applicable to lots of data processing tasks. The concept of dependency can be expanded. Based on the understanding of the conventional IND and approximate approach FAIDA, we present our algorithm for detecting tuple IND, converting column-to-column detection to row-to-row dimension, more in line with real-world data retrieval tasks in distributed system. Through probabilistic and accurate detection and the use of multi-threading, both accuracy and performance are guaranteed and IND detection performance is taken to a new level.

Access to Document (DOI)

Accelerating Concurrency Control with Active Thread Adjustment

Masumura K., Hoshino T., Kawashima H.

We attempted to improve the performance of Silo, a concurrency control protocol for inmemory DataBase Management System that performs well under high-contention work-loads. Adaptive backoff is known as an effective optimization method under high-contention workloads. As a result of analyzing, we found that its efficacy lies in the non-existence of conflict events rather than in the reduction of the conflict rate, which has been considered in the past. On the basis of this analysis, we propose a method of adjusting the number of active threads. We conducted experiments comparing Cicada, another concurrency control protocol, and our method applied to Silo. The results indicate that the proposed method enabled Silo to significantly outperform. We found that cache misses are related to the performance.

Access to Document (DOI)

Accelerating Geo-Distributed Transaction Processing with Fast Logging

Ogura T., Akita Y., Miyazawa Y., Kawashima H.

Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021 （Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021） 2390 - 2399 2021年

We herein propose three novel optimization methods to accelerate distributed transaction processing into a geographically distributed database. The first optimization involves the parallelization of the write-ahead logging protocol. It allows multiple worker threads to synchronize log entries to the storage device simultaneously without any dependencies. The second optimization involves the grouped transfer of log entries from the leader to followers. This reduces the number of transmissions and effectively uses the network bandwidth. The third optimization involves the separation of the worker thread logic. By breaking the logic into the prepare phase and the commit phase, the worker threads at the leader node run asynchronously in parallel without waiting for responses from the follower nodes. The experimental results demonstrated that the proposed method achieved more than 10 million tps and less than 100 ms with client interactions through the network. The CPU utilization was almost 100%, which implied a dramatic reduction in synchronization in worker threads.

Access to Document (DOI)

Scalable distributed metadata server based on nonblocking transactions

Hiraga K., Tatebe O., Kawashima H.

Journal of Universal Computer Science （Journal of Universal Computer Science） 26 （ 1 ） 89 - 106 2020年

ISSN 0948695X

Metadata performance scalability is critically important in high-performance computing when accessing many small files from millions of clients. This paper proposes a design of a scalable distributed metadata server, PPMDS, for parallel file systems using multiple key-value servers. In PPMDS, hierarchical namespace of a file system is efficiently managed by multiple servers. Multiple entries can be atomically updated using a nonblocking distributed transaction based on an algorithm of dynamic software transactional memory. This paper also proposes optimizations to further improve the metadata performance by introducing a server-side transaction processing, multiple readers, and a shared lock mode, which reduce the number of remote procedure calls and prevent unnecessary blocking.Performance evaluation shows the scalable performance up to 3 servers, and achieves 62,000 operations per second, which is 2.58x performance improvement compared to a single metadata performance.

An analysis of concurrency control protocols for in-memory databases with ccbench

Tanabe T., Hoshino T., Kawashima H., Tatebe O.

Proceedings of the VLDB Endowment （Proceedings of the VLDB Endowment） 13 （ 13 ） 3531 - 3544 2020年

This paper presents yet another concurrency control analysis platform, CCBench. CCBench supports seven protocols (Silo, TicToc, MOCC, Cicada, SI, SI with latch-free SSN, 2PL) and seven versatile optimization methods and enables the configuration of seven workload parameters. We analyzed the protocols and optimization methods using various workload parameters and a thread count of 224. Previous studies focused on thread scalability and did not explore the space analyzed here. We classified the optimization methods on the basis of three performance factors: CPU cache, delay on conflict, and version lifetime. Analyses using CCBench and 224 threads, produced six insights. (I1) The performance of optimistic concurrency control protocol for a readonly workload rapidly degrades as cardinality increases even without L3 cache misses. (I2) Silo can outperform TicToc for some write-intensive workloads by using invisible reads optimization. (I3) The effectiveness of two approaches to coping with conflict (wait and no-wait) depends on the situation. (I4) OCC reads the same record two or more times if a concurrent transaction interruption occurs, which can improve performance. (I5) Mixing different implementations is inappropriate for deep analysis. (I6) Even a state-of-the-art garbage collection method cannot improve the performance of multi-version protocols if there is a single long transaction mixed into the workload. On the basis of I4, we defined the read phase extension optimization in which an artificial delay is added to the read phase. On the basis of I6, we defined the aggressive garbage collection optimization in which even visible versions are collected. The code for CCBench and all the data in this paper are available online at GitHub.

Access to Document (DOI)

An Analysis of Concurrency Control Protocols for In-Memory Databases with CCBench (Extended Version).

Takayuki Tanabe, Takashi Hoshino, Hideyuki Kawashima, Osamu Tatebe

abs/2009.11558 2020年

Accelerating Sequence Operator with Reduced Expression

Kawashima H., Tatebe O.

Frontiers in Artificial Intelligence and Applications （Frontiers in Artificial Intelligence and Applications） 321 71 - 82 2019年12月

ISSN 9781643680446

Sequence operators are effective for efficiently combining multiple events when state recognition is performed by combining time series events. Since sensor data are inherently noisy, one can take a strict attitude to deal with them: It is conceivable that all of time series events are regarded as false positives. Then, all complex events should be constructed carefully. Such an attitude is called the skip-till-any-match model in the sequence operator. When using this model, huge amounts of potential complex events are generated. A sequence operator usually supports both Kleene closure and non-Kleene closure. While efficient methods have been studied for Kleene closure so far, that for non-Kleene closure have been still explored. In this paper, we propose the reduced expression method to improve the efficiency of sequence operator processing for the skip-till-any-match model. Experimental results showed that the processing time and memory size were more efficient compared with SASE, which is the conventional method, and that degree is up to several thousand times.

Access to Document (DOI)

Skew-Aware Collective Communication for MapReduce Shuffling

Daikoku H., Kawashima H., Tatebe O.

Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018 （Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018） 3331 - 3340 2019年01月

ISSN 9781538650356

This paper proposes and examines the three in-memory shuffling methods designed to address problems in MapReduce shuffling caused by skewed data. Coupled Shuffle Architecture (CSA) employs a single pairwise all-to-all exchange to shuffle both blocks, units of shuffle transfer, and meta-blocks, which contain the metadata of corresponding blocks. Decoupled Shuffle Architecture (DSA) separates the shuffling of meta-blocks and blocks, and applies different all-to-all exchange algorithms to each shuffling process, attempting to mitigate the impact of stragglers in strongly skewed distributions. Decoupled Shuffle Architecture with Skew-Aware Meta-Shuffle (DSA w/ SMS) autonomously determines the proper placement of blocks based on the memory consumption of each worker process. This approach targets extremely skewed situations where some worker processes could exceed their node memory limitation. This study evaluates implementations of the three shuffling methods in our prototype in-memory MapReduce engine, which employs high performance interconnects such as InfiniBand and Intel Omni-Path. Our results suggest that DSA w/ SMS is the only viable solution for extremely skewed data distributions, but this solution is only valid on systems equipped with high performance interconnects. We also present a detailed investigation of the performance of CSA and DSA in various skew situations.

Access to Document (DOI)

Skew-aware collective communication for MapReduce shuffling

Daikoku H., Kawashima H., Tatebe O.

IEICE Transactions on Information and Systems （IEICE Transactions on Information and Systems） E102D （ 12 ） 2389 - 2399 2019年

ISSN 09168532

This paper proposes and examines the three in-memory shuffling methods designed to address problems in MapReduce shuffling caused by skewed data. Coupled Shuffle Architecture (CSA) employs a single pairwise all-to-all exchange to shuffle both blocks, units of shuffle transfer, and meta-blocks, which contain the metadata of corresponding blocks. Decoupled Shuffle Architecture (DSA) separates the shuffling of meta-blocks and blocks, and applies different all-to-all exchange algorithms to each shuffling process, attempting to mitigate the impact of stragglers in strongly skewed distributions. Decoupled Shuffle Architecture with Skew-Aware Meta-Shuffle (DSA w/ SMS) autonomously determines the proper placement of blocks based on the memory consumption of each worker process. This approach targets extremely skewed situations where some worker processes could exceed their node memory limitation. This study evaluates implementations of the three shuffling methods in our prototype in-memory MapReduce engine, which employs high performance interconnects such as InfiniBand and Intel Omni-Path. Our results suggest that DSA w/ SMS is the only viable solution for extremely skewed data distributions. We also present a detailed investigation of the performance of CSA and DSA in various skew situations.

Access to Document (DOI)

Integration of TicToc Concurrency Control Protocol with Parallel Write Ahead Logging Protocol.

Yasuhiro Nakamura, Hideyuki Kawashima, Osamu Tatebe

9 （ 2 ） 339 - 353 2019年

InvisibleWriteRule: the sufficient condition for safely omittable write operations in concurrency control.

Sho Nakazono, Hiroyuki Uchiyama, Yasuhiro Fujiwara, Yasuhiro Nakamura, Hideyuki Kawashima

abs/1904.08119 2019年

Integrating tictoc with parallel logging

Nakamura Y., Kawashima H., Tatebe O.

Proceedings - 2018 6th International Symposium on Computing and Networking Workshops, CANDARW 2018 （Proceedings - 2018 6th International Symposium on Computing and Networking Workshops, CANDARW 2018） 105 - 111 2018年12月

ISSN 9781538691847

A transactional system consists of a concurrency control system and a recovery system. TicToc is one of the state of the art concurrency control protocols today, but it lacks recovery system. We studied the ways to integrate TicToc and recovery system. For efficiency, we adopted a parallel write ahead logging scheme for the recovery system. There are two methods to optimize the logging. First method is early lock release which executes lock release early on data objects. Second method is group commit which executes batched logs transfer to storage from memory. We integrated a transactional system consisted by TicToc and P-WAL logging system assuming non-volatile memory. We found that the two optimization methods incur performance degradation when storage access latency is equivalent to that of NVRAM.

Access to Document (DOI)

PPMDS: A Distributed Metadata Server Based on Nonblocking Transactions

Hiraga K., Tatebe O., Kawashima H.

2018 5th International Conference on Social Networks Analysis, Management and Security, SNAMS 2018 （2018 5th International Conference on Social Networks Analysis, Management and Security, SNAMS 2018） 202 - 208 2018年11月

ISSN 9781538695883

There is a critical problem of metadata performance scalability in high-performance computing when accessing many small files from millions of clients. This paper proposes a design of PPMDS, a scalable distributed metadata server, to improve metadata performance and scalability. To efficiently manage hierarchical namespace of file system across multiple servers, it manages inode entries using a parent inode number and an entry name as a key. To update multiple inode entries atomically, it uses a nonblocking distributed transaction based on an algorithm of dynamic software transactional memory. It improves the metadata performance by introducing server-side transaction processing, multi-reader, and a shared lock mode to reduce the number of remote procedure calls and to prevent unnecessary blocking. A prototype implementation achieves 62,000 operations per second when creating files in a single directory using 8 metadata servers, which is 2.58x performance improvement compared to a single metadata performance.

Access to Document (DOI)

Applying Pwrake Workflow System and Gfarm File System to Telescope Data Processing

Tanaka M., Tatebe O., Kawashima H.

Proceedings - IEEE International Conference on Cluster Computing, ICCC （Proceedings - IEEE International Conference on Cluster Computing, ICCC） 2018-September 124 - 133 2018年10月

ISSN 9781538683194

In this paper, we describe a use case applying a scientific workflow system and a distributed file system to improve the performance of telescope data processing. The application is pipeline processing of data generated by Hyper Suprime-Cam (HSC) which is a focal plane camera mounted on the Subaru telescope. In this paper, we focus on the scalability of parallel I/O and core utilization. The IBM Spectrum Scale (GPFS) used for actual operation has a limit on scalability due to the configuration using storage servers. Therefore, we introduce the Gfarm file system which uses the storage of the worker node for parallel I/O performance. To improve core utilization, we introduce the Pwrake workflow system instead of the parallel processing framework developed for the HSC pipeline. Descriptions of task dependencies are necessary to further improve core utilization by overlapping different types of tasks. We discuss the usefulness of the workflow description language with the function of scripting language for defining complex task dependency. In the experiment, the performance of the pipeline is evaluated using a quarter of the observation data per night (input files: 80 GB, output files: 1.2 TB). Measurements on strong scaling from 48 to 576 cores show that the processing with Gfarm file system is more scalable than that with GPFS. Measurement using 576 cores shows that our method improves the processing speed of the pipeline by 2.2 times compared with the method used in actual operation.

Access to Document (DOI)

Integration of parallel write ahead logging and cicada concurrency control method

Tanabe T., Kawashima H., Tatebe O.

Proceedings - 2018 IEEE International Conference on Smart Computing, SMARTCOMP 2018 （Proceedings - 2018 IEEE International Conference on Smart Computing, SMARTCOMP 2018） 291 - 296 2018年07月

ISSN 9781538647059

We proposed the idea of combining the Cicada concurrency control mechanism with P-WAL (parallel write-Ahead logging) and experimentally evaluated the proposed control mechanism. Our results show that P-WAL can be combined suitably with Cicada without decreasing Cicada's performance. We then experimentally evaluated the most optimal parallel write-Ahead logging parameter among (1) conservative lock release; (2) early lock release, the early release of locks on database objects; and (3) group commit, which writes the transaction log to storage all at once. The results show that early lock release and group commit were the most optimal parameters for the combination of Cicada and P-WAL.

Access to Document (DOI)

Performing external join operator on PostgreSQL with data transfer approach

Takizawa R., Kawashima H., Mitsuhashi R., Tatebe O.

ACM International Conference Proceeding Series （ACM International Conference Proceeding Series） 271 - 277 2018年01月

ISSN 9781450353724

With the development of sensing devices, the size of data managed by human being has been rapidly increasing. To manage such huge data, relational database management system (RDBMS) plays a key role. RDBMS models the real world data as n-ary relational tables. Join operator is one of the most important relational operators, and its acceleration has been studied widely and deeply. How can an RDBMS provide such an efficient join operator? The performance improvement of join operator has been deeply studied for a decade, and many techniques are proposed already. The problem that we face is how to actually use such excellent techniques in real RDBMSs. We propose to implement an efficient join technique by the data transfer approach. The approach makes a hook point inside an RDBMS internal, and pulls data streams from the operator pipeline in the RDBMS, and applies our original join operator to the data, and finally returns the result to the operator pipeline in the RDBMS. The result of the experiment showed that our proposed method achieved 1.42x speedup compared with PostgreSQL. Our code is available on GitHub.

Access to Document (DOI)

　前のページ - 次のページ　

川島 英之

論文 - 川島 英之

川島　英之

論文 - 川島　英之