An apparatus includes at least one processing device configured to identify a logical storage volume stored across multiple storage nodes of a distributed storage system, and for each of a plurality of different portions of the logical storage volume, to send one or more locality determination commands to each of one or more of the storage nodes, a given such command requesting a corresponding one of the storage nodes to respond with an indication as to whether or not the portion of the logical storage volume is local to that storage node, and to receive from the one or more storage nodes responses to the one or more locality determination commands. The processing device is further configured to store locality information for the plurality of different portions of the logical storage volume based at least in part on the responses of the storage nodes to the locality determination commands.