| |
2008/2009 SOUTHERN CALIFORNIA REGIONAL |
ACM INTERNATIONAL COLLEGIATE PROGRAMMING CONTEST |
|
|
|
Modern data centers often use large storage arrays to hold the
storage used by the servers. The arrays take a set of physical disk
drives, remap them to LUNs (logical units), then present those LUNs
to the servers. To the server operating system, these LUNs appear to
be disk drives that are connected to the server, in the same way that
physical drives connected directly by cables do. The storage arrays
can present logical units of arbitrary sizes, provide built-in
redundancy for reliability, and provide other advanced storage
management features.
There are several protocols that can be used between servers and
storage arrays, but the most common at present is Fibre Channel. A
server has one or more Fibre Channel Host Bus Adapter (HBA) ports that
connect to Fibre Channel switch(es). An array also has one or more
(usually several) Fibre Channel ports that connect to the switches.
Logical paths between the servers and arrays are defined in the
switches-these paths are known as zones.
An array has LUNs of varying sizes defined on it, and these LUNs are
presented to specific servers using specified Fibre Channel ports on
the array. A LUN may be presented to more than one server.
Server and array Fibre Channel ports are identified by their "Port
World Wide Name" (PWWN). A PWWN is a globally-unique 64-bit address.
A server sees the PWWNs of the arrays it uses storage on; the array
sees the PWWNs of the servers that connect to it. The server PWWNs
are used to define which servers have access to each LUN.
Over time, servers are added and removed from large data centers.
The storage administrators are certainly notified when servers are
added so they can create and allocate new LUNs-but they are not
necessarily notified when servers are removed or server
configurations change. This means that there may be storage on an
array that is configured but not actually in use ("dark" or
"stranded" storage). It is not unheard of for terabytes of storage
to be stranded in large data centers.
There are commercial tools that cost thousands of dollars to help
find this storage (among other features). However, in the interest
of saving money, the management of one such data center has decided
to ask programming contest teams to develop a tool to find stranded
storage instead.
The relationships between the storage array LUNs, the servers, and
the switches are defined in pairwise relationships:
-
·
-
A LUN is mapped to a storage port (possibly more than one)
-
·
-
A LUN is masked to a server HBA (possibly more than one)
-
·
-
A storage port has a PWWN
-
·
-
A server has one or more server HBAs, each with a PWWN
-
·
-
A switch zone connects a storage PWWN to a server HBA PWWN
(a given storage PWWN may be zoned to multiple server HBA PWWNs, and
a given server HBA PWWN may be zoned to multiple storage PWWNs)
-
·
-
A server file system resides on a LUN or logical volume
(a LUN may hold multiple server file systems)
-
·
-
A server logical volume uses one or more LUNs
These relationships are defined on a series of input lines for your
program. Each line describes one relationship as described below.
Words in uppercase appear literally in the input. Elements on a line
are separated from each other by one or more spaces.
A line may contain leading and/or trailing spaces.
No input line is longer than 80 columns. Relationships can appear in
any order in the input. There will be no more than 3000 relationships.
LUNMAP < Array ID > < LUN ID > < Port ID >
LUNMASK < Array ID > < LUN ID > < Server PWWN >
ARRAYPORT < Array ID > < Port ID > < Port PWWN >
ZONE < Port PWWN > < Server PWWN >
SERVERHBA < Server name > < Server PWWN >
SERVERFS < Server name > < File system name > LUN < Array ID > < LUN ID >
SERVERFS < Server name > < File system name > LV < Logical volume name >
SERVERLV < Server name > < Logical volume name > < Array ID > < LUN ID >
Each array ID, port ID, server name, file system name, and logical
volume name is a string of one to twenty alphanumeric characters.
Case is significant.
A server HBA or port PWWN is a 64-bit value expressed as eight pairs
of hexadecimal digits separated from each other by colons (for
example, 01:23:45:67:89:AB:CD:EF). Case is not significant.
A LUN ID is a hexadecimal value from 0 to FFFF16. Case is not
significant. The same LUN ID value may be used on different storage
arrays.
For a storage LUN to be used, it must be mapped to a storage port,
masked to one or more HBAs on one or more servers, connected with one
or more zones between the storage port(s) and the server(s), and then
used on one or more file systems. A server file system may reside
directly on a LUN or use a logical volume that is made up of one or
more LUNs.
Your program is to read a set of descriptions as defined above and
determine which storage LUNs are defined in LUN mapping or masking
entries but are not actually in use.
Your program should produce a list of the "dark" unused LUNs, one per
line. The list should be sorted by array name in ASCII order, and
within an array, by increasing hexadecimal LUN value. Each line
should contain the array name starting in the first column, followed
immediately by a colon and the four-digit hexadecimal LUN number
(including leading zeroes, with the values A-F in upper case).
No trailing whitespace is to appear on an output line.
LUNMAP S6 1 C1
LUNMAP S6 2 C1
LUNMAP CX 10 SPA0
LUNMAP CX 11 SPA0
LUNMAP CX 10 SPB0
LUNMAP CX 11 SPB0
ARRAYPORT S6 C1 20:00:00:10:00:0A:00:C1
ARRAYPORT CX SPA0 50:06:00:60:00:00:00:00
ARRAYPORT CX SPB0 50:06:00:68:00:00:00:00
SERVERHBA PRD1 10:00:00:00:C9:01:00:01
SERVERHBA PRD2 10:00:00:00:C9:01:01:01
SERVERHBA PRD2 10:00:00:00:C9:01:01:02
LUNMASK S6 1 10:00:00:00:C9:01:00:01
LUNMASK S6 1 10:00:00:00:C9:02:00:01
LUNMASK S6 2 10:00:00:00:C9:02:00:01
ZONE 20:00:00:10:00:0a:00:C1 10:00:00:00:C9:01:00:01
ZONE 50:06:00:60:00:00:00:00 10:00:00:00:C9:01:01:01
ZONE 50:06:00:68:00:00:00:00 10:00:00:00:C9:01:01:02
LUNMASK CX 10 10:00:00:00:C9:01:01:01
LUNMASK CX 11 10:00:00:00:C9:01:01:01
LUNMASK CX 10 10:00:00:00:C9:01:01:02
LUNMASK CX 11 10:00:00:00:C9:01:01:02
SERVERFS PRD1 tempdb LUN S6 1
SERVERFS PRD1 scratchfs LUN S6 2
SERVERFS PRD2 bigsas LV SASLV
SERVERLV PRD2 SASLV CX 11
Output for the Sample Input |
CX:0010
S6:0002