Project

General

Profile

Algorithms » History » Revision 21

Revision 20 (Greg Burri, 08/11/2009 09:03 AM) → Revision 21/35 (Greg Burri, 08/11/2009 09:04 AM)

h1. Algorithms 


 h2. Word indexing 

 Theses steps are valid independently of the language. 

 # Each file is split in word, there is a set of characters which will use as delimiter between the word like [' ', '#', '.', '?',..]. 
 # Some character are replaced by a another, for example : ['é', 'ë',..] => 'e'. The goal is to remove all accent. 


 h2. Searching 

 For a functional description see here : [[Functional definition#The-search-window]] 

 The match of a word can be partial from the beginning, for example _train_ will match _training_. 

 !aybabtu_search.png! 
 _This schema depicts how the results are sorted from one peer. Each peer result are then merged._ 

 h2. Peer ID 

 Each peer owns a peer id which is unique and generated during the first start. This ID is used to identify a peer, it's better than the previous usage of peer IP, considering this situation : 

 * _A_ put in queue a file entry _f_ from _B_, _B_ doesn't know the hashes of this file entry. 
 * _B_ change his IP address. 
 * _A_ want to download _f_, it can ask _B_ for the hashes even _B_'s IP changed. 

 h2. Core threads 

 There are three kind of threads in the core in addition to the main thread : 
 * [[Protocol_core-core#Downloading-thread|Downloading thread]] : @DownloadManager::ChunkDownloader@ 
 * Uploading thread : @UploadManager::Uploader@ 
 * [[Algorithms#Updating-the-file-cache|Updating file cache thread]] : @FileManager::FileUpdater@ 

 h2. Updating the file cache (Obsolete, must be rewritten after the seventh prototype ended) 

 Here is the algorithm for the thread (@FileManager::FileUpdater@) which will periodically update the file cache and persist it. 

 <pre> 
 D : The set of shared directories 
 T : Time during the hashes are computed (for example 30s) 
 F : A set of file initialy empty 

 - Add a watcher to the shared directories 

 // First synchronize (at start) 
 For each d in D (recursively) : 
    - Synchronize physical folders and files with d content 
    - Add in F the files which doesn't have computed hashes 

 Loop :    
    t : Time.now 
    For each f in F : 
       - Compute the unknown hash of files f 
       - Remove f from F 
       If (Time.now - t) > T : break 
    - Wait T - (Time.now - t) 
    - Wait for changes for a period of P 
       - When a modification occurs synchronise the file/folder 
       - Add each new file in F 
    - Persist the entire cache in a file (only every ~30min) 
 </pre> 


 h2. Downloading 

 See here : [[Protocol_core-core#Downloading-threads]]