Synchronized data transfer system

• US 7,788,396 B2
• Filed: 11/30/2004
• Issued: 08/31/2010
• Est. Priority Date: 11/28/2001
• Status: Active Grant

• Current Assignee: Interactive Content Engines, LLC
• Original Assignee: Interactive Content Engines, LLC
• Inventors: Rose, Steven W.
• Primary Examiner(s): Wang; Liangche A.
• Assistant Examiner(s): Kim; Tae K
• Application Number:
  US10/999,661
• Publication Number:
  US 20050114538A1
• Time in Patent Office: 2,100 Days
• Field of Search: 725/115, 725/117, 725/92, 711/100, 711/114, 711/167, 709/233, 709/217, 709/231, 709/232, 707/10
• US Class Current: 709/232
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04N 21/2182 involving memory arrays, e.g. RAID disk arrays RAID arrays per se G06F3/0689; use of parity to protect data in RAID systems G06F11/1008
• CPC Class Codes: H04N 21/21825 involving removable storage units, e.g. tertiary storage such as magnetic tapes or optical disks
• CPC Class Codes: H04N 21/2315 using interleaving
• CPC Class Codes: H04N 21/2318 using striping
• CPC Class Codes: H04N 21/2326 Scheduling disk or memory reading operations
• CPC Class Codes: H04N 21/2405 Monitoring of the internal components or processes of the server, e.g. server load allocation of resources in multiprogramming arrangements G06F9/50; performance measurement of computer activity G06F11/34
• CPC Class Codes: H04N 7/17318 Direct or substantially direct transmission and handling of requests

Abstract

A synchronized data transfer system including storage processor nodes, a backbone communication switch, multiple titles subdivided into subchunks and distributed across the nodes, a user process executed on a first node, a transfer process executed on a second node, and a management process executed on a management node. The user process sends a timestamped read request to request a corresponding subchunk. The transfer process sends a message to the management process for each received read request, where each message identifies source and destination nodes. The management process broadcasts transmit commands to initiate sequential transmit periods, receives the messages, and selects from among the received messages to ensure that each node sends and/or receives no more than one subchunk at a time. The management process sends a transmit request for each selected message, and the transfer process sends a subchunk identified by a transmit request in response to the transmit command.

Claims

1. A method of synchronously transferring distributed subchunks of data between a plurality of processor nodes coupled to a network switch, said method comprising:

periodically broadcasting, by a management process executed on at least one of the processor nodes to each of the plurality of processor nodes via the network switch, a transmit command to initiate each of a plurality of sequential transmit periods;

sending to the management process, by each processor node having at least one subchunk to send, a message for each subchunk to be sent, each message identifying a source processor node and a destination processor node;

selecting, by the management process, at least one message received from the processor nodes to ensure that each processor node scheduled to send at least one subchunk sends only one subchunk during a following transmit period and that each processor node scheduled to receive at least on subchunk receives only one subchunk during the following transmit period;

sending, by the management process, a plurality of transmit requests, each transmit request sent to a processor node that had sent a corresponding message that was selected; and

transmitting, by each processor node receiving a transmit request, a subchunk identified by the received transmit request to a destination processor node in response to the following transmit command.

2. The method of claim 1, further comprising:

prior to said sending a message for each subchunk to be sent, timestamping each message;

said selecting comprising prioritizing based on timestamp order; and

said sending a plurality of transmit requests comprising sending transmit requests in timestamp order.

3. The method of claim 2, further comprising:

sending, by at least one processor node, a plurality of timestamped read requests; and

wherein said timestamping each message comprises incorporating a timestamp from a received timestamped read request into a corresponding message.

4. The method of claim 3, further comprising:

organizing, by the management process, received messages into a ready message list in timestamp order; and

scanning, by the management process, the ready message list in timestamp order just prior to each transmit period.

5. The method of claim 4, wherein said scanning comprises selecting a message if the identified source processor node has not already been selected for transmitting a subchunk during the following transmit period and if the identified destination processor node has not already been selected for receiving a subchunk during the following transmit period.

6. The method of claim 5, wherein said scanning is completed when the entire ready message list has been scanned, or if all of the processor nodes have been selected to transmit a subchunk or if all of the processor nodes have been selected to receive a subchunk.

7. The method of claim 1, further comprising:

storing received subchunk read requests into a read request queue, each subchunk read request indicating a request for a locally stored subchunk;

reading, by a local disk drive, subchunks identified in the read request queue in physical order;

listing entries of subchunks read successfully into a successful read queue; and

said sending a message for each subchunk to be sent comprising sending a message for each entry in said successful read queue.

8. The method of claim 7, wherein each subchunk read request comprises a timestamped read request, wherein said listing entries of subchunks read successfully into a successful read queue comprises listing entries in timestamp order, and wherein said sending a message for each entry in said successful read queue comprises sending messages in timestamp order.

9. The method of claim 7, further comprising:

removing an entry from the successful request queue that is associated with a subchunk identified by a corresponding transmit request; and

building network packets used to transfer the identified subchunk to a destination processor node in response to a transmit command.

10. The method of claim 1, further comprising executing the management processor on a first management node and executing a mirrored management process on a mirrored management node which mirrors the first management node.

11. A synchronized data transfer system, comprising:

a plurality of storage processor nodes including first and second user nodes and a management node;

a backbone communication switch coupled to said plurality of storage processor nodes;

a plurality of titles each subdivided into a plurality of subchunks which are distributed across said plurality of storage processor nodes;

a user process, executed on said first user node, which sends a plurality of timestamped read requests, each timestamped read request for requesting a corresponding subchunk;

a transfer process, executed on said second user node, which sends a message to a management process for each received timestamped read request requesting a locally stored subchunk, each message including a source node identifier and a destination node identifier; and

a said management process, executed on said management node, which periodically broadcasts a transmit command to said plurality of storage processor nodes via said switch to initiate each of a plurality of sequential transmit periods, which receives a plurality of messages, and, prior to each transmit period, which selects at least one of said plurality of messages to ensure that each storage processor node sends no more than one subchunk and receives no more than one subchunk during each transmit period in which at least one subchunk is transferred, and which sends a plurality of transmit requests corresponding to selected messages; and

wherein said transfer process, in response to receiving a transmit request from said management process, sends a corresponding subchunk to a storage processor node identified by said destination node identifier during the next transmit period initiated by the next broadcasted transmit command.

12. The synchronized data transfer system of claim 11, wherein said management process selects from among said plurality of messages based on timestamp priority.

13. The synchronized data transfer system of claim 12, wherein said management process first selects a message with a highest priority timestamp and then selects each subsequent message if an identified source node has not already been selected for transmitting a subchunk during said following transmit period and if an identified destination node has not already been selected for receiving a subchunk during said following transmit period.

14. A synchronized data transfer system, comprising:

a plurality of processor nodes;

a backbone network switch coupled to said plurality of processor nodes to enable communication between said plurality of processor nodes;

a plurality of storage devices coupled to and distributed across said plurality of processor nodes and storing a plurality of titles, each title divided into a plurality of subchunks that are distributed across said plurality of storage devices;

a plurality of transfer processes, each executed on a corresponding one of said plurality of processor nodes and operative to send a message to a synchronous switch manager process for each subchunk that is to be transferred from a source processor node to a destination processor node, each message including a source node identifier and a destination node identifier; and

said synchronous switch manager process, executed on at least one of said plurality of processor nodes, which periodically broadcasts a transmit command to said plurality of processor nodes to initiate each of a plurality of sequential transmit periods, which receives a plurality of messages, and, prior to each transmit period, which selects at least one of said plurality of messages to ensure that each processor node sends no more than one subchunk and receives no more than one subchunk during each transmit period in which at least one subchunk is transferred, and which sends a plurality of transmit requests corresponding to selected messages; and

wherein each transfer process which sent at least one message and which received a transmit request from said synchronous switch manager process identifying a corresponding subchunk sends said corresponding subchunk to said destination processor node during the next transmit period initiated by a broadcasted transmit command.

15. The synchronized data transfer system of claim 14, wherein each of said plurality of messages comprises a timestamp and wherein said synchronous switch manager process prioritizes said plurality of messages based on timestamp order and sends said plurality of transmit requests in timestamp order.

16. The synchronized data transfer system of claim 15, further comprising:

a plurality of user processes, each executed on a corresponding one of said plurality of processor nodes and operative to send a plurality of timestamped read requests; and

wherein each transfer process incorporates a timestamp from a corresponding timestamped read request into a corresponding message.

17. The synchronized data transfer system of claim 16, wherein said synchronous switch manager process organizes said plurality of messages into a ready message list in timestamp order, scans said ready message list in timestamp order just prior to each of said plurality of sequential transmit periods, and selects messages based on timestamp priority.

18. The synchronized data transfer system of claim 17, wherein said synchronous switch manager process selects a message if an identified source processor node has not already been selected for transmitting a subchunk during a following transmit period and if an identified destination processor node has not already been selected for receiving a subchunk during said following transmit period.

19. The synchronized data transfer system of claim 14, further comprising:

each of said plurality of transfer processes storing received subchunk read requests into a read request queue, each subchunk read request indicating a locally stored subchunk;

each of said plurality of storage devices reading subchunks identified in a local read request queue in physical order;

each of said plurality of processor nodes listing subchunks read successfully by a corresponding storage device into a successful read queue; and

each of said plurality of transfer processes sending a message for each entry in a corresponding successful read queue to said synchronous switch manager process.

20. The synchronized data transfer system of claim 19, wherein each said subchunk read request comprises a timestamped read request, wherein entries in each said successful read queue are listed in timestamp order, and wherein each transfer process sends a message for each entry in a corresponding successful read queue in timestamp order.

21. The synchronized data transfer system of claim 19, further comprising:

each of said plurality of transfer processes removing an entry from a corresponding successful request queue in which said entry is associated with a subchunk identified by a corresponding transmit request; and

a plurality of network transfer processes, each executed on a corresponding one of said plurality of processor nodes, and each operative to build network packets used to transfer an identified subchunk to a destination processor node in response to a transmit command.

22. The synchronized data transfer system of claim 14, wherein said network switch comprises a gigabit Ethernet switch with a plurality of ports, and wherein each of said plurality of processor nodes is coupled to a corresponding port of said network switch.

23. The synchronized data transfer system of claim 14, wherein said plurality of processor nodes includes a management node which executes said synchronous switch manager process.

24. The synchronized data transfer system of claim 14, wherein said plurality of processor nodes includes a first management node executing said synchronous switch manager process and a second management node executing a mirrored synchronous switch manager process.