GNU/Linux Semantic Storage System

Informations

• Publié par: mtoledan
• Publié le: 24 juin 2011
• Nombre de lectures: 82
• Langue: English

Extrait

GNU/Linux Semantic Storage System Ahmed Salama, Ahmed Samih Amr Ramadan, Karim M. YousefContents Preface ix I Introduction 1 1 Introduction 3 1.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 What is the GNU/Linux Semantic Storage System? . . . . . . . . . 6 1.2.1 Rich Information . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.2 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.3 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.4 Developer Support . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Architecture 13 2.1 Client-Server Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.1 Daemon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.2 Web Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.3 API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.4 Pseudo File System . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Event Monitoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Request Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Type System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5 Browser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.6 Unicode Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 iii 2.7 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . 21 II Design 23 3 Data Model 25 3.1 Type System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.1.1 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.1.2 Stores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1.3 Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1.4 Importers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Persistent Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3 Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4 Event Monitoring 37 4.1 Kernel Notifications . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.2 Methodology of Monitoring . . . . . . . . . . . . . . . . . . . . . . 39 4.2.1 Watches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2.2 Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2.3 File System Events . . . . . . . . . . . . . . . . . . . . . . . 41 4.3 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3.1 Event Watcher Thread(s) . . . . . . . . . . . . . . . . . . . 41 4.3.2 Action Executor Thread . . . . . . . . . . . . . . . . . . . . 45 4.3.3 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . 46 5 Indexing and Searching 49 5.1 Information Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.1.1 Lucene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.2 Choosing an Information Retrieval Library . . . . . . . . . . . . . . 52 5.2.1 How Lucene Works . . . . . . . . . . . . . . . . . . . . . . . 52 5.2.2 Data organization in Lucene . . . . . . . . . . . . . . . . . . 53 5.3 Design Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.4 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.4.1 Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58iii 5.4.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 III Experimental Studies 65 6 Performance Analysis 67 6.1 Testing Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.2 Indexing Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.3 Searching Experiment . . . . . . . . . . . . . . . . . . . . . . . . . 70 Appendix 72 A GNU Free Documentation License 73 B Unicode 85ivList of Figures 2.1 Architecture of GLScube . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Path of a System Call on the FUSE glscubeFS . . . . . . . . . . . . 17 2.3 Propagation of a DataAccessRequest . . . . . . . . . . . . . . . . . 19 3.1 Inheritance in the Type System . . . . . . . . . . . . . . . . . . . . 27 3.2 Specializations of Documents . . . . . . . . . . . . . . . . . . . . . 28 3.3 Design diagram of the Importers submodule . . . . . . . . . . . . . 31 4.1 Design of the Event Monitoring module . . . . . . . . . . . . . . . . 42 5.1 Indexing submodule. . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.2 Flowchart of Adding a Document to the index . . . . . . . . . . . . 59 5.3 Flowchart of Deleting a Document from the index . . . . . . . . . . 64 6.1 ComparisonoftheAverageUserCPUusage,bothwithandwithout Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 vviList of Tables 3.1 An example Empty Document for an “AddressBook” Empty Type . 30 3.2 Information Extracted by an Importer . . . . . . . . . . . . . . . . 32 4.1 A Typical Sequence of inotify Events . . . . . . . . . . . . . . . . . 40 4.2 Significance Levels for inotify events . . . . . . . . . . . . . . . . . . 43 4.3 File system events and the corresponding actions executed by the Action Executor Thread . . . . . . . . . . . . . . . . . . . . . . . . 46 5.1 Comparison of Information Retrieval libraries . . . . . . . . . . . . 51 5.2 Lucenes valid simultaneous action combinations . . . . . . . . . . . 56 5.3 Search Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6.1 Statistics of the sample data used to test full indexing performance 67 6.2 Indexing Statistics: Storage Overhead for sample data of size 678 MB 68 6.3 Statistics: Performance Overhead . . . . . . . . . . . . . . 70 6.4 Searching Statistics: Response time to executing 100 Queries . . . . 70 6.5 Searching Statistics: Comparison of response time to executing 100 queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 viiviiiPreface As the amount of information stored on and accessed through computers has in- creasedoverthepasttwentyyears,thetoolsavailablefororganizingandretrieving such information have become outdated. The GNU/Linux Semantic Storage Sys- temisaninformationstorethatrepresentsdatabasedontheirattributes,contents, and relationships. The system provides access to the data through advanced orga- nization mechanisms and fast data searching, and it also maintains compatibility with existing applications. Objective WiththediskdrivecapacitygrowingataratefasterthanMoore’slaw-adoubling of capacity every year, the increase in the amount of data that can be stored on the computer has led to a similar growth in the complexity in its retrieval. However, the current tools and solutions have not kept pace with this informa- tion explosion, and the absence of such vision when they were designed does not make them easily extensible. The conventional file systems, for instance, impose a hierarchical structure on the user and force him to create strict organization schemes, and provide a monotonic constraint for document retrieval; a combina- tion of its location and name. GNU/Linux Semantic Storage System addresses these issues. It presents the user with a “semantic” interface to his data, and is designed to pull the user away from thinking of where the data is, and encourage him to think of what the data contains. The semantic attributes of a file are automatically extracted using developer-programmable importers and are indexed for efficient retrieval against a user’s search queries. ix