Patent Publication Number: US-8527556-B2

Title: Systems and methods to update a content store associated with a search index

Description:
BACKGROUND 
     Index-based search systems have been developed to facilitate the identification of desired information within increasingly large quantities of electronic data. An index-based search of millions of electronic documents may produce a search result within a time that may be noticeable but acceptable, e.g., few seconds. A search result identifies relevant documents, and may also contain metadata such as a title and a description of the relevant documents, as well as snippets of relevant content. 
     The search index of an index-based search system typically contains structured files that store the contents of documents within field-value pairs. Such an index is often referred to as an “inverted index” because each record thereof contains a mapping from a unique word (i.e., a field) to a list (i.e., values) of document identifiers of all documents in the repository that contain this word. During operation, a search engine receives search terms, queries the search index to determine identifiers of documents which contain the search terms, and returns the documents identifiers in an order based on their relevance to the search terms. 
     An inverted index is optimized for quick response. For example, a search index may return a list of document identifiers in response to a search query within imperceptible time, e.g., tens of milliseconds. Once the list is returned, the identified documents are opened to retrieve the metadata and other fields (e.g., description, content snippets) to be returned in the search result. Opening the documents and retrieving information therefrom is by far the most time-consuming component of the search process. 
     In order to increase the speed at which this information is retrieved, some search systems store a blueprint of each stored document in a set of flat files, known as a content store. Using a content store, document information may be retrieved in tens of milliseconds. Document identifiers stored in the search index are used to reference corresponding document information from the content store. 
     Conventional systems require complete regeneration of a content store every time the search index is updated. In this regard, the document identifiers in the search index may change during an update to the search index, rendering the references in the content store invalid. By completely regenerating the entire content store each time the search index is updated, the content store references are always valid. 
     Moreover, the content store files are typically sequential in order to facilitate fast retrieval of information therefrom. However, using conventional techniques, updating the content store files based only on search index updates while maintaining the sequential nature of the files is often more time- and resource-consuming than simply regenerating the entire content store based on the entire search index. 
     Completely regenerating a content store in response to search index updates results in a significant delay between changes to a document repository and reflection of the changes within the content store. This delay is exacerbated over time because the time required to generate a content store scales poorly as the number of documents in the search index increases. 
     Systems are desired to efficiently update a content store based on changes to a search index. For example, systems are desired to efficiently update a content store in response to the addition, deletion and/or modification of document identifiers within a search index. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of a system according to some embodiments. 
         FIG. 2  is a diagram of a content store schema according to some embodiments. 
         FIGS. 3A and 3B  illustrate the storage and interrelationships of data within a content store according to some embodiments. 
         FIG. 4  is a sequence diagram of a process according to some embodiments. 
         FIG. 5  is a flow diagram of a process according to some embodiments. 
         FIGS. 6A and 6B  comprise a flow diagram associated with optimization of a search index according to some embodiments. 
         FIGS. 7A through 7C  comprise a flow diagram associated with defragmentation of a content store according to some embodiments. 
         FIG. 8  is a block diagram of a system according to some embodiments. 
         FIG. 9  is a block diagram of an apparatus according to some embodiments. 
     
    
    
     DETAILED DESCRIPTION 
     The following description is provided to enable any person in the art to make and use the described embodiments and sets forth the best mode contemplated for carrying out some embodiments. Various modifications, however, will remain readily apparent to those in the art. 
     Some embodiments may be implemented within a hardware architecture such as that shown in  FIG. 1 . System  100  may represent any system providing search functionality. System  100  includes client system  110 , object repository  120  and search server  130 . In general operation, client system  110  submits a search query and, in response, search server  130  provides a search result identifying one or more objects of object repository  120 . As described above, the search result may identify the one or more objects and include metadata and/or other information of the identified objects. 
     Although  FIG. 1  depicts a search query passing from client system  110  to search server  130  via object repository  120 , a search query may pass from client system  110  to search server  130  through other or additional functional components according to some embodiments. In this regard, embodiments are not limited to the architecture of system  100 . 
     Client system  110  may comprise any suitable device, such as a desktop computer, a laptop computer, a personal digital assistant, a tablet PC, and a smartphone. Client system  110  may, for example, execute program code of a rich client application or a Web-browser to provide the functions attributed thereto herein. 
     Object repository  120  may comprise any one or more storage devices storing objects. The objects may comprise files of any type, including but not limited to Web pages, word processing documents, spreadsheets, Portable Document Format (PDF) documents, etc. In some embodiments, object repository  120  is a repository of a Business Intelligence (BI) system storing BI reports and other BI objects. According to the description below, a report object may include one or more documents, such as text, tables, etc. 
     Search server  130  includes crawler/indexer  140  and search index  150 . Crawler/indexer  140  identifies objects of object repository  120  to be indexed, and indexes the objects in search index  150 . For example, crawler/indexer  140  may identify new or modified objects within object repository  120 . For each new or modified object of a particular format (e.g., .doc, .pdf, .wid), crawler/indexer  140  executes an extractor associated with the particular format to extract information from the document. The extracted information is used to update search index  150 . 
     As described in the above Background, such updating may include associating document identifiers of the new or modified objects with existing words in search index  150 , and/or entering new words (i.e., fields) in search index  150  and associating document identifiers of the new or modified objects with the new words. 
     Content store  160  is a set of flat files storing metadata and other information of each indexed document. A detailed example of an implementation of content store  160  will be described below with respect to  FIGS. 2 ,  3 A and  3 B. 
     Delta content store queue  170  includes a list of document identifiers based on which content store  160  should be updated. In some embodiments, crawler/indexer  140  adds a document identifier to delta content store queue  170  each time a document is indexed in search index  150 . Accordingly, in response to adding or modifying a document in object repository  120 , crawler/indexer  140  indexes the document in search index  150  and adds an identifier of the document to delta content store queue  170 . 
     Content store updater  180  updates content store  160  based on delta content store queue  170 . Details of the update process according to some embodiments are described below. The update process may, according to some embodiments, eliminate the need to completely regenerate content store  160  each time search index  150  is updated. 
     Crawler/indexer  140  and/or content store updater  180  may be implemented in program code executed by a processor of search server  130 . Search index  150  and content store  160  may be stored in any one or more common or separate electronic storage elements, including but not limited to Random Access Memory, cache memory, a hard drive, etc. The components of search server  130  (and of system  100  in general) may be embodied in any number of common or separate devices, using any suitable combination of hardware and/or software. 
       FIG. 2  illustrates schema  200  of a content store according to some embodiments. For example, the files of content store  160  may conform to schema  200 . 
     During indexing, objects stored in an object repository may be split into their constituent parts, such as tables and charts, and each constituent part is independently indexed. Each constituent part will be referred to as a document. For example, a report object may include two tables, and each table will be represented by a unique document identifier in the search index and the content store. 
     Schema  200  includes seven files: ObjectIndex; ObjectMaster; IndexDocIndex; IndexDocMaster; ObjectFacetMapping; FacetIndex and FacetMaster. 
     The ObjectMaster file stores metadata records for each object in the object repository. The data structure of the ObjectMaster file permits the storage of any number of metadata fields. Each record in the ObjectMaster file includes a pointer, ObjectFacetMappingSeekAddress, to an address in the ObjectFacetMapping table that holds the list of facets for the corresponding object. 
     The facets of an object include the various fields of the object and their corresponding values. Some fields of a particular object (e.g., the Country column of a table) may be associated with several values (e.g., Canada, France), and these field-value associations may be reflected in the list of facets stored in the content store. 
     The ObjectIndex file stores the starting address of each object&#39;s record in the ObjectMaster table. In an embodiment, an object identifier is a unsigned 32 bit integer. If object identifiers are used to calculate the addresses of corresponding records in the ObjectMaster file, the ObjectMaster file will include a lot of unused addresses. Therefore, each object is assigned a sequence number, starting at  0 , when its metadata is stored in the ObjectMaster file. The ObjectIndex file maintains the mapping between an object sequence number and its corresponding record in the ObjectMaster file. 
     The FacetMaster file stores information such as facet name and a parent facet id identifier for each unique facet. The FacetIndex file contains the starting address of each record in the FacetMaster file. Each unique facet is assigned a sequence number starting from 0 when it is stored in the FacetMaster file. Analogous to the ObjectIndex file, the FacetIndex file maintains mappings between the facet sequence number and the address of the facet&#39;s record in the FacetMaster file. 
     The IndexDocMaster file stores metadata about the index documents. Each record in the IndexDocMaster also has a pointer, called IndexDocFacetSeekAddress, to the address in the ObjectFacetMapping table that holds the list of facets for this document. The ObjectSequenceID of the object corresponding to this index document is also stored in the index document&#39;s record. The address stored at this pointer location points to the metadata record for this object in the ObjectMaster table. 
     The IndexDocIndex file maps each document identifier of the search index to a starting address of a record of an associated document in the IndexDocMaster file. 
     The ObjectFacetMapping file contains mappings between an object and the object-level facets for that object. Examples of object-level facets are object type (e.g., Webi, Crystal Report) and folder path. The ObjectFacetMapping file also contains mappings between a document identified in the search index and categories corresponding to that document. Each record in the ObjectFacetMapping file contains a list of FacetlDs (integers) terminated by −1. 
     The following example describes the population of content store files based on schema  200  according to some embodiments. The example considers two report objects: 
     Report 1 
     Name: Resorts 
     Description: Details about resorts such as resort name, city and country. 
     Type: Web Intelligence Report 
     Last Updated: 12 Jul. 2009 
     ID: 1200 
     Report 1 contains one table, Resort Details, as shown below: 
                                             Resort   Country                          Bahamas Beach   U.S.           French Riviera   France                        
