주기억장치 데이터베이스를 위한 동시성 제어 관리자의 설계 및 구현

김상욱,장연정,김윤호,김진호,이승선,최완,Kim, Sang-Wook,Jang, Yeon-Jeong,Kim, Yun-Ho,Kim, Jin-Ho,Lee, Seung-Sun,Choi, Wan 한국통신학회 2000 韓國通信學會論文誌 Vol.25 No.4

본 논문에서는 주기억장치 DBMS(main memory DBMS: MMDBMS)를 위한 동시성 제어 관리자의 설계 및 구현에 관하여 논의한다. MMDBMS는 디스크 기반 DBMS와는 달리 주기억장치 액세스만으로 데이터 검색 및 갱신을 수행하므로 전체 수행 비용 중 동시성 제어 관리자의 수행 비용이 차지하는 비중은 매우 크다. 따라서 효율적인 동시성 제어 관리자의 개발은 MMDBMS의 성능에 큰 영향을 미치게 된다. 본 연구에서 개발된 동시성 제어 관리자는 이단계 라킹 규약을 기반으로 하며, 다음과 같은 특징을 갖는다. 첫째, 락의 단위를 주기억장치의 물리적인 할당 단위인 파티션으로 설정함으로써 응용 분야의 특성 분석을 통하여 동시성과 락 관리 비용을 유연하게 조정할 수 있다. 둘째, 락에 관한 정보를 파티션 내부에서 직접 관리함으로써 락 관리 비용을 크게 줄일 수 있다. 셋째, 시스템 데이터의 물리적 일관성 유지를 위한 수단으로서 래치를 제공한다. 개발된 래치는 공유 모드와 배제 모드를 모두 지원하며, CPU 이용률의 극대화를 위하여 Bakery 알고리즘과 Unix의 세마포어 기능을 결합하는 방법을 사용한다. 넷째, 락에 의한 교착 상태의 해결을 위하여 락 대기 정보를 기반으로 시스템의 교착 상태 여부를 주기적으로 검출하는 기능을 제공한다. 본 논문에서는 트랜잭션 테이블의 상호배제, 인덱스 혹은 시스템 카탈로그의 상호 배제, 실시간 응용의 지원 등 실제 구현에서 발생하는 중요한 이슈들에 관해서도 이울러 논의한다. In this paper, we discuss the design and implementation of a concurrency control manager for a main memory DBMS(MMDBMS). Since an MMDBMS, unlike a disk-based DBMS, performs all of data update or retrieval operations by accessing main memory only, the portion of the cost for concurrency control in the total cost for a data update or retrieval is fairly high. Thus, the development of an efficient concurrency control manager highly accelerates the performance of the entire system. Our concurrency control manager employs the 2-phase locking protocol, and has the following characteristics. First, it adapts the partition, an allocation unit of main memory, as a locking granule, and thus, effectively adjusts the trade-off between the system concurrency and locking cost through the analysis of applications. Second, it enjoys low locking costs by maintaining the lock information directly in the partition itself. Third, it provides the latch as a mechanism for physical consistency of system data. Our latch supports both of the shared and exclusive modes, and maximizes the CPU utilization by combining the Bakery algorithm and Unix semaphore facility. Fourth, for solving the deadlock problem, it periodically examines whether a system is in a deadlock state using lock waiting information. In addition, we discuss various issues arising in development such as mutual exclusion of a transaction table, mutual exclusion of indexes and system catalogs, and realtime application supports.

데이타베이스 관리 시스템에서 대화식 UNDO를 지원하는 회복 기법

김상욱,김장수(Won-Young Kim),김원영,황규영,Kyu-Young Whang,Sang-Wook Kim,Jang-Su Kim 한국정보과학회 1999 정보과학회논문지(B) Vol.26 No.1

