多屬性動態醯序結構上協同控制方法的研究

Abstract

In order to minimize response time and maximize throughput, the database management system must support multiple users at the same time and allow multiple transactions to in parallel. Concurrency control is the activity of coordinating concurrent accesses to a database in a multiuser system so that the database consistency and integrity can be maintained. Agood concurrency control algorithm not only prevents harmful interference from asynchronous paralel user transactions, but also provides sufficient paralelism. Recently there have been many algorithms proposed to allow concurrent accesses on dynamic tree structures such as B7 tree. The studies of concurrent operations on dynamic hash structures, particularly in multi7 attribute structures, are rare. However, the multi7 attribute dynamic hash structures have wider applicability. In this report, we study and present algorithms for synchornizing concurrent operations in multi7 attributeextendible hashing and multi7 attribute linear, hashing, respective.y. We propose the algorithms by integrating the dynamic locking protocol with the principle of optimistic concurrency control technique. Moreover, these algorithms minimize synchronization overhead and enhance the degree of concurrency by combining the special locking system with the exploited semantics of the operations and the underlying data structures. The algorithm for multi7 attribute extendible hashing allows the search and partial7 match operations to proceed concurrently with insertion operations without having to acquire any locks. It also allows cnocurrent insertion/deletion operations to proceed without having to set locks on the directory entries. By reading and checking the content of directory entry repeatedly, the algorithm employs the notion of verification and guarantees a consistent view of the data structures. In addition to using a verification technique to retry when conflict occurs among concurrent operations, the algorithm of multi7 attribute linear hashing makes use of a strictly increasing counter to filter out a significant number of unnecessary retries, thus allowing partial7 match, search, insert and delete operations to proceed concurrently with split and merge operations. Furthermore, the search and partial7 match operations do not need to set any lock, and no operation needs to set locks on any file global variables, therefore enabling a higher degree of parallelism in the system. An argument for correctness based on the notion of weak consistency is also presented. Eventually, this report uses the random walk model in the probability theory to formalize the probability of false7 retry in our concurrency control algorithm of linear hashing. Based on the formalization, we can almost prune off all the probabilities of false7 retry by a minor modification of our algorithm. Moreover, the formalization and reduction of false7 retry triggers us to apply the random walk model to study another problem7 the performance analysis of stack space allocation. According to the studied results, the probability of stakc overflow can readily be determined after the stack space has been allocated. Therefore, it is possible to allocate suitable size to stacks, making their use more effective and efficient without wasting storage resources. 為了使回應時間降到最低以及使單位生產量提到最高，資料庫管理系統必須提供許多 使用者時使用，並且允許眾多的交易並行執行。而在多使用者的系統中，協同控制正 是用來協調各交易同時擷取資料庫的問題，以便能保持資料庫的一致性與正確性。因 此一個好的協同控制法不僅能防止各使用者間並行交易相互干擾所造成的傷害，並且 尚能提供充份的並行運算程度。 近年來，在動態樹狀結構上，如B7 tree ，提出了許多的協同控制法，而在動態醢序 結構上，其協同控制法的研究則很少。至於在多屬性醢序結構上，其協同控制法的研 究更是幾乎找不到。然而，多屬性醢序結構的應用層面卻更為廣泛。因此在本論文中 ，我們研究多屬性延展醢序及多屬性線性醢序的結構，並分別為其提出適當的協同控 制法。這些協同控制法結合了樂觀協同控制法的原則以及機動鎖定，外加對資料庫結 構及其運算語意的預先瞭解，因而能降低負荷且提高並行執行的程度。 在多屬性延展醢序上的協同控制法，允許搜尋以及部分匹配搜尋與插入運算同時進行 而不需任何鎖定。佗也准許插入以及去除運算同時進行而不需鎖定目錄。利用重覆讀 取以及檢查目錄，此方法亦能夠保證資料結構的一致性和正確性。 在多屬性線性醢序的協同控制法上，當並行運算間有了衝突時，除了使用驗證的技術 來重新嘗試外，它使用一個遞增的計數器把大部份不必要的嘗試給過濾掉而允許搜尋 ，部份匹配搜尋，插入以及去除運算能與分裂及結合運算同時進行。此外，搜尋以及 部份匹配搜尋運算不需任何鎖定，並且其他運算也不需對檔案的通用變數作鎖定，因 此此系能提供較高的並行程度。 最後，本論文使用機率理論上的隨步模式，將線性醢序上協同控制法的錯誤嘗試 正規化。根據此正規化的結果，我們僅需對此協同控制法作一微小的修改，即可幾乎 去除所有可能的錯誤嘗試。此外，此正規化與去除錯誤嘗試的經驗激發我們應用隨步 模式來研究另外一個問題──堆疊器空間分派的績效分析。根據此分析結果，一旦分 派空間給堆疊器後，其滿溢的機率便很容易決定。因此使得我們能夠分派適當大小的 空間給堆疊器並使堆疊器的運用更為有效而不會浪費儲存體的資源。