John M Maccormick

US Patent:

7483906, Jan 27, 2009

Filed:

Apr 14, 2004

Appl. No.:

10/823870

Inventors:

John Philip MacCormick - Mountain View CA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 17/30

US Classification:

707101, 707 3, 707100, 707200

Abstract:

An efficient method for renaming consecutive keys in a B-tree representing a hierarchical namespace, such as a file system, has an estimated time efficiency of O(logN), where N is the number of nodes in the B-tree. All the consecutive keys to be renamed are first excised from the original B-tree to form a trimmed B-tree, and the excised nodes are stored in a separate temporary extracted B-tree. The nodes in extracted B-tree are then renamed, and the renamed extracted B-tree is inserted into the trimmed B-tree to form a final B-tree that contains the renamed keys.

US Patent:

7529891, May 5, 2009

Filed:

Sep 19, 2005

Appl. No.:

11/230028

Inventors:

Chandramohan A. Thekkath - Palo Alto CA, US
John P. MacCormick - Mountain View CA, US
Lidong Zhou - Sunnyvale CA, US
Nicholas Charles Murphy - San Mateo CA, US

Assignee:

Microsoft Corporation - Armonk NY

International Classification:

G06F 12/00
G06F 13/00
G06F 13/28
G06F 9/26
G06F 9/34

US Classification:

711137, 711129, 711204

Abstract:

Balanced prefetching automatically balances the benefits of prefetching data that has not been accessed recently against the benefits of caching recently accessed data, and can be applied to most types of structured data without needing application-specific details or hints. Balanced prefetching is performed in applications in a computer system, such as storage-centric applications, including file systems and databases. Balanced prefetching exploits the structure of the data being prefetched, providing superior application throughput. For a fixed amount of memory, it is automatically and dynamically determined how much memory should be devoted to prefetching.

US Patent:

7636868, Dec 22, 2009

Filed:

Jun 27, 2006

Appl. No.:

11/476974

Inventors:

William R. Hoffman - Berkeley CA, US
Marcus J. Jager - Boulder Creek CA, US
John P. MacCormick - San Francisco CA, US
Kristof Roomp - Seattle WA, US
Chandramohan A. Thekkath - Palo Alto CA, US
Lidong Zhou - Sunnyvale CA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 11/00

US Classification:

714 13, 709223

Abstract:

A global state management service manages replication in a distributed system. A distributed system can have several replica groups. The global state management service manages state associated with each replica group. Data replication is implemented without implementing an instance of a state machine on each device in a replica group. A replica group comprises a primary device and at least one secondary device. Each device in a replica group contains a replica of data of interest. The global state management service manages the allocation of primary and secondary devices. In the absence of a failure in either a primary device or a secondary device, read and write operations are performed without consulting the global state management service. When a failure is detected, the global state management service manages failover.

US Patent:

7676513, Mar 9, 2010

Filed:

Jan 6, 2006

Appl. No.:

11/326884

Inventors:

Frank D. McSherry - San Francisco CA, US
John P. MacCormick - Mountain View CA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 17/00

US Classification:

707616, 707719, 707751

Abstract:

While consulting indexes to conduct a search, a determination is made from time to time as to whether it is more efficient to consult individual indexes in a set or to merge the indexes and consult the merged index. The cost of merging indexes is compared with the cost of individually querying indexes. In accordance with the result of this comparison, the indexes are merged and the merged index is consulted, or the indexes are individually consulted. A cost-balance invariant in the form of an inequality is used to equate the cost of merging indexes to a weighted cost of individually querying indexes. As query events are received, the costs are updated. As long as the cost-balance invariant is not violated, indexes are merged and the merged index is queried. If the cost-balance invariant is violated, indexes are not merged, and the indexes are individually queried.

US Patent:

7685179, Mar 23, 2010

Filed:

Mar 13, 2007

Appl. No.:

11/717285

Inventors:

John P. MacCormick - Mountain View CA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 12/00
G06F 17/30

US Classification:

707204, 707202, 706 19, 709226, 714 1

Abstract:

A deterministic technique is used for assigning locations to object replicas in a data center, while taking the various constraints into account that guarantee high availability and fast recovery. Example constraints include not putting the replicas on the same machine and not on the same rack, in case the rack or the network switch goes down. Also, because power distribution units (PDUs) can fail, the two replicas are not put on the same PDU. A solution is guaranteed to be found, if one exists.

US Patent:

7698258, Apr 13, 2010

Filed:

Jun 2, 2006

Appl. No.:

11/445960

Inventors:

William R Hoffman - Berkeley CA, US
Marcus J. Jager - Boulder Creek CA, US
John P. MacCormick - San Francisco CA, US
Kristof Roomp - Seattle WA, US
Chandramohan A. Thekkath - Palo Alto CA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 7/00

US Classification:

707 3

Abstract:

A searchable storage system indexes data, such as a blob (binary large object) as it is stored. The indexes are stored simultaneously with the data by the same storage mechanism. Data cannot be stored without indexing it. Any indexing technique may be used. The indexes are then used to access the data. This ensures that any inconsistencies can handled at the local level, and are not visible to clients of the system. Data can be put in to, or taken out from, the searchable storage system. Additionally, a query on the data in the searchable storage system may be performed.

US Patent:

7734573, Jun 8, 2010

Filed:

Dec 14, 2004

Appl. No.:

11/013274

Inventors:

John P. MacCormick - Mountain View CA, US
Chandramohan A. Thekkath - Palo Alto CA, US
Lidong Zhou - Sunnyvale CA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G06F 17/30

US Classification:

707202, 707204

Abstract:

Methods and apparatuses are provided for recovering one or more replicated datasets. In accordance to some embodiments of the invention, this is accomplished by determining whether a log contains one or more entries indicating a corruption in a replicated data item; and recovering the replicated data item if the log contains any such entries. The log, however, is maintained at a higher layer in a software hierarchy than the layer at which the replicated data item is recovered. As a result, there is no need to maintain a separate replication log at the layer where the replicated data item is recovered. In accordance to some embodiments of the invention, this is accomplished by recording an entry indicating that an operation was performed on a replicated record in a log at a higher layer in a software hierarchy, determining whether a failure occurred during the operation, and reconciling the replicated record at a lower layer in the software hierarchy if it is determined that a failure occurred during the operation. As a result, the present invention eliminates the need for additional disk writes required by conventional techniques that use a replication log to at the same layer where the data recovery is performed.

US Patent:

7821947, Oct 26, 2010

Filed:

Apr 24, 2007

Appl. No.:

11/739312

Inventors:

John MacCormick - San Francisco CA, US
Paul Barham - Cambridge, GB
Moises Goldszmidt - Palo Alto CA, US

Assignee:

Microsoft Corporation - Redmond WA

International Classification:

G01R 31/08
G06F 15/173

US Classification:

370241, 370252, 709224

Abstract:

An activity model is generated at a computer. The activity model may be generated by monitoring incoming and outgoing channels for packets for a predetermined window of time. To generate an activity model, an input and an output channel are selected. A probability distribution function describing the observed waiting time between packet arrivals on the selected input channel and the selected output channel is generated by mining the data collected during the selected window of time. A probability distribution function describing the observed waiting time between a randomly chosen instant and receiving a packet on the selected input channel is also generated. The distance between the two generated probability distribution functions is computed. If the computed distance is greater than a predefined confidence level, then the two selected channels are deemed to be related. Otherwise, the selected channels are deemed to be unrelated.