User-interactive undo is a kind of recovery facility that allows users to correct easily mistakes by canceling and reexecuting already executed operations. Supporting user-interactive undo is essential for authoring processes in new database applications such as software engineering, hypermedia, and computer aided design. A partial rollback using savepoints supported by commercial database management systems(DBMSs), which allows only cancellation of already executed operations, is a restricted from of user-interactive undo. Although many applications use DBMSs, they have to provide user-interactive undo by themselves due to lack of support from the DBMSs. Since implementation of the user-interactive undo is Quite complex, it poses significant burden to application programmers. This paper proposes a new recovery method facilitating user-interactive undo in DBMSs. Such a facility relieves the programmers from implementing user-interactive undo themselves in developing DBMS applications. The method guarantees fast rollback of transactions that contain user-interactive undos. It also provides users with the bulk undo operation that restores the database to a predefined point in the past. The bulk undo operation resembles partial rollback, but differs m that it allows redo that cancels bulk undo. Moreover, the performance of the method is comparable to that of the traditional recovery method in spite of added functionalities. 대화식 UNDO는 수행된 연산을 철회시키거나 재실행시킴으로써 사용자의 오류를 쉽게 교정할 수 있도록 허용하기 위한 일종의 회복 기능이다. 소프트웨어 개발, 하이퍼미디어, CAD 등과 같은 새로운 데이타베이스 응용 분야에서는 편리한 저작 및 편집 과정을 위하여 대화식 UNDO 기능의 지원이 필수적이다. 상용 DBMS들이 제공하는 세이브포인트를 이용한 부분 철회는 수행된 연산의 철회만을 허용하는 것으로 대화식 UNDO의 제한적 기능이다. 기존의 응용 시스템들은 데이타 관리를 위해서는 DBMS를 사용하면서도 이러한 대화식 UNDO 기능은 응용 시스템에서 직접 제공하고 있다. 대화식 UNDO 기능의 구현은 매우 복잡하기 때문에 응용 프로그래머에게 상당한 개발 오버헤드를 요구한다. 본 연구의 목적은 다양한 응용 시스템 개발을 위하여 공통적으로 필요한 고급 기능을 응용 프로그래머가 쉽게 이용할 수 있도록 대화식 UNDO 기능을 DBMS에서 직접 지원하는 새로운 회복 기법을 제안하는 것이다. 제안된 기법에서는 트랜잭션 철회시 대화식 UNDO에 의해 UNDO된 연산들을 스킵함로써 빠른 철회를 보장하고 여러 연산을 한번에 철회할 수 있는 벌크 UNDO 연산(bulk undo)을 제공한다. 벌크 UNDO 연산은 기록된 시점으로 철회한다는 점에서 기존의 부분 철회와 유사하지만 벌크 UNDO된 연산들도 다시 재실행될 수 있다는 점에서 부분 철회와 구별된다. 특히, 일반 DBMS에서 회복을 위하여 관리해야 하는 정보를 최대한 활용함으로써 새로운 기능의 추가에도 불구하고 제안된 기법의 성능은 이러한 기능을 제공하지 않는 기존의 회복 기법과 비교할만한 좋은 성능을 보인다.

산화·환원법에 의한 폐텅스텐 스크랩의 재활용에 관한 기초연구

김상욱,윤지석,김태욱,조봉휘,김인호,김상무,송창빈,Kim, Sang-Uk,Yun, Ji-seok,Kim, Tae-Wook,Cho, Bong-Hwi,Kim, In-Ho,Kim, Sang-Mu,Song, Chang-Bin 한국분말야금학회 2017 한국분말재료학회지 (KPMI) Vol.24 No.1

This study is carried out to obtain basic data regarding oxidation and reduction reactions, originated on the recycling of waste tungsten hard scraps by oxidation and reduction processes. First, it is estimated that the theoretical Gibbs free energy for the formation reaction of $WO_2$ and $WO_3$ are calculated as ${\Delta}G_{1,000K}=-407.335kJ/mol$ and ${\Delta}G_{1,000K}=-585.679kJ/mol$, from the thermodynamics data reported by Ihsan Barin. In the experiments, the oxidation of pure tungsten rod by oxygen is carried out over a temperature range of $700-1,000^{\circ}C$ for 1 h, and it is possible to conclude that the oxidation reaction can be represented by a relatively linear relationship. Second, the reduction of $WO_2$ and $WO_3$ powder by hydrogen is also calculated from the same thermodynamics data, and it can be found that it was difficult for the reduction reaction to occur at $1,027^{\circ}C$, in the case of $WO_2$, but it can happen for temperatures higher than $1127^{\circ}C$. On the other hand, $WO_3$ reduction reaction occurs at the relatively low temperature of $827^{\circ}C$. Based on these results, the reduction experiments are carried out at a temperature range of $500-1,000^{\circ}C$ for 15 min to 4 h, in the case of $WO_3$ powder, and it is possible to conclude that the reduction at $900^{\circ}C$ for 2h is needed for a perfect reduction reaction.

주기억장치 DBMS를 위한 인덱스 관리자의 설계 및 구현

김상욱,염상민,김윤호,이승선,최완,Kim, Sang-Wook,Yeom, Sang-Min,Kim, Yun-Ho,Lee, Seung-Sun,Choi, Wan 한국통신학회 2000 韓國通信學會論文誌 Vol.25 No.4

