Exclusive Create

Ordinary file system semantics require that most operations that create directory entries be exclusive. For example, trying to create a directory that already exists should fail, and creating a file that already exists should return a reference to the existing file. Ivy implements exclusive creation of directory entries because some applications use those semantics to implement locks. However, Ivy only guarantees exclusion when the network provides full connectivity.

ExclusiveLink(dir-inum, file, file-inum)
   append a Prepare(dir-inum, file) log record
   if file exists
       append a Cancel(dir-inum, file) record
       return EXISTS
   if another un-canceled Prepare(dir-inum, file) exists
       append a Cancel(dir-inum, file) record
       backoff()
       return ExclusiveLink(dir-inum, file, file-inum)
   append Link(dir-inum, file, file-inum) log record
   return OK

Figure 3: Ivy's exclusive directory entry creation algorithm.

Whenever Ivy is about to append a Link log record, it first ensures exclusion with a variant of two-phase commit shown in Figure 3. Ivy first appends a Prepare record announcing the intention to create the directory entry. This intention can be canceled by a Cancel record, an eventual Link record, or a timeout. Then, Ivy checks to see whether any other participant has appended a Prepare that mentions the same directory i-number and file name. If not, Ivy appends the Link record. If Ivy sees a different participant's Prepare, it appends a Cancel record, waits a random amount of time, and retries. If Ivy sees a different participant's Link record, it appends a Cancel record and indicates a failure.