Multics Technical Bulletin MTB-528 DM: Plan To: Distribution From: André Bensoussan Date: 06/10/81 Subject: Multics Data Management Plan 1 ABSTRACT This memo describes our plan to improve the data management facility in Multics. It includes the work to be done at CISL and in Phoenix during the next three years, with emphasis on what should be done in the MR10 time frame. The memo contains the following parts: o MR10 Features o MR11 Features o Reviews I and II o Schedule o Manpower Estimate o Potential Problems Comments should be sent to the author: via Multics Mail: Bensoussan.Multics on System M. via US Mail: André Bensoussan Honeywell Information Systems, Inc. 4 Cambridge Center Cambridge, Massachusetts 02142 via telephone: (HVN) 261-9334, or (617) 492-9334 _________________________________________________________________ Multics project internal working documentation. Not to be reproduced or distributed outside the Multics project without the consent of the author or the author's management. Page i. CONTENTS Page 1 Abstract . . . . . . . . . . . . . . i 2 MR10 Features . . . . . . . . . . . 1 2.1 Data Management Transaction . . 1 2.2 Recovery . . . . . . . . . . . 1 2.3 Concurrency . . . . . . . . . . 2 2.4 Limitations . . . . . . . . . . 2 2.5 Performance . . . . . . . . . . 2 3 MR11 Features . . . . . . . . . . . 4 3.1 Checkpoint . . . . . . . . . . 4 3.2 Capacity . . . . . . . . . . . 4 3.3 Security . . . . . . . . . . . 4 3.4 Administrative Services . . . . 4 4 Technical Reviews . . . . . . . . . 5 4.1 Review I -- End of April . . . 5 4.2 Review II -- End of October . . 6 5 Schedule . . . . . . . . . . . . . . 7 6 Manpower Estimate . . . . . . . . . 8 6.1 Work to be done at CISL for MR10 (Starting Jan 1, 1981) . . . 8 6.2 Work to be done by the MRDS group for MR10 . . . . . . . . . . 9 7 Potential Problems . . . . . . . . . 10 iii Multics Technical Bulletin MTB-528 DM: Plan 2 MR10 FEATURES The following features are planned to be provided in the MR10 time frame: o Transaction for data management o Recovery o Concurrency o Relaxation of Some Current Limitations o Performance Improvement 2.1 Data Management Transaction o A transaction is the basic unit of data base consistency. o It is basic to our definition of recovery and concurrency. o Primitives to begin, commit, and abort a transaction will be provided. 2.2 Recovery o Non-catastrophic failures: The system can undo any uncommitted transaction by performing a "rollback" using the Before Image Journal. o Catastrophic failures: The system can redo all committed transactions starting with the last saved version of the data base and redoing all modifications recorded in the After Image Journal. The work involved in providing recovery is very significant, as it requires not only implementing recovery modules that are currently non-existent but also making drastic changes to many existing parts of the current data management system. These changes are necessary in order to enforce the journalization protocol on which our method for recovery is predicated. The list of modules to be created or modified is as follows: o Before Image Journal Manager o After Image Journal Manager o Saved Data Base Manager o Page File Manager (with get/put interface) o vfile Total Replacement by - Index Manager - Record Manger - Tuple Manager Page 1. MTB-528 Multics Technical Bulletin DM: Plan o MRDS: Must be changed to use the tuple, index and record managers instead of vfile. o Converrsion program to convert old data bases into new 2.3 Concurrency o Transactions will be allowed to execute concurrently but will be prevented from interfering with one another. o Automatic physical locking at the control interval level has been chosen because of its simplicity and because it has been proven to be a satisfactory implementation in the GCOS system. o Deadlock detection. The work involved in providing concurrency control is as follows: o Provide lock and unlock primitives o Implement read locks and write locks o Implement intention locks for hierarchical locking o Perform deadlock detection o Release all locks at the end of the transaction 2.4 Limitations o Some limitations currently introduced by vfile and/or MRDS will be relaxed to become acceptable. The most important of these limitations are: - Maximum number of relations per data base - Maximum number of tuples per relation - Maximum number of attributes per model Maximum number of data base openings o It will require making a change to the PL/I compiler to accept more than 64 arguments in a call. o The capacity limitations introduced by MSF's will still be present and will be removed in MR11 when "large files" are implemented. 2.5 Performance o CPU time -- The global data management package, including MRDS, tuple, index, record and page file managers, must be Page 2. Multics Technical Bulletin MTB-528 DM: Plan five times faster than in MR6.5, in virtual CPU time. o I/O's -- A simple update should take less than 5 I/O's on data base pages and control structures. A simple update is defined here as a tuple modification, with no index modification, starting with the tuple identifier. Page 3. MTB-528 Multics Technical Bulletin DM: Plan 3 MR11 FEATURES The following features are planned to be provided in the MR11 time frame: 3.1 Checkpoint After a non-catastrophic failure, the system can partially undo an uncommitted transaction up to its last checkpoint. After a catastrophic failure, the system can partially redo an uncommitted transaction up to its last checkpoint. 3.2 Capacity Multi-Segment Files will be replaced by non-segmented files, also known as "large files," to be able to support very large data bases (50 to 100 billion bytes). 3.3 Security MRDS will be made secure by being moved into a lower ring, in order to provide attribute level security. The difficulty of moving MRDS into a lower ring has not been well evaluated yet, and a further investigation is necessary before making a commitment to our users. We understand it is being run, with MRDS and system modifications, in a lower ring at AFDSC. 3.4 Administrative Services o Dynamic Restructuring and Relocation o Placement Control Page 4. Multics Technical Bulletin MTB-528 DM: Plan 4 TECHNICAL REVIEWS Two technical reviews will take place before coding begins. At these reviews, the plan for the entire project will be presented, with emphasis on what has to be done for MR10. 4.1 Review I -- End of April The following documents (MTBs) will be available for this review: o Evolution and History of MRDS o Data Management: Problem Statement o Goals o Medium Range Goals o Data Management Plan for MR10, MR11 o Data Management Architecture Overview o vfile Versus Its Replacement o Index Manager Overview o Record Manager Overview o Container Manager Overview o Page File Manager Overview o Transaction Manager Overview o Recovery Manager Overview o Concurrency Manager Overview o Conditions for Distributed Systems o MRDS Documents Page 5. MTB-528 Multics Technical Bulletin DM: Plan 4.2 Review II -- End of October The purpose of this review is to present in more detail the work to be done for MR10. The following documents will be available for this review: o Tuple Manager - Functional Specifications - Design and Implementation o Index Manager - Functional Specifications - Design and Implementation o Record Manager - Functional Specifications - Design and Implementation o Page File Manager - Functional Specifications - Design and Implementation o Transaction Manager - Functional Specifications - Design and Implementation o Recovery Manager - Functional Specifications - Design and Implementation o Lock Manager - Functional Specifications - Design and Implementation o Use of Control Intervals o MRDS Documents o Coding Schedule with Testing Dependencies o Integration and Migration Plan. o Documentation Plan Page 6. Multics Technical Bulletin MTB-528 DM: Plan 5 SCHEDULE DESIGN CODE DEB EXPOSURE <----------> <----------><---> <-------> | | | | | | | | | | | | | | | v v v v v |---|---|----|----|---|---|----|----|---|---|---|---|---|---|---|---| | | | | | | 81 | 82 | 83 | 84 | | | | | | |---|---|----|----|---|---|----|----|---|---|---|---|---|---|---|---| ^ ^ ^ ^ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ____|___ ___|____ ______________|_________ ____|______ |REVIEW| |REVIEW| | TRANSACTION | | LARGE | | I | | II | | RECOVERY | | FILES | |______| |______| | BIJ, AIJ, SAVE | | SECURITY | | PAGE FILE | | ADMIN. | | TUPLE | | SERVICES | | INDEX + RECORD | | CHECKPT. | | MRDS CHANGES | |__________| | DB CONVERSION | | CONCURRENCY | | LIMITATIONS | | PERFORMANCE | | USER DOCUMENT | |_______________________| Page 7. MTB-528 Multics Technical Bulletin DM: Plan 6 MANPOWER ESTIMATE 6.1 Work to be done at CISL for MR10 (Starting Jan 1, 1981) Overv. Code Debug User Total Funct. Doc. Spec. Design m/m m/m m/m m/m m/m DM Architecture 2 2 Page File Mgt. 1 1 1 1 4 Tuple Mgt. 2 2 2 1 7 Index Mgt. 3 6 2 2 13 Record Mgt. 1 4 1 1 7 Transaction Mgt. 2 2 2 1 7 Before Journal Mgt. 2 6 3 1 12 After Journal Mgt. 2 6 3 1 12 Save DB Mgt. 2 6 3 1 12 Lock Mgt. 2 2 2 1 7 Tape for After Journal 3 Integration 6 Reviews, Prepration, Response 5 ------ Total: 97 m/m or: 8.8 m/y Available resources: Six people, with different percentage of their time, are currently assigned to this project, averaging 4 full time persons. Page 8. Multics Technical Bulletin MTB-528 DM: Plan 6.2 Work to be done by the MRDS group for MR10 Adapt MRDS to use the Tuple Manager 12 m/m Participation in tuple mgr design 3 m/m Debugging and exposure 12 m/m ------- Total 27 m/m The detailed manpower allocation will be provided after MR9 is installed. The tuple manager specification must be available by the end of July 1981, in order to allow the MRDS group to start working on adapting MRDS to use it. Page 9. MTB-528 Multics Technical Bulletin DM: Plan 7 POTENTIAL PROBLEMS These are the most serious problems in the sense that their probability to occur is high and their impact is also high. o Problem: The work to be done may be underestimated. This is the largest project undertaken by the Multics project for many years. Action: Allow for a 25 to 30% margin of error in our manpower estimate. Have a plan to assign additional resources to compensate for this error if and when necessary. o Problem: Testing dependencies may stretch the real time. Action: Good pert chart. MTB on testing dependencies for Review II. o Problem: Debugging of concurrency, recovery, and capacity may be harder than expected. Action: Design test programs for each layer. We have a good level of confidence that we can accomplish what is planned in the MR10 time frame, provided that we manage to use all the manpower available effectively. The result of Review II will be a real measurement of how good our schedule and estimates are. Page 10.