+++ /dev/null
-
-SPANNING TREE PROPERTY
-
-All metadata that exists in the cache is attached directly or
-indirectly to the root inode. That is, if the /usr/bin/vi inode is in
-the cache, then /usr/bin, /usr, and / are too, including the inodes,
-directory objects, and dentries.
-
-
-AUTHORITY
-
-The authority maintains a list of what nodes cache each inode.
-Additionally, each replica is assigned a nonce (initial 0) to
-disambiguate multiple replicas of the same item (see below).
-
- map<int, int> replicas; // maps replicating mds# to nonce
-
-The cached_by set _always_ includes all nodes that cache the
-partcuarly object, but may additionally include nodes that used to
-cache it but no longer do. In those cases, an expire message should
-be in transit. That is, we have two invariants:
-
- 1) the authority's replica set will always include all actual
- replicas, and
-
- 2) cache expiration notices will be reliably delivered to the
- authority.
-
-The second invariant is particularly important because the presence of
-replicas will pin the metadata object in memory on the authority,
-preventing it from being trimmed from the cache. Notification of
-expiration of the replicas is required to allow previously replicated
-objects from eventually being trimmed from the cache as well.
-
-Each metdata object has a authority bit that indicates whether it is
-authoritative or a replica.
-
-
-REPLICA NONCE
-
-Each replicated object maintains a "nonce" value, issued by the
-authority at the time the replica was created. If the authority has
-already created a replica for the given MDS, the new replica will be
-issues a new (incremented) nonce. This nonce is attached
-to cache expirations, and allows the authority to disambiguate
-expirations when multiple replicas of the same object are created and
-cache expiration is coincident with replication. That is, when an
-old replica is expired from the replicating MDS at the same time that
-a new replica is issued by the authority and the resulting messages
-cross paths, the authority can tell that it was the old replica that
-was expired and effectively ignore the expiration message. The
-replica is removed from the replicas map only if the nonce matches.
-
-
-SUBTREE PARTITION
-
-Authority of the file system namespace is partitioned using a
-subtree-based partitioning strategy. This strategy effectively
-separates directory inodes from directory contents, such that the
-directory contents are the unit of redelegation. That is, if / is
-assigned to mds0 and /usr to mds1, the inode for /usr will be managed
-by mds0 (it is part of the / directory), while the contents of /usr
-(and everything nested beneath it) will be managed by mds1.
-
-The description for this partition exists solely in the collective
-memory of the MDS cluster and in the individual MDS journals. It is
-not described in the regular on-disk metadata structures. This is
-related to the fact that authority delegation is a property of the
-{\it directory} and not the directory's {\it inode}.
-
-Subsequently, if an MDS is authoritative for a directory inode and does
-not yet have any state associated with the directory in its cache,
-then it can assume that it is also authoritative for the directory.
-
-Directory state consists of a data object that describes any cached
-dentries contained in the directory, information about the
-relationship between the cached contents and what appears on disk, and
-any delegation of authority. That is, each CDir object has a dir_auth
-element. Normally dir_auth has a value of AUTH_PARENT, meaning that
-the authority for the directory is the same as the directory's inode.
-When dir_auth specifies another metadata server, that directory is
-point of authority delegation and becomes a {\it subtree root}. A
-CDir is a subtree root iff its dir_auth specifies an MDS id (and is not
-AUTH_PARENT).
-
- - A dir is a subtree root iff dir_auth != AUTH_PARENT.
-
- - If dir_auth = AUTH_PARENT then the inode auth == dir auth, but the
- converse may not be true.
-
-The authority for any metadata object in the cache can be determined
-by following the parent pointers toward the root until a subtree root
-CDir object is reached, at which point the authority is specified by
-its dir_auth.
-
-Each MDS cache maintains a subtree data structure that describes the
-subtree partition for all objects currently in the cache:
-
- map< CDir*, set<CDir*> > subtrees;
-
- - A dir will appear in the subtree map (as a key) IFF it is a subtree
- root.
-
-Each subtree root will have an entry in the map. The map value is a
-set of all other subtree roots nested beneath that point. Nested
-subtree roots effectively bound or prune a subtree. For example, if
-we had the following partition:
-
- mds0 /
- mds1 /usr
- mds0 /usr/local
- mds0 /home
-
-The subtree map on mds0 would be
-
- / -> (/usr, /home)
- /usr/local -> ()
- /home -> ()
-
-and on mds1:
-
- /usr -> (/usr/local)
-
-
-AMBIGUOUS DIR_AUTH
-
-While metadata for a subtree is being migrated between two MDS nodes,
-the dir_auth for the subtree root is allowed to be ambiguous. That
-is, it will specify both the old and new MDS ids, indicating that a
-migration is in progress.
-
-If a replicated metadata object is expired from the cache from a
-subtree whose authority is ambiguous, the cache expiration is sent to
-both potential authorities. This ensures that the message will be
-reliably delivered, even if either of those nodes fails. A number of
-alternative strategies were considered. Sending the expiration to the
-old or new authority and having it forwarded if authority has been
-delegated can result in message loss if the forwarding node fails.
-Pinning ambiguous metadata in cache is computationally expensive for
-implementation reasons, and while delaying the transmission of expiration
-messages is difficult to implement because the replicating must send
-the final expiration messages when the subtree authority is
-disambiguated, forcing it to keep certain elements of it cache in
-memory. Although duplicated expirations incurs a small communications
-overhead, the implementation is much simpler.
-
-
-AUTH PINS
-
-Most operations that modify metadata must allow some amount of time to
-pass in order for the operation to be journaled or for communication
-to take place between the object's authority and any replicas. For
-this reason it must not only be pinned in the authority's metadata
-cache, but also be locked such that the object's authority is not
-allowed to change until the operation completes. This is accomplished
-using {\it auth pins}, which increment a reference counter on the
-object in question, as well as all parent metadata objects up to the
-root of the subtree. As long as the pin is in place, it is impossible
-for that subtree (or any fragment of it that contains one or more
-pins) to be migrated to a different MDS node. Pins can be placed on
-both inodes and directories.
-
-Auth pins can only exist for authoritative metadata, because they are
-only created if the object is authoritative, and their presense
-prevents the migration of authority.
-
-
-FREEZING
-
-More specifically, auth pins prevent a subtree from being frozen.
-When a subtree is frozen, all updates to metadata are forbidden. This
-includes updates to the replicas map that describes which replicas
-(and nonces) exist for each object.
-
-In order for metadata to be migrated between MDS nodes, it must first
-be frozen. The root of the subtree is initially marked as {\it
-freezing}. This prevents the creation of any new auth pins within the
-subtree. After all existing auth pins are removed, the subtree is
-then marked as {\it frozen}, at which point all updates are
-forbidden. This allows metadata state to be packaged up in a message
-and transmitted to the new authority, without worrying about
-intervening updates.
-
-If the directory at the base of a freezing or frozen subtree is not
-also a subtree root (that is, it has dir_auth == AUTH_PARENT), the
-directory's parent inode is auth pinned.
-
- - a frozen tree root dir will auth_pin its inode IFF it is auth AND
- not a subtree root.
-
-This prevents a parent directory from being concurrently frozen, and a
-range of resulting implementation complications relating metadata
-migration.
-
-
-CACHE EXPIRATION FOR EXPORTING SUBTREES
-
-Cache expiration messages that are received for a subtree that is
-being exported are either deferred or handled immediately, based on
-the sender and reciever states. The importing MDS will always defer until
-after the export finishes, because the import could fail. The exporting MDS
-processes the expire UNLESS the expiring MDS does not know about the export or
-the exporting MDS is no longer auth.
-Because MDSes get witness notifications on export, this is safe. Either:
-a) The expiring MDS knows about the export, and has sent messages to both
-MDSes involved, or
-b) The expiring MDS did not know about the export at the time the message
-was sent, and so only sent it to the exporting MDS. (This implies that the
-exporting MDS hasn't yet encoded the state to send to the replica MDS.)
-
-When the subtree export completes, deferred expirations are either processed
-(if the MDS is authoritative) or discarded (if it is not). Because either
-the exporting or importing metadata can fail during the migration
-process, the MDS cannot tell whether it will be authoritative or not
-until the process completes.
-
-During a migration, the subtree will first be frozen on both the
-exporter and importer, and then all other replicas will be informed of
-a subtrees ambiguous authority. This ensures that all expirations
-during migration will go to both parties, and nothing will be lost in
-the event of a failure.
-
-
-
-NORMAL MIGRATION
-
-The exporter begins by doing some checks in export_dir() to verify
-that it is permissible to export the subtree at this time. In
-particular, the cluster must not be degraded, the subtree root may not
-be freezing or frozen, and the path must be pinned (\ie not conflicted
-with a rename). If these conditions are met, the subtree root
-directory is temporarily auth pinned, the subtree freeze is initiated,
-and the exporter is committed to the subtree migration, barring an
-intervening failure of the importer or itself.
-
-The MExportDiscover serves simply to ensure that the inode for the
-base directory being exported is open on the destination node. It is
-pinned by the importer to prevent it from being trimmed. This occurs
-before the exporter completes the freeze of the subtree to ensure that
-the importer is able to replicate the necessary metadata. When the
-exporter receives the MDiscoverAck, it allows the freeze to proceed by
-removing its temporary auth pin.
-
-The MExportPrep message then follows to populate the importer with a
-spanning tree that includes all dirs, inodes, and dentries necessary
-to reach any nested subtrees within the exported region. This
-replicates metadata as well, but it is pushed out by the exporter,
-avoiding deadlock with the regular discover and replication process.
-The importer is responsible for opening the bounding directories from
-any third parties authoritative for those subtrees before
-acknowledging. This ensures that the importer has correct dir_auth
-information about where authority is redelegated for all points nested
-beneath the subtree being migrated. While processing the MExportPrep,
-the importer freezes the entire subtree region to prevent any new
-replication or cache expiration.
-
-A warning stage occurs only if the base subtree directory is open by
-nodes other than the importer and exporter. If it is not, then this
-implies that no metadata within or nested beneath the subtree is
-replicated by any node other than the importer an exporter. If it is,
-then a MExportWarning message informs any bystanders that the
-authority for the region is temporarily ambiguous, and lists both the
-exporter and importer as authoritative MDS nodes. In particular,
-bystanders who are trimming items from their cache must send
-MCacheExpire messages to both the old and new authorities. This is
-necessary to ensure that the surviving authority reliably receives all
-expirations even if the importer or exporter fails. While the subtree
-is frozen (on both the importer and exporter), expirations will not be
-immediately processed; instead, they will be queued until the region
-is unfrozen and it can be determined that the node is or is not
-authoritative.
-
-The exporter walks the subtree hierarchy and packages up an MExport
-message containing all metadata and important state (\eg, information
-about metadata replicas). At the same time, the expoter's metadata
-objects are flagged as non-authoritative. The MExport message sends
-the actual subtree metadata to the importer. Upon receipt, the
-importer inserts the data into its cache, marks all objects as
-authoritative, and logs a copy of all metadata in an EImportStart
-journal message. Once that has safely flushed, it replies with an
-MExportAck. The exporter can now log an EExport journal entry, which
-ultimately specifies that the export was a success. In the presence
-of failures, it is the existence of the EExport entry only that
-disambiguates authority during recovery.
-
-Once logged, the exporter will send an MExportNotify to any
-bystanders, informing them that the authority is no longer ambiguous
-and cache expirations should be sent only to the new authority (the
-importer). Once these are acknowledged back to the exporter,
-implicitly flushing the bystander to exporter message streams of any
-stray expiration notices, the exporter unfreezes the subtree, cleans
-up its migration-related state, and sends a final MExportFinish to the
-importer. Upon receipt, the importer logs an EImportFinish(true)
-(noting locally that the export was indeed a success), unfreezes its
-subtree, processes any queued cache expierations, and cleans up its
-state.
-
-
-PARTIAL FAILURE RECOVERY
-
-
-
-
-RECOVERY FROM JOURNAL
-
-
-
-
-
-
-
-
-
Code Review / stor4nfv.git / blobdiff