The main memory DBMS(MMDBMS) efficiently supports various database applications that require high performance since it employs main memory rather than disk as a primary storage. In this paper, we discuss theexperiences obtained in developing the index manager of the Tachyon, a next-generation MMDBMS. The indexmanager is an essential sub-component of the DBMS used to speed up the retrieval of objects from a largevolume of a database in response to a certain search condition. Previous research efforts on indexing proposed various index structures. However, they hardly dealt with the practical issues occured in implementating an index manager on a target DBMS. In this paper, we touch these issues and present our experiences in developing the index manager on the Tachyon as solutions. The main issues touched are (1) compact representation of an indexentry, (2) support of variable-length keys, (3) support of multiple-attribute keys, (4) support of duplicated keys,(5) definition of external APls, (6) concurrency control, and (7) backup and recovery. We believe that ourcontribution would help MMDBMS developers highly reduce their trial-and-errors. 주기억장치 DBMS(MMDBMS)는 디스크가 아닌 주기억장치를 주요 저장 매체로서 사용하므로 고속의 처리를 요구하는 다양한 데이터베이스 응용을 효과적으로 지원한다. 본 논문에서는 차세대 MMDBMS Tachyon의 인덱스 관리자 개발에 관하여 논의한다. 인덱스 관리자는 객체에 대한 빠른 검색 기능을 지원하는 필수적인 DBMS 서브 컴포넌트이다. 기존의 연구 결과로서 다양한 인덱스 구조가 제안된 바 있으나, 실제 DBMS 상에서 인덱스 관리자를 개발하는 경우에 발생하는 실질적인 이슈들에 대해서는 거의 언급하고 있지 않다. 본 논문에서는 Tachyon의 인덱스 관리자의 개발 중에 경험한 실질적인 구현 이슈들을 언급하고, 이들에 대한 해결 방안을 제시한다. 본 논문에서 다루는 주요 이슈들은 (1) 인덱스 엔트리의 집약적 표헌, (2) 가변 길이 키의 지원, (3) 다중 애트리뷰트 키의 지원, (4) 중복 키의 지원, (5) 외부 API의 정의, (6) 동시성 제어, (7) 백업 및 회복 등이다. 본 연구 결과를 통하여 향후 MMDBMS 개발자들의 시행 착오를 최소화할 수 있으리라 생각된다.

B⁺ 트리를 위한 벌크 로드

김상욱,황환규,Kim, Sang-Wook,Whang, Whan-Kyu 강원대학교 산업기술연구소 1995 産業技術硏究 Vol.15 No.-

In this paper, we propose a bulk-load algorithm for $B^+-trees$, the most widely used index structures in database systems. The main characteristic of our algorithm is to simultaneously process all the keys to be placed on each $B^+-trees$ page when accessing the page. This avoids the overhead for accessing the same page multiple times, which results from applying the $B^+-trees$ insertion algorithm repeatedly. For performance evaluation, we analyze our algorithm in terms of the number of disk accesses. The results show that the number of disk accesses excluding those in the redistribution process in identical to the number of $B^+-trees$ pages. Considering that the redistribution process is an unavoidable preprocessing step for bulk-loading, our algorithm requires just one disk access per $B^+-trees$ page, and therefore turns out to be optimal. We also present performance tendancy according to the changes of parameter values via simulation.

위상수학의 시조 Euler

김상욱,이승온,Kim, Sang-Wook,Lee, Seung-On 한국수학사학회 2006 Journal for history of mathematics Vol.19 No.1

Topology began to be studied relatively later than the other branches of mathematics, such as geometry, algebra and analysis. Leonhard Euler is generally considered to be the founder of topology. In this paper we first investigate the beginning of topology and its development and then study Euler's life and his achievements in mathematics. 위상수학은 기하학, 대수학, 해석학 등 수학의 다른 분야에 비하여 비교적 늦게 연구되기 시작하였고 Euler는 위상수학의 시조로 알려져 있다. 우리는 먼저 위상수학의 기원과 발달에 대해 살피고 Euler의 삶과 업적에 대해 알아본다.

지식 창조 플랫폼으로서의 소셜미디어 관리모델 설계를 위한 탐색 연구

김상욱,Kim, Sang Wook 한국산업정보학회 2012 한국산업정보학회논문지 Vol.17 No.7

소셜미디어(Social Media)는 최근 집단지성 형성의 새로운 매체로 주목을 받고 있다. 이에 본 연구는 소셜미디어의 사회적 함의를 규명하고 그에 근거하여 지식 창조 플랫폼(Knowledge Creation Platform)으로서의 소셜미디어 관리를 위한 개념적 틀을 탐색 차원에서 제시하고자 하였다. 소셜미디어를 통한 정보 소통은 문자 그대로 범사회적 영향을 끼치는 공공성이 강하기 때문에 민간 기업뿐만 아니라 정부를 비롯한 각급 공공기관에서도 홍보, 크라우드 소싱(Crowd Sourcing) 등 다양한 용도로 그 활용방안을 모색하고 있다. 특히 빅데이터(Big Data) 시대와 맞물리면서 소셜미디어가 사회적 지식창조 플랫폼으로서의 가능성을 열고 있다는 측면에서 볼 때 본 연구에서 제시하는 소셜미디어 관리를 위한 개념적 틀은 향후 지식창조 플랫폼으로서의 소셜미디어 관리모델을 구체화하는데 중요한 단서와 기본방향을 제시할 수 있을 것으로 기대된다. Much attention is being paid to social media because of their potentials to draw collective intelligence. In this context does this study attempt to draw some implications of social media as knowledge creation platform and suggest a conceptual framework of social media management. Information sharing among the public through social media literally produces profound influence throughout the society and thus not only business firms but all levels of public institutions, including government are seeking to take its advantage for various purposes such as public relations, crowd sourcing, etc. Especially considering that social media open the possibility of social knowledge creation platform in the Big Data era, this study is perhaps able to contribute to further development of social media management model together with a series of measuring indexes.

나카가미 페이딩 채널하에서 멀티톤 재밍을 고려한 FH MC/DS CDMA 시스템의 성능분석

김상욱,박진수,Kim Sang-Wook,Park Jin-Soo 한국정보통신학회 2005 한국정보통신학회논문지 Vol.9 No.4

본 논문에서는 Multi-Carrier 방식중의 하나인 MC DS/CDMA 방식과 대역확산 방식중의 하나인 주파수 호핑 방식을 결합한 FH MC-DS CDMA 시스템에서 SFH와 FFH를 적용하여 나카가미 페이딩 채널 하에서 멀티톤 재밍을 고려하여 시스템의 BER 성능을 비교 $\cdot$ 분석하였다. 호핑 횟수가 증가된다는 것은 주파수 다이버시티의 효과를 얻을 수 있게 되어 수신측의 부담을 줄이면서 FH MC DS/CDMA 시스템의 BER 성능을향상 시킬 수 있다는 것을 의미한다. 따라서 호핑 횟수를 증가시킴으로써 FH MC/DS CDMA 시스템의 성능을 개선할 수 있음을 입증하였다. In this paper, it was estimated the BER performance of the individual system type by applying the SFH type and the FFH type to the FH MC-DS CDMA system that combined the strong points of MC DS/CDMA and that of Frequency Mewing under the Nakagami fading channel with Multi-tone Jamming. An increase in the number of hoppings means that it can improve theBER performance by reducing the receiving burden of the FH MC DS/CDMA by achieving a frequency diversity effect. Therefore, I verified that the performances of the FH MC DS/CBMA system could be impoved by increasing the number of hoppings.

주기억장치 DBMS를 위한 고성능 인덱스 관리자의 설계 및 구현

김상욱,이경태,최완,Kim, Sang-Wook,Lee, Kyung-Tae,Choi, Wan 한국통신학회 2003 韓國通信學會論文誌 Vol.28 No.7B

주기억장치 DBMS(MMDBMS)는 디스크가 아닌 주기억장치를 주요 저장 매체로서 사용하므로 고속의 처리를 요구하는 다양한 데이터베이스 응용을 효과적으로 지원한다. 본 논문에서는 차세대 MMDBMS Tachyon의 인덱스 관리자 개발에 관하여 논의한다. 최근 하드웨어의 급격한 발전으로 인하여 주기억장치 액세스 속도와 CPU의 처리 속도의 차는 점점 커지고 있다. 따라서 CPU 내에 있는 캐쉬(cache)의 존재를 충분히 활용하는 자료 구조 및 알고리즘을 고안함으로써 MMDBMS의 성능을 크게 개선시킬 수 있다. 본 논문에서는 Tachyon를 위한 캐쉬-인지 인덱스 관리자의 개발 중에 경험한 실질적인 구현 이슈들을 언급하고, 이들에 대한 해결 방안을 제시한다. 본 논문에서 다루는 주요 이슈들은 (1) 캐쉬(cache)의 효과적인 사용, (2)인덱스 엔트리 및 인덱스 노드의 집약적 표현(compact representation). (3) 가변 길이 키(variable-length key)의 지원, (4) 다중 애트리뷰트 키(multiple-attribute key)의 지원, (5) 중복키(duplicated key)의 지원. (6) 인덱스를 위한 시스템 카탈로그의 정의. (7) 외부 API(application programming interface)의 정의. (8) 효과적인 동시성 제어 방안. (9) 효율적인 백업 및 회복 방안 등이다. 또한, 다양한 실험을 통한 성능 분석을 통하여 제안된 인덱스 관리자의 우수성을 규명한다. The main memory DBMS(MMDBMS) efficiently supports various database applications that require high performance since it employs main memory rather than disk as a primary storage. In this paper, we discuss the index manager of the Tachyon, a next-generation MMDBMS. Recently, the gap between the CPU processing and main memory access times is becoming much wider due to rapid advance of CPU technology. By devising data structures and algorithms that utilize the behavior of the cache in CPU, we are able to enhance the overall performance of MMDBMSs considerably. In this paper, we address the practical implementation issues and our solutions for them obtained in developing the cache-conscious index manager of the Tachyon. The main issues touched are (1) consideration of the cache behavior, (2) compact representation of the index entry and the index node, (3) support of variable-length keys, (4) support of multiple-attribute keys, (5) support of duplicated keys, (6) definition of the system catalog for indexes, (7) definition of external APIs, (8) concurrency control, and (9) backup and recovery. We also show the effectiveness of our approach through extensive experiments.

주기억장치 데이타베이스에서 교착 상태의 검출을 위한 락 대기 정보의 효과적인 상호 배제 기법

김상욱,이승선,최완,Kim, Sang-Wook,Lee, Seung-Sun,Choi, Wan 한국통신학회 1999 韓國通信學會論文誌 Vol.24 No.7

이단계 라킹 규약은 다수의 트랜잭션들의 수행이 병행되는 데이터베이스 환경에서 데이터의 논리적인 일관성을 보장하기 위하여 널리 사용되는 동시성 제어 기법이다. 이단계 라킹 규약을 사용하는 시스템에서는 두 개 이상의 트랜잭션들이 락을 잡은 상태를 서로 다른 트랜잭션이 가진 락을 무한정으로 상호 대기하는 교착 상태가 발생할 수 있다. 교착 상태 검출기는 트랜잭션들 간의 락 대기 정보를 기반으로 시스템 내에 교착 상태가 발생하였는가를 주기적으로 검출하는 기능을 제공한다. 데이터베이스 시스템에서는 트랜잭션들과 교착 상태 검출기의 수행이 병행되며, 이들은 각각의 수행을 위하여 락 대기 정보를 공통으로 읽고 쓰게 된다. 이와 같이, 락 대기 정보는 공유 정보에 해당되므로 상호 배제 기법을 이용한 락 대기 정보의 물리적 일관성을 보장하는 기법이 요구된다. 특히, 고성능의 주기억장치 데이타베이스에서는 이러한 상호 배제 기법의 성능이 전체 시스템에 큰 영향을 미치게 되므로 효율적인 상호 배제 기법은 매우 중요하다. 본 연구에서는 락 대기 정보의 물리적 일관성을 효과적으로 보장하는 새로운 상호 배제 기법을 제안한다. 제안\ulcorner는 기법은 상호 배제를 위한 처리 오버헤드를 극소화하고, 전체 시스템의 동시성을 극대화하는 것을 주요 목표로 한다. The two-phase locking protocol(2PL) is the most widely-used concurrency control mechanism for guaranteeing logical consistency of data in a database environment where a number of transactions perform concurrently. The problem inherent in the 2PL protocol is a deadlock, where a set of transactions holding some locks indefinitely wait an additional lock that is already held by other transactions in the set. The deadlock detector is a DBMS sub-component that examines periodically whether a system is in a deadlock state based on lock waiting information of transactions. The deadlock detector and transactions execute concurrently in a DBMS and read and/or write the lock waiting information simultaneously. Since the lock waiting information is a shared one, we need an efficient method guaranteeing its physical consistency by using mutual exclusion. The efficiency of the mutual exclusion method is crucial especially in a main memory DBMS with high performance since it seriously affects the performance of an entire system. In this paper, we propose a new method that effectively guarantees physical consistency of lock waiting information. Two primary goals of our method are to minimize the processing overhead and to maximize system concurrency.