Software Defined Networking (SDN) enables flexible management of networks through policies that are stored as a set of rules in ternary content-addressable memory (TCAM) in the switches. With increasing Cloud and Network Function Virtualization (NFV) demands, the number of network policies required will also increase accordingly. As the TCAM memory capacity available in the switches is limited, any rule placement algorithm must be highly scalable to accommodate a large number of policies in the network. In this paper, we propose Raptor, a scalable rule placement scheme that supports multi-path routing as well as immediate failure-recovery to a backup path without policy violation. The requirement is that any path which a flow may take should see the same set of policy rules and the challenge is to do this efficiently. We model our problem as an Integer Linear Program to maximize the sharing of rules, followed by heuristic based graph partition for the final placement of rules so as to preserve the rules' priority orderings. Our evaluation shows that Raptor can achieve savings of up to 98% in TCAM usage or support 250% more policies compared to existing works.