Report 2
 
     Name: Customers 
     Description: Details about customers such as customer name, city and country of origin. 
     Type: Web Intelligence Report 
     Last Updated: 10 Jun. 2009 
     ID: 1300 
     Report 2 contains one table, Customer Details, as shown below: 
     
       
         
           
               
               
               
             
               
                   
                   
               
               
                   
                 Customer 
                 Country 
               
               
                   
                   
               
             
            
               
                   
                 Arai 
                 Japan 
               
               
                   
                 Baker 
                 U.S. 
               
               
                   
                   
               
            
           
         
       
     
       FIGS. 3A and 3B  illustrate files of a content store generated based on these two reports. As shown, each report is considered a separate object, and each table is considered a separate document. However, an object and a document within that object share the same ObjectSequenceID. 
       FIG. 4  is a sequence diagram of a process according to some embodiments. The sequence diagram reflects the components of system  100 , but the components of the sequence diagram may be configured differently than that of system  100 . Embodiments are not limited to the components of  FIGS. 1 and 4 , or to the functions thereby attributed to each component. 
     Initially, a user operates a client device to add or modify a document stored in an object repository. For example, the user may operate a reporting tool executed by the client device to retrieve a report from the object repository. The user may then modify a table of the report and save the modified report back to the object repository using the reporting tool. 
     A crawler task (e.g., running on a search server) periodically crawls the object repository looking for new or modified documents. When new or modified documents are identified, an indexer indexes the contents of the documents within a search index. More specifically, the search index initially associates each of a plurality of words with at least one of a plurality of document identifiers. The indexer extracts the contents of the identified new or modified documents and adds document identifiers associated with the new or modified documents to the search index where appropriate. 
     The indexer also adds document identifiers associated with the new or modified documents to a delta content store queue. A delta content store updater periodically checks the delta content store queue for document identifiers. Accordingly, the delta content store updater determines document identifiers which have been added to the search index. 
     The delta content store updater reads the documents associated with the document identifiers of the delta content store queue. Metadata and/or other information of each read document is then added to a content store. Advantageously, updates to the search index do not require regeneration of the entire content store. 
       FIG. 5  is a flow diagram of process  500  according to some embodiments. Process  500 , and all other process described herein, may be executed by hardware and embodied in program code stored on a non-transitory computer-readable medium. Process  500 , and the other described processes, may be performed by one or more elements of system  100 , such as delta content store updater  180 , but embodiments are not limited thereto. 
     Generally, process  500  may be executed to update a content store based on updates to a corresponding search index, without requiring complete regeneration of the content store. Initially, at S 505 , new or modified documents added to the search index are detected. In some embodiments, the documents are detected by reading document identifiers from a delta content store queue generated as described above. 
     It is preferable to update the content store without pausing or otherwise affecting searches on the search index. Accordingly, a “working” copy of the content store is generated at S 510 . The working copy includes copies of each file of the content store (i.e., IndexDocIndex, IndexDocMaster, ObjectMaster, ObjectIndex, ObjectFacetMapping, FacetIndex, FacetMaster). 
     According to some embodiments, a checksum of each content store file was stored after a previous successful update to the content store. At S 515 , checksums of the working copy files are compared with the corresponding stored checksums to determine whether the working copy files are corrupted. If the checksums do not match, the working copy is deleted at S 520  and flow returns to S 510 . Flow proceeds to S 525  if the checksums match. 
     A portion of the indexing process will now be described to facilitate understanding of the next several steps of process  500 . Specifically, when an object is modified or deleted in the object repository, the search index is searched for all document identifiers corresponding to this object. These document identifiers are written to a “deleted identifiers” file. Therefore, at S 525 , the deleted identifiers file is read and, for each identifier in the file, the seek address in the corresponding record of the IndexDocIndex file is set to −1 at S 530 . This seek address serves as a flag to indicate that the corresponding document should not be returned as a search result, even if the corresponding document identifier was selected from the search index based on a search query. 
     Next, at S 535 , new records are created in the IndexDocMaster, ObjectMaster, FacetMaster and ObjectFacetMapping files of the working copy of the content store. These records are simply appended to the end of these files to maintain the sequential nature of these files. Accordingly, the IndexDocIndex, ObjectIndex and FacetIndex files of the working copy are updated at S 540  to point to the new records created at S 535 . 
     The working copy is copied at S 545 , and the copy of the working copy is defined as the latest version of the content store at S 550 . As mentioned above, checksums may be generated for each file of the content store and saved for use during a next content store update. 
     The objects in the delta content store queue are not deleted until the content store update is successful. If the update is not successful, the new content store can be generated from the latest “good” version because identifiers of the updated objects remain in the delta content store queue. 
     The search index must be optimized periodically in order to prevent the degradation of search response times. Optimization includes removal of all document identifiers specified in the deleted identifiers file. These document identifiers are associated with documents that have been deleted from the object repository, or that have been modified and are now represented by a different document identifier. After removing the identifiers, the search index is defragmented to improve search response times. However, defragmentation changes the document identifiers within the search index. The content store must be modified to account for these changed document identifiers, preferably without regenerating the entire content store. 
     Process  600  of  FIGS. 6A and 6B  may be executed to maintain the validity of the content store references across index optimizations without regenerating the entire content store. Process  600  assumes that every indexed document is associated with a unique identifier (UID) which is stored in a field of the document. This UID does not change when the search index is optimized. 
     At S 610 , a first mapping of UIDs to document identifiers is created. The mapping includes the UID and document identifier of each document represented in the search index. The index is optimized at S 620  to remove the document identifiers of the deleted identifiers file and to defragment the resulting search index. As mentioned above, defragmentation changes the document identifiers within the search index. 
     A second mapping of UIDs to document identifiers is created at S 625 . The mapping includes the UID and document identifier of each document represented in the optimized search index. 
     The remainder of process  600  populates a new IndexDocIndex file for the content store. The new IndexDocIndex file is intended to compensate for the changed document identifiers such that the changes are transparent to the remaining content store files. 
     The new IndexDocIndex file is created at S 630 . Next, at S 635 , a new document identifier and a corresponding UID are retrieved from the second mapping. A document identifier which corresponds to the retrieved UID is then determined from the first mapping at S 640 . The determined document identifier is the “old” (i.e., pre-optimization) identifier of the document corresponding to the retrieved UID. 
     The current process seeks to (old document identifier*8) in the old IndexDocIndex file to locate a record corresponding to the old document identifier at S 645 , and reads the IndexDocSeekAddress from the record of the old IndexDocIndex file at S 650 . The address (new document identifier*8) is located in the new IndexDocIndex file at S 660 , and the IndexDocSeekAddress read at S 650  is written to this address in the new IndexDocIndex file. 
     At S 670 , it is determined whether the second mapping includes more document identifiers (and corresponding UIDs). If so, a new document identifier and corresponding UID are retrieved from the second mapping at S 675  and flow returns to S 640 . If not, flow terminates. 
     As a result of process  600 , a new document identifier associated with a document can be used to access data associated with the document in the content store, even if the document was associated with a different document identifier when the data was originally stored in the content store. According to the described implementation, the old document identifier pointed to a record of the old IndexDocIndex file which in turn pointed to a relevant record of the IndexDocMaster file. After execution of process  600 , the new document identifier points to a record of the new IndexDocIndex file which points to the same relevant record of the IndexDocMaster file. 
     As described with respect to process  500 , new records are added to the end of the IndexDocMaster, ObjectMaster, FacetMaster and ObjectFacetMapping files when objects are added to or modified in the object repository. The records associated with deleted or previous versions of objects are not affected, but they are no longer pointed to by the ObjectIndex and IndexDocIndex files. Accordingly, the content store files become fragmented over time, resulting in degradation of search response times. 
     Process  700  of  FIGS. 7A through 7C  may be executed to defragment a content store according to some embodiments. In some embodiments, a content store is defragmented after its corresponding search index is optimized (e.g., via process  600 ). 
     At S 705 , new IndexDocIndex, IndexDocMaster, ObjectIndex, ObjectMaster and ObjectFacetMapping files are created. Then, at S 710 , an OldObjSeqID to NewObjSeqID map is created. The variable Next_Seq_ID is initialized to −1 at S 715 . 
     After the foregoing preparatory steps are complete, a new document identifier and corresponding UID are retrieved at S 720  from the second mapping created during process  600 . The second mapping is available because, as described above, process  700  is executed after optimization of the search index. 
     The retrieved UID is used at S 725  to determine, from the first mapping created prior to search index optimization, an old document identifier which corresponds to the retrieved new document identifier. The old document identifier is then used at S 730  to identify a corresponding record from the old IndexDocMaster file and to read an old object sequence identifier from the corresponding record. Similarly, an old record from the old ObjectMaster file is read at S 735  using the old object sequence identifier. 
     Specifically, the ObjectFacetMappingSeekAddr is read from the old record of the old ObjectMaster file and assigned to the variable Facet_Seek_Addr at S 740 . Next, at S 745 , the record located at Facet_Seek_Addr in the old ObjectFacetMapping file is copied to the new ObjectFacetMapping file. The ObjectFacetMappingSeekAddr of the old record of the ObjectMaster file is set to the address of the record copied in the new ObjectMaster file at S 750 . Then, this old record is written to the new ObjectMaster file at S 755 . 
     At S 760 , process  700  seeks to (New_Seq_ID*8) in the new ObjectIndex file. The address of the record written at S 755  is then written to the seek position of the new ObjectIndex file at S 765 . It is then determined at S 770  whether the mapping created at S 710  includes a new object sequence identifier corresponding to the old object sequence identifier. If a new object sequence identifier is not found, the variable Next_Seq_ID is incremented at S 775  and the Next_Seq_ID is assigned to New_Seq_ID at S 780 . If the determination at S 770  is affirmative, the new object sequence identifier is assigned the value of New_Seq_ID at S 785 . 
     At S 790 , the object sequence identifier in the old record from the old IndexDocMaster file is set to New_Seq_ID. This old record is then written to the new IndexDocMaster file at S 792 . After seeking to (old document identifier*8) in the new IndexDocIndex file, the address of the record written at S 792  is written to the seek position of the new IndexDocIndex file at S 796 . 
     At S 798 , it is determined whether the second mapping includes more document identifiers (and corresponding UIDs). If so, flow returns to S 720  to retrieve a new document identifier and corresponding UID from the second mapping and continue as described above. If not, process  700  terminates. 
     Some search systems include several search processing nodes. Each search processing node includes a search engine and a copy of the search index. The processing nodes provide scalability of search services and fault-tolerance. A cluster-aware content store is desirable for similar reasons. 
       FIG. 8  is a block diagram of system  800  including object repository  810  and a cluster of processing nodes  820 ,  830  and  840 . Each of nodes  820 ,  830  and  840  generates and updates a dedicated copy of the content store. When one or more nodes fail, the remaining nodes are available for serving search queries. 
     Delta content store queue  812  is a global queue visible to all nodes. The delta store content updater ( 822 ,  832  and  842 ) of each node picks up objects  813  from queue  812  and updates a corresponding content store  824 ,  834  and  844  based thereon (e.g., using process  500 ). 
     Each of nodes  820 ,  830  and  840  maintains a corresponding service session object  814 ,  815  or  816  in object repository  810 . A service session object contains state information associated with its corresponding node. The state information includes attributes such as a timestamp representing the last content store update and the latest content store version. The objects in the delta content store queue are ordered by their update timestamp. 
     As mentioned above, the delta store content updater ( 822 ,  832  and  842 ) of each node may update its corresponding content store based on techniques described herein. After a successful delta content store update, each node stores the timestamp of its last processed queue object in the node&#39;s corresponding service session. 
     An object in delta content store queue  812  is removed only after being processed by all nodes in the cluster. Cleanup tasks  826 ,  836  and  846  may perform this removal. For example, a cleanup task of a node may read the last object-processed timestamp from each of service sessions  814 ,  815  and  816 . The earliest timestamp is identified, and all objects from delta content store queue  812  whose timestamps are earlier than the last-processed timestamp are deleted. 
     Cleanup tasks  826 ,  836  and  846  coordinate these actions by locking and unlocking delta content store queue  812 . Therefore, if one node fails, the cleanup tasks of the other nodes may continue cleaning delta content store queue  812 . 
     Each node maintains its own copy of the content store. If a checksum comparison at the beginning of a content store update (e.g., process  500 ) indicates that a node&#39;s content store is corrupted, the other nodes can continue to serve search requests using their content stores. The affected node does not process search requests until its content store is recovered. 
       FIG. 9  is a block diagram of apparatus  900  according to some embodiments. Apparatus  900  may comprise a general-purpose computing apparatus and may execute program code to perform any of the functions described herein. Apparatus  900  may comprise an implementation of search server  130  and/or any of nodes  820 ,  830  and  840 . Apparatus  900  may include other unshown elements according to some embodiments. 
     Apparatus  900  includes processor  910  operatively coupled to communication device  920 , data storage device  930 , one or more input devices  940 , one or more output devices  950  and memory  960 . Communication device  920  may facilitate communication with external devices, such as an object repository. Input device(s)  940  may comprise, for example, a keyboard, a keypad, a mouse or other pointing device, a microphone, knob or a switch, an infra-red (IR) port, a docking station, and/or a touch screen. Input device(s)  940  may be used, for example, to enter information into apparatus  900 . Output device(s)  950  may comprise, for example, a display (e.g., a display screen) a speaker, and/or a printer. 
     Data storage device  930  may comprise any appropriate persistent storage device, including combinations of magnetic storage devices (e.g., magnetic tape, hard disk drives and flash memory), optical storage devices, Read Only Memory (ROM) devices, etc., while memory  960  may comprise Random Access Memory (RAM). 
     Program code of delta content store updater  932  may be executed by processor  910  to cause apparatus  900  to perform any one or more of the processes described herein. Embodiments are not limited to execution of these processes by a single apparatus. Content store  934  may include any type of data structures of information associated with object, including but not limited to flat files conforming to schema  200 . Data storage device  930  may also store data and other program code for providing additional functionality and/or which are necessary for operation thereof, such as device drivers, operating system files, etc. 
     The foregoing diagrams represent logical architectures for describing processes according to some embodiments, and actual implementations may include more or different components arranged in other manners. Moreover, each system described herein may be implemented by any number of devices in communication via any number of other public and/or private networks. Two or more devices of may be located remote from one another and may communicate with one another via any known manner of network(s) and/or a dedicated connection. Moreover, each device may comprise any number of hardware and/or software elements suitable to provide the functions described herein as well as any other functions. Other topologies may be used in conjunction with other embodiments. 
     All systems and processes discussed herein may be embodied in program code stored on one or more computer-readable media. Such media may include, for example, a floppy disk, a CD-ROM, a DVD-ROM, a Flash drive, magnetic tape, and solid state Random Access Memory (RAM) or Read Only Memory (ROM) storage units. Embodiments are therefore not limited to any specific combination of hardware and software. 
     The embodiments described herein are solely for the purpose of illustration. Those in the art will recognize that other embodiments may be practiced with modifications and alterations limited only by the